Standard graph API?

[Paul Moore]

"Robert Brewer" <fumanchu at amor.org> writes:

>> Is there any interest in a (hypothetical) standard graph API (with
>> 'graph' meaning a network, consisting of nodes and edges)?
>
> 1) Yes!
> 2) Only if it's in C. I don't mind (re)writing pure Python graph
> containers, it's the speed of a pure Python graph that's the bigger
> issue to me (mostly object inspection and/or
> decorate-insert-retrieve-undecorate cycles). If it started in a
> pure-Python package, then went into the stdlib, and then got a C
> implementation (like sets.py did), that would be fine.
> 3) It would have to accept arbitrary objects. No "make your class a
> subclass of GraphNode" garbage. If someone wanted to make a subclass of
> Graph called StringGraph, which was optimized for strings, or IntGraph
> optimized for ints, that would be fine. But the base class (I assume a
> class implementation?) should handle instances of Object.
>
> I'm sure there are many more details, but those are the big ones IMO.

1) Yes, from me as well. I've not used graphs in Python much, but
   mainly because I found that I got sidetracked from my original
   project into implementing graph algorithms, and never completed the
   original job :-)

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

Paul.
-- 
In theory, there is no difference between theory and practice; In
practice, there is. -- Chuck Reid