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@gmail.com> 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users