How can I know a specific edge from a Graph?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

How can I know a specific edge from a Graph?

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.

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
Bellman-Ford 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/
_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool
Reply | Threaded
Open this post in threaded view
|

Re: How can I know a specific edge from a Graph?

Tiago Peixoto
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.
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 <[hidden email]>


_______________________________________________
graph-tool mailing list
[hidden email]
https://lists.skewed.de/mailman/listinfo/graph-tool

signature.asc (849 bytes) Download Attachment
--
Tiago de Paula Peixoto <tiago@skewed.de>