graphs in python...

  • Thread starter Douglas F. Calvert
  • Start date
D

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...
 
D

Diez B. Roggisch

Douglas said:
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
 
A

Aaron Watters

Diez B. Roggisch said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top