Обнаружение многократных циклов в циклически ориентированном графе

Question

У меня есть ориентированный циклический граф с более чем одним циклом, и мне нужен способ обнаружить (и перечислить) каждый цикл, присутствующий в орграфе.

График можно увидеть здесь: http://img412.imageshack.us/img412/3327/schematic.gif

Это фиктивный график, составленный для отладки моего скрипта на python.Он содержит циклы:

[n13, n14], [n6, n8, n15, n16, n7], [n6, n8, n9, n7]

Алгоритм должен обнаруживать каждый цикл в орграфе, а не только самый маленький или первый, с которым он сталкивается.

Answer 1

Вы не указали, как именно вы представляете Направленный граф, но вы можете взглянуть на Неопитоник: Обнаружение циклов в ориентированном графе .

Answer 2

AFAIK, python-graph находит только один цикл, а не все возможные циклы. См:

http://groups.google.com/group/python-graph/browse_thread/thread/9170926f1bdd097b

Эта другая статья, кажется, решает проблему, представленную в этом вопросе:

http://www.bitformation.com/art/python_toposort.html

Используется алгоритм, разработанный Р. Э. Тарьяном в 1972 г.

Answer 3

Возможно, вы захотите попробовать эту библиотеку .Имеет алгоритм обнаружения цикла.