Is there a python module somewhere (been searching today, no luck)
which has efficiently coded various graphhandling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compscieducated person, so coding my own
would be less parsimonious.
Thanks for any suggestions!
D 9 2733
Lilith wrote: Is there a python module somewhere (been searching today, no luck) which has efficiently coded various graphhandling routines, such as finding the shortest path through a graph, or the set of all paths through a graph? I'm not a compscieducated person, so coding my own would be less parsimonious.
Thanks for any suggestions!
Thank Guido, http://www.python.org/doc/essays/graphs.html
 Josiah li****@umich.edu (Lilith) wrote in message news:<75**************************@posting.google. com>... Is there a python module somewhere (been searching today, no luck) which has efficiently coded various graphhandling routines, such as finding the shortest path through a graph, or the set of all paths through a graph? I'm not a compscieducated person, so coding my own would be less parsimonious.
Thanks for any suggestions!
D http://www.research.att.com/~mohri/fsm/doc4/fsmpy.html
J
Josiah Carlson <jc******@nospam.uci.edu> wrote in message news:<c3**********@news.service.uci.edu>... Lilith wrote: Is there a python module somewhere (been searching today, no luck) which has efficiently coded various graphhandling routines, such as finding the shortest path through a graph, or the set of all paths through a graph? I'm not a compscieducated person, so coding my own would be less parsimonious. Thanks for any suggestions! Thank Guido, http://www.python.org/doc/essays/graphs.html
That's not working for me. I should have mentioned I tried that, but I
get a slew of these errors:
File "guidograph.py", line 40, in find_all_paths newpaths = find_all_paths(graph, node, end, path)
RuntimeError: maximum recursion depth exceeded
Guido's example works fine when I use his simple graph. When I plug in
my 9000node graph, I get those problems even if the nodes are a few
steps away. I think my network is too big for that code.
I imagine there's some kind of recursion limit I can set somewhere,
but it's probably a problem in that the code can't handle larger
graphs. Not only does find_all_paths crash, but so does find_path.
Josiah Carlson <jc******@nospam.uci.edu> wrote in message news:<c3**********@news.service.uci.edu>... Lilith wrote: Is there a python module somewhere (been searching today, no luck) which has efficiently coded various graphhandling routines, such as finding the shortest path through a graph, or the set of all paths through a graph? I'm not a compscieducated person, so coding my own would be less parsimonious.
Thanks for any suggestions!
Thank Guido, http://www.python.org/doc/essays/graphs.html
I figured it out...I needed to use sys.setrecursionlimit. D'oh. :)
Thanks for your help!
>>Thank Guido, http://www.python.org/doc/essays/graphs.html I figured it out...I needed to use sys.setrecursionlimit. D'oh. :)
You may eventually run into a case where setting the recursion limit
still doesn't help you (you start getting C stack overflows). At this
point, a nonrecursive version of the shortest paths algorithm would
probably help you.
 Josiah li****@umich.edu (Lilith) wrote in message news:<75**************************@posting.google. com>... Josiah Carlson <jc******@nospam.uci.edu> wrote in message news:<c3**********@news.service.uci.edu>... Lilith wrote: Is there a python module somewhere (been searching today, no luck) which has efficiently coded various graphhandling routines, such as finding the shortest path through a graph, or the set of all paths through a graph? I'm not a compscieducated person, so coding my own would be less parsimonious. Thanks for any suggestions!
