1 //=======================================================================
2 // Copyright 2013 University of Warsaw.
3 // Authors: Piotr Wygocki
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 //
11 // This algorithm is described in "Network Flows: Theory, Algorithms, and
12 // Applications"
13 // by Ahuja, Magnanti, Orlin.
14
15 #ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP
16 #define BOOST_GRAPH_CYCLE_CANCELING_HPP
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>
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
29 namespace boost
30 {
31
32 namespace detail
33 {
34
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;
42
43 public:
RecordEdgeMapAndCycleVertex(PredEdgeMap pred,Vertex & v)44 RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex& v)
45 : bellman_visitor< PredRec >(PredRec(pred)), m_v(v), m_pred(pred)
46 {
47 }
48
49 template < typename Graph, typename Edge >
edge_not_minimized(Edge e,const Graph & g) const50 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);
64 }
65
66 private:
67 Vertex& m_v;
68 PredEdgeMap m_pred;
69 };
70
71 } // detail
72
73 template < class Graph, class Pred, class Distance, class Reversed,
74 class ResidualCapacity, class Weight >
cycle_canceling(const Graph & g,Weight weight,Reversed rev,ResidualCapacity residual_capacity,Pred pred,Distance distance)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;
80 ResGraph gres = detail::residual_graph(g, residual_capacity);
81
82 typedef graph_traits< ResGraph > ResGTraits;
83 typedef graph_traits< Graph > GTraits;
84 typedef typename ResGTraits::edge_descriptor edge_descriptor;
85 typedef typename ResGTraits::vertex_descriptor vertex_descriptor;
86
87 typename GTraits::vertices_size_type N = num_vertices(g);
88
89 BGL_FORALL_VERTICES_T(v, g, Graph)
90 {
91 put(pred, v, edge_descriptor());
92 put(distance, v, 0);
93 }
94
95 vertex_descriptor cycleStart;
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 {
101
102 detail::augment(
103 g, cycleStart, cycleStart, pred, residual_capacity, rev);
104
105 BGL_FORALL_VERTICES_T(v, g, Graph)
106 {
107 put(pred, v, edge_descriptor());
108 put(distance, v, 0);
109 }
110 }
111 }
112
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 >
cycle_canceling_dispatch2(const Graph & g,Weight weight,Reversed rev,ResidualCapacity residual_capacity,Pred pred,Distance dist,const bgl_named_params<P,T,R> & params)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 }
125
126 // setting default distance map
127 template < class Graph, class P, class T, class R, class Pred,
128 class ResidualCapacity, class Weight, class Reversed >
cycle_canceling_dispatch2(Graph & g,Weight weight,Reversed rev,ResidualCapacity residual_capacity,Pred pred,param_not_found,const bgl_named_params<P,T,R> & params)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 }
142
143 template < class Graph, class P, class T, class R, class ResidualCapacity,
144 class Weight, class Reversed, class Pred >
cycle_canceling_dispatch1(Graph & g,Weight weight,Reversed rev,ResidualCapacity residual_capacity,Pred pred,const bgl_named_params<P,T,R> & params)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 }
152
153 // setting default predecessors map
154 template < class Graph, class P, class T, class R, class ResidualCapacity,
155 class Weight, class Reversed >
cycle_canceling_dispatch1(Graph & g,Weight weight,Reversed rev,ResidualCapacity residual_capacity,param_not_found,const bgl_named_params<P,T,R> & params)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 }
169
170 } // detail
171
172 template < class Graph, class P, class T, class R >
cycle_canceling(Graph & g,const bgl_named_params<P,T,R> & params)173 void cycle_canceling(Graph& g, const bgl_named_params< P, T, R >& params)
174 {
175 cycle_canceling_dispatch1(g,
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);
181 }
182
cycle_canceling(Graph & g)183 template < class Graph > void cycle_canceling(Graph& g)
184 {
185 bgl_named_params< int, buffer_param_t > params(0);
186 cycle_canceling(g, params);
187 }
188
189 }
190
191 #endif /* BOOST_GRAPH_CYCLE_CANCELING_HPP */
192