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

Subject: Re: [Boost-users] [BGL] Kolmogorov max flow
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-02-03 14:24:59

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