Уважаемые коллеги,
По работе (анализ данных эксперимента, количество вершин - сотни) возникла следующая задача: есть направленный граф, из особенностей, видимо, могу отметить только, что нет таких ребер, которые из вершины приходят в неё же саму (петель). На этом графе требуется найти всевозможные замкнутые циклы и перечислить их (причем такие, чтобы каждая вершина была посещена лишь один раз), а кроме того - оценить какова максимальная длина встречающихся циклов на этом графе.
Пример: пусть есть граф
Код:
digraph G {
A->B;
A->D;
B->C;
C->B;
C->A;
D->A;
}
Циклы A->D->A и A->B->C->A - искомые. Цикл A->B->C->B->C->A - не интересен. Максимальная длина цикла - 3 вершины.
Домашнее задание я сделал - нашел основные статьи по этой теме:
- 1972 - Robert Tarjan - диссертация "Enumeration of the elementary circuits of a directed graph" (Cornell Univ.)
- 1975 - Donald B. Johnson - "Finding all the elementary circuits of a directed graph" (SIAM J. COMPUT. Vol. 4, No. 1, March 1975)
- 2006 - Hongbo Liu, Jiaxin Wang - "A new way to enumerate cycles in graph", Proceedings of the Advanced International Conference on Telecommunications and International Conference on Internet and Web Applications and Services (AICT/ICIW 2006)
Посмотрел все, сделал вывод, что последнее - это как раз то, что мне надо . К CS я никак не отношусь, к сожалению, статьи написаны, видимо, математиками для математиков, понять как реализовать этот алгоритм на Паскале (Delphi) для моей структуры не могу.
Пытался поискать доступные описания алгоритма Тарьяна - все они опираются на рекурсивное использование неких алгоритмов "поиска в ширину" или "поиска в глубину", с которыми я не знаком, как и с тем, как их реализовывать, т.к. не знаком с теорией графов, к сожалению. Кроме того, некоторые реализации дают какие списки вершин, которые называются strongly connected components и непонятно какое отношение имеют к циклам, которые мне нужны.
Также все примеры, которые я смог найти, полагаются на какое-то очень странное задание графа с т.з. ООП-программиста - в виде каких-то таблиц. У меня в программе граф задаётся так - есть список указателей (TObjectList), который содержит вершины (у каждой вершины есть свой уникальный идентификатор), к каждой вершине привязаны два списка указателей (тоже TObjectList) - список, в котором перечислены исходящие связи (номера тех вершин, куда от этой вершины уходят ребра) и список входящих связей.
Собственно вот задача. Не мог бы кто-нибудь перевести мне на доступный язык алгоритм нахождения циклов на таким образом заданном графе, может быть поделиться исходниками, если не на Pascal, то на C/C++ я тоже читаю?
Искал, кстати, какие-нибудь библиотеки - нашел только Boost Graph Library из приличного, причем циклов там, как я понял, нет.
Спасибо!
Давайте пока оставим эту грустную тему или перенесем в личные сообщения.