Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / edmunds_karp_max_flow.hpp
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 EDMUNDS_KARP_MAX_FLOW_HPP
11 #define EDMUNDS_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.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   // Edmunds-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 = p[sink];
56       do {
57         BOOST_USING_STD_MIN();
58         delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[e]);
59         u = source(e, g);
60         e = p[u];
61       } while (u != src);
62
63       // push delta units of flow along the augmenting path
64       e = p[sink];
65       do {
66         residual_capacity[e] -= delta;
67         residual_capacity[reverse_edge[e]] += delta;
68         u = source(e, g);
69         e = 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   edmunds_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 (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)
97         res[*ei] = cap[*ei];
98     
99     color[sink] = Color::gray();
100     while (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 (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 (tie(ei, e_end) = out_edges(src, g); ei != e_end; ++ei)
112       flow += (cap[*ei] - res[*ei]);
113     return flow;
114   } // edmunds_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 edmunds_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 edmunds_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 edmunds_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
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        detail::error_property_not_found)
153       {
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)) ?
157           num_vertices(g) : 1;
158         std::vector<default_color_type> color_vec(n);
159         return edmunds_karp_max_flow
160           (g, src, sink, 
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]),
168            pred);
169       }
170     };
171
172     //-------------------------------------------------------------------------
173     // Handle default for predecessor property map
174
175     // use of class here is a VC++ workaround
176     template <class PredMap>
177     struct edmunds_karp_dispatch1 {
178       template <class Graph, class P, class T, class R>
179       static typename edge_capacity_value<Graph, P, T, R>::type
180       apply(Graph& g,
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,
184             PredMap pred)
185       {
186         typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C;
187         return edmunds_karp_dispatch2<C>::apply
188           (g, src, sink, pred, params, get_param(params, vertex_color));
189       }
190     };
191     template<>
192     struct edmunds_karp_dispatch1<detail::error_property_not_found> {
193
194       template <class Graph, class P, class T, class R>
195       static typename edge_capacity_value<Graph, P, T, R>::type
196       apply
197       (Graph& g,
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)
202       {
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)) ?
206           num_vertices(g) : 1;
207         std::vector<edge_descriptor> pred_vec(n);
208         
209         typedef typename property_value< bgl_named_params<P,T,R>, vertex_color_t>::type C;
210         return edmunds_karp_dispatch2<C>::apply
211           (g, src, sink, 
212            make_iterator_property_map(pred_vec.begin(), choose_const_pmap
213                                       (get_param(params, vertex_index),
214                                        g, vertex_index), pred_vec[0]),
215            params, 
216            get_param(params, vertex_color));
217       }
218     };
219     
220   } // namespace detail
221
222   template <class Graph, class P, class T, class R>
223   typename detail::edge_capacity_value<Graph, P, T, R>::type
224   edmunds_karp_max_flow
225     (Graph& g,
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)
229   {
230     typedef typename property_value< bgl_named_params<P,T,R>, vertex_predecessor_t>::type Pred;
231     return detail::edmunds_karp_dispatch1<Pred>::apply
232       (g, src, sink, params, get_param(params, vertex_predecessor));
233   }
234
235   template <class Graph>
236   typename property_traits<
237     typename property_map<Graph, edge_capacity_t>::const_type
238   >::value_type
239   edmunds_karp_max_flow
240     (Graph& g,
241      typename graph_traits<Graph>::vertex_descriptor src,
242      typename graph_traits<Graph>::vertex_descriptor sink)
243   {
244     bgl_named_params<int, buffer_param_t> params(0);
245     return edmunds_karp_max_flow(g, src, sink, params);
246   }
247
248 } // namespace boost
249
250 #endif // EDMUNDS_KARP_MAX_FLOW_HPP