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> >
residual_graph(const Graph & g,ResCapMap residual_capacity)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
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)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
64