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