On Wed, 3 Feb 2010, Olivier Tournaire wrote:
Hi all,
I am currently trying to use kolmogorov_max_flow algorithm. I am building a graph from another lib, namely CGAL. I first build an arrangement of the plane, and use the dual arrangement representation provided by CGAL (seehttp://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Arrangement_2/Chapter_ma... on_20.12.2). So, each vertex of the graph is a face of the arrangement, and each edge in the graph is an edge of the arrangement. CGAL provides a graph_traits to use BGL algorithm. However, I do not know how to use kolmogorov_max_flow with this graph_traits. The doc states that reversed edges must be included in the graph. The graph provided by CGAL already has reverse edges. How can I deal with that ? Could you please give me the way to call kolmogorov_max_flow withthe graph provided by CGAL ?
Looking at the CGAL manual, it looks like the graph does have reverse
edges already included, and you need to use the opposite_edge() function
(adapted as a property map) from the HalfedgeGraph concept in CGAL as the
reverse edge map for kolmogorov_max_flow. You can do something like (not
tested):
template <typename Graph>
struct opposite_edge_map {
const Graph& g;
explicit opposite_edge_map(const Graph& g): g(g) {}
};
template <typename Graph>
opposite_edge_map<Graph>
make_opposite_edge_map(const Graph& g) {
return opposite_edge_map<Graph>(g);
}
namespace boost {
template <typename Graph>
struct property_traits