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
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4