diff DEPENDENCIES/generic/include/boost/graph/cycle_canceling.hpp @ 16:2665513ce2d3

Add boost headers

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/DEPENDENCIES/generic/include/boost/graph/cycle_canceling.hpp	Tue Aug 05 11:11:38 2014 +0100
@@ -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 */
+