Is there a map or graph module?

[Lilith]

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

[Josiah Carlson]

Re: Is there a map or graph module?

Lilith wrote:[color=blue]
> 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![/color]

Thank Guido, http://www.python.org/doc/essays/graphs.html


- Josiah

[Jesper Olsen]

Re: Is there a map or graph module?

lilyth@umich.ed u (Lilith) wrote in message news:<75200cbc. 0403181507.350f eeb7@posting.go ogle.com>...[color=blue]
> 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[/color]

http://www.research.att.com/~mohri/fsm/doc4/fsmpy.html

J

[Lilith]

Graph Problems (was Re: Is there a map or graph module?)

Josiah Carlson <jcarlson@nospa m.uci.edu> wrote in message news:<c3dpmp$7r 5$1@news.servic e.uci.edu>...[color=blue]
> Lilith wrote:[color=green]
> > 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![/color]
>
> Thank Guido, http://www.python.org/doc/essays/graphs.html[/color]

That's not working for me. I should have mentioned I tried that, but I
get a slew of these errors:
[color=blue]
> File "guidograph.py" , line 40, in find_all_paths
> newpaths = find_all_paths( graph, node, end, path)[/color]
[color=blue]
> RuntimeError: maximum recursion depth exceeded[/color]

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.

[Lilith]

Graphing problems (was: Re: Is there a map or graph module?)

Josiah Carlson <jcarlson@nospa m.uci.edu> wrote in message news:<c3dpmp$7r 5$1@news.servic e.uci.edu>...[color=blue]
> Lilith wrote:[color=green]
> > 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![/color]
>
> Thank Guido, http://www.python.org/doc/essays/graphs.html[/color]

I figured it out...I needed to use sys.setrecursio nlimit. D'oh. :)

Thanks for your help!

[Josiah Carlson]

Re: Graphing problems

>>Thank Guido, http://www.python.org/doc/essays/graphs.html[color=blue]
>
> I figured it out...I needed to use sys.setrecursio nlimit. D'oh. :)[/color]

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

[Lilith]

Re: Graph Problems (was Re: Is there a map or graph module?)

lilyth@umich.ed u (Lilith) wrote in message news:<75200cbc. 0403190755.5765 890a@posting.go ogle.com>...[color=blue]
> Josiah Carlson <jcarlson@nospa m.uci.edu> wrote in message news:<c3dpmp$7r 5$1@news.servic e.uci.edu>...[color=green]
> > Lilith wrote:[color=darkred]
> > > 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![/color]
> >
> > Thank Guido, http://www.python.org/doc/essays/graphs.html[/color]
>
> That's not working for me. I should have mentioned I tried that, but I
> get a slew of these errors:
>[color=green]
> > File "guidograph.py" , line 40, in find_all_paths
> > newpaths = find_all_paths( graph, node, end, path)[/color]
>[color=green]
> > RuntimeError: maximum recursion depth exceeded[/color]
>
> 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.[/color]

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)

[Elaine Jackson]

Re: Is there a map or graph module?

"""
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 'bidirectionali ze' 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 bidirectionaliz e(graph):
converse = dict([((b,a),graph[a,b]) for (a,b) in graph.keys()])
graph.update(co nverse)

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,gra ph):
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.value s())+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(di ct([(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((la mbda edge: A(edge) and len(B(edge))==2 ),freeEdges)[0]
freeEdges.remov e(edge)
takenEdges.appe nd(edge)
newTree=B(edge)[0]+B(edge)[1]
forest=[x for x in forest if x not in B(edge)]
forest.append(n ewTree)
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,grap h)
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=kruska l(graph)
print totalWeight(spa nTree,graph)
"""

[Morten Kjeldgaard]

Re: Graph Problems (was Re: Is there a map or graph module?)

On Fri, 19 Mar 2004 07:55:23 -0800, Lilith wrote:
[color=blue]
> 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.[/color]

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

[Brian Kelley]

Re: Graph Problems (was Re: Is there a map or graph module?)

Morten Kjeldgaard wrote:[color=blue]
> On Fri, 19 Mar 2004 07:55:23 -0800, Lilith wrote:
>
> Any Python implementation is going to be extremely slow.[/color]

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.adjacentVe rtices -> the list of vertices adjacent to this vertex

such that
for edge, vertex in zip(vertex.edge s, vertex.adjacent Vertices):

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