diff options
Diffstat (limited to 'boost/graph/cycle_canceling.hpp')
| -rw-r--r-- | boost/graph/cycle_canceling.hpp | 181 |
1 files changed, 181 insertions, 0 deletions
diff --git a/boost/graph/cycle_canceling.hpp b/boost/graph/cycle_canceling.hpp new file mode 100644 index 0000000000..46a4b864c8 --- /dev/null +++ b/boost/graph/cycle_canceling.hpp @@ -0,0 +1,181 @@ +//======================================================================= +// 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 */ + |