Hacker News Reader

Comment by peaton | Hacker News Reader

I completely disagree that this question is irrelevant. I can imagine this exact situation in compiler design where you have dependent types that can't have infinite loops (in pseudo-code where forward declarations are not needed or implied):

type a = b

type b = a

If a program has a structure like this with cyclic dependencies, then the compiler must be aware of this and break. (At least, I can imagine a situation where this could be a desired attribute.)

View on HN

You are mixing up cyclical linked lists with loops in a graph. The reason why the question is bad stems from the fact that it's specifically about linked lists.

I could definitely be mistaken, but I don't see a difference between a linked list and a graph. They are two ways to represent the same thing. That being said, if he asked me to find cycles in a linked list, I might determine the adjacency matrix and check for loops:

http://stackoverflow.com/questions/16436165/detecting-cycles...

This is at least very easy to reason about. However, if you are still right my thought process is just very wrong.

"I could definitely be mistaken, but I don't see a difference between a linked list and a graph."

A linked list is a particular type of DAG (or at least DG). The relevant distinction between linked list and the general case is that a linked list restricts nodes to (zero or) one outbound edge. This is relevant to the problem at hand, because you only have one tortoise and one hare and so they can only follow one path.

Ok, that was poorly worded. What I mean is that a linked list can be thought of as a restrictive graph. I'm just saying I'd prefer to think of it as a graph. I could still be wrong. Is that kosher?

That's certainly kosher (though, nitpicking terminology, I'd say "restricted" rather than "restrictive").

That doesn't get around the original objection, though, which is that the restriction has to be exploited to get the algorithm in question, and thus the algorithm cannot be applied to the general case of graphs.

Having said that, certainly the ability to make use of restrictions provided by your domain is hugely valuable, and this should serve as a relatively familiar case.

Right. As a graph theorist might put it, a linked list is a directed graph with a vertex-disjoint path cover consisting of exactly one path. I.e., linked lists are specialized graphs. The tortoise-and-hare algorithm can be generalized to detect cycles in any connected graph, as long as a consistent traversal order is used.

"The tortoise-and-hare algorithm can be generalized to detect cycles in any connected graph, as long as a consistent traversal order is used."

But not in O(1) space, right?

I think it depends on how the graph is represented. With the "standard" representations, it would be O(n) space in the worst case, where n is the number of nodes in the graph. You'd still only need the 2 pointers, but the traversal itself would need to also remember which paths it has not yet visited. The worst case is when the number of paths is much larger than the length of any particular path. The best case (apart from the null graph) is equivalent to the linked list, where there is only one path in the cover.

I can imagine representing the graph as a list of paths, in which case the tortoise-and-hare algorithm is O(1) space, though the graph itself would be (potentially much) larger. Virtually every other operation on such a graph would take a performance hit, too.

There may be other factors I haven't thought of, but you're right that the generalized algorithm could not be as space-efficient as the special algorithm.

It's worth noting, though, that the original question poised in the article did not place an O(1) restriction on space.

"It's worth noting, though, that the original question poised in the article did not place an O(1) restriction on space."

For sure.

A graph can have branches, but a linked list is linear.

Reply on news.ycombinator.com