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