//=======================================================================
//
//
-//This algorithm is described in "Network Flows: Theory, Algorithms, and Applications"
+// This algorithm is described in "Network Flows: Theory, Algorithms, and
+// Applications"
// by Ahuja, Magnanti, Orlin.
#ifndef BOOST_GRAPH_CYCLE_CANCELING_HPP
#include <boost/graph/detail/augment.hpp>
#include <boost/graph/find_flow_cost.hpp>
-namespace boost {
+namespace boost
+{
+namespace detail
+{
-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;
-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;
+ public:
+ RecordEdgeMapAndCycleVertex(PredEdgeMap pred, Vertex& v)
+ : bellman_visitor< PredRec >(PredRec(pred)), m_v(v), m_pred(pred)
+ {
+ }
- //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;
+ 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);
}
- m_v = source(e, g);
- }
-private:
- Vertex & m_v;
- PredEdgeMap m_pred;
-};
-} //detail
+ 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;
+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 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) {
+ 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)))) {
+ 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);
+ detail::augment(
+ g, cycleStart, cycleStart, pred, residual_capacity, rev);
- BGL_FORALL_VERTICES_T(v, g, Graph) {
+ 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);
+ }
-//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)));
-}
+ // 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);
-}
+ 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);
-}
+ // 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
+} // detail
-template <class Graph, class P, class T, class R>
-void cycle_canceling(Graph &g,
- const bgl_named_params<P, T, R>& params) {
+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);
+ 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);
+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 */
projects / ceph.git / blobdiff