[Python-Dev] RE: finalization again

[Tim Peters]

Quickie:

[Tim]
>> It's not obvious, but the SCCs can be found in linear time (via Tarjan's
>> algorithm, which is simple but subtle;

[NeilS]
> Wow, it seems like it should be more expensive than that.

Oh yes!  Many bright people failed to discover the trick; Tarjan didn't
discover it until (IIRC) the early 70's, and it was a surprise.  It's just a
few lines of simple code added to an ordinary depth-first search.  However,
while the code is simple, a correctness proof is not.  BTW, if it wasn't
clear, when talking about graph algorithms "linear" is usual taken to mean
"in the sum of the number of nodes and edges".  Cyclops.py finds all the
cycles in linear time in that sense, too (but does not find the SCCs in
linear time, at least not in theory -- in practice you can't tell the
difference <wink>).

> What are the space requirements?

Same as depth-first search, plus a way to associate an SCC id with each
node, plus a single global "id" vrbl.  So it's worst-case linear (in the
number of nodes) space.  See, e.g., any of the books in Sedgewick's
"Algorithms in [Language du Jour]" series for working code.

> Also, does the simple algorithm you used in Cyclops have a name?

Not officially, but it answers to "hey, dumb-ass!" <wink>.

then-again-so-do-i-so-make-eye-contact-ly y'rs  - tim