Am 22.07.20 um 00:12 schrieb spolo96:
Hello everyone, I'm having a hard time dealing with multiple edges in a graph with the use of gt.shortest_path with negative weights. This is a simple code that creates a simple graph in order to show my problem:
g70 = gt.Graph()
edge_weight = g70.new_edge_property("double") g70.edge_properties["weight"] = edge_weight
edges = [[0,1],[1,2],[0,2],[0,2]] weights = [-1,0,-2, 0]
for i in range(len(edges)): e = g70.add_edge(edges[i][0], edges[i][1]) g70.ep.weight[e] = weights[i]
for path in gt.shortest_path(g70, 0, 2, weights=g70.ep.weight, negative_weights=True): print(path)
gt.graph_draw(g70, vertex_text=g70.vertex_index, edge_text=g70.ep.weight)
As you can see in the image, there are 2 edges from node 0 to node 2, the solution that appears before the image specifies: <Edge object with source '0' and target '2' at 0x7f2b70d49930> meaning that the shortest path from node 0 to node 2 is an edge from node 0 to node 2. However it doesn't specify which one of the two edges: (0,2) ->0, (0,2)->-2 is the solution edge.
Of course it does. The function returns both the vertices and the edges. The edge descriptors map to a specific edges, which have their own index and properties (such as weight). Just do the following: for e in gt.shortest_path(g70, 0, 2, weights=g70.ep.weight, negative_weights=True)[1]: print(e, g70.edge_index[e], g70.ep.weight[e]) which will print: (0, 2) 2 -2.0 Note that it's always obvious which of the parallel edges get selected: it's always the one with the smallest weight, otherwise it would not be part of the shortest path. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>