]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | //======================================================================= |
2 | // Copyright 2013 University of Warsaw. | |
92f5a8d4 | 3 | // Authors: Piotr Wygocki |
7c673cae FG |
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 | // | |
f67539c2 TL |
11 | // This algorithm is described in "Network Flows: Theory, Algorithms, and |
12 | // Applications" | |
7c673cae FG |
13 | // by Ahuja, Magnanti, Orlin. |
14 | ||
15 | #ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP | |
92f5a8d4 | 16 | #define BOOST_GRAPH_CYCLE_CANCELING_HPP |
7c673cae FG |
17 | |
18 | #include <numeric> | |
19 | ||
20 | #include <boost/property_map/property_map.hpp> | |
21 | #include <boost/graph/graph_traits.hpp> | |
22 | #include <boost/graph/graph_concepts.hpp> | |
23 | #include <boost/pending/indirect_cmp.hpp> | |
7c673cae FG |
24 | #include <boost/graph/bellman_ford_shortest_paths.hpp> |
25 | #include <boost/graph/iteration_macros.hpp> | |
26 | #include <boost/graph/detail/augment.hpp> | |
27 | #include <boost/graph/find_flow_cost.hpp> | |
28 | ||
f67539c2 TL |
29 | namespace boost |
30 | { | |
7c673cae | 31 | |
f67539c2 TL |
32 | namespace detail |
33 | { | |
7c673cae | 34 | |
f67539c2 TL |
35 | template < typename PredEdgeMap, typename Vertex > |
36 | class RecordEdgeMapAndCycleVertex | |
37 | : public bellman_visitor< | |
38 | edge_predecessor_recorder< PredEdgeMap, on_edge_relaxed > > | |
39 | { | |
40 | typedef edge_predecessor_recorder< PredEdgeMap, on_edge_relaxed > | |
41 | PredRec; | |
7c673cae | 42 | |
f67539c2 TL |
43 | public: |
44 | RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex& v) | |
45 | : bellman_visitor< PredRec >(PredRec(pred)), m_v(v), m_pred(pred) | |
46 | { | |
47 | } | |
7c673cae | 48 | |
f67539c2 TL |
49 | template < typename Graph, typename Edge > |
50 | void edge_not_minimized(Edge e, const Graph& g) const | |
51 | { | |
52 | typename graph_traits< Graph >::vertices_size_type n | |
53 | = num_vertices(g) + 1; | |
54 | ||
55 | // edge e is not minimized but does not have to be on the negative | |
56 | // weight cycle to find vertex on negative wieight cycle we move n+1 | |
57 | // times backword in the PredEdgeMap graph. | |
58 | while (n > 0) | |
59 | { | |
60 | e = get(m_pred, source(e, g)); | |
61 | --n; | |
62 | } | |
63 | m_v = source(e, g); | |
7c673cae | 64 | } |
7c673cae | 65 | |
f67539c2 TL |
66 | private: |
67 | Vertex& m_v; | |
68 | PredEdgeMap m_pred; | |
69 | }; | |
7c673cae | 70 | |
f67539c2 | 71 | } // detail |
7c673cae | 72 | |
f67539c2 TL |
73 | template < class Graph, class Pred, class Distance, class Reversed, |
74 | class ResidualCapacity, class Weight > | |
75 | void cycle_canceling(const Graph& g, Weight weight, Reversed rev, | |
76 | ResidualCapacity residual_capacity, Pred pred, Distance distance) | |
77 | { | |
78 | typedef filtered_graph< const Graph, is_residual_edge< ResidualCapacity > > | |
79 | ResGraph; | |
7c673cae | 80 | ResGraph gres = detail::residual_graph(g, residual_capacity); |
92f5a8d4 | 81 | |
f67539c2 TL |
82 | typedef graph_traits< ResGraph > ResGTraits; |
83 | typedef graph_traits< Graph > GTraits; | |
7c673cae FG |
84 | typedef typename ResGTraits::edge_descriptor edge_descriptor; |
85 | typedef typename ResGTraits::vertex_descriptor vertex_descriptor; | |
92f5a8d4 | 86 | |
7c673cae | 87 | typename GTraits::vertices_size_type N = num_vertices(g); |
92f5a8d4 | 88 | |
f67539c2 TL |
89 | BGL_FORALL_VERTICES_T(v, g, Graph) |
90 | { | |
7c673cae FG |
91 | put(pred, v, edge_descriptor()); |
92 | put(distance, v, 0); | |
93 | } | |
94 | ||
95 | vertex_descriptor cycleStart; | |
f67539c2 TL |
96 | while (!bellman_ford_shortest_paths(gres, N, |
97 | weight_map(weight).distance_map(distance).visitor( | |
98 | detail::RecordEdgeMapAndCycleVertex< Pred, vertex_descriptor >( | |
99 | pred, cycleStart)))) | |
100 | { | |
7c673cae | 101 | |
f67539c2 TL |
102 | detail::augment( |
103 | g, cycleStart, cycleStart, pred, residual_capacity, rev); | |
92f5a8d4 | 104 | |
f67539c2 TL |
105 | BGL_FORALL_VERTICES_T(v, g, Graph) |
106 | { | |
7c673cae FG |
107 | put(pred, v, edge_descriptor()); |
108 | put(distance, v, 0); | |
109 | } | |
110 | } | |
111 | } | |
112 | ||
f67539c2 TL |
113 | // in this namespace argument dispatching takes place |
114 | namespace detail | |
115 | { | |
116 | ||
117 | template < class Graph, class P, class T, class R, class ResidualCapacity, | |
118 | class Weight, class Reversed, class Pred, class Distance > | |
119 | void cycle_canceling_dispatch2(const Graph& g, Weight weight, Reversed rev, | |
120 | ResidualCapacity residual_capacity, Pred pred, Distance dist, | |
121 | const bgl_named_params< P, T, R >& params) | |
122 | { | |
123 | cycle_canceling(g, weight, rev, residual_capacity, pred, dist); | |
124 | } | |
7c673cae | 125 | |
f67539c2 TL |
126 | // setting default distance map |
127 | template < class Graph, class P, class T, class R, class Pred, | |
128 | class ResidualCapacity, class Weight, class Reversed > | |
129 | void cycle_canceling_dispatch2(Graph& g, Weight weight, Reversed rev, | |
130 | ResidualCapacity residual_capacity, Pred pred, param_not_found, | |
131 | const bgl_named_params< P, T, R >& params) | |
132 | { | |
133 | typedef typename property_traits< Weight >::value_type D; | |
134 | ||
135 | std::vector< D > d_map(num_vertices(g)); | |
136 | ||
137 | cycle_canceling(g, weight, rev, residual_capacity, pred, | |
138 | make_iterator_property_map(d_map.begin(), | |
139 | choose_const_pmap( | |
140 | get_param(params, vertex_index), g, vertex_index))); | |
141 | } | |
7c673cae | 142 | |
f67539c2 TL |
143 | template < class Graph, class P, class T, class R, class ResidualCapacity, |
144 | class Weight, class Reversed, class Pred > | |
145 | void cycle_canceling_dispatch1(Graph& g, Weight weight, Reversed rev, | |
146 | ResidualCapacity residual_capacity, Pred pred, | |
147 | const bgl_named_params< P, T, R >& params) | |
148 | { | |
149 | cycle_canceling_dispatch2(g, weight, rev, residual_capacity, pred, | |
150 | get_param(params, vertex_distance), params); | |
151 | } | |
7c673cae | 152 | |
f67539c2 TL |
153 | // setting default predecessors map |
154 | template < class Graph, class P, class T, class R, class ResidualCapacity, | |
155 | class Weight, class Reversed > | |
156 | void cycle_canceling_dispatch1(Graph& g, Weight weight, Reversed rev, | |
157 | ResidualCapacity residual_capacity, param_not_found, | |
158 | const bgl_named_params< P, T, R >& params) | |
159 | { | |
160 | typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor; | |
161 | std::vector< edge_descriptor > p_map(num_vertices(g)); | |
162 | ||
163 | cycle_canceling_dispatch2(g, weight, rev, residual_capacity, | |
164 | make_iterator_property_map(p_map.begin(), | |
165 | choose_const_pmap( | |
166 | get_param(params, vertex_index), g, vertex_index)), | |
167 | get_param(params, vertex_distance), params); | |
168 | } | |
7c673cae | 169 | |
f67539c2 | 170 | } // detail |
7c673cae | 171 | |
f67539c2 TL |
172 | template < class Graph, class P, class T, class R > |
173 | void cycle_canceling(Graph& g, const bgl_named_params< P, T, R >& params) | |
174 | { | |
92f5a8d4 | 175 | cycle_canceling_dispatch1(g, |
f67539c2 TL |
176 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), |
177 | choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse), | |
178 | choose_pmap(get_param(params, edge_residual_capacity), g, | |
179 | edge_residual_capacity), | |
180 | get_param(params, vertex_predecessor), params); | |
7c673cae FG |
181 | } |
182 | ||
f67539c2 TL |
183 | template < class Graph > void cycle_canceling(Graph& g) |
184 | { | |
185 | bgl_named_params< int, buffer_param_t > params(0); | |
7c673cae FG |
186 | cycle_canceling(g, params); |
187 | } | |
188 | ||
7c673cae FG |
189 | } |
190 | ||
191 | #endif /* BOOST_GRAPH_CYCLE_CANCELING_HPP */ |