1 //=======================================================================
2 // Copyright 2000 University of Notre Dame.
3 // Authors: Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
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 //=======================================================================
10 #ifndef EDMONDS_KARP_MAX_FLOW_HPP
11 #define EDMONDS_KARP_MAX_FLOW_HPP
13 #include <boost/config.hpp>
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>
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.
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
));
39 template <class Graph
, class PredEdgeMap
, class ResCapMap
,
43 typename graph_traits
<Graph
>::vertex_descriptor src
,
44 typename graph_traits
<Graph
>::vertex_descriptor sink
,
46 ResCapMap residual_capacity
,
47 RevEdgeMap reverse_edge
)
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
;
53 // find minimum residual capacity along the augmenting path
54 FlowValue delta
= (std::numeric_limits
<FlowValue
>::max
)();
57 BOOST_USING_STD_MIN();
58 delta
= min
BOOST_PREVENT_MACRO_SUBSTITUTION(delta
, residual_capacity
[e
]);
63 // push delta units of flow along the augmenting path
66 residual_capacity
[e
] -= delta
;
67 residual_capacity
[reverse_edge
[e
]] += delta
;
75 template <class Graph
,
76 class CapacityEdgeMap
, class ResidualCapacityEdgeMap
,
77 class ReverseEdgeMap
, class ColorMap
, class PredEdgeMap
>
78 typename property_traits
<CapacityEdgeMap
>::value_type
81 typename graph_traits
<Graph
>::vertex_descriptor src
,
82 typename graph_traits
<Graph
>::vertex_descriptor sink
,
84 ResidualCapacityEdgeMap res
,
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
;
93 typename graph_traits
<Graph
>::vertex_iterator u_iter
, u_end
;
94 typename graph_traits
<Graph
>::out_edge_iterator ei
, e_end
;
95 for (tie(u_iter
, u_end
) = vertices(g
); u_iter
!= u_end
; ++u_iter
)
96 for (tie(ei
, e_end
) = out_edges(*u_iter
, g
); ei
!= e_end
; ++ei
)
99 color
[sink
] = Color::gray();
100 while (color
[sink
] != Color::white()) {
101 boost::queue
<vertex_t
> Q
;
103 (detail::residual_graph(g
, res
), src
, Q
,
104 make_bfs_visitor(record_edge_predecessors(pred
, on_tree_edge())),
106 if (color
[sink
] != Color::white())
107 detail::augment(g
, src
, sink
, pred
, res
, rev
);
110 typename property_traits
<CapacityEdgeMap
>::value_type flow
= 0;
111 for (tie(ei
, e_end
) = out_edges(src
, g
); ei
!= e_end
; ++ei
)
112 flow
+= (cap
[*ei
] - res
[*ei
]);
114 } // edmonds_karp_max_flow()
117 //-------------------------------------------------------------------------
118 // Handle default for color property map
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
127 typename graph_traits
<Graph
>::vertex_descriptor src
,
128 typename graph_traits
<Graph
>::vertex_descriptor sink
,
130 const bgl_named_params
<P
, T
, R
>& params
,
133 return edmonds_karp_max_flow
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
),
143 struct edmonds_karp_dispatch2
<detail::error_property_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
148 typename graph_traits
<Graph
>::vertex_descriptor src
,
149 typename graph_traits
<Graph
>::vertex_descriptor sink
,
151 const bgl_named_params
<P
, T
, R
>& params
,
152 detail::error_property_not_found
)
154 typedef typename graph_traits
<Graph
>::edge_descriptor edge_descriptor
;
155 typedef typename graph_traits
<Graph
>::vertices_size_type size_type
;
156 size_type n
= is_default_param(get_param(params
, vertex_color
)) ?
158 std::vector
<default_color_type
> color_vec(n
);
159 return edmonds_karp_max_flow
161 choose_const_pmap(get_param(params
, edge_capacity
), g
, edge_capacity
),
162 choose_pmap(get_param(params
, edge_residual_capacity
),
163 g
, edge_residual_capacity
),
164 choose_const_pmap(get_param(params
, edge_reverse
), g
, edge_reverse
),
165 make_iterator_property_map(color_vec
.begin(), choose_const_pmap
166 (get_param(params
, vertex_index
),
167 g
, vertex_index
), color_vec
[0]),
172 //-------------------------------------------------------------------------
173 // Handle default for predecessor property map
175 // use of class here is a VC++ workaround
176 template <class PredMap
>
177 struct edmonds_karp_dispatch1
{
178 template <class Graph
, class P
, class T
, class R
>
179 static typename edge_capacity_value
<Graph
, P
, T
, R
>::type
181 typename graph_traits
<Graph
>::vertex_descriptor src
,
182 typename graph_traits
<Graph
>::vertex_descriptor sink
,
183 const bgl_named_params
<P
, T
, R
>& params
,
186 typedef typename property_value
< bgl_named_params
<P
,T
,R
>, vertex_color_t
>::type C
;
187 return edmonds_karp_dispatch2
<C
>::apply
188 (g
, src
, sink
, pred
, params
, get_param(params
, vertex_color
));
192 struct edmonds_karp_dispatch1
<detail::error_property_not_found
> {
194 template <class Graph
, class P
, class T
, class R
>
195 static typename edge_capacity_value
<Graph
, P
, T
, R
>::type
198 typename graph_traits
<Graph
>::vertex_descriptor src
,
199 typename graph_traits
<Graph
>::vertex_descriptor sink
,
200 const bgl_named_params
<P
, T
, R
>& params
,
201 detail::error_property_not_found
)
203 typedef typename graph_traits
<Graph
>::edge_descriptor edge_descriptor
;
204 typedef typename graph_traits
<Graph
>::vertices_size_type size_type
;
205 size_type n
= is_default_param(get_param(params
, vertex_predecessor
)) ?
207 std::vector
<edge_descriptor
> pred_vec(n
);
209 typedef typename property_value
< bgl_named_params
<P
,T
,R
>, vertex_color_t
>::type C
;
210 return edmonds_karp_dispatch2
<C
>::apply
212 make_iterator_property_map(pred_vec
.begin(), choose_const_pmap
213 (get_param(params
, vertex_index
),
214 g
, vertex_index
), pred_vec
[0]),
216 get_param(params
, vertex_color
));
220 } // namespace detail
222 template <class Graph
, class P
, class T
, class R
>
223 typename
detail::edge_capacity_value
<Graph
, P
, T
, R
>::type
224 edmonds_karp_max_flow
226 typename graph_traits
<Graph
>::vertex_descriptor src
,
227 typename graph_traits
<Graph
>::vertex_descriptor sink
,
228 const bgl_named_params
<P
, T
, R
>& params
)
230 typedef typename property_value
< bgl_named_params
<P
,T
,R
>, vertex_predecessor_t
>::type Pred
;
231 return detail::edmonds_karp_dispatch1
<Pred
>::apply
232 (g
, src
, sink
, params
, get_param(params
, vertex_predecessor
));
235 template <class Graph
>
236 typename property_traits
<
237 typename property_map
<Graph
, edge_capacity_t
>::const_type
239 edmonds_karp_max_flow
241 typename graph_traits
<Graph
>::vertex_descriptor src
,
242 typename graph_traits
<Graph
>::vertex_descriptor sink
)
244 bgl_named_params
<int, buffer_param_t
> params(0);
245 return edmonds_karp_max_flow(g
, src
, sink
, params
);
250 #endif // EDMONDS_KARP_MAX_FLOW_HPP