Re^3: Sort mechanics problems with objects and potentially contradicting comparisons (would cause infinite loop)

This problem is known as cycle detection, and there are a number of different solutions, depending on your requirements.

Repeat visits to a node in the structure tell you nothing about whether the traversal is finite.

I'm not sure what you mean by that. Repeat visits to a node tell you that you're in a cycle, and you'll keep going around forever unless you break out (as Floyd's code does).

Most sort algorithms won't loop infinitely if the comparison function is inconsistent. They'll just return the list in a non-meaningful order.

Comment on Re^3: Sort mechanics problems with objects and potentially contradicting comparisons (would cause infinite loop)

Replies are listed 'Best First'.
Re^4: Sort mechanics problems with objects and potentially contradicting comparisons (would cause infinite loop) by anonymized user 468275 (Curate) on Jun 15, 2016 at 13:14 UTC
The problem with that is that all you do is move the infinite loop somewhere else rather than predict it. Or if the sort algorithm terminates instead, it will ignore dependencies. One world, one people	[reply]