63e88f80
 Hu Chunming
提交三方库
|
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
64
65
66
|
//=======================================================================
// 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 */
|
