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