Standard graph API?
David Eppstein
eppstein at ics.uci.edu
Mon Aug 23 21:14:26 CEST 2004
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/
More information about the Python-list
mailing list