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-17 18:17:34

Hi Alberto and others,

Thanks, this is awesome!  Please find my example attached.

I need to use successive_shortest_path_nonnegative_weights, which 
requires that a reverse edge of edge e has the weight of -w, where w 
is the weight of edge e.

Referring to my example, the remaining problem is how to provide the 
weight map "e2w" efficiently.  It would be cool to overlay the weights 
for reverse edges to the weight property map in the graph, or to copy 
the graph's property map, and add the extra weights.

Any idea how to do this best?  The simple solution is just to copy the 
weights one by one for each edge, but that's uncool.

Thanks & 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
>