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