Chris@16: //=======================================================================
Chris@16: // Copyright 2013 University of Warsaw.
Chris@16: // Authors: Piotr Wygocki 
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_AUGMENT_HPP
Chris@16: #define BOOST_GRAPH_AUGMENT_HPP
Chris@16: 
Chris@16: #include <boost/graph/filtered_graph.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <class Graph, class ResCapMap>
Chris@16: filtered_graph<const Graph, is_residual_edge<ResCapMap> >
Chris@16: residual_graph(const Graph& g, ResCapMap residual_capacity) {
Chris@16:     return filtered_graph<const Graph, is_residual_edge<ResCapMap> >
Chris@16:         (g, is_residual_edge<ResCapMap>(residual_capacity));
Chris@16: }
Chris@16: 
Chris@16: template <class Graph, class PredEdgeMap, class ResCapMap,
Chris@16:          class RevEdgeMap>
Chris@16: inline void
Chris@16: augment(const Graph& g, 
Chris@16:         typename graph_traits<Graph>::vertex_descriptor src,
Chris@16:         typename graph_traits<Graph>::vertex_descriptor sink,
Chris@16:         PredEdgeMap p, 
Chris@16:         ResCapMap residual_capacity,
Chris@16:         RevEdgeMap reverse_edge)
Chris@16: {
Chris@16:     typename graph_traits<Graph>::edge_descriptor e;
Chris@16:     typename graph_traits<Graph>::vertex_descriptor u;
Chris@16:     typedef typename property_traits<ResCapMap>::value_type FlowValue;
Chris@16: 
Chris@16:     // find minimum residual capacity along the augmenting path
Chris@16:     FlowValue delta = (std::numeric_limits<FlowValue>::max)();
Chris@16:     e = get(p, sink);
Chris@16:     do {
Chris@16:         BOOST_USING_STD_MIN();
Chris@16:         delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
Chris@16:         u = source(e, g);
Chris@16:         e = get(p, u);
Chris@16:     } while (u != src);
Chris@16: 
Chris@16:     // push delta units of flow along the augmenting path
Chris@16:     e = get(p, sink);
Chris@16:     do {
Chris@16:         put(residual_capacity, e, get(residual_capacity, e) - delta);
Chris@16:         put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
Chris@16:         u = source(e, g);
Chris@16:         e = get(p, u);
Chris@16:     } while (u != src);
Chris@16: }
Chris@16: 
Chris@16: } // namespace detail
Chris@16: } //namespace boost
Chris@16: 
Chris@16: #endif /* BOOST_GRAPH_AUGMENT_HPP */
Chris@16: