Hacker News Reader

Comment by tunesmith | Hacker News Reader

How do you detect a cycle with linked lists? :) I actually have a side project where I've run into this - it's a distributed directed graph structure where the nodes can send messages to each other. It's intended to be acyclic, but "walking the graph" is really only used to send truth values, which are combined with others to run Boolean logic. So in that case, the occasional cycle doesn't matter, because if the calculated boolean value matches that of the node's internal state, it just can cease propagating. So a structural loop won't turn into an infinite processing loop.

The problem then becomes that I can't introduce NOT gates anywhere in a cycle, because then the bit will continue flipping and I'll get an infinite processing loop.

So it seems my only hope is external processes that continually walk the graph and keep track of where it visited to try and detect loops, and I don't like how that scales...

View on HN

With "just" a linked list, you need a turtle (advance one-node at a time), and a hare (advance two-nodes at a time).

If the turtle and hare ever meet, you have a cycle. Otherwise, if the hare reaches the end of the list, you don't have a cycle.

Just in case performance matters, there is a more efficient way: have the tortoise stay in place and advance the hare only one node at a time, and assign the hare to the tortoise every time a power of 2 number of steps have been made. This is known as Brent's algorithm, and it requires fewer advancements than the original tortoise and hare algorithm by Floyd.

Another notable advantage of Brent's algorithm is that it automatically finds the cycle length, rather than (in Floyd's case) any multiple of the cycle length.

https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algori...

https://rosettacode.org/wiki/Cycle_detection

Cycle detection in (currently) 44 languages. Most (all?) use Brent's algorithm. They're operating on an iterated function but converting most of these to detect cycles in a linked list would be straightforward.

Recycler.

To be clear, http://trout.me.uk/gc/recycler-overview.pdf

There's also a paper with the full algorithm in that directory.

It's how Nim's ORC collector works.

(note that yes, I know, this is for collection, not cycle detection in general, but it's also brilliant and works)

There are a bunch of algorithms for detecting cycles. One of the classics is the tortoise and hare algorithm, which uses only O(1) space. https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...

It's not difficult. Keep a pointer to a recently-visited node. After visiting N nodes, update the pointer to the current node, but also double N. If the pointer ever matches the next node, the list has a cycle. The doubling of N ensures that even large cycles will eventually be detected.

Does the graph have static structure? I’m not sure if you’re describing something like an actor system.

Akka cluster sharding :) Shape of the graph can change as processes are being run.

One of the standard texts on the matter: https://aphyr.com/posts/341-hexing-the-technical-interview

Set two pointers to the head of the list.

Step through the list by one element per iteration with one of them, and with the other, step every other iteration.

If the two pointers are ever again equal you've found a cycle.

If you hit end of list, no cycle.

Can you just store the first reference as a local variable and then compare each time you move to a new node?

Or to save the comparisons make the thing the first node points to have a stop flag of some sort.

That approach works only when the first node is included in the cycle. Other cycles are possible.

Consider this kind of cycle:

  Head -> Node1 -> Node2 -> Node3
            ^                 |
            +-----------------+

If it's a circular list then your option would work, but not all cycles will produce circular lists.

Thanks. This seems so obvious now! Always draw it out I guess.

I would say the easiest way is to walk the graph and tag the nodes as visited. If you don't visit every node each iteration use a increasing key you store in each node.

Reply on news.ycombinator.com