graphs in python...

[Douglas F. Calvert]

Hello,
I read "Python Patterns: Implementing Graphs" document on the website
and was impressed with doing graphs in this fashion. Is this still the
best documented way to do graphs. The document alludes to a follow up
article tuned for speed but I have not found it. Can anyone suggest
other ways that might be faster? I am looking to implement a graph with
over 11k nodes and I am afraid that the speed might begin to wither. I
have implemented a test version with this code and a set of 5k nodes and
the speed could be quicker
Thanks a lot...

 

[Diez B. Roggisch]

Hello,
I read "Python Patterns: Implementing Graphs" document on the website
and was impressed with doing graphs in this fashion. Is this still the
best documented way to do graphs. The document alludes to a follow up
article tuned for speed but I have not found it. Can anyone suggest
other ways that might be faster? I am looking to implement a graph with
over 11k nodes and I am afraid that the speed might begin to wither. I
have implemented a test version with this code and a set of 5k nodes and
the speed could be quicker

Maybe its faster to store the adjacences in a matrix (e.g. Numeric array) -
some graph ops then are simple matrix ops.

A node of course is than only an number - used as index. That should speed
things up. You can of course have a dictionary to map names to nums and
vice versa.

Diez

 

[Aaron Watters]

Maybe its faster to store the adjacences in a matrix (e.g. Numeric array) -
some graph ops then are simple matrix ops.

That will work if the graph is extremely dense. If it is not I don't
think it is a good idea. Please also look at kjbuckets available as part
of the gadfly package as either kjbuckets0.py or kjbucketsmodule.c.

http://gadfly.sourceforge.net
http://cvs.sourceforge.net/viewcvs.py/gadfly/gadfly/kjbuckets/
http://cvs.sourceforge.net/viewcvs.py/gadfly/gadfly/gadfly/kjbuckets0.py

--Aaron Watters

ps: off topic http://xsdb.sourceforge.net
===
An apple every 8 hours will keep 3 doctors away. --kliban