Standard graph API?

David Eppstein eppstein at
Mon Aug 23 21:14:26 CEST 2004

In article <mailman.2240.1093287844.5135.python-list at>,
 Phil Frost <indigo at> 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

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

More information about the Python-list mailing list