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 2887
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.ed u (Lilith) wrote in message news:<75******* *************** ****@posting.go ogle.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******@nospa m.uci.edu> wrote in message news:<c3******* ***@news.servic e.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******@nospa m.uci.edu> wrote in message news:<c3******* ***@news.servic e.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.setrecursio nlimit. 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.setrecursio nlimit. 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.ed u (Lilith) wrote in message news:<75******* *************** ****@posting.go ogle.com>... Josiah Carlson <jc******@nospa m.uci.edu> wrote in message news:<c3******* ***@news.servic e.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 '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)
"""
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.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 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.) dicts
mapping nodes to neighbor-sets, but if one wants a graph that's
implemented in some other way, this may not be the most convenient (or...
|
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:
ftp://xray.imsb.au.dk/pub/python/packages/Python2.1/RPMS/python-kjbuckets-2.2-7.i686.rpm
(This makes my work less important, but it also tells me that "many"
people can...
|
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 version of the MS Graph type
library. Up until now I have been walking them through
the process of setting the references to include their
version...
|
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 microsft graph object on it that shows
a graph of the bookings over a 20 week period.
the first form is still open to allow the user to select another...
|
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 about the paths.
This is (what I want to show) like a graph - show ways, stations, etc,
and I want to show the strength of lines (how many of mails...
| |
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 Graph(object):
...
It seems that their Graph is subclassed from "object" but I couldn't
find a "object" class anywhere. So, I abandoned using that...
|
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 dictionary. Currently my
implementation works like this:
t = Graph()
n1 = Node("Node1")
n2 = Node("Test2")
|
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 have been unable to find how to specifically refer to properties within a graph object.
Below is a snippet of code from my module in which the graph...
|
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 into igraph (http://cneurocvs.rmki.kfki.hu/igraph/doc/
python/index.html) and networkX (https://networkx.lanl.gov/wiki) for
generating a file to store...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
|
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, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it. ...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |