ceph/src/boost/libs/graph/include/boost/graph/detail/augment.hpp

   1 //=======================================================================
   2 // Copyright 2013 University of Warsaw.
   3 // Authors: Piotr Wygocki
   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 BOOST_GRAPH_AUGMENT_HPP
  11 #define BOOST_GRAPH_AUGMENT_HPP
  12
  13 #include <boost/graph/filtered_graph.hpp>
  14
  15 namespace boost {
  16 namespace detail {
  17
  18 template <class Graph, class ResCapMap>
  19 filtered_graph<const Graph, is_residual_edge<ResCapMap> >
  20 residual_graph(const Graph& g, ResCapMap residual_capacity) {
  21     return filtered_graph<const Graph, is_residual_edge<ResCapMap> >
  22         (g, is_residual_edge<ResCapMap>(residual_capacity));
  23 }
  24
  25 template <class Graph, class PredEdgeMap, class ResCapMap,
  26          class RevEdgeMap>
  27 inline void
  28 augment(const Graph& g,
  29         typename graph_traits<Graph>::vertex_descriptor src,
  30         typename graph_traits<Graph>::vertex_descriptor sink,
  31         PredEdgeMap p,
  32         ResCapMap residual_capacity,
  33         RevEdgeMap reverse_edge)
  34 {
  35     typename graph_traits<Graph>::edge_descriptor e;
  36     typename graph_traits<Graph>::vertex_descriptor u;
  37     typedef typename property_traits<ResCapMap>::value_type FlowValue;
  38
  39     // find minimum residual capacity along the augmenting path
  40     FlowValue delta = (std::numeric_limits<FlowValue>::max)();
  41     e = get(p, sink);
  42     do {
  43         BOOST_USING_STD_MIN();
  44         delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
  45         u = source(e, g);
  46         e = get(p, u);
  47     } while (u != src);
  48
  49     // push delta units of flow along the augmenting path
  50     e = get(p, sink);
  51     do {
  52         put(residual_capacity, e, get(residual_capacity, e) - delta);
  53         put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
  54         u = source(e, g);
  55         e = get(p, u);
  56     } while (u != src);
  57 }
  58
  59 } // namespace detail
  60 } //namespace boost
  61
  62 #endif /* BOOST_GRAPH_AUGMENT_HPP */
  63