1//=======================================================================
2// Copyright 2000 University of Notre Dame.
3// Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
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 EDMONDS_KARP_MAX_FLOW_HPP
11#define EDMONDS_KARP_MAX_FLOW_HPP
12
13#include <boost/config.hpp>
14#include <vector>
15#include <algorithm> // for std::min and std::max
16#include <boost/config.hpp>
17#include <boost/pending/queue.hpp>
18#include <boost/property_map/property_map.hpp>
19#include <boost/graph/graph_traits.hpp>
20#include <boost/graph/properties.hpp>
21#include <boost/graph/filtered_graph.hpp>
22#include <boost/graph/breadth_first_search.hpp>
23
24namespace boost {
25
26 // The "labeling" algorithm from "Network Flows" by Ahuja, Magnanti,
27 // Orlin. I think this is the same as or very similar to the original
28 // Edmonds-Karp algorithm. This solves the maximum flow problem.
29
30 namespace detail {
31
32 template <class Graph, class ResCapMap>
33 filtered_graph<Graph, is_residual_edge<ResCapMap> >
34 residual_graph(Graph& g, ResCapMap residual_capacity) {
35 return filtered_graph<Graph, is_residual_edge<ResCapMap> >
36 (g, is_residual_edge<ResCapMap>(residual_capacity));
37 }
38
39 template <class Graph, class PredEdgeMap, class ResCapMap,
40 class RevEdgeMap>
41 inline void
42 augment(Graph& g,
43 typename graph_traits<Graph>::vertex_descriptor src,
44 typename graph_traits<Graph>::vertex_descriptor sink,
45 PredEdgeMap p,
46 ResCapMap residual_capacity,
47 RevEdgeMap reverse_edge)
48 {
49 typename graph_traits<Graph>::edge_descriptor e;
50 typename graph_traits<Graph>::vertex_descriptor u;
51 typedef typename property_traits<ResCapMap>::value_type FlowValue;
52
53 // find minimum residual capacity along the augmenting path
54 FlowValue delta = (std::numeric_limits<FlowValue>::max)();
55 e = get(p, sink);
56 do {
57 BOOST_USING_STD_MIN();
58 delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
59 u = source(e, g);
60 e = get(p, u);
61 } while (u != src);
62
63 // push delta units of flow along the augmenting path
64 e = get(p, sink);
65 do {
66 put(residual_capacity, e, get(residual_capacity, e) - delta);
67 put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
68 u = source(e, g);
69 e = get(p, u);
70 } while (u != src);
71 }
72
73 } // namespace detail
74
75 template <class Graph,
76 class CapacityEdgeMap, class ResidualCapacityEdgeMap,
77 class ReverseEdgeMap, class ColorMap, class PredEdgeMap>
78 typename property_traits<CapacityEdgeMap>::value_type
79 edmonds_karp_max_flow
80 (Graph& g,
81 typename graph_traits<Graph>::vertex_descriptor src,
82 typename graph_traits<Graph>::vertex_descriptor sink,
83 CapacityEdgeMap cap,
84 ResidualCapacityEdgeMap res,
85 ReverseEdgeMap rev,
86 ColorMap color,
87 PredEdgeMap pred)
88 {
89 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
90 typedef typename property_traits<ColorMap>::value_type ColorValue;
91 typedef color_traits<ColorValue> Color;
92
93 typename graph_traits<Graph>::vertex_iterator u_iter, u_end;
94 typename graph_traits<Graph>::out_edge_iterator ei, e_end;
95 for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
96 for (boost::tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
97 put(res, *ei, get(cap, *ei));
98
99 put(color, sink, Color::gray());
100 while (get(color, sink) != Color::white()) {
101 boost::queue<vertex_t> Q;
102 breadth_first_search
103 (detail::residual_graph(g, res), src, Q,
104 make_bfs_visitor(record_edge_predecessors(pred, on_tree_edge())),
105 color);
106 if (get(color, sink) != Color::white())
107 detail::augment(g, src, sink, pred, res, rev);
108 } // while
109
110 typename property_traits<CapacityEdgeMap>::value_type flow = 0;
111 for (boost::tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei)
112 flow += (get(cap, *ei) - get(res, *ei));
113 return flow;
114 } // edmonds_karp_max_flow()
115
116 namespace detail {
117 //-------------------------------------------------------------------------
118 // Handle default for color property map
119
120 // use of class here is a VC++ workaround
121 template <class ColorMap>
122 struct edmonds_karp_dispatch2 {
123 template <class Graph, class PredMap, class P, class T, class R>
124 static typename edge_capacity_value<Graph, P, T, R>::type
125 apply
126 (Graph& g,
127 typename graph_traits<Graph>::vertex_descriptor src,
128 typename graph_traits<Graph>::vertex_descriptor sink,
129 PredMap pred,
130 const bgl_named_params<P, T, R>& params,
131 ColorMap color)
132 {
133 return edmonds_karp_max_flow
134 (g, src, sink,
135 choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
136 choose_pmap(get_param(params, edge_residual_capacity),
137 g, edge_residual_capacity),
138 choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
139 color, pred);
140 }
141 };
142 template<>
143 struct edmonds_karp_dispatch2<param_not_found> {
144 template <class Graph, class PredMap, class P, class T, class R>
145 static typename edge_capacity_value<Graph, P, T, R>::type
146 apply
147 (Graph& g,
148 typename graph_traits<Graph>::vertex_descriptor src,
149 typename graph_traits<Graph>::vertex_descriptor sink,
150 PredMap pred,
151 const bgl_named_params<P, T, R>& params,
152 param_not_found)
153 {
154 typedef typename graph_traits<Graph>::vertices_size_type size_type;
155 size_type n = is_default_param(get_param(params, vertex_color)) ?
156 num_vertices(g) : 1;
157 std::vector<default_color_type> color_vec(n);
158 return edmonds_karp_max_flow
159 (g, src, sink,
160 choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
161 choose_pmap(get_param(params, edge_residual_capacity),
162 g, edge_residual_capacity),
163 choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
164 make_iterator_property_map(color_vec.begin(), choose_const_pmap
165 (get_param(params, vertex_index),
166 g, vertex_index), color_vec[0]),
167 pred);
168 }
169 };
170
171 //-------------------------------------------------------------------------
172 // Handle default for predecessor property map
173
174 // use of class here is a VC++ workaround
175 template <class PredMap>
176 struct edmonds_karp_dispatch1 {
177 template <class Graph, class P, class T, class R>
178 static typename edge_capacity_value<Graph, P, T, R>::type
179 apply(Graph& g,
180 typename graph_traits<Graph>::vertex_descriptor src,
181 typename graph_traits<Graph>::vertex_descriptor sink,
182 const bgl_named_params<P, T, R>& params,
183 PredMap pred)
184 {
185 typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C;
186 return edmonds_karp_dispatch2<C>::apply
187 (g, src, sink, pred, params, get_param(params, vertex_color));
188 }
189 };
190 template<>
191 struct edmonds_karp_dispatch1<param_not_found> {
192
193 template <class Graph, class P, class T, class R>
194 static typename edge_capacity_value<Graph, P, T, R>::type
195 apply
196 (Graph& g,
197 typename graph_traits<Graph>::vertex_descriptor src,
198 typename graph_traits<Graph>::vertex_descriptor sink,
199 const bgl_named_params<P, T, R>& params,
200 param_not_found)
201 {
202 typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
203 typedef typename graph_traits<Graph>::vertices_size_type size_type;
204 size_type n = is_default_param(get_param(params, vertex_predecessor)) ?
205 num_vertices(g) : 1;
206 std::vector<edge_descriptor> pred_vec(n);
207
208 typedef typename get_param_type< vertex_color_t, bgl_named_params<P,T,R> >::type C;
209 return edmonds_karp_dispatch2<C>::apply
210 (g, src, sink,
211 make_iterator_property_map(pred_vec.begin(), choose_const_pmap
212 (get_param(params, vertex_index),
213 g, vertex_index), pred_vec[0]),
214 params,
215 get_param(params, vertex_color));
216 }
217 };
218
219 } // namespace detail
220
221 template <class Graph, class P, class T, class R>
222 typename detail::edge_capacity_value<Graph, P, T, R>::type
223 edmonds_karp_max_flow
224 (Graph& g,
225 typename graph_traits<Graph>::vertex_descriptor src,
226 typename graph_traits<Graph>::vertex_descriptor sink,
227 const bgl_named_params<P, T, R>& params)
228 {
229 typedef typename get_param_type< vertex_predecessor_t, bgl_named_params<P,T,R> >::type Pred;
230 return detail::edmonds_karp_dispatch1<Pred>::apply
231 (g, src, sink, params, get_param(params, vertex_predecessor));
232 }
233
234 template <class Graph>
235 typename property_traits<
236 typename property_map<Graph, edge_capacity_t>::const_type
237 >::value_type
238 edmonds_karp_max_flow
239 (Graph& g,
240 typename graph_traits<Graph>::vertex_descriptor src,
241 typename graph_traits<Graph>::vertex_descriptor sink)
242 {
243 bgl_named_params<int, buffer_param_t> params(0);
244 return edmonds_karp_max_flow(g, src, sink, params);
245 }
246
247} // namespace boost
248
249#endif // EDMONDS_KARP_MAX_FLOW_HPP
250

source code of boost/boost/graph/edmonds_karp_max_flow.hpp