Standard graph API?

[David Eppstein]

In article <mailman.2240.1093287844.5135.python-list at python.org>,
 Phil Frost <indigo at bitglue.com> wrote:

> +1 for standard graph API!
> 
> I don't have a "high-end" use for it, but I did write a program which
> graphs the revision history of a software repository. It would have been
> nice to have most of that code in a library, and if such a library
> existed, it would probably implement operations I was too lazy to
> implement, such as coloring.

I have a random sample of graph algorithms implemented in
http://www.ics.uci.edu/~eppstein/PADS/

I use the existing Guido-standard graph representation, that is:
iter(G) and iter(G[v]) list vertices of G and neighbors of v in G
v in G and w in G[v] test existence of vertices and edges in G

It includes both simple basic graph algorithm stuff (copying a graph, a 
DFS implementation that works non-recursively so it doesn't run into 
Python's recursion limit) and some much more advanced algorithms (e.g. 
non-bipartite maximum matching).

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/