В одном проекте где я участвую я написал специальную утилиту которая по некоторым данным генерирует файл в формате graphviz

Дальше я написал еще одну утилиту которая читает файл от первой утилиты и ее задача вычленить все циклы в графе и сгенрировать еще один graphviz файл содержащий только циклы.

Для этого я сперва использовал алгоритм из boost::graph::tiernan_all_cycles(), который давал весьма среднюю производительность.
Потом я нашел этот репозиторий https://github.com/ldionne/hawick_circuits/blob/master/boost/graph/hawick_circuits.hpp , и это значительно ускорило обработку файлов.

Могу уверить что файлов из которых требуется вычленить циклы просто тонны.
И второй алогритм (hawick_circuits) например с 100!!! мегабайтный файлом лгеко справляется за минут 20, не говоря о более мелких файлах которые просто пролетают мгновенно.

И тут мне попался один небольшой файл который весит всего 5 мегеабайт. Файлы примерно с таким размером hawick_circuits обрабатывает 2-3 секунды, но этот обрабатывается уже 2-е!!! сутки!!! т.е. больше 48 часов.
Я даже. ради эксперемента, попробовал натравить dot утилиту на него и та уже трудиться над ним более 12-ти часов!!!
И что само интересное, она не падает как обычно это бывает с dot когда он не может справиться с большим файлом.

Т.е. созадется впечатление что алгорим hawick_circuits что dot попросту вошли в бесконечный цикл, и это просто какой то особый случай который приводит к неправильной работе алгоритма (да я понимаю что это вряд ли и возможно это какой кейс где граф с супер высокой связностью, но я лишь говорю о том что вижу сам).

Вопрос, что это может быть?

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

Здравствуйте, nen777w, Вы писали:

N>Для этого я сперва использовал алгоритм из boost::graph::tiernan_all_cycles(), который давал весьма среднюю производительность.

N>Если кому интересен файл для анализа (хотя я не очень понимаю как его вобще можно проанализировать), я могу предоставить его.

А вы медленный алгоритм из boost пробовали на этом файле?

очень интересная задача. поучавствовал бы в анализе, и в оптимизации тоже. пиши в лс, если интересно.

Здравствуйте, nen777w, Вы писали:

N>И второй алогритм (hawick_circuits) например с 100!!! мегабайтный файлом лгеко справляется за минут 20, не говоря о более мелких файлах которые просто пролетают мгновенно.
N>И тут мне попался один небольшой файл который весит всего 5 мегеабайт. Файлы примерно с таким размером hawick_circuits обрабатывает 2-3 секунды, но этот обрабатывается уже 2-е!!! сутки!!! т.е. больше 48 часов.
N>Я даже. ради эксперемента, попробовал натравить dot утилиту на него и та уже трудиться над ним более 12-ти часов!!!

N>Вопрос, что это может быть?

Так тебе надо сравнивать не мегабайты исходного формата. А сравнить число вершин и число дуг в «патологическом» и «контрольном» графе. Можно ведь искусственно сгенерировать файл на стопицот мегабайт, который будет содержать разреженный тривиальный граф, типа дерева (без циклов) или просто много изолированных вершин. На нём всё быстро отработает, если асимптотика алгоритма зависит от числа рёбер.

Здравствуйте, nen777w, Вы писали:

N>Т.е. созадется впечатление что алгорим hawick_circuits что dot попросту вошли в бесконечный цикл, и это просто какой то особый случай который приводит к неправильной работе алгоритма (да я понимаю что это вряд ли и возможно это какой кейс где граф с супер высокой связностью, но я лишь говорю о том что вижу сам).

N>Вопрос, что это может быть?
Очевидно, циклов в графе из n вершин может быть больше чем n! . То есть на их перечисление, даже для небольших графов, может уйти всё время вселенной независимо от используемого алгоритма.

Поэтому появляется встречный вопрос: а зачем вообще понадобилось перечислять все циклы? Напиши исходную задачу, а не то (или не только то), как её решаешь сейчас.
В первом сообщении написано так:
N>Дальше я написал еще одну утилиту которая читает файл от первой утилиты и ее задача вычленить все циклы в графе и сгенрировать еще один graphviz файл содержащий только циклы.
Но это слишком размыто. Например совершенно не нужно уметь перечислять циклы чтобы сгенерировать граф, в котором оставлены все циклы из исходного, и удалены все рёбра и вершины, которые в циклы не входят. Если требуется это, то попытка решить такую задачу через перечисление циклов похожа на попытку отсортировать массив через bogosort.

N>Если кому интересен файл для анализа (хотя я не очень понимаю как его вобще можно проанализировать), я могу предоставить его.
Неправильно делаешь. Это кому нужно, тебе или им? Хочешь помощи — выкладывай код/данные сразу. Так сильно увеличишь вероятность ответа.
Короче, читай: http://rsdn.org/Info/Howtoask.xml
И, повторюсь, напиши исходную задачу, а не свои подходы к решению.

N>Вопрос, что это может быть?

