becks
@becks

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

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

Далее нацелился оптимизировать обработку графа. Задача звучит тривиально.
Исходные данные: матрица инцидентности (сильно разреженная матрица);
Задача:
1) максимально быстро получить кратчайший путь из одного узла в любой другой (веса всех ребер, допустим, равны)
2) максимально быстро получить матрицу независимых контуров графа (независимый - не содержит вложенных контуров)
Задачи довольно типовые. Возможно уже имеются готовые, быстрые, "high-quality" решения на С++?
  • Вопрос задан
  • 782 просмотра
Пригласить эксперта
Ответы на вопрос 3
Adamos
@Adamos
maaGames
@maaGames
Погроммирую программы
3000 вершин и 10000 рёбер это маленький граф.)
Для решения матриц могу посоветовать ещё попробовать taucs и mkl pardiso (придётся воровать).

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

Независимые контуры можно найти методом "в лоб". Создать дополнительную структуру с номером вершины и номером контура. Затем берёшь любую вершину и рекурсивно помечаешь все связанные с ней вершиной. Потом начинаешь новый контур с любой не помеченной вершины. Сложность алгоритма линейная.
Ответ написан
Комментировать
@coodan
Любая библиотека, ориентированная на работу с графами, естественно, должна поддерживать и базовые алгоритмы обхода графов, причем не в наивном, а в самом что ни на есть математически безупречном исполнении. Поэтому Вам подойдет любая. Самому такого не написать.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы