python graph_tool: получить _все_ кратчайшие пути

Question

Я хочу вычислить все кратчайшие пути между всеми парами в графе. Чтобы достичь этого, я использую функцию all_shortest_paths в graph_tool для каждой пары узлов в графе. Согласно документации, функция может учитывать веса ребер, если они заданы. На первый взгляд это работает нормально. Однако я обнаружил, что возвращенный список кратчайших путей неполон. По-видимому, он включает только кратчайшие пути, которые также используют наименьшее количество прыжков из полного набора кратчайших путей.

Вот небольшой пример:

import graph_tool
import graph_tool.topology

#setup graph
g = graph_tool.Graph()
g.add_vertex(5)
edges = [(0,1),(1,2),(3,2),(0,4),(4,3)]
metrics = [3, 4, 2, 1, 3]
g.edge_properties["metric"] = g.new_edge_property("int")
for i in range(len(metrics)):
    e = g.add_edge(*(edges[i]))
    g.edge_properties["metric"][e] = metrics[i]

#compute all shortest paths from 0 to 2
paths = graph_tool.topology.all_shortest_paths(g, 0, 2, weights=g.edge_properties["metric"])

for path in paths:
    print(path)

print("-"*10)

#increase metric of edge 0-4
g.edge_properties["metric"][g.edge(0,4)] = 2

#recompute all shortest paths from 0 to 2
paths = graph_tool.topology.all_shortest_paths(g, 0, 2, weights=g.edge_properties["metric"])

for path in paths:
    print(path)

Он генерирует граф с 5 вершинами и ребрами, которые образуют 2 пути от вершины 0 до вершины 2 следующим образом:

0 --- 1 --- 2
 \         /
  \       /
   4 --- 3

Очевидно, что путь [0, 1, 2] короче, чем [0, 4, 3, 2] с точки зрения количества переходов. Если метрика не указана, это правильно распознается (здесь не показано).

В начале примера ребра взвешиваются таким образом, что второй путь с большим количеством прыжков "короче". Сумма метрик равна 6, тогда как другой путь имеет общее значение 7. Следовательно, алгоритм корректно возвращает [0, 4, 3, 2].

Затем метрика ребра между 0 и 4 увеличивается на 1. Теперь оба пути имеют одинаковое общее значение и должны возвращаться оба. Тем не менее, алгоритм возвращает только [0, 1, 2]. Я могу только предположить, что количество прыжков все еще каким-то образом учитывается, даже если я указал метрику, и поэтому второй путь игнорируется. Насколько я видел, в официальной документации нет упоминаний об этом поведении.

Я что-то пропускаю? Есть ли лучшая функция для этого, возможно, даже если другая библиотека? Я уже рассматривал igraph как альтернативу, но, похоже, он способен вычислять только один кратчайший путь на пару узлов.

Answer 1

Такое поведение действительно является ошибкой в ​​графическом инструменте, которая возникает при использовании весов! Я только что совершил исправление, которое решает это: https://git.skewed.de/count0/graph-tool/commit/dc06771604dfd8f38d40e68ce16b537bc1afc272

Спасибо за то, что поймали это, и за очень четкий пример!