Какие есть библиотеки для быстрого поиска в графе кратчайших путей и независимых замкнутых контуров на С++? В аспирантуре по роду деятельности пришлось иметь дело с большими графами (1000-3000 вершин, 10.000 ребер).
Граф представляется матрицей инцидентности (https://ru.wikipedia.org/wiki/Матрица_инцидентности). Работу с матрицами и графом в прототипе программы написал сам. Теперь настало время оптимизировать отдельные участки. Для работы с линейной алгеброй (умножение матриц, solve, разреженные матрицы) взял Armadillo. И, о чудо, выиграл в скорости 20-50 раз.
Далее нацелился оптимизировать обработку графа. Задача звучит тривиально.
Исходные данные: матрица инцидентности (сильно разреженная матрица);
Задача:
1) максимально быстро получить кратчайший путь из одного узла в любой другой (веса всех ребер, допустим, равны)
2) максимально быстро получить матрицу независимых контуров графа (независимый - не содержит вложенных контуров)
Задачи довольно типовые. Возможно уже имеются готовые, быстрые, "high-quality" решения на С++?
Какие есть библиотеки для быстрого поиска в графе кратчайших путей и независимых замкнутых контуров на С++? В аспирантуре по роду деятельности пришлось иметь дело с большими графами (1000-3000 вершин, 10.000 ребер).
Граф представляется матрицей инцидентности (https://ru.wikipedia.org/wiki/Матрица_инцидентности). Работу с матрицами и графом в прототипе программы написал сам. Теперь настало время оптимизировать отдельные участки. Для работы с линейной алгеброй (умножение матриц, solve, разреженные матрицы) взял Armadillo. И, о чудо, выиграл в скорости 20-50 раз.
Далее нацелился оптимизировать обработку графа. Задача звучит тривиально.
Исходные данные: матрица инцидентности (сильно разреженная матрица);
Задача:
1) максимально быстро получить кратчайший путь из одного узла в любой другой (веса всех ребер, допустим, равны)
2) максимально быстро получить матрицу независимых контуров графа (независимый - не содержит вложенных контуров)
Задачи довольно типовые. Возможно уже имеются готовые, быстрые, "high-quality" решения на С++?
Граф представляется матрицей инцидентности (https://ru.wikipedia.org/wiki/Матрица_инцидентности). Работу с матрицами и графом в прототипе программы написал сам. Теперь настало время оптимизировать отдельные участки. Для работы с линейной алгеброй (умножение матриц, solve, разреженные матрицы) взял Armadillo. И, о чудо, выиграл в скорости 20-50 раз.
Далее нацелился оптимизировать обработку графа. Задача звучит тривиально.
Исходные данные: матрица инцидентности (сильно разреженная матрица);
Задача:
1) максимально быстро получить кратчайший путь из одного узла в любой другой (веса всех ребер, допустим, равны)
2) максимально быстро получить матрицу независимых контуров графа (независимый - не содержит вложенных контуров)
Задачи довольно типовые. Возможно уже имеются готовые, быстрые, "high-quality" решения на С++?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для работы с графами и поиском кратчайших путей в C++ вы можете воспользоваться следующими библиотеками:
Boost.Graph - Boost - это библиотека, которая включает в себя множество инструментов для работы с графами, включая алгоритмы поиска кратчайших путей, обхода графа и т.д. С ее помощью можно эффективно работать с графами любого размера.
Lemon Graph Library - Lemon - это еще одна мощная библиотека для работы с графами на языке C++. Она включает в себя широкий спектр алгоритмов для работы с графами, включая поиск кратчайшего пути и различные алгоритмы обхода графа.
igraph - igraph - это библиотека для работы с графами на языке C. Она также имеет обертку для языка C++, что позволяет использовать ее удобно в проектах на этом языке.
Эти библиотеки предоставляют широкий спектр функций для работы с графами и поиском кратчайших путей, которые могут быть полезны в вашем проекте. Каждая из них имеет свои особенности и преимущества, поэтому вам стоит попробовать их и выбрать наиболее подходящую для вашей задачи.