Re: [Boost-users] [BGL] adding an edge without modifying a graph?!

Subject: Re: [Boost-users] [BGL] adding an edge without modifying a graph?!
From: Ireneusz Szcześniak (irek.szczesniak_at_[hidden])
Date: 2015-10-24 13:15:38

Hi Alberto,

Thanks again for you input, but I guess you're wrong, at least when a 
graph has parallel edges.

Why?  You use the "edge" function to get a descriptor of the reverse 
edge, which returns pair(edge_descriptor, bool).  The edge_descriptor has:

* the source vertex descriptor,
* the target vertex descriptor,
* the pointer to an edge property object.

If the edge doesn't exist in the graph, the pointer is 0, otherwise it 
points to the object with the edge properties.  If there are parallel 
edges, the function always returns the descriptor to the first edge. 
Therefore when you build your "reverse_edge" vector, all parallel 
edges point to a single reverse edge, while they should point to their 
respective reverse edges.

This is important for the successive_shortest_path_nonnegative_weights 
algorithm, where:

"The WeightMap has to map each edge from E to nonnegative number, and 
each edge from ET to -weight of its reversed edge."

So different parallel edges must have their respective different 
reverse edges, because the reverse edges must be mapped to their 
proper negative weights.

Best,
Irek

On 15.10.2015 16:10, Alberto Santini wrote:
> Hi, you don't need to actually add the edges to the graph. For
> example, I usually put them in an std::vector... as long as there is a
> way to link each edge with its reverse (i.e. a property_map). Example:
>
> struct Vertex { int id; };
> struct Edge { int id; };
>
> using Graph = adjacency_list<listS, listS, directedS, Vertex, Edge>;
> using Edge = Graph::edge_descriptor;
> using EdgeIterator = Graph::edge_iterator;
>
> Graph g;
> EdgeIterator ei,ei_end;
>
> // ... Fill g
>
> std::vector<Edge> reverse_edge(num_edges(g));
>
> for(std::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
>    auto id = graph[*ei].id;
>    reverse_edge[id] = (edge(target(*ei, g), source(*ei, g), g).first);
> }
>
> boykov_kolmogorov_max_flow(
>    g,
>    // ... Other params
>    make_iterator_property_map(reverse_edge.begin(), get(&Edge::id, g)),
>    // ... Other params
> );
>
> On 15 October 2015 at 15:10, Ireneusz Szcześniak
> <irek.szczesniak_at_[hidden] <mailto:irek.szczesniak_at_[hidden]>> wrote:
>
>     Hi,
>
>     The subject sounds crazy, I know.  But I need to add reverse edges
>     so I can run a max-flow algorithm on my graph, and I would not
>     like to modify the input graph.
>
>     I can make a copy of the graph, modify it all right, run a
>     max-flow algorithm, and discard the modified graph, but that would
>     be inefficient.
>
>     So I wonder whether someone could share some trick on how to do
>     that, if this is possible.  I was hoping to use boost::subgraph:
>     create a root graph, create its subgraph, and then add reverse
>     edges only to the root graph.  Unfortunately, these edges also
>     popped up in the subgraph.
>
>
>     Thanks & best,
>     Irek
>     _______________________________________________
>     Boost-users mailing list
>     Boost-users_at_[hidden] <mailto:Boost-users_at_[hidden]>
>     http://lists.boost.org/mailman/listinfo.cgi/boost-users
>
>
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>