5 ms·
I've always thought Floyd's tortoise and hare[0] algorithm was handy as it can find a cycle in a DAG with low memory usage. [0] https://en.wikipedia.org/wiki/C
by karmakaze 2y ago
I've always thought Floyd's tortoise and hare[0] algorithm was handy as it can find a cycle in a DAG with low memory usage.
[0] https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...
- konstantinua00 2y agohow does it work on DAG? I always thought it's a linked list algo
- tejtm 2y agoBy never finding a cycle, it proves the graph is a DAG.
- jerf 2y agoBut you have to run it on a sequence, or perhaps even more accurately, something that is putatively a sequence but may have an infinite loop in it. Tortoise & hare requires an unambiguous "next" function, which a graph does not have. Modifying it to not require that so it can run on a graph may be possible but that would constitute a different algorithm for sure, with different complexity analysis, etc.
- pavon 2y agoIt is useful for determining whether a given traversal of a graph has encountered a cycle, rather than determining whether the entire graph has any cycles. So different from what the article was about, but still a nice tool to have in the box.
- water-data-dude 2y agoHere is where a smartass might point out that by definition you won’t find any cycles in your DAG
- pavon 2y agoIt's short for Directed Accidentally-cyclic Graph.
- alfiedotwtf 2y agoThanks for the morning laugh :)