Abstracting algorithms (graph depth first search)

[Raymond Hettinger]

"Paul Moore"
> The "obvious" way is to pass in a callback function - but you'd need
> 2, one for preorder and one for postorder. And maybe others if extra
> hooks are needed, as they are for other algorithms. And the whole
> thing gets slowed down by extra tests (if callback is not None...).
>
> Or I could write a DFS class, with dummy methods for the hooks (the
> default implementation is "pass"). Users then subclass to add their
> own behaviour. But that seems overcomplicated, and probably also adds
> overhead due to the class mechanism.

You might want to take a look at my generic puzzle solving framework
(an abstracted graph traverser) at
http://users.rcn.com/python/download/puzzle.py

I took the class based approach and it is just a fast as a toplevel
function.  Users subclass the solver and supply ann iterator or
generator for the edges from each node.

The generic solver is about 25 lines.  The rest of the module
consists of instructions and seven examples which solve classic
puzzles.


Raymond Hettinger