boost/boost/graph/detail/augment.hpp

//=======================================================================
// Copyright 2013 University of Warsaw.
// Authors: Piotr Wygocki 
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#ifndef BOOST_GRAPH_AUGMENT_HPP
#define BOOST_GRAPH_AUGMENT_HPP

#include <boost/graph/filtered_graph.hpp>

namespace boost {
namespace detail {

template <class Graph, class ResCapMap>
filtered_graph<const Graph, is_residual_edge<ResCapMap> >
residual_graph(const Graph& g, ResCapMap residual_capacity) {
    return filtered_graph<const Graph, is_residual_edge<ResCapMap> >
        (g, is_residual_edge<ResCapMap>(residual_capacity));
}

template <class Graph, class PredEdgeMap, class ResCapMap,
         class RevEdgeMap>
inline void
augment(const Graph& g, 
        typename graph_traits<Graph>::vertex_descriptor src,
        typename graph_traits<Graph>::vertex_descriptor sink,
        PredEdgeMap p, 
        ResCapMap residual_capacity,
        RevEdgeMap reverse_edge)
{
    typename graph_traits<Graph>::edge_descriptor e;
    typename graph_traits<Graph>::vertex_descriptor u;
    typedef typename property_traits<ResCapMap>::value_type FlowValue;

    // find minimum residual capacity along the augmenting path
    FlowValue delta = (std::numeric_limits<FlowValue>::max)();
    e = get(p, sink);
    do {
        BOOST_USING_STD_MIN();
        delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
        u = source(e, g);
        e = get(p, u);
    } while (u != src);

    // push delta units of flow along the augmenting path
    e = get(p, sink);
    do {
        put(residual_capacity, e, get(residual_capacity, e) - delta);
        put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
        u = source(e, g);
        e = get(p, u);
    } while (u != src);
}

} // namespace detail
} //namespace boost

#endif /* BOOST_GRAPH_AUGMENT_HPP */