Standard graph API?

[David Eppstein]

In article <slrncikma7.e8q.mlh at furu.idi.ntnu.no>,
 mlh at furu.idi.ntnu.no (Magnus Lie Hetland) wrote:

> >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
> 
> Yes... I've been thinking about this -- it might be useful to allow
> some form of traversal (where you could supply your own queue object,
> for example, giving you bfs, dfs, dijkstra, prim, whatever) and have
> the traversal take the form of an iterator (similar to the Boost graph
> library). But if access to each node and its neighbors is available in
> the interface, such traversals wouldn't really have to be part of the
> standard API...

I've tried two different ways of writing a general purpose DFS with as 
you say sufficiently many relevant hooks.  They're both in 
<http://www.ics.uci.edu/~eppstein/PADS/DFS.py>

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

-- 
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/