So, any interest? Or am I just a lone nut in wanting this?

I'm sure there are many more details, but those are the big ones IMO.

Pros and cons of this approach:

- You can use a list instead of a set in the adjacency list part of the
representation.  This may be faster and more space efficient when the
vertex degrees are small.

- It's easy to create test graphs as code literals

    G1 = {
        0: [1,2,5],
        1: [0,5],
        2: [0,3,4],
        3: [2,4,5,6],
        4: [2,3,5,6],
        5: [0,1,3,4],
        6: [3,4],
    }
    G2 = {
        0: [2,5],
        1: [3,8],
        2: [0,3,5],
        3: [1,2,6,8],
        4: [7],
        5: [0,2],
        6: [3,8],
        7: [4],
        8: [1,3,6],
    }

- Any indexable object can be a vertex.  The vertex identities can be
something meaningful to your program.  On the other hand, that means
(unless you know where your graph came from) you can't rely on the
vertices being special vertex objects with nice properties and you can't
use objects like None as flag values unless you're sure they won't be
vertices.

- It doesn't provide an abstract way of changing the graph (although
that's relatively easy if G is e.g. a dict of sets)

- 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.  This
can be an advantage in terms of memory usage but a disadvantage in terms
of number of object creations.  Also it means that if you want to store
information on the edges you have to use a dict indexed by the edge
instead of attributes on an edge object (probably better style anyway
since it prevents different algorithms on the same graph from colliding
with each other's attributes).

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.

2) I don't see a need for C at the start. prototype in Python, and
   migrate to C if the speed is needed. Like the set datatype did. But
   aim for fast Python, so that a C implementation can be avoided if
   it's unnecessary.

3) Definitely arbitrary objects. I'm not sure about a Graph class,
   even - given that the dictionary of adjacency lists implementation
   is so easy to build, it may be worth writing algorithms that just
   depend on a graph "protocol". Something like: for n in g iterates
   through all nodes in g, for m in g[n] iterates through all nodes
   adjacent to n, and for cases where edge weights are needed, g[n][m]
   is the weight of edge n->m. You can get a long way on just those
   primitives. If we had adaptation in Python (PEP 246) I'd suggest an
   IGraph protocol, plus adapters for common implementation methods.

In my personal graph library, I found that one of the nastiest issues
was writing suitably general DFS/BFS algorithms which had "hooks" at
relevant points (node visited in preorder, inorder, and postorder, for
example) without swamping the runtime of the algorithm with calls to
possibly dummy hook functions. I'm not sure that a C implementation
would help here, but good design and fine tuning certainly would.

(If anyone wants to see my current code, I'd be happy to share it).

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).

This is a Python API to the Graphviz DOT language:
http://dkbza.org/pydot.html

So I think this is evidence you are not alone.

http://www.personal.psu.edu/staff/i/u/iua1/python/graphlib/html/

I do have a lot functionality working, you can associate arbitrary
data with the nodes and edges, bfs, dfs, topological sort,graph
generation, David Epstein's python dijkstra algorithm, graphviz
visualization.

* 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.

But if this does turn out to be an acceptable API, I'm all for it. I
just think it would be nice to have a Recommended Standard(tm), to
create interoperability.

[snip]

[snip]

As I tried to state in the original post (I probably wasn't clear
enough) I'm not talking about a standard *implementation*, just a
standard *API*, like the DB-API. This could easily cover all kinds of
strange beasts such as directed or undirected, weighted or unweighted
(etc.) graphs; multigraphs, chain graphs, hypergraphs, who knows.

I'm basically just suggesting that it might be useful to have a
"standard" interface for these things. It may be that the simple de
facto standard that David cites is sufficient (although it certainly
doesn't cover hypergraphs -- but that's possibly going a bit too far
anyway.)

[snip]

