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