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. Since this is a small part of an another algorithm I'm writing, I also need to know the final sum of the path (2 in this case), because I'm using BellmanFord as a solution to linear inequalities, so I tried accessing the edge with the nodes like g70.weight[g70.edge(path[node],path[node+1])] and because the path doesn't specify which of the two edges is the solution, I can't seem to find the SPECIFIC edge that appears in the path. (In this case it was simple: (0>2), however in my program for example a path is: (0>4>5>6) and I have two edges (5>6) ) TL;DR: I have a directed graph with multiple edges and negative weights. I plan to use Bellman Ford to solve a small system of linear inequalities. After using gt.shortest_path, how can I access each EDGE of the path in order to sum each weight of the specific edge that appears in the path? <https://nabble.skewed.de/file/t496248/errorGraphTool.png>  Sent from: https://nabble.skewed.de/ _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool 
Administrator

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. 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 <[hidden email]> _______________________________________________ graphtool mailing list [hidden email] https://lists.skewed.de/mailman/listinfo/graphtool signature.asc (849 bytes) Download Attachment

Tiago de Paula Peixoto <tiago@skewed.de> 
Free forum by Nabble  Edit this page 