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



--
Douglas F. Calvert <douglist@anize .org>

[Diez B. Roggisch]

Re: graphs in python...

Douglas F. Calvert wrote:
[color=blue]
> 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:)[/color]

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]

Re: graphs in python...

"Diez B. Roggisch" <deets_noospaam @web.de> wrote in message news:<bqlsvd$q6 7$07$1@news.t-online.com>...[color=blue]
> Douglas F. Calvert wrote:
>[color=green]
> > Hello,
> > I read "Python Patterns: Implementing Graphs" ...[/color]
>
> Maybe its faster to store the adjacences in a matrix (e.g. Numeric array) -
> some graph ops then are simple matrix ops.[/color]

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