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

Subject: Re: [Boost-users] [BGL] Kolmogorov max flow
From: Olivier Tournaire (olitour_at_[hidden])
Date: 2010-02-03 14:43:32

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_at_[hidden]>

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