Re: [Boost-users] [BGL] Kolmogorov max flow

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

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