]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2013 University of Warsaw. | |
f67539c2 | 3 | // Authors: Piotr Wygocki |
7c673cae FG |
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 | ||
f67539c2 | 15 | namespace boost |
7c673cae | 16 | { |
f67539c2 TL |
17 | namespace detail |
18 | { | |
19 | ||
20 | template < class Graph, class ResCapMap > | |
21 | filtered_graph< const Graph, is_residual_edge< ResCapMap > > residual_graph( | |
22 | const Graph& g, ResCapMap residual_capacity) | |
23 | { | |
24 | return filtered_graph< const Graph, is_residual_edge< ResCapMap > >( | |
25 | g, is_residual_edge< ResCapMap >(residual_capacity)); | |
26 | } | |
27 | ||
28 | template < class Graph, class PredEdgeMap, class ResCapMap, | |
29 | class RevEdgeMap > | |
30 | inline void augment(const Graph& g, | |
31 | typename graph_traits< Graph >::vertex_descriptor src, | |
32 | typename graph_traits< Graph >::vertex_descriptor sink, PredEdgeMap p, | |
33 | ResCapMap residual_capacity, 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 | { | |
44 | BOOST_USING_STD_MIN(); | |
45 | delta = min BOOST_PREVENT_MACRO_SUBSTITUTION( | |
46 | delta, get(residual_capacity, e)); | |
47 | u = source(e, g); | |
48 | e = get(p, u); | |
49 | } while (u != src); | |
50 | ||
51 | // push delta units of flow along the augmenting path | |
52 | e = get(p, sink); | |
53 | do | |
54 | { | |
55 | put(residual_capacity, e, get(residual_capacity, e) - delta); | |
56 | put(residual_capacity, get(reverse_edge, e), | |
57 | get(residual_capacity, get(reverse_edge, e)) + delta); | |
58 | u = source(e, g); | |
59 | e = get(p, u); | |
60 | } while (u != src); | |
61 | } | |
7c673cae FG |
62 | |
63 | } // namespace detail | |
f67539c2 | 64 | } // namespace boost |
7c673cae FG |
65 | |
66 | #endif /* BOOST_GRAPH_AUGMENT_HPP */ |