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

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

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users