хм. а что имеется в виду под "перечислить все циклы"?
если есть регулярная прямоугольная сетка 100 на 100, и все четные горизонтальные линии ведут влево, а нечетные -- вправо (аналогично с вертикальными), то какое количество возможных циклов мы получаем?

A11 -> A12 -> A13 -> A14
 ^      |      ^      | 
 |      v      |      v
A21 <- A22 <- A23 -< A24
 ^      |      ^      | 
 |      v      |      v
A31 <- A32 <- A33 -< A34
 ^      |      ^      | 
 |      v      |      v
A41 <- A42 <- A43 -< A44

сколько циклов получается на таком примере, всего 16 вершин и 24 ребра?

N>>Для этого я сперва использовал алгоритм из boost::graph::tiernan_all_cycles(), который давал весьма среднюю производительность.
С>А вы медленный алгоритм из boost пробовали на этом файле?

Пробовал, подождал пару часов и вырубил, однозначно hawick_circuits зарекомендовал себя гораздо лучше.
Можно конечно предположить что он содержит багу, но... я не знаю, учитывая то кол-во файлов которые уже были обработаны ним.

Здравствуйте, nen777w, Вы писали:

N>... Дальше я написал еще одну утилиту которая читает файл от первой утилиты и ее задача вычленить все циклы в графе и сгенрировать еще один graphviz файл содержащий только циклы.

N>Для этого я сперва использовал алгоритм из boost::graph::tiernan_all_cycles(), ...

А нужно ли находить все циклы? Из исходной постановки задачи, на первый взгляд, кажется что нет.
Проверить содержится ли вершина в каком ни будь цикле можно за O(N+M) (M=число ребер), т.е. если нужен только подграф вершин содержащихся в каком-либо цикле это O(N*(N+M)), в худшем случае при решении "в лоб". Наверное можно еще быстрее, если подумать.

N>>Вопрос, что это может быть?
W>Очевидно, циклов в графе из n вершин может быть больше чем n! . То есть на их перечисление, даже для небольших графов, может уйти всё время вселенной независимо от используемого алгоритма.

W>Поэтому появляется встречный вопрос: а зачем вообще понадобилось перечислять все циклы? Напиши исходную задачу, а не то (или не только то), как её решаешь сейчас.
W>В первом сообщении написано так:
N>>Дальше я написал еще одну утилиту которая читает файл от первой утилиты и ее задача вычленить все циклы в графе и сгенрировать еще один graphviz файл содержащий только циклы.
W>Но это слишком размыто. Например совершенно не нужно уметь перечислять циклы чтобы сгенерировать граф, в котором оставлены все циклы из исходного, и удалены все рёбра и вершины, которые в циклы не входят. Если требуется это, то попытка решить такую задачу через перечисление циклов похожа на попытку отсортировать массив через bogosort.

Ноды графа представляют собой объекты в системе, рёбра (направленные) это связи между этими объектами.
Система знает обо всех объектах которые она когда либо создавала.
По завершению теста некоторые объекты дестурктятся, а некоторые нет потому что:
— либо это объекты созданные глобально/статически
— либо это объекты которые находятся в циклических связях.
Поэтому по завершеню теста система пробегает специальным визитором по реестру живых объектов и генерирует файл graphviz со всемя связями.
A меня для анализа связей интересуют только ноды которые зациклены.
Т.е. интересует их визуализация. Потому и была написана вторая утилита для вычленения этих связей.
Т.е. считай что это визуализация memory leaks в системе.

N>>Если кому интересен файл для анализа (хотя я не очень понимаю как его вобще можно проанализировать), я могу предоставить его.
W>Неправильно делаешь. Это кому нужно, тебе или им? Хочешь помощи — выкладывай код/данные сразу. Так сильно увеличишь вероятность ответа.
W>Короче, читай: http://rsdn.org/Info/Howtoask.xml
W>И, повторюсь, напиши исходную задачу, а не свои подходы к решению.

Вот пожалуйста: http://files.rsdn.org/38394/gv_test_pack.zip
Что в архиве:
data/easy_file.gv — 10Mb файл, время обаботки 36 секунд.
data/problem_file.gv — 5Mb проблемный файл
data/processed/easy_file_cycle.gv — обработаный файл содержит только циклы (как пример)
data/processed/easy_file_cycle.gv.svg — обработаный файл утилитой dot для визуализации циклов (можно открыть в браузере Google Chrome например)
gv_test/ — исходники утилиты для обработки graphviz файлов
gv_test.exe — скомпилированная утилита 64bit

Пример запуска утилиты:
gv_test.exe <файл c исходными данными> <генерируемый файл> <алгоритм: alg_tiernan_all_cycles или alg_hawick_circuits>
gv_test.exe easy_file.gv easy_file_cycle.gv alg_hawick_circuits

Здравствуйте, nen777w, Вы писали:

