test: epoc32/include/stdapis/boost/graph/edmunds_karp_max

     1 //=======================================================================

     2 // Copyright 2000 University of Notre Dame.

     3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee

     4 //

     5 // Distributed under the Boost Software License, Version 1.0. (See

     6 // accompanying file LICENSE_1_0.txt or copy at

     7 // http://www.boost.org/LICENSE_1_0.txt)

     8 //=======================================================================

    10 #ifndef EDMUNDS_KARP_MAX_FLOW_HPP

    11 #define EDMUNDS_KARP_MAX_FLOW_HPP

    13 #include <boost/config.hpp>

    14 #include <vector>

    15 #include <algorithm> // for std::min and std::max

    16 #include <boost/config.hpp>

    17 #include <boost/pending/queue.hpp>

    18 #include <boost/property_map.hpp>

    19 #include <boost/graph/graph_traits.hpp>

    20 #include <boost/graph/properties.hpp>

    21 #include <boost/graph/filtered_graph.hpp>

    22 #include <boost/graph/breadth_first_search.hpp>

    24 namespace boost {

    26   // The "labeling" algorithm from "Network Flows" by Ahuja, Magnanti,

    27   // Orlin.  I think this is the same as or very similar to the original

    28   // Edmunds-Karp algorithm.  This solves the maximum flow problem.

    30   namespace detail {

    32     template <class Graph, class ResCapMap>

    33     filtered_graph<Graph, is_residual_edge<ResCapMap> >

    34     residual_graph(Graph& g, ResCapMap residual_capacity) {

    35       return filtered_graph<Graph, is_residual_edge<ResCapMap> >

    36         (g, is_residual_edge<ResCapMap>(residual_capacity));

    37     }

    39     template <class Graph, class PredEdgeMap, class ResCapMap,

    40               class RevEdgeMap>

    41     inline void

    42     augment(Graph& g,

    43             typename graph_traits<Graph>::vertex_descriptor src,

    44             typename graph_traits<Graph>::vertex_descriptor sink,

    45             PredEdgeMap p,

    46             ResCapMap residual_capacity,

    47             RevEdgeMap reverse_edge)

    48     {

    49       typename graph_traits<Graph>::edge_descriptor e;

    50       typename graph_traits<Graph>::vertex_descriptor u;

    51       typedef typename property_traits<ResCapMap>::value_type FlowValue;

    53       // find minimum residual capacity along the augmenting path

    54       FlowValue delta = (std::numeric_limits<FlowValue>::max)();

    55       e = p[sink];

    56       do {

    57         BOOST_USING_STD_MIN();

    58         delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[e]);

    59         u = source(e, g);

    60         e = p[u];

    61       } while (u != src);

    63       // push delta units of flow along the augmenting path

    64       e = p[sink];

    65       do {

    66         residual_capacity[e] -= delta;

    67         residual_capacity[reverse_edge[e]] += delta;

    68         u = source(e, g);

    69         e = p[u];

    70       } while (u != src);

    71     }

    73   } // namespace detail

    75   template <class Graph,

    76             class CapacityEdgeMap, class ResidualCapacityEdgeMap,

    77             class ReverseEdgeMap, class ColorMap, class PredEdgeMap>

    78   typename property_traits<CapacityEdgeMap>::value_type

    79   edmunds_karp_max_flow

    80     (Graph& g,

    81      typename graph_traits<Graph>::vertex_descriptor src,

    82      typename graph_traits<Graph>::vertex_descriptor sink,

    83      CapacityEdgeMap cap,

    84      ResidualCapacityEdgeMap res,

    85      ReverseEdgeMap rev,

    86      ColorMap color,

    87      PredEdgeMap pred)

    88   {

    89     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;

    90     typedef typename property_traits<ColorMap>::value_type ColorValue;

    91     typedef color_traits<ColorValue> Color;

    93     typename graph_traits<Graph>::vertex_iterator u_iter, u_end;

    94     typename graph_traits<Graph>::out_edge_iterator ei, e_end;

    95     for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)

    96       for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)

    97         res[*ei] = cap[*ei];

    99     color[sink] = Color::gray();

   100     while (color[sink] != Color::white()) {

   101       boost::queue<vertex_t> Q;

   102       breadth_first_search

   103         (detail::residual_graph(g, res), src, Q,

   104          make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())),

   105          color);

   106       if (color[sink] != Color::white())

   107         detail::augment(g, src, sink, pred, res, rev);

   108     } // while

   110     typename property_traits<CapacityEdgeMap>::value_type flow = 0;

   111     for (tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei)

   112       flow += (cap[*ei] - res[*ei]);

   113     return flow;

   114   } // edmunds_karp_max_flow()

   116   namespace detail {

   117     //-------------------------------------------------------------------------

   118     // Handle default for color property map

   120     // use of class here is a VC++ workaround

   121     template <class ColorMap>

   122     struct edmunds_karp_dispatch2 {

   123       template <class Graph, class PredMap, class P, class T, class R>

   124       static typename edge_capacity_value<Graph, P, T, R>::type

   125       apply

   126       (Graph& g,

   127        typename graph_traits<Graph>::vertex_descriptor src,

   128        typename graph_traits<Graph>::vertex_descriptor sink,

   129        PredMap pred,

   130        const bgl_named_params<P, T, R>& params,

   131        ColorMap color)

   132       {

   133         return edmunds_karp_max_flow

   134           (g, src, sink,

   135            choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),

   136            choose_pmap(get_param(params, edge_residual_capacity),

   137                        g, edge_residual_capacity),

   138            choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),

   139            color, pred);

   140       }

   141     };

   142     template<>

   143     struct edmunds_karp_dispatch2<detail::error_property_not_found> {

   144       template <class Graph, class PredMap, class P, class T, class R>

   145       static typename edge_capacity_value<Graph, P, T, R>::type

   146       apply

   147       (Graph& g,

   148        typename graph_traits<Graph>::vertex_descriptor src,

   149        typename graph_traits<Graph>::vertex_descriptor sink,

   150        PredMap pred,

   151        const bgl_named_params<P, T, R>& params,

   152        detail::error_property_not_found)

   153       {

   154         typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

   155         typedef typename graph_traits<Graph>::vertices_size_type size_type;

   156         size_type n = is_default_param(get_param(params, vertex_color)) ?

   157           num_vertices(g) : 1;

   158         std::vector<default_color_type> color_vec(n);

   159         return edmunds_karp_max_flow

   160           (g, src, sink,

   161            choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),

   162            choose_pmap(get_param(params, edge_residual_capacity),

   163                        g, edge_residual_capacity),

   164            choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),

   165            make_iterator_property_map(color_vec.begin(), choose_const_pmap

   166                                       (get_param(params, vertex_index),

   167                                        g, vertex_index), color_vec[0]),

   168            pred);

   169       }

   170     };

   172     //-------------------------------------------------------------------------

   173     // Handle default for predecessor property map

   175     // use of class here is a VC++ workaround

   176     template <class PredMap>

   177     struct edmunds_karp_dispatch1 {

   178       template <class Graph, class P, class T, class R>

   179       static typename edge_capacity_value<Graph, P, T, R>::type

   180       apply(Graph& g,

   181             typename graph_traits<Graph>::vertex_descriptor src,

   182             typename graph_traits<Graph>::vertex_descriptor sink,

   183             const bgl_named_params<P, T, R>& params,

   184             PredMap pred)

   185       {

   186         typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C;

   187         return edmunds_karp_dispatch2<C>::apply

   188           (g, src, sink, pred, params, get_param(params, vertex_color));

   189       }

   190     };

   191     template<>

   192     struct edmunds_karp_dispatch1<detail::error_property_not_found> {

   194       template <class Graph, class P, class T, class R>

   195       static typename edge_capacity_value<Graph, P, T, R>::type

   196       apply

   197       (Graph& g,

   198        typename graph_traits<Graph>::vertex_descriptor src,

   199        typename graph_traits<Graph>::vertex_descriptor sink,

   200        const bgl_named_params<P, T, R>& params,

   201        detail::error_property_not_found)

   202       {

   203         typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;

   204         typedef typename graph_traits<Graph>::vertices_size_type size_type;

   205         size_type n = is_default_param(get_param(params, vertex_predecessor)) ?

   206           num_vertices(g) : 1;

   207         std::vector<edge_descriptor> pred_vec(n);

   209         typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C;

   210         return edmunds_karp_dispatch2<C>::apply

   211           (g, src, sink,

   212            make_iterator_property_map(pred_vec.begin(), choose_const_pmap

   213                                       (get_param(params, vertex_index),

   214                                        g, vertex_index), pred_vec[0]),

   215            params,

   216            get_param(params, vertex_color));

   217       }

   218     };

   220   } // namespace detail

   222   template <class Graph, class P, class T, class R>

   223   typename detail::edge_capacity_value<Graph, P, T, R>::type

   224   edmunds_karp_max_flow

   225     (Graph& g,

   226      typename graph_traits<Graph>::vertex_descriptor src,

   227      typename graph_traits<Graph>::vertex_descriptor sink,

   228      const bgl_named_params<P, T, R>& params)

   229   {

   230     typedef typename property_value< bgl_named_params<P,T,R>, vertex_predecessor_t>::type Pred;

   231     return detail::edmunds_karp_dispatch1<Pred>::apply

   232       (g, src, sink, params, get_param(params, vertex_predecessor));

   233   }

   235   template <class Graph>

   236   typename property_traits<

   237     typename property_map<Graph, edge_capacity_t>::const_type

   238   >::value_type

   239   edmunds_karp_max_flow

   240     (Graph& g,

   241      typename graph_traits<Graph>::vertex_descriptor src,

   242      typename graph_traits<Graph>::vertex_descriptor sink)

   243   {

   244     bgl_named_params<int, buffer_param_t> params(0);

   245     return edmunds_karp_max_flow(g, src, sink, params);

   246   }

   248 } // namespace boost

   250 #endif // EDMUNDS_KARP_MAX_FLOW_HPP

author	William Roberts <williamr@symbian.org>
	Wed, 31 Mar 2010 12:33:34 +0100
branch	Symbian3
changeset 4	837f303aceeb
permissions	-rw-r--r--