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
--
https://mail.python.org/mailman/listinfo/python-list
