Re:Possibly all the ways to get loop-finding in graphs wrong
by pavon on Wednesday September 11, 2024 @03:02PM
(#41514305)
It 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.
Re:Possibly all the ways to get loop-finding in graphs wrong
by tejtm on Wednesday September 11, 2024 @01:38PM
(#41513558)
By never finding a cycle, it proves the graph is a DAG.
Re:Possibly all the ways to get loop-finding in graphs wrong
by jerf on Wednesday September 11, 2024 @02:38PM
(#41514078)
But 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.
I always thought it's a linked list algo