Standard graph API?

[Jeremy Bowers]

On Mon, 23 Aug 2004 11:58:15 -0700, David Eppstein wrote:

> - It doesn't directly represent multigraphs
> 
> - It doesn't directly represent undirected graphs (instead you have to
> replace an undirected edge by two directed edges and hope your callers
> don't give you a directed graph by mistake).
> 
> - There isn't an explicit object representing an edge, although you can
> create one by using a tuple (v,w) or (for undirected edges) a set.

I think these three things speak to why there isn't a graph type and
probably won't be one any time soon; unlike "Sets", there are just too
many types of "graphs" in use, all fundamentally different in
implementation, and with all differences having massive performance
implications. As you indirectly point out, each of the following is an
independent dimension:

* Directed, undirected
* Multi or non-multi
* Explicit edges/explicit nodes with links/node and edge objects
* Simple and fast implementation of nodes/nodes and edges that take
  attributes

That's a good 24 possible types of graph library, each with implications
w.r.t. algorithms and performance.

While the abstract idea of a standard graph library is appealing to some
people, any actual concrete implementation will likely leave the majority
of people who want to use it out in the cold, resulting either in
something only useful in the simplest of cases, or suffering from major
feeping creaturitis as it tries to cover too many bases at once.