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 | |
24 | namespace 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 | |