1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
//=======================================================================
// 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 */
|