Graph algorithms - DFS, generators callbacks, and optimisation
pf_moore at yahoo.co.uk
Sat Nov 29 21:27:59 CET 2003
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
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...
This signature intentionally left blank
More information about the Python-list