Какие есть библиотеки для быстрого поиска в графе кратчайших путей и независимых замкнутых контуров на С++?

Question

[becks]

В аспирантуре по роду деятельности пришлось иметь дело с большими графами (1000-3000 вершин, 10.000 ребер).
Граф представляется матрицей инцидентности (https://ru.wikipedia.org/wiki/Матрица_инцидентности). Работу с матрицами и графом в прототипе программы написал сам. Теперь настало время оптимизировать отдельные участки. Для работы с линейной алгеброй (умножение матриц, solve, разреженные матрицы) взял Armadillo. И, о чудо, выиграл в скорости 20-50 раз.

Далее нацелился оптимизировать обработку графа. Задача звучит тривиально.
Исходные данные: матрица инцидентности (сильно разреженная матрица);
Задача:
1) максимально быстро получить кратчайший путь из одного узла в любой другой (веса всех ребер, допустим, равны)
2) максимально быстро получить матрицу независимых контуров графа (независимый - не содержит вложенных контуров)
Задачи довольно типовые. Возможно уже имеются готовые, быстрые, "high-quality" решения на С++?

Answer 1

[Adamos]

boost::graph ?

Comments

[becks]

Про boost::graph знаю (не использовал правда никогда).
Сколько понял никаких оптимизаций внутри у него нет (нет тех же разреженных матриц, многопоточности "such as the multi-threaded Intel MKL, or AMD ACML, or OpenBLAS libraries"). Может быть есть что-то, но с магией внутри ))?

[Adamos]

becks: убей, не знаю. Мне как-то попадалась книга по нему на русском, и я ее даже почитал. Но на практике ничего этого не применял. Есть ощущение, что там тупо реализована готовая абстракция для классических уже методов поиска вглубь, вширь и т.п. Без лишнего оверхеда, который получается в собственных велосипедах. А уж насколько оно оптимизировано и проч. - бог весть, тут офсайт изучать нужно.

Answer 2

[maaGames]

3000 вершин и 10000 рёбер это маленький граф.)
Для решения матриц могу посоветовать ещё попробовать taucs и mkl pardiso (придётся воровать).

Уже упомянутый BGL можно прикрутить для поиска кратчайшего пути. Там не имеет значения, как граф представлен в памяти, потому что ты предоставляешь итераторы, для обхода графа, но придётся повозиться, чтобы их запрограммировать. Зато сможешь попробовать и поиск в глубину и поиск в ширину. Если не боишься слово "рекурсия", то реализуй поиск А*. Будет и проще и быстрее(может быть), чем буст.

Независимые контуры можно найти методом "в лоб". Создать дополнительную структуру с номером вершины и номером контура. Затем берёшь любую вершину и рекурсивно помечаешь все связанные с ней вершиной. Потом начинаешь новый контур с любой не помеченной вершины. Сложность алгоритма линейная.

Answer 3

[coodan]

Любая библиотека, ориентированная на работу с графами, естественно, должна поддерживать и базовые алгоритмы обхода графов, причем не в наивном, а в самом что ни на есть математически безупречном исполнении. Поэтому Вам подойдет любая. Самому такого не написать.

Когда озадачивался графами, пришел к выводу, что boost::graph лучшее, хотя и небезупречное решение. Но если Вы сильно ориентированны ООП-подход, а generic programming вызывает трудности, то лучше поискать альтернативу, ориентированную на ООП.