Thank you Jereliah for your quick reply. I will try tomorrow and give you the results. One more question : I compute for each edge its capacity, and store the, for instance, in a std::vector. How can I set them to the edge_capacity property ? Note that I can adapt my code to use another container.

Regards,

Olivier


2010/2/3 Jeremiah Willcock <jewillco@osl.iu.edu>
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_main.html#Subsecti

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<opposite_edge_map<Graph> > {
   typedef typename boost::graph_traits<Graph>::edge_descriptor value_type;
   typedef value_type reference;
   typedef value_type key_type;
   typedef readable_property_map_tag category;
 };
}

template <typename Graph>
typename boost::graph_traits<Graph>::edge_descriptor
get(const opposite_edge_map& em,
   typename boost::graph_traits<Graph>::edge_descriptor e) {
 return opposite_edge(e, em.g);
}

Then you can use make_opposite_edge_map(g) on your graph g as the reverse edge map argument to kolmogorov_max_flow.

-- Jeremiah Willcock

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