471,071 Members | 1,205 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,071 software developers and data experts.

Is there a map or graph module?

Is there a python module somewhere (been searching today, no luck)
which has efficiently coded various graph-handling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compsci-educated person, so coding my own
would be less parsimonious.

Thanks for any suggestions!

D
Jul 18 '05 #1
9 2733
Lilith wrote:
Is there a python module somewhere (been searching today, no luck)
which has efficiently coded various graph-handling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compsci-educated person, so coding my own
would be less parsimonious.

Thanks for any suggestions!


Thank Guido, http://www.python.org/doc/essays/graphs.html
- Josiah
Jul 18 '05 #2
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 graph-handling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compsci-educated 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
Jul 18 '05 #3
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 graph-handling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compsci-educated 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 9000-node 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.
Jul 18 '05 #4
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 graph-handling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compsci-educated 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!
Jul 18 '05 #5
>>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 non-recursive version of the shortest paths algorithm would
probably help you.

- Josiah
Jul 18 '05 #6
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 graph-handling routines, such as
finding the shortest path through a graph, or the set of all paths
through a graph? I'm not a compsci-educated 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 9000-node 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)
Jul 18 '05 #7
"""
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 self-referring 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)
"""

Jul 18 '05 #8
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 9000-node 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, DK-8000 Aarhus C, Denmark

Jul 18 '05 #9
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
red-herring since the java implementation had a lot of extra baggage.

Brian Kelley
Jul 18 '05 #10

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
reply views Thread by leo001 | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.