Detecting a cycle in a graph
Christian Gollwitzer
auriocus at gmx.de
Sun Jan 14 16:14:44 EST 2018
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
More information about the Python-list
mailing list