Another possibility, which fits into the same general abstract API but
is more specialized, would be to represent a multigraph by a dict of
dicts, where the outer dict maps each vertex to its neighbors and the
inner dict maps each neighbor to the number of edges; then you could
represent each edge by a tuple (v,w,index) with index in range(G[v][w]).

The (as of now quite hypothetical) standard would, however, not have
to include such an interface; one could easily implement that (and
adapters) based on the standard description.

I'm thinking along the lines of an informational PEP.

A secondary reason is that we already have in Python a good general
mechanism (dicts) for associating arbitrary information with objects, I
don't see a need for reinventing a more specific mechanism for doing so
when the objects are pieces of graphs and the information is some list
of weight, label, etc that some graph API designer thinks is sufficient.

I think this may contradict some things I said a year or two ago about
using a dict-of-dicts representation in which G[v][w] provides the
weight; I've changed my mind.

http://www.boost.org/libs/graph/doc/table_of_contents.html
http://www.awprofessional.com/bookstore/product.asp?isbn=0201729148

I tried using it once, and it was so horrendously complicated that I gave
up.  Some of the complexity came from having to abstract all the different
kinds of graphs that were supported, but a lot of it was also a result of
the static nature of C++.

Still, it may be useful as a source of ideas and/or warning of problems.

The first way is to generate a sequence of triples (v,w,edgetype):
(v,v,forward) = start of new DFS tree with root v
(v,w,forward) = first time DFS reaches w from parent v
(v,w,nontree) = edge from v to already-visited vertex w
(v,w,reverse) = DFS returns from v to parent w
(v,v,reverse) = finish DFS tree with root v

The second way is a class with shadowable calls preorder(parent,child),
postorder(parent,child), and backedge(source,destination).  The
arguments to the calls are basically the same as the first and second
items in the triples described above, although I suppose I could have
made separate calls for the DFS tree roots.  The class is instantiated
with a graph argument and as part of its initialization performs a DFS
on that graph, making the calls as it goes.

The first way is lower level and I think uglier, but on the other hand
it's usable to make iterators in a way that the second isn't; see e.g.
the code in the same DFS.py file for iterating through the vertices of a
graph in DFS postorder.

A much more complex example of the second way occurs in
<http://www.ics.uci.edu/~eppstein/PADS/Biconnectivity.py>.

[snip stuff about using dicts]

This can be said about all objects, really; no reason to have
attributes as long as we can associate values with the objects using
dicts. This is where things start to look implementation-specific,
even though it is *possible* to keep it abstract using this interface.

One of my motivations is allowing arbitrary structures behind the
scenes, e.g. the graph may be a front-end for something that is
computed on-the-fly using specialized hardware (in fact a very real
possibilit in my case). I could have something like this be
represented by several distinct objects (e.g. one for the topological
structure, one for the weights), of course, but I'd certainly have to
implement the weight mapping myself, and not use built-in dicts.

I do think your API is nice in that it is simple, but I also have the
feeling that using it with other implementations would be sort of
unnatural; one would be trying to emulate the "dict-of-lists with
dicts for properties" implementation, because that implementation
*would* have been simple -- had one used it.

Also, again, this doesn't lend itself very well to manipulating
graphs. If I set one weight to infinity, I might expect (perhaps) the
corresponding edge to disappear (otherwise the graph would have to be
complete in the first place) or similar things; there may also be
other dependencies between properties. Not easily handled with a
separate object for each property. And using functions for everything
that needs calculating doesn't easily lead to polymorphism...

It's not horribly inconvenient, of course (just a matter of defining a
few objects referring to the same underlying mechanism, each with
a different __getitem__ method). I'm just airing my thoughts about why
it *might* be useful to have something else -- possibly in addition.

Perhaps one could have something like two levels? The Level 1 Graph
API would support the "graph as mapping from nodes to neighbors" with
"properties as separate mappings" and the Level 2 Graph API could add
some convenience methods/properties for encapsulation and
manipulation?

[snip]