graph/detail/augment.hpp

0001 //=======================================================================
0002 // Copyright 2013 University of Warsaw.
0003 // Authors: Piotr Wygocki
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009
0010 #ifndef BOOST_GRAPH_AUGMENT_HPP
0011 #define BOOST_GRAPH_AUGMENT_HPP
0012
0013 #include <boost/graph/filtered_graph.hpp>
0014
0015 namespace boost
0016 {
0017 namespace detail
0018 {
0019
0020     template < class Graph, class ResCapMap >
0021     filtered_graph< const Graph, is_residual_edge< ResCapMap > > residual_graph(
0022         const Graph& g, ResCapMap residual_capacity)
0023     {
0024         return filtered_graph< const Graph, is_residual_edge< ResCapMap > >(
0025             g, is_residual_edge< ResCapMap >(residual_capacity));
0026     }
0027
0028     template < class Graph, class PredEdgeMap, class ResCapMap,
0029         class RevEdgeMap >
0030     inline void augment(const Graph& g,
0031         typename graph_traits< Graph >::vertex_descriptor src,
0032         typename graph_traits< Graph >::vertex_descriptor sink, PredEdgeMap p,
0033         ResCapMap residual_capacity, RevEdgeMap reverse_edge)
0034     {
0035         typename graph_traits< Graph >::edge_descriptor e;
0036         typename graph_traits< Graph >::vertex_descriptor u;
0037         typedef typename property_traits< ResCapMap >::value_type FlowValue;
0038
0039         // find minimum residual capacity along the augmenting path
0040         FlowValue delta = (std::numeric_limits< FlowValue >::max)();
0041         e = get(p, sink);
0042         do
0043         {
0044             BOOST_USING_STD_MIN();
0045             delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(
0046                 delta, get(residual_capacity, e));
0047             u = source(e, g);
0048             e = get(p, u);
0049         } while (u != src);
0050
0051         // push delta units of flow along the augmenting path
0052         e = get(p, sink);
0053         do
0054         {
0055             put(residual_capacity, e, get(residual_capacity, e) - delta);
0056             put(residual_capacity, get(reverse_edge, e),
0057                 get(residual_capacity, get(reverse_edge, e)) + delta);
0058             u = source(e, g);
0059             e = get(p, u);
0060         } while (u != src);
0061     }
0062
0063 } // namespace detail
0064 } // namespace boost
0065
0066 #endif /* BOOST_GRAPH_AUGMENT_HPP */