]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> > | |
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 | |
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 |