Abstracting algorithms (graph depth first search)

[Paul Moore]

"andrew cooke" <andrew at acooke.org> writes:

> for a "completely different" way of looking at graphs, check out martin
> erwig's functional graph library.  it's very elegant (worth learning
> haskell for): http://cs.oregonstate.edu/~erwig/fgl/haskell/  - even if you
> don't want to use the library, read the paper to find a new way of
> thinking about graphs.

I love Haskell, in theory, but I've never seen any "serious" Haskell
code which hasn't made my brain explode :-) This is no exception...

I'll keep the link, as one of these days I hope to understand it :-)

> answering your question more directly, wouldn't a Python iterator be the
> right way to do it: http://www.python.org/doc/current/lib/typeiter.html
> (it's like a callback turned inside out :o)

Iterators work quite well, but there's often a need to hook into more
than one point in the search. For more details, see the Boost Graph
Library - http://www.boost.org - and the various visitor classes.
Actually, I've now got something quite interesting modeled on the
Boost code.

> i don't know about general graphs, but all four of the popular traversal
> methods for trees can be generated from a single algorithm - breadth/depth
> depends on whether you use a fifo or lifo queue and pre/post order depends
> on whether you call the processing before or after recursing. 

Yes, this is what I started trying to do. But in practice, it's pretty
messy to get right.

Thanks for the suggestions,
Paul.
-- 
This signature intentionally left blank