boost/graph/cycle_canceling.hpp

0001 //=======================================================================
0002 // Copyright 2013 University of Warsaw.
0003 // Authors: Piotr Wygocki
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008 //=======================================================================
0009 //
0010 //
0011 // This algorithm is described in "Network Flows: Theory, Algorithms, and
0012 // Applications"
0013 // by Ahuja, Magnanti, Orlin.
0014
0015 #ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP
0016 #define BOOST_GRAPH_CYCLE_CANCELING_HPP
0017
0018 #include <numeric>
0019
0020 #include <boost/property_map/property_map.hpp>
0021 #include <boost/graph/graph_traits.hpp>
0022 #include <boost/graph/graph_concepts.hpp>
0023 #include <boost/pending/indirect_cmp.hpp>
0024 #include <boost/graph/bellman_ford_shortest_paths.hpp>
0025 #include <boost/graph/iteration_macros.hpp>
0026 #include <boost/graph/detail/augment.hpp>
0027 #include <boost/graph/find_flow_cost.hpp>
0028
0029 namespace boost
0030 {
0031
0032 namespace detail
0033 {
0034
0035     template < typename PredEdgeMap, typename Vertex >
0036     class RecordEdgeMapAndCycleVertex
0037     : public bellman_visitor<
0038           edge_predecessor_recorder< PredEdgeMap, on_edge_relaxed > >
0039     {
0040         typedef edge_predecessor_recorder< PredEdgeMap, on_edge_relaxed >
0041             PredRec;
0042
0043     public:
0044         RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex& v)
0045         : bellman_visitor< PredRec >(PredRec(pred)), m_v(v), m_pred(pred)
0046         {
0047         }
0048
0049         template < typename Graph, typename Edge >
0050         void edge_not_minimized(Edge e, const Graph& g) const
0051         {
0052             typename graph_traits< Graph >::vertices_size_type n
0053                 = num_vertices(g) + 1;
0054
0055             // edge e is not minimized but does not have to be on the negative
0056             // weight cycle to find vertex on negative wieight cycle we move n+1
0057             // times backword in the PredEdgeMap graph.
0058             while (n > 0)
0059             {
0060                 e = get(m_pred, source(e, g));
0061                 --n;
0062             }
0063             m_v = source(e, g);
0064         }
0065
0066     private:
0067         Vertex& m_v;
0068         PredEdgeMap m_pred;
0069     };
0070
0071 } // detail
0072
0073 template < class Graph, class Pred, class Distance, class Reversed,
0074     class ResidualCapacity, class Weight >
0075 void cycle_canceling(const Graph& g, Weight weight, Reversed rev,
0076     ResidualCapacity residual_capacity, Pred pred, Distance distance)
0077 {
0078     typedef filtered_graph< const Graph, is_residual_edge< ResidualCapacity > >
0079         ResGraph;
0080     ResGraph gres = detail::residual_graph(g, residual_capacity);
0081
0082     typedef graph_traits< ResGraph > ResGTraits;
0083     typedef graph_traits< Graph > GTraits;
0084     typedef typename ResGTraits::edge_descriptor edge_descriptor;
0085     typedef typename ResGTraits::vertex_descriptor vertex_descriptor;
0086
0087     typename GTraits::vertices_size_type N = num_vertices(g);
0088
0089     BGL_FORALL_VERTICES_T(v, g, Graph)
0090     {
0091         put(pred, v, edge_descriptor());
0092         put(distance, v, 0);
0093     }
0094
0095     vertex_descriptor cycleStart;
0096     while (!bellman_ford_shortest_paths(gres, N,
0097         weight_map(weight).distance_map(distance).visitor(
0098             detail::RecordEdgeMapAndCycleVertex< Pred, vertex_descriptor >(
0099                 pred, cycleStart))))
0100     {
0101
0102         detail::augment(
0103             g, cycleStart, cycleStart, pred, residual_capacity, rev);
0104
0105         BGL_FORALL_VERTICES_T(v, g, Graph)
0106         {
0107             put(pred, v, edge_descriptor());
0108             put(distance, v, 0);
0109         }
0110     }
0111 }
0112
0113 // in this namespace argument dispatching takes place
0114 namespace detail
0115 {
0116
0117     template < class Graph, class P, class T, class R, class ResidualCapacity,
0118         class Weight, class Reversed, class Pred, class Distance >
0119     void cycle_canceling_dispatch2(const Graph& g, Weight weight, Reversed rev,
0120         ResidualCapacity residual_capacity, Pred pred, Distance dist,
0121         const bgl_named_params< P, T, R >& params)
0122     {
0123         cycle_canceling(g, weight, rev, residual_capacity, pred, dist);
0124     }
0125
0126     // setting default distance map
0127     template < class Graph, class P, class T, class R, class Pred,
0128         class ResidualCapacity, class Weight, class Reversed >
0129     void cycle_canceling_dispatch2(Graph& g, Weight weight, Reversed rev,
0130         ResidualCapacity residual_capacity, Pred pred, param_not_found,
0131         const bgl_named_params< P, T, R >& params)
0132     {
0133         typedef typename property_traits< Weight >::value_type D;
0134
0135         std::vector< D > d_map(num_vertices(g));
0136
0137         cycle_canceling(g, weight, rev, residual_capacity, pred,
0138             make_iterator_property_map(d_map.begin(),
0139                 choose_const_pmap(
0140                     get_param(params, vertex_index), g, vertex_index)));
0141     }
0142
0143     template < class Graph, class P, class T, class R, class ResidualCapacity,
0144         class Weight, class Reversed, class Pred >
0145     void cycle_canceling_dispatch1(Graph& g, Weight weight, Reversed rev,
0146         ResidualCapacity residual_capacity, Pred pred,
0147         const bgl_named_params< P, T, R >& params)
0148     {
0149         cycle_canceling_dispatch2(g, weight, rev, residual_capacity, pred,
0150             get_param(params, vertex_distance), params);
0151     }
0152
0153     // setting default predecessors map
0154     template < class Graph, class P, class T, class R, class ResidualCapacity,
0155         class Weight, class Reversed >
0156     void cycle_canceling_dispatch1(Graph& g, Weight weight, Reversed rev,
0157         ResidualCapacity residual_capacity, param_not_found,
0158         const bgl_named_params< P, T, R >& params)
0159     {
0160         typedef typename graph_traits< Graph >::edge_descriptor edge_descriptor;
0161         std::vector< edge_descriptor > p_map(num_vertices(g));
0162
0163         cycle_canceling_dispatch2(g, weight, rev, residual_capacity,
0164             make_iterator_property_map(p_map.begin(),
0165                 choose_const_pmap(
0166                     get_param(params, vertex_index), g, vertex_index)),
0167             get_param(params, vertex_distance), params);
0168     }
0169
0170 } // detail
0171
0172 template < class Graph, class P, class T, class R >
0173 void cycle_canceling(Graph& g, const bgl_named_params< P, T, R >& params)
0174 {
0175     cycle_canceling_dispatch1(g,
0176         choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
0177         choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
0178         choose_pmap(get_param(params, edge_residual_capacity), g,
0179             edge_residual_capacity),
0180         get_param(params, vertex_predecessor), params);
0181 }
0182
0183 template < class Graph > void cycle_canceling(Graph& g)
0184 {
0185     bgl_named_params< int, buffer_param_t > params(0);
0186     cycle_canceling(g, params);
0187 }
0188
0189 }
0190
0191 #endif /* BOOST_GRAPH_CYCLE_CANCELING_HPP */