Thank Guido, http://www.python.org/doc/essays/graphs.html
That's not working for me. I should have mentioned I tried that, but I get a slew of these errors:
> File "guidograph.py", line 40, in find_all_paths > newpaths = find_all_paths(graph, node, end, path)
> RuntimeError: maximum recursion depth exceeded
Guido's example works fine when I use his simple graph. When I plug in my 9000node graph, I get those problems even if the nodes are a few steps away. I think my network is too big for that code.
I imagine there's some kind of recursion limit I can set somewhere, but it's probably a problem in that the code can't handle larger graphs. Not only does find_all_paths crash, but so does find_path.
Just in case my second posting didn't get through on one, I did find
the way to use the sys module to up the recursion limit. Never had to
use that one, thanks in advance for anyone who points that out, ahead
of time. (I'm on Google, so I'm lagging behind a few hours)
"""
Hopefully some of the following will help you. The idea is to implement weighted
digraphs as dictionaries: the keys are edges and the values are weights. If
direction is not important in a particular graph, you can 'bidirectionalize' it
(see below). If weights are not important, just ignore them. Since the only
important property of a vertex is its name, the sensible thing is to build
graphs whose vertices are selfreferring strings: a function is provided that
declares any number of such vertices at the same time. Another function returns
all the edges of the cyclic digraph with specified vertices. The exercises at
the bottom are from Discrete Mathematics and its Applications by Kenneth Rosen.
"""
def declareVertices(strg):
from string import split
for name in split(strg,','):
globals()[name]=name
cycleEdges = lambda *X: [(X[i],X[(i+1)%len(X)]) for i in range(len(X))]
def bidirectionalize(graph):
converse = dict([((b,a),graph[a,b]) for (a,b) in graph.keys()])
graph.update(converse)
def vertexSet(graph):
A=[a for (a,b) in graph.keys()]
B=[b for (a,b) in graph.keys()]
X=A+B
return [X[i] for i in range(len(X)) if X[i] not in X[0:i]]
def neighbors(a,graph):
leftNeighbors=[b for b in vertexSet(graph) if (b,a) in graph.keys()]
rightNeighbors=[b for b in vertexSet(graph) if (a,b) in graph.keys()]
X=leftNeighbors+rightNeighbors
return [X[i] for i in range(len(X)) if X[i] not in X[0:i]]
def dijkstra(origin,graph):
infinity = sum(graph.values())+1
reVal = {origin:0}
A = lambda y: [x for x in reVal.keys() if (x,y) in graph.keys()]
B = lambda y: (A(y) and min([reVal[x]+graph[x,y] for x in A(y)])) \
or infinity
while [y for y in vertexSet(graph) if y not in reVal.keys()]:
C = [(y,B(y)) for y in vertexSet(graph) if y not in reVal.keys()]
m = min([pair[1] for pair in C])
reVal.update(dict([(y,z) for (y,z) in C if z==m]))
return reVal
def kruskal(graph):
forest=[[x] for x in vertexSet(graph)]
freeEdges=graph.keys()
takenEdges=[]
while len(forest)>1:
minWeight=min([graph[edge] for edge in freeEdges])
A = lambda edge: graph[edge]==minWeight
B = lambda edge: [x for x in forest if edge[0] in x or edge[1] in x]
edge=filter((lambda edge: A(edge) and len(B(edge))==2),freeEdges)[0]
freeEdges.remove(edge)
takenEdges.append(edge)
newTree=B(edge)[0]+B(edge)[1]
forest=[x for x in forest if x not in B(edge)]
forest.append(newTree)
return takenEdges
################################################## ##
################################################## ##
"""
#################################
## Rosen; Section 7.6; Exercise 4
#################################
declareVertices('a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q ,r,s,t,u,v,w,x,y,z')
graph = { \
(a,b):2, (a,c):4, (a,d):1, (b,c):3, (b,e):1, \
(c,e):2, (c,f):2, (d,f):5, (d,g):4, (e,h):3, \
(f,g):3, (f,h):3, (f,i):2, (f,j):4, (g,k):2, \
(h,l):1, (h,o):8, (i,j):3, (i,l):3, (i,m):2, \
(j,k):6, (j,m):6, (j,n):3, (k,n):4, (k,r):2, \
(l,m):3, (l,o):6, (m,n):5, (m,o):4, (m,p):2, \
(n,q):2, (n,r):1, (o,p):2, (o,s):6, (p,q):1, \
(p,s):2, (p,t):1, (q,r):8, (q,t):3, (r,t):8, \
(s,z):2, (t,z):8 \
}
distances = dijkstra(a,graph)
X = distances.keys()
X.sort()
for vertex in X: print vertex, ": ", distances[vertex]
"""
################################################## ##
################################################## ##
"""
#################################
## Rosen; Section 8.6; Exercise 3
#################################
declareVertices('a,b,c,d,e,f,g,h,i,j,k,l')
graph = { \
(a,b):2, (b,c):3, (c,d):1, \
(a,e):3, (b,f):1, (c,g):2, (d,h):5, \
(e,f):4, (f,g):3, (g,h):3, \
(e,i):4, (f,j):2, (g,k):4, (h,l):3, \
(i,j):3, (j,k):3, (k,l):1 \
}
totalWeight = lambda tree,graph: sum([graph[edge] for edge in tree])
spanTree=kruskal(graph)
print totalWeight(spanTree,graph)
"""
On Fri, 19 Mar 2004 07:55:23 0800, Lilith wrote: Guido's example works fine when I use his simple graph. When I plug in my 9000node graph, I get those problems even if the nodes are a few steps away. I think my network is too big for that code.
Any Python implementation is going to be extremely slow. You need to
google for kjbuckets, which is a C extension to Python by Aron Watters. It
is extremely effictient, even with 9000 nodes. If you can use RPMS, look
in my ftp directory: ftp://xray.imsb.au.dk:/pub/python/pa...Python2.1/RPMS
Good luck,
Morten

Morten Kjeldgaard
Department of Molecular Biology
Aarhus University
Gustav Wieds Vej 10 C, DK8000 Aarhus C, Denmark
Morten Kjeldgaard wrote: On Fri, 19 Mar 2004 07:55:23 0800, Lilith wrote:
Any Python implementation is going to be extremely slow.
I have found this not to be true. I have subgraph isomorphism routines
that run between 4 and 8 time slower than the equivalent C code. I do
have some issues with using dictionaries as graphs since this means that
traversing through them can be quite a bit slower than the equivalent
list traversal.
By far, the best optimization that I have found is to make a vertex
object that contains the following items:
self.edges > the list of edges connected to this vertex
self.adjacentVertices > the list of vertices adjacent to this vertex
such that
for edge, vertex in zip(vertex.edges, vertex.adjacentVertices):
returns a vertex's edges and corresponding adjacent vertices. This ends
up being more memory efficient than using dictionaries as well. The
downsides are that editing the graph takes longer.
I regularly use graphs of 10,000+ nodes and 100,000+ edges and use
scoring functions to find best scoring paths within the graph. In case
you are interested, check this out: http://www.pathblast.org/
Surprisingly, the python implementation ended up being faster than the
java implementation (even when using a JIT), although this might be a
redherring since the java implementation had a lot of extra baggage.
Brian Kelley This discussion thread is closed Replies have been disabled for this discussion. Similar topics
25 posts
views
Thread by Magnus Lie Hetland 
last post: by

reply
views
Thread by bearophileHUGS 
last post: by

1 post
views
Thread by JD Kronicz 
last post: by

reply
views
Thread by Peter Bailey 
last post: by

3 posts
views
Thread by Durumdara 
last post: by

4 posts
views
Thread by John Henry 
last post: by

12 posts
views
Thread by Nathan Harmston 
last post: by
 
5 posts
views
Thread by chrispoliquin 
last post: by
          