Graph algorithms - DFS, generators callbacks, and optimisation

[Paul Moore]

Robin Becker <robin at jessikat.fsnet.co.uk> writes:

> Well in this case couldn't you make seen do the detection for you.
> If I understand your analysis you could make the seen dictionary a
> special kind of dictionary.

Interesting trick. I hadn't thought of this, mainly because "seen" is
only in the parameter list to allow the recursive call to work - I'd
never intended it to be passed by the user. (I have a non-recursive
version of DFS without a "seen" parameter).

More general DFS algorithms have a "colour" dictionary, where vertices
can be "White" (not seen) "Black" (seen) or "Grey" (essentially,
"still being looked at"). I'm not sure how that would interact with
this trick.

Hmm. I wish I had a "big" use case where issues like this matter. But
all of my uses are small - the sort of thing where a general library
helps a lot, because the whole project is too small to justify
(re-)implementing the algorithm. But with just small examples, you
never get the breadth of use cases to make the optimal design obvious.

Or maybe I'm just a lousy library designer :-)

Time to stop rambling and do something productive...

Paul.
-- 
This signature intentionally left blank