N>Для этого я сперва использовал алгоритм из boost::graph::tiernan_all_cycles(), который давал весьма среднюю производительность.
N>Потом я нашел этот репозиторий https://github.com/ldionne/hawick_circuits/blob/master/boost/graph/hawick_circuits.hpp , и это значительно ускорило обработку файлов.

Если ты уже разбирался с этими алгоритмами — как оценивается их асимптотическая сложность, от чего она зависит?

Здравствуйте, nen777w, Вы писали:

N>A меня для анализа связей интересуют только ноды которые зациклены.

N>gv_test/ — исходники утилиты для обработки graphviz файлов
Реально аналогия с сортировка массива через bogosort оказалась удачной Простая задача была сведена к адски сложной. Неудивительно, что программа неспешно работает.

Короче, твоя задача решается алгоритмом https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm за время O(E+V). Или любым другим алгоритмом поиска компонент сильной связности.

N>data/easy_file.gv — 10Mb файл, время обаботки 36 секунд.
N>data/problem_file.gv — 5Mb проблемный файл
150 миллисекунд тупой реализацией на питоне. Да исходный файл с диска читался дольше

N>>Для этого я сперва использовал алгоритм из boost::graph::tiernan_all_cycles(), который давал весьма среднюю производительность.
N>>Потом я нашел этот репозиторий https://github.com/ldionne/hawick_circuits/blob/master/boost/graph/hawick_circuits.hpp , и это значительно ускорило обработку файлов.
Q>Если ты уже разбирался с этими алгоритмами — как оценивается их асимптотическая сложность, от чего она зависит?
Не разбирался.

N>>A меня для анализа связей интересуют только ноды которые зациклены.
N>>gv_test/ — исходники утилиты для обработки graphviz файлов
W>Реально аналогия с сортировка массива через bogosort оказалась удачной Простая задача была сведена к адски сложной. Неудивительно, что программа неспешно работает.
W>Короче, твоя задача решается алгоритмом https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm за время O(E+V). Или любым другим алгоритмом поиска компонент сильной связности.

Подразобрался я немного с strong_components() из boost::graph.

	"Вот пример визуализаированонго графа из examples:"

А вот выхлоп алогритма:

Total number of components: 4
Vertex a is in component 3
Vertex b is in component 3
Vertex c is in component 3
Vertex d is in component 0
Vertex e is in component 0
Vertex f is in component 1
Vertex g is in component 1
Vertex h is in component 3
Vertex i is in component 3
Vertex j is in component 2

Алгоритм показал группы: abchj, de, fg, j

В принципе очень не плохо даже. Задача теперь "востановить" ребра в каждой группе.

N>>data/easy_file.gv — 10Mb файл, время обаботки 36 секунд.
N>>data/problem_file.gv — 5Mb проблемный файл
W>150 миллисекунд тупой реализацией на питоне. Да исходный файл с диска читался дольше

Да работает быстро.
Надо бы поучиться алгоритмам на графе.

Здравствуйте, nen777w, Вы писали:

N>А вот выхлоп алогритма:
N>

N>Total number of components: 4
N>Vertex a is in component 3
N>Vertex b is in component 3
N>Vertex c is in component 3
N>Vertex d is in component 0
N>Vertex e is in component 0
N>Vertex f is in component 1
N>Vertex g is in component 1
N>Vertex h is in component 3
N>Vertex i is in component 3
N>Vertex j is in component 2

N>Задача теперь "востановить" ребра в каждой группе.
Да что там восстанавливать-то?
Просто проходишь по всем исходным рёбрам. Если у ребра обе вершины находятся в одной компоненте связности, то оставляешь его, иначе пропускаешь (в примере оставляем (f, g), так как там номер компоненты 1, и пропускаем (i,j) так как там разные компоненты 3 и 2). На выходе получится тот же набор ребёр, что и строился первоначальным алгоритмом через объединение всех простых циклов.

N>>А вот выхлоп алогритма:
N>>

N>>Total number of components: 4
N>>Vertex a is in component 3
N>>Vertex b is in component 3
N>>Vertex c is in component 3
N>>Vertex d is in component 0
N>>Vertex e is in component 0
N>>Vertex f is in component 1
N>>Vertex g is in component 1
N>>Vertex h is in component 3
N>>Vertex i is in component 3
N>>Vertex j is in component 2

N>>Задача теперь "востановить" ребра в каждой группе.
W>Да что там восстанавливать-то?
W>Просто проходишь по всем исходным рёбрам. Если у ребра обе вершины находятся в одной компоненте связности, то оставляешь его, иначе пропускаешь (в примере оставляем (f, g), так как там номер компоненты 1, и пропускаем (i,j) так как там разные компоненты 3 и 2). На выходе получится тот же набор ребёр, что и строился первоначальным алгоритмом через объединение всех простых циклов.

Не воставновить это не задача. Задача докопаться к этой информации в bgl Но это уже мелочи.
В целом, спасибо за подсказку!

Здравствуйте, niXman, Вы писали:

X>очень интересная задача. поучавствовал бы в анализе, и в оптимизации тоже. пиши в лс, если интересно.
Забыл перелогиниться?