1 //=======================================================================
2 // Copyright 2013 University of Warsaw.
3 // Authors: Piotr Wygocki
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 //=======================================================================
10 #ifndef BOOST_GRAPH_AUGMENT_HPP
11 #define BOOST_GRAPH_AUGMENT_HPP
13 #include <boost/graph/filtered_graph.hpp>
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));
25 template <class Graph, class PredEdgeMap, class ResCapMap,
28 augment(const Graph& g,
29 typename graph_traits<Graph>::vertex_descriptor src,
30 typename graph_traits<Graph>::vertex_descriptor sink,
32 ResCapMap residual_capacity,
33 RevEdgeMap reverse_edge)
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;
39 // find minimum residual capacity along the augmenting path
40 FlowValue delta = (std::numeric_limits<FlowValue>::max)();
43 BOOST_USING_STD_MIN();
44 delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
49 // push delta units of flow along the augmenting path
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);
62 #endif /* BOOST_GRAPH_AUGMENT_HPP */