epoc32/include/stdapis/boost/graph/edmunds_karp_max_flow.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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 //=======================================================================
     9 
    10 #ifndef EDMUNDS_KARP_MAX_FLOW_HPP
    11 #define EDMUNDS_KARP_MAX_FLOW_HPP
    12 
    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>
    23 
    24 namespace boost {
    25 
    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.
    29 
    30   namespace detail {
    31 
    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     }
    38 
    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;
    52 
    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);
    62 
    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     }
    72 
    73   } // namespace detail
    74 
    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;
    92     
    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];
    98     
    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
   109     
   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()
   115   
   116   namespace detail {
   117     //-------------------------------------------------------------------------
   118     // Handle default for color property map
   119 
   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     };
   171 
   172     //-------------------------------------------------------------------------
   173     // Handle default for predecessor property map
   174 
   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> {
   193 
   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);
   208         
   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     };
   219     
   220   } // namespace detail
   221 
   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   }
   234 
   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   }
   247 
   248 } // namespace boost
   249 
   250 #endif // EDMUNDS_KARP_MAX_FLOW_HPP