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

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; 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