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

[Brian Kelley]

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