Bug with all_shortest_paths() with edges=True and parallel edges have different weights


I think the function all_shortest_paths is not returning the correct answer when the input parameter edges = True . I created 3 edges between 2 nodes. These edges have different attributes. 2 of them have the weight set to 200 and one of the edges weight is 100. As the diagram below shows. However, graph tool return an edge object but the attribute for edge object are not correct. You can see the example in python below.

  1. graph-tool version : 2.45 .
  2. Operating system : macOS Monterey 12.6.1.
  3. A minimal working example that shows the problem.
g = gt.Graph()

edge_weight = g.new_edge_property("double")
g.edge_properties["weight"] = edge_weight

edges = [[0,1],[0,1],[0,1]]
weights = [200,200,100]

for i in range(len(edges)):
    e = g.add_edge(edges[i][0], edges[i][1])
    g.ep.weight[e] = weights[i]

for path in gt.all_shortest_paths(g, 0, 1, weights=g.ep.weight, edges = True):
    for edge in path:

For the above it will return:

[<Edge object with source '0' and target '1' at 0x1769584c0>]
(0, 1) 200.0

Which is wrong. I was expecting to see the edge with the weight 100. The good news is that it identifies the shortest path is one edge (not three) but it is not returning it right.

Could you please open an issue in the gitlab repository: https://git.skewed.de/count0/graph-tool/-/issues ?

I’ll fix this in the next release.

Thank you for the reply. May I ask when will the next release be?

We’ve developed a network failure modelling software based on graph-tool library and it’s critical to us to know. If the release date is not close, is it possible to do a hot fix release by any chance since it’s impacting the shortest path calculation? Thanks.

Release dates are not planned in advance — they depend on many factors, including other time commitments.

In the mean time, you can workaround this issue simply by either removing or filtering parallel edges that have a larger weight, since they can never belong to a shortest path, or by selecting the one with the shortest weight a posteriori.

This is a rather “cosmetic” bug fix, since it’s always obvious what the right answer should have been, and it’s easy to work around.