Chris@16: //=======================================================================
Chris@16: // Copyright 2013 University of Warsaw.
Chris@16: // Authors: Piotr Wygocki 
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: //
Chris@16: //
Chris@16: //This algorithm is described in "Network Flows: Theory, Algorithms, and Applications"
Chris@16: // by Ahuja, Magnanti, Orlin.
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP
Chris@16: #define BOOST_GRAPH_CYCLE_CANCELING_HPP 
Chris@16: 
Chris@16: #include <numeric>
Chris@16: 
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/graph_concepts.hpp>
Chris@16: #include <boost/pending/indirect_cmp.hpp>
Chris@16: #include <boost/pending/relaxed_heap.hpp>
Chris@16: #include <boost/graph/bellman_ford_shortest_paths.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: #include <boost/graph/detail/augment.hpp>
Chris@16: #include <boost/graph/find_flow_cost.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <typename PredEdgeMap, typename Vertex>
Chris@16: class RecordEdgeMapAndCycleVertex 
Chris@16:     : public bellman_visitor<edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> > {
Chris@16:         typedef edge_predecessor_recorder<PredEdgeMap, on_edge_relaxed> PredRec;
Chris@16: public:
Chris@16:     RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex & v) : 
Chris@16:         bellman_visitor<PredRec>(PredRec(pred)), m_v(v), m_pred(pred) {}
Chris@16: 
Chris@16:     template <typename Graph, typename Edge>
Chris@16:     void edge_not_minimized(Edge e, const Graph & g) const {
Chris@16:         typename graph_traits<Graph>::vertices_size_type n = num_vertices(g) + 1;
Chris@16: 
Chris@16:         //edge e is not minimized but does not have to be on the negative weight cycle
Chris@16:         //to find vertex on negative wieight cycle we move n+1 times backword in the PredEdgeMap graph.
Chris@16:         while(n > 0) {
Chris@16:             e = get(m_pred, source(e, g));
Chris@16:             --n;
Chris@16:         }
Chris@16:         m_v = source(e, g);
Chris@16:     }
Chris@16: private:
Chris@16:     Vertex & m_v;
Chris@16:     PredEdgeMap m_pred;
Chris@16: };
Chris@16: 
Chris@16: } //detail
Chris@16: 
Chris@16: 
Chris@16: template <class Graph, class Pred, class Distance, class Reversed, class ResidualCapacity, class Weight>
Chris@16: void cycle_canceling(const Graph &g, Weight weight, Reversed rev, ResidualCapacity residual_capacity, Pred pred, Distance distance) {
Chris@16:     typedef filtered_graph<const Graph, is_residual_edge<ResidualCapacity> > ResGraph;
Chris@16:     ResGraph gres = detail::residual_graph(g, residual_capacity);
Chris@16:     
Chris@16:     typedef graph_traits<ResGraph> ResGTraits;
Chris@16:     typedef graph_traits<Graph> GTraits;
Chris@16:     typedef typename ResGTraits::edge_descriptor edge_descriptor;
Chris@16:     typedef typename ResGTraits::vertex_descriptor vertex_descriptor;
Chris@16:     
Chris@16:     typename GTraits::vertices_size_type N = num_vertices(g);
Chris@16:     
Chris@16:     BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:         put(pred, v, edge_descriptor());
Chris@16:         put(distance, v, 0);
Chris@16:     }
Chris@16: 
Chris@16:     vertex_descriptor cycleStart;
Chris@16:     while(!bellman_ford_shortest_paths(gres, N, 
Chris@16:             weight_map(weight).
Chris@16:             distance_map(distance).
Chris@16:             visitor(detail::RecordEdgeMapAndCycleVertex<Pred, vertex_descriptor>(pred, cycleStart)))) {
Chris@16: 
Chris@16:         detail::augment(g, cycleStart, cycleStart, pred, residual_capacity, rev);
Chris@16:         
Chris@16:         BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@16:             put(pred, v, edge_descriptor());
Chris@16:             put(distance, v, 0);
Chris@16:         }
Chris@16:     }
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: //in this namespace argument dispatching takes place
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance>
Chris@16: void cycle_canceling_dispatch2(
Chris@16:         const Graph &g, 
Chris@16:         Weight weight,
Chris@16:         Reversed rev,
Chris@16:         ResidualCapacity residual_capacity,
Chris@16:         Pred pred,
Chris@16:         Distance dist,
Chris@16:         const bgl_named_params<P, T, R>& params) {
Chris@16:     cycle_canceling(g, weight, rev, residual_capacity, pred, dist);
Chris@16: }
Chris@16: 
Chris@16: //setting default distance map
Chris@16: template <class Graph, class P, class T, class R, class Pred, class ResidualCapacity, class Weight, class Reversed>
Chris@16: void cycle_canceling_dispatch2(
Chris@16:         Graph &g, 
Chris@16:         Weight weight,
Chris@16:         Reversed rev,
Chris@16:         ResidualCapacity residual_capacity,
Chris@16:         Pred pred,
Chris@16:         param_not_found,
Chris@16:         const bgl_named_params<P, T, R>& params) {
Chris@16:     typedef typename property_traits<Weight>::value_type D;
Chris@16: 
Chris@16:     std::vector<D> d_map(num_vertices(g));
Chris@16: 
Chris@16:     cycle_canceling(g, weight, rev, residual_capacity, pred, 
Chris@16:                     make_iterator_property_map(d_map.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)));
Chris@16: }
Chris@16: 
Chris@16: template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed, class Pred>
Chris@16: void cycle_canceling_dispatch1(
Chris@16:         Graph &g, 
Chris@16:         Weight weight, 
Chris@16:         Reversed rev,
Chris@16:         ResidualCapacity residual_capacity,
Chris@16:         Pred pred,
Chris@16:         const bgl_named_params<P, T, R>& params) {
Chris@16:     cycle_canceling_dispatch2(g, weight, rev,residual_capacity,  pred, 
Chris@16:                                 get_param(params, vertex_distance), params);
Chris@16: }
Chris@16: 
Chris@16: //setting default predecessors map
Chris@16: template <class Graph, class P, class T, class R, class ResidualCapacity, class Weight, class Reversed>
Chris@16: void cycle_canceling_dispatch1(
Chris@16:         Graph &g, 
Chris@16:         Weight weight, 
Chris@16:         Reversed rev,
Chris@16:         ResidualCapacity residual_capacity,
Chris@16:         param_not_found,
Chris@16:         const bgl_named_params<P, T, R>& params) {
Chris@16:     typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
Chris@16:     std::vector<edge_descriptor> p_map(num_vertices(g));
Chris@16: 
Chris@16:     cycle_canceling_dispatch2(g, weight, rev, residual_capacity,
Chris@16:                               make_iterator_property_map(p_map.begin(), choose_const_pmap(get_param(params, vertex_index), g, vertex_index)),
Chris@16:                                 get_param(params, vertex_distance), params); 
Chris@16: }
Chris@16: 
Chris@16: }//detail
Chris@16: 
Chris@16: template <class Graph, class  P, class T, class R>
Chris@16: void cycle_canceling(Graph &g,
Chris@16:         const bgl_named_params<P, T, R>& params) {
Chris@16:     cycle_canceling_dispatch1(g, 
Chris@16:            choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
Chris@16:            choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
Chris@16:            choose_pmap(get_param(params, edge_residual_capacity), 
Chris@16:                        g, edge_residual_capacity),
Chris@16:            get_param(params, vertex_predecessor), 
Chris@16:            params);
Chris@16: }
Chris@16: 
Chris@16: template <class Graph>
Chris@16: void cycle_canceling(Graph &g) {
Chris@16:     bgl_named_params<int, buffer_param_t> params(0);
Chris@16:     cycle_canceling(g, params);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: #endif /* BOOST_GRAPH_CYCLE_CANCELING_HPP */
Chris@16: