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 9 2868
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 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
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.
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!
>>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 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)
"""
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)
"""
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
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Magnus Lie Hetland |
last post by:
Is there any interest in a (hypothetical) standard graph API (with
'graph' meaning a network, consisting of nodes and edges)? Yes, we
have the standard ways of implementing graphs through (e.g.)...
|
by: bearophileHUGS |
last post by:
This is the first version of the graph module I was developing... In
the meantime I've seen that there are already lots of graph
implementations, even a compiled one:...
|
by: JD Kronicz |
last post by:
Hi .. I have an issue I have been beating my head against
the wall on for some time. I am trying to use late
binding for MS graph so that my end users don't have to
worry about having the right...
|
by: Peter Bailey |
last post by:
I have a list box that allows me to select a course module after update the
vba creates various quiries and recordsets that populate the form. the last
action in vba opens a new form with a...
|
by: Durumdara |
last post by:
Hi !
I need to create a program that read eml file headers, analyze the
receive tags and create a path database. I finished with this program
section.
But I want to show a graphical summary...
|
by: John Henry |
last post by:
I am looking for a ready made simple graph package. I found an
extensive one in the piana package but when I try to use just the
graph portion, it fails to load because of the line:
class...
|
by: Nathan Harmston |
last post by:
Hi All,
Currently I am working on a generic graph library so I can do various
graph based analysis for various projects I have ideas for. Currently
I am implementing Graph as a wrapper around a...
|
by: CanOfWorms |
last post by:
Access 2003 (previous 2000)
Windows XP Pro
I am fairly new at VBA within Access, learning as I go thorugh forums and discussion groups. I generally find my answers through previous posts, but I...
|
by: chrispoliquin |
last post by:
I need to represent the hyperlinks between a large number of HTML
files as a graph. My non-directed graph will have about 63,000 nodes
and and probably close to 500,000 edges.
I have looked...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |