Graph library for Python

[geremy condra]

On Tue, Dec 8, 2009 at 7:27 AM, Robin Becker <robin at reportlab.com> wrote:
> geremy condra wrote:
> ...........
>>
>> I don't have a problem with adding this if there's a strong desire for it,
>> but at the moment I'm leaning towards a wait-and-see approach, for
>> all the reasons you described.
>>
>> Geremy Condra
>
> I don't want to sound pessimistic, but graph and digraph theory has a lot of
> history, especially in computer science.

Of course it does- the rich set of problem-solving tools provided
by theoretical computer science and mathematical graph theory
are what make graphs so useful, which is why I'm advocating
that they be in the standard library.

>There are already very many
> implementations eg
>
> http://code.google.com/p/igraph
> http://www.boost.org/doc/libs/release/libs/graph
> http://ernst-schroeder.uni.lu/Digraph/doc/
> http://code.google.com/p/python-graph
> http://compbio.washington.edu/~zach/py_graph/doc/html/public/py_graph-module.html
>
> and many others......some of the above already seem to be very useful.

I suspect that part of the reason there are so many implementations
is because graphs are a) useful and b) not in the standard library.

> Is there reason to suppose that any one representation of graphs or digraphs
> is so good we need to add it to python?

I think there are several implementations that would meet the
standards for code quality, and both graphine and python-graph
are full-featured, easy to use, pure python graph libraries. Any
one of them would be a credit to the standard library.

> Even for fairly common algorithms eg Dijkstra's shortest path there doesn't
> seem to be complete agreement on how to implement them; for the details of
> how nodes/edges/paths should be stored and efficiently manipulated there is
> huge variety.

Of course there are. Different authors envision different use
cases, and select their data structures and algorithms
appropriately. That doesn't imply that none of them are
appropriate for the common case, which is what we would
be targeting here.

Geremy Condra