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
29namespace boost {
30
31
32namespace detail {
33
34template <typename PredEdgeMap, typename Vertex>
35class RecordEdgeMapAndCycleVertex
36 : public bellman_visitor<edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> > {
37 typedef edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> PredRec;
38public:
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 }
54private:
55 Vertex & m_v;
56 PredEdgeMap m_pred;
57};
58
59} //detail
60
61
62template <class Graph, class Pred, class Distance, class Reversed, class ResidualCapacity, class Weight>
63void 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
96namespace detail {
97
98template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance>
99void 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
111template <class Graph, class P, class T, class R, class Pred, class ResidualCapacity, class Weight, class Reversed>
112void 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
128template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred>
129void 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
141template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed>
142void 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
159template <class Graph, class P, class T, class R>
160void 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
171template <class Graph>
172void 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

source code of boost/boost/graph/cycle_canceling.hpp