Detecting a cycle in a graph

[Christian Gollwitzer]

Am 14.01.18 um 22:04 schrieb Christian Gollwitzer:
> Am 14.01.18 um 09:30 schrieb Frank Millman:
>> I need to detect when a 'cycle' occurs - when a path loops back on 
>> itself and revisits a node previously visited. I have figured out a 
>> way to do this, but I have a problem.
> 
> I don't know if that helps, but there is a classic graph theory 
> algorithm called "Floyd's cycle detector". The idea is to have a pointer 
> move along the graph and a second one which runs at double the speed. If 
> they meet, you found a cycle. It is not straight-forward to come up with 
> this algorithm, which even runs in constant storage. ISTR that there are 
> some variants which can give you the split point of the cycle, too.

And here is an algorithm to enumerate all cycles in a directed graph:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.335.5999&rep=rep1&type=pdf

	with an implementation in C++ here:

https://github.com/hellogcc/circuit-finding-algorithm

	Christian