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

Subject: Re: [Boost-users] [BGL] adding an edge without modifying a graph?!
From: Alberto Santini (santini.alberto_at_[hidden])
Date: 2015-10-15 10:10:18

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