|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r85536 - in trunk: boost/graph boost/graph/detail libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2013-08-31 16:09:12
Author: jewillco
Date: 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013)
New Revision: 85536
URL: http://svn.boost.org/trac/boost/changeset/85536
Log:
Added min_cost_max_flow code from Piotr Wygocki
Added:
trunk/boost/graph/cycle_canceling.hpp (contents, props changed)
trunk/boost/graph/detail/augment.hpp (contents, props changed)
trunk/boost/graph/find_flow_cost.hpp (contents, props changed)
trunk/boost/graph/successive_shortest_path.hpp (contents, props changed)
trunk/libs/graph/doc/cycle_canceling.html (contents, props changed)
trunk/libs/graph/doc/find_flow_cost.html (contents, props changed)
trunk/libs/graph/doc/successive_shortest_path.html (contents, props changed)
trunk/libs/graph/example/cycle_canceling_example.cpp (contents, props changed)
trunk/libs/graph/example/successive_shortest_path_example.cpp (contents, props changed)
trunk/libs/graph/test/cycle_canceling_test.cpp (contents, props changed)
trunk/libs/graph/test/min_cost_max_flow_utils.hpp (contents, props changed)
trunk/libs/graph/test/successive_shortest_path_test.cpp (contents, props changed)
Text files modified:
trunk/boost/graph/cycle_canceling.hpp | 181 +++++++++++++++++++++++++++
trunk/boost/graph/detail/augment.hpp | 63 +++++++++
trunk/boost/graph/find_flow_cost.hpp | 52 +++++++
trunk/boost/graph/named_function_params.hpp | 1
trunk/boost/graph/successive_shortest_path.hpp | 261 +++++++++++++++++++++++++++++++++++++++
trunk/libs/graph/doc/cycle_canceling.html | 223 +++++++++++++++++++++++++++++++++
trunk/libs/graph/doc/find_flow_cost.html | 139 +++++++++++++++++++++
trunk/libs/graph/doc/graph_theory_review.html | 3
trunk/libs/graph/doc/successive_shortest_path.html | 264 ++++++++++++++++++++++++++++++++++++++++
trunk/libs/graph/example/Jamfile.v2 | 2
trunk/libs/graph/example/cycle_canceling_example.cpp | 19 ++
trunk/libs/graph/example/successive_shortest_path_example.cpp | 21 +++
trunk/libs/graph/test/Jamfile.v2 | 2
trunk/libs/graph/test/cycle_canceling_test.cpp | 51 +++++++
trunk/libs/graph/test/min_cost_max_flow_utils.hpp | 128 +++++++++++++++++++
trunk/libs/graph/test/successive_shortest_path_test.cpp | 55 ++++++++
16 files changed, 1465 insertions(+), 0 deletions(-)
Added: trunk/boost/graph/cycle_canceling.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/graph/cycle_canceling.hpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -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 tak 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 */
+
Added: trunk/boost/graph/detail/augment.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/graph/detail/augment.hpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,63 @@
+//=======================================================================
+// 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)
+//=======================================================================
+
+#ifndef BOOST_GRAPH_AUGMENT_HPP
+#define BOOST_GRAPH_AUGMENT_HPP
+
+#include <boost/graph/filtered_graph.hpp>
+
+namespace boost {
+namespace detail {
+
+template <class Graph, class ResCapMap>
+filtered_graph<const Graph, is_residual_edge<ResCapMap> >
+residual_graph(const Graph& g, ResCapMap residual_capacity) {
+ return filtered_graph<const Graph, is_residual_edge<ResCapMap> >
+ (g, is_residual_edge<ResCapMap>(residual_capacity));
+}
+
+template <class Graph, class PredEdgeMap, class ResCapMap,
+ class RevEdgeMap>
+inline void
+augment(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor src,
+ typename graph_traits<Graph>::vertex_descriptor sink,
+ PredEdgeMap p,
+ ResCapMap residual_capacity,
+ RevEdgeMap reverse_edge)
+{
+ typename graph_traits<Graph>::edge_descriptor e;
+ typename graph_traits<Graph>::vertex_descriptor u;
+ typedef typename property_traits<ResCapMap>::value_type FlowValue;
+
+ // find minimum residual capacity along the augmenting path
+ FlowValue delta = (std::numeric_limits<FlowValue>::max)();
+ e = get(p, sink);
+ do {
+ BOOST_USING_STD_MIN();
+ delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, get(residual_capacity, e));
+ u = source(e, g);
+ e = get(p, u);
+ } while (u != src);
+
+ // push delta units of flow along the augmenting path
+ e = get(p, sink);
+ do {
+ put(residual_capacity, e, get(residual_capacity, e) - delta);
+ put(residual_capacity, get(reverse_edge, e), get(residual_capacity, get(reverse_edge, e)) + delta);
+ u = source(e, g);
+ e = get(p, u);
+ } while (u != src);
+}
+
+} // namespace detail
+} //namespace boost
+
+#endif /* BOOST_GRAPH_AUGMENT_HPP */
+
Added: trunk/boost/graph/find_flow_cost.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/graph/find_flow_cost.hpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,52 @@
+//=======================================================================
+// 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)
+//=======================================================================
+#ifndef BOOST_GRAPH_FIND_FLOW_COST_HPP
+#define BOOST_GRAPH_FIND_FLOW_COST_HPP
+
+#include <boost/graph/iteration_macros.hpp>
+
+namespace boost {
+
+template<class Graph, class Capacity, class ResidualCapacity, class Weight>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph & g, Capacity capacity, ResidualCapacity residual_capacity, Weight weight) {
+ typedef typename property_traits<typename property_map<Graph, edge_weight_t>::const_type>::value_type Cost;
+
+ Cost cost = 0;
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ if(get(capacity, e) > Cost(0)) {
+ cost += (get(capacity, e) - get(residual_capacity, e)) * get(weight, e);
+ }
+ }
+ return cost;
+}
+
+template <class Graph, class P, class T, class R>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph & g,
+ const bgl_named_params<P, T, R>& params) {
+ return find_flow_cost(g,
+ choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
+ choose_const_pmap(get_param(params, edge_residual_capacity),
+ g, edge_residual_capacity),
+ choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
+}
+
+template <class Graph>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph &g) {
+ bgl_named_params<int, buffer_param_t> params(0);
+ return find_flow_cost(g, params);
+}
+
+
+} //boost
+
+#endif /* BOOST_GRAPH_FIND_FLOW_COST_HPP */
+
Modified: trunk/boost/graph/named_function_params.hpp
==============================================================================
--- trunk/boost/graph/named_function_params.hpp Sat Aug 31 15:54:11 2013 (r85535)
+++ trunk/boost/graph/named_function_params.hpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -64,6 +64,7 @@
BOOST_BGL_ONE_PARAM_CREF(weight_map, edge_weight) \
BOOST_BGL_ONE_PARAM_CREF(weight_map2, edge_weight2) \
BOOST_BGL_ONE_PARAM_CREF(distance_map, vertex_distance) \
+ BOOST_BGL_ONE_PARAM_CREF(distance_map2, vertex_distance2) \
BOOST_BGL_ONE_PARAM_CREF(predecessor_map, vertex_predecessor) \
BOOST_BGL_ONE_PARAM_CREF(rank_map, vertex_rank) \
BOOST_BGL_ONE_PARAM_CREF(root_map, vertex_root) \
Added: trunk/boost/graph/successive_shortest_path.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/boost/graph/successive_shortest_path.hpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,261 @@
+//=======================================================================
+// 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_SUCCESSIVE_SHORTEST_PATH_HPP
+#define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_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/dijkstra_shortest_paths.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/detail/augment.hpp>
+
+namespace boost {
+
+
+namespace detail {
+
+template <class Graph, class Weight, class Distance, class Reversed>
+class MapReducedWeight :
+ public put_get_helper<typename property_traits<Weight>::value_type, MapReducedWeight<Graph, Weight, Distance, Reversed> > {
+ typedef graph_traits<Graph> gtraits;
+public:
+ typedef boost::readable_property_map_tag category;
+ typedef typename property_traits<Weight>::value_type value_type;
+ typedef value_type reference;
+ typedef typename gtraits::edge_descriptor key_type;
+ MapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) :
+ g_(g), weight_(w), distance_(d), rev_(r) {}
+
+ reference operator[](key_type v) const {
+ return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v);
+ }
+private:
+ const Graph & g_;
+ Weight weight_;
+ Distance distance_;
+ Reversed rev_;
+};
+
+template <class Graph, class Weight, class Distance, class Reversed>
+MapReducedWeight<Graph, Weight, Distance, Reversed>
+make_mapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) {
+ return MapReducedWeight<Graph, Weight, Distance, Reversed>(g, w, d, r);
+}
+
+}//detail
+
+
+template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
+void successive_shortest_path(
+ const Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance distance,
+ Distance2 distance_prev) {
+ filtered_graph<const Graph, is_residual_edge<ResidualCapacity> >
+ gres = detail::residual_graph(g, residual_capacity);
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+
+ BGL_FORALL_EDGES_T(e, g, Graph) {
+ put(residual_capacity, e, get(capacity, e));
+ }
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(distance_prev, v, 0);
+ }
+
+ while(true) {
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(pred, v, edge_descriptor());
+ }
+ dijkstra_shortest_paths(gres, s,
+ weight_map(detail::make_mapReducedWeight(gres, weight, distance_prev, rev)).
+ distance_map(distance).
+ vertex_index_map(index).
+ visitor(make_dijkstra_visitor(record_edge_predecessors(pred, on_edge_relaxed()))));
+
+ if(get(pred, t) == edge_descriptor()) {
+ break;
+ }
+
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(distance_prev, v, get(distance_prev, v) + get(distance, v));
+ }
+
+ detail::augment(g, s, t, pred, residual_capacity, rev);
+ }
+}
+
+//in this namespace argument dispatching tak place
+namespace detail {
+
+template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class Distance2, class VertexIndex>
+void successive_shortest_path_dispatch3(
+ const Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance dist,
+ Distance2 dist_pred) {
+ successive_shortest_path(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, dist_pred);
+}
+
+//setting default distance map
+template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
+void successive_shortest_path_dispatch3(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance dist,
+ param_not_found) {
+ typedef typename property_traits<Weight>::value_type D;
+
+ std::vector<D> d_map(num_vertices(g));
+
+ successive_shortest_path(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist,
+ make_iterator_property_map(d_map.begin(), index));
+}
+
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
+void successive_shortest_path_dispatch2(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance dist,
+ const bgl_named_params<P, T, R>& params) {
+ successive_shortest_path_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, get_param(params, vertex_distance2));
+}
+
+//setting default distance map
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
+void successive_shortest_path_dispatch2(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ 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));
+
+ successive_shortest_path_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred,
+ make_iterator_property_map(d_map.begin(), index),
+ get_param(params, vertex_distance2));
+}
+
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
+void successive_shortest_path_dispatch1(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ const bgl_named_params<P, T, R>& params) {
+ successive_shortest_path_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, pred,
+ get_param(params, vertex_distance), params);
+}
+
+//setting default predecessors map
+template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class VertexIndex>
+void successive_shortest_path_dispatch1(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ param_not_found,
+ const bgl_named_params<P, T, R>& params) {
+ typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
+ std::vector<edge_descriptor> pred_vec(num_vertices(g));
+
+ successive_shortest_path_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index,
+ make_iterator_property_map(pred_vec.begin(), index),
+ get_param(params, vertex_distance), params);
+}
+
+}//detail
+
+
+template <class Graph, class P, class T, class R>
+void successive_shortest_path(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ const bgl_named_params<P, T, R>& params) {
+
+ return detail::successive_shortest_path_dispatch1(g, s, t,
+ choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
+ choose_pmap(get_param(params, edge_residual_capacity),
+ g, edge_residual_capacity),
+ choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
+ choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
+ choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
+ get_param(params, vertex_predecessor),
+ params);
+}
+
+template <class Graph>
+void successive_shortest_path(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t) {
+ bgl_named_params<int, buffer_param_t> params(0);
+ successive_shortest_path(g, s, t, params);
+}
+
+
+}//boost
+#endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */
+
Added: trunk/libs/graph/doc/cycle_canceling.html
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/doc/cycle_canceling.html 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,223 @@
+<HTML>
+<!--
+ Copyright (c) Piotr Wygocki 2013
+
+ 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)
+ -->
+<Head>
+<Title>Boost Graph Library: Cycle Canceling for Min Cost Max Flow</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><A NAME="sec:cycle_canceling">
+<TT>cycle_canceling</TT>
+</H1>
+
+<PRE>
+<i>// named parameter version</i>
+template <class Graph, class P, class T, class R>
+void cycle_canceling(
+ Graph &g,
+ const bgl_named_params<P, T, R> & params = <i>all defaults</i>)
+
+<i>// non-named parameter version</i>
+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)
+</PRE>
+
+<P>
+The <tt>cycle_canceling()</tt> function calculates the minimum cost flow of a network with given flow. See Section <a
+href="./graph_theory_review.html#sec:network-flow-algorithms">Network
+Flow Algorithms</a> for a description of maximum flow.
+For given flow values <i> f(u,v)</i> function minimizes flow cost in such a way, that for each <i>v in V</i> the
+ <i> sum<sub> u in V</sub> f(v,u) </i> is preserved. Particularly if the input flow was the maximum flow, the function produces min cost max flow.
+
+
+ The function calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
+<i>E</i>, which are returned in the form of the residual capacity
+<i>r(u,v) = c(u,v) - f(u,v)</i>.
+
+<p>
+There are several special requirements on the input graph and property
+map parameters for this algorithm. First, the directed graph
+<i>G=(V,E)</i> that represents the network must be augmented to
+include the reverse edge for every edge in <i>E</i>. That is, the
+input graph should be <i>G<sub>in</sub> = (V,{E U
+E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
+must map each edge in the original graph to its reverse edge, that is
+<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>.
+The <tt>WeightMap</tt> has to map each edge from <i>E<sup>T</sup></i> to <i>-weight</i> of its reversed edge.
+Note that edges from <i>E</i> can have negative weights.
+<p>
+If weights in the graph are nonnegative, the
+successive_shortest_path()
+might be better choice for min cost max flow.
+
+<p>
+The algorithm is described in <a
+href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
+
+<p>
+In each round algorithm augments the negative cycle (in terms of weight) in the residual graph.
+If there is no negative cycle in the network, the cost is optimized.
+
+<p>
+Note that, although we mention capacity in the problem description, the actual algorithm doesn't have to now it.
+
+<p>
+In order to find the cost of the result flow use:
+find_flow_cost().
+
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/successive_shortest_path.hpp
+
+<P>
+
+<h3>Parameters</h3>
+
+IN: <tt>Graph& g</tt>
+<blockquote>
+ A directed graph. The
+ graph's type must be a model of <a
+ href="./VertexListGraph.html">VertexListGraph</a> and IncidenceGraph For each edge
+ <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
+ be in the graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+
+IN/OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
+<blockquote>
+ This maps edges to their residual capacity. The type must be a model
+ of a mutable <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
+ Map</a>. The key type of the map must be the graph's edge descriptor
+ type.<br>
+ <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
+</blockquote>
+
+IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
+<blockquote>
+ An edge property map that maps every edge <i>(u,v)</i> in the graph
+ to the reverse edge <i>(v,u)</i>. The map must be a model of
+ constant <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue
+ Property Map</a>. The key type of the map must be the graph's edge
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(edge_reverse, g)</tt>
+</blockquote>
+
+IN: <tt>weight_map(WeightMap w)</tt>
+<blockquote>
+ The weight (also know as ``length'' or ``cost'') of each edge in the
+ graph. The <tt>WeightMap</tt> type must be a model of <a
+ href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+ Map</a>. The key type for this property map must be the edge
+ descriptor of the graph. The value type for the weight map must be
+ <i>Addable</i> with the distance map's value type. <br>
+ <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
+</blockquote>
+
+UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
+<blockquote>
+ Use by the algorithm to store augmenting paths. The map must be a
+ model of mutable <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
+ The key type must be the graph's vertex descriptor type and the
+ value type must be the graph's edge descriptor type.<br>
+
+ <b>Default:</b> an <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
+ of edge descriptors of size <tt>num_vertices(g)</tt> and
+ using the <tt>i_map</tt> for the index map.
+</blockquote>
+
+UTIL: <tt>distance_map(DistanceMap d_map)</tt>
+<blockquote>
+ The shortest path weight from the source vertex <tt>s</tt> to each
+ vertex in the graph <tt>g</tt> is recorded in this property map. The
+ shortest path weight is the sum of the edge weights along the
+ shortest path. The type <tt>DistanceMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a>. The vertex descriptor type of the graph needs to
+ be usable as the key type of the distance map.
+
+ <b>Default:</b> <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a
+ <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+ <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
+ map.<br>
+
+</blockquote>
+
+IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
+<blockquote>
+ Maps each vertex of the graph to a unique integer in the range
+ <tt>[0, num_vertices(g))</tt>. This property map is only needed
+ if the default for the distance or predecessor map is used.
+ The vertex index map must be a model of <a
+ href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+ Map</a>. The key type of the map must be the graph's vertex
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(vertex_index, g)</tt>
+ Note: if you use this default, make sure your graph has
+ an internal <tt>vertex_index</tt> property. For example,
+ <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+<h3>Complexity</h3>
+In the integer capacity and weight case, if <i>C</i> is the initial cost of the flow, then the complexity is <i> O(C * |V| * |E|)</i>,
+where <i>O(|E|* |V|)</i> is the complexity of the bellman ford shortest paths algorithm and <i>C</i> is upper bound on number of iteration.
+In many real world cases number of iterations is much smaller than <i>C</i>.
+
+
+<h3>Example</h3>
+
+The program in <a
+href="../example/cycle_canceling_example.cpp"><tt>example/cycle_canceling_example.cpp</tt></a>.
+
+
+<h3>See Also</h3>
+
+successive_shortest_path()<br>
+find_flow_cost().
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2013</TD><TD>
+Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos_at_[hidden]">wygos at mimuw.edu.pl</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
+<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
+ -->
+<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
+ -->
+<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
+ -->
+<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
+ -->
+<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
+ -->
+<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
+ -->
+<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
+ -->
+<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
+p -->
+
Added: trunk/libs/graph/doc/find_flow_cost.html
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/doc/find_flow_cost.html 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,139 @@
+<HTML>
+<!--
+ Copyright (c) Piotr Wygocki 2013
+
+ 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)
+ -->
+<Head>
+<Title>Boost Graph Library: Find Flow Cost</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><A NAME="sec:find_flow_cost">
+<TT>find_flow_cost</TT>
+</H1>
+
+<PRE>
+<i>// named parameter version</i>
+template <class Graph>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph & g,
+ const bgl_named_params<P, T, R> & params = <i>all defaults</i>)
+
+<i>// non-named parameter version</i>
+template<class Graph, class Capacity, class ResidualCapacity, class Weight>
+typename property_traits<typename property_map < Graph, edge_capacity_t >::type>::value_type
+find_flow_cost(const Graph & g, Capacity capacity, ResidualCapacity residual_capacity, Weight weight)
+</PRE>
+
+<P>
+The <tt>find_flow_cost()</tt> function calculates the minimum cost maximum flow value of a network and given flow. See Section <a
+href="./graph_theory_review.html#sec:network-flow-algorithms">Network
+Flow Algorithms</a> for a description of maximum flow.
+The function calculates the cost from the flow values <i>f(u,v)</i> for <i>(u,v)</i> in
+<i>E</i>, which are passed in the form of the residual capacity
+<i>r(u,v) = c(u,v) - f(u,v)</i>.
+
+<p>
+In order to compute the min cost max flow use :
+successive_shortest_path() or
+cycle_canceling().
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/successive_shortest_path.hpp
+
+<P>
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph& g</tt>
+<blockquote>
+ A directed graph. The
+ graph's type must be a model of <a
+ href="./VertexListGraph.html">VertexListGraph</a> and IncidenceGraph For each edge
+ <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
+ be in the graph.
+</blockquote>
+<h3>Named Parameters</h3>
+
+
+IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
+<blockquote>
+ The edge capacity property map. The type must be a model of a
+ constant <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The
+ key type of the map must be the graph's edge descriptor type.<br>
+ <b>Default:</b> <tt>get(edge_capacity, g)</tt>
+</blockquote>
+
+IN: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
+<blockquote>
+ This maps edges to their residual capacity. The type must be a model
+ of a mutable <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
+ Map</a>. The key type of the map must be the graph's edge descriptor
+ type.<br>
+ <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
+</blockquote>
+
+
+IN: <tt>weight_map(WeightMap w_map)</tt>
+<blockquote>
+ The weight or ``cost'' of each edge in the graph.
+ The type <tt>WeightMap</tt> must be a model of
+ Readable Property Map. The edge descriptor type of
+ the graph needs to be usable as the key type for the weight
+ map. The value type for this map must be
+ the same as the value type of the distance map.<br>
+ <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
+
+</blockquote>
+
+<h3>Complexity</h3>
+The complexity is <i> O(|E|)</i>,
+
+<h3>Example</h3>
+
+The function is used in the successive_shortest_path example. The program in <a
+href="../example/successive_shortest_path_example.cpp"><tt>example/successive_shortest_path_example.cpp</tt></a>.
+
+<h3>See Also</h3>
+
+cycle_canceling()<br>
+successive_shortest_path().
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2013</TD><TD>
+Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos_at_[hidden]">wygos at mimuw.edu.pl</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
+<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
+ -->
+<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
+ -->
+<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
+ -->
+<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
+ -->
+<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
+ -->
+<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
+ -->
+<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
+ -->
+<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
+p -->
+
Modified: trunk/libs/graph/doc/graph_theory_review.html
==============================================================================
--- trunk/libs/graph/doc/graph_theory_review.html Sat Aug 31 15:54:11 2013 (r85535)
+++ trunk/libs/graph/doc/graph_theory_review.html 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -552,6 +552,9 @@
The <b><i>maximum flow problem</i></b> is to determine the maximum
possible value for <i>|f|</i> and the corresponding flow values for
every vertex pair in the graph.
+<p>
+The <b><i>minimum cost maximum flow problem</i></b> is to determine the maximum flow which minimizes <i> sum<sub>(u,v) in E</sub>
+cost(u,v) * f(u,v) </i>.
<p>
A flow network is shown in <a href="#fig:max-flow">Figure
Added: trunk/libs/graph/doc/successive_shortest_path.html
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/doc/successive_shortest_path.html 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,264 @@
+<HTML>
+<!--
+ Copyright (c) Piotr Wygocki 2013
+
+ 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)
+ -->
+<Head>
+<Title>Boost Graph Library: Successive Shortest Path for Min Cost Max Flow</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
+ ALINK="#ff0000">
+<IMG SRC="../../../boost.png"
+ ALT="C++ Boost" width="277" height="86">
+
+<BR Clear>
+
+<H1><A NAME="sec:successive_shortest_path">
+<TT>successive_shortest_path</TT>
+</H1>
+
+<PRE>
+<i>// named parameter version</i>
+template <class Graph, class P, class T, class R>
+void successive_shortest_path(
+ Graph &g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ const bgl_named_params<P, T, R> & params = <i>all defaults</i>)
+
+<i>// non-named parameter version</i>
+template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
+void successive_shortest_path(
+ const Graph & g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ typename graph_traits<Graph>::vertex_descriptor t,
+ Capacity capacity,
+ ResidualCapacity residual_capacity,
+ Weight weight,
+ Reversed rev,
+ VertexIndex index,
+ Pred pred,
+ Distance distance,
+ Distance2 distance_prev)
+</PRE>
+
+<P>
+The <tt>successive_shortest_path()</tt> function calculates the minimum cost maximum flow of a network. See Section <a
+href="./graph_theory_review.html#sec:network-flow-algorithms">Network
+Flow Algorithms</a> for a description of maximum flow.
+ The function calculates the flow values <i>f(u,v)</i> for all <i>(u,v)</i> in
+<i>E</i>, which are returned in the form of the residual capacity
+<i>r(u,v) = c(u,v) - f(u,v)</i>.
+
+<p>
+There are several special requirements on the input graph and property
+map parameters for this algorithm. First, the directed graph
+<i>G=(V,E)</i> that represents the network must be augmented to
+include the reverse edge for every edge in <i>E</i>. That is, the
+input graph should be <i>G<sub>in</sub> = (V,{E U
+E<sup>T</sup>})</i>. The <tt>ReverseEdgeMap</tt> argument <tt>rev</tt>
+must map each edge in the original graph to its reverse edge, that is
+<i>(u,v) -> (v,u)</i> for all <i>(u,v)</i> in <i>E</i>. The
+<tt>CapacityEdgeMap</tt> argument <tt>cap</tt> must map each edge in
+<i>E</i> to a positive number, and each edge in <i>E<sup>T</sup></i>
+to 0. The <tt>WeightMap</tt> has to map each edge from <i>E</i> to nonnegative number, and each edge from <i>E<sup>T</sup></i> to <i>-weight</i> of its reversed edge.
+
+<p>
+The algorithm is described in <a
+href="./bibliography.html#ahuja93:_network_flows">Network Flows</a>.
+
+<p>
+This algorithm starts with empty flow and in each round augments the shortest path (in terms of weight) in the residual graph.
+
+<p>
+In order to find the cost of the result flow use:
+find_flow_cost().
+
+<H3>Where Defined</H3>
+
+<P>
+boost/graph/successive_shortest_path.hpp
+
+<P>
+
+<h3>Parameters</h3>
+
+IN: <tt>Graph& g</tt>
+<blockquote>
+ A directed graph. The
+ graph's type must be a model of <a
+ href="./VertexListGraph.html">VertexListGraph</a> and IncidenceGraph For each edge
+ <i>(u,v)</i> in the graph, the reverse edge <i>(v,u)</i> must also
+ be in the graph.
+</blockquote>
+
+IN: <tt>vertex_descriptor s</tt>
+<blockquote>
+ The source vertex for the flow network graph.
+</blockquote>
+
+IN: <tt>vertex_descriptor t</tt>
+<blockquote>
+ The sink vertex for the flow network graph.
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+
+IN: <tt>capacity_map(CapacityEdgeMap cap)</tt>
+<blockquote>
+ The edge capacity property map. The type must be a model of a
+ constant <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>. The
+ key type of the map must be the graph's edge descriptor type.<br>
+ <b>Default:</b> <tt>get(edge_capacity, g)</tt>
+</blockquote>
+
+OUT: <tt>residual_capacity_map(ResidualCapacityEdgeMap res)</tt>
+<blockquote>
+ This maps edges to their residual capacity. The type must be a model
+ of a mutable <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property
+ Map</a>. The key type of the map must be the graph's edge descriptor
+ type.<br>
+ <b>Default:</b> <tt>get(edge_residual_capacity, g)</tt>
+</blockquote>
+
+IN: <tt>reverse_edge_map(ReverseEdgeMap rev)</tt>
+<blockquote>
+ An edge property map that maps every edge <i>(u,v)</i> in the graph
+ to the reverse edge <i>(v,u)</i>. The map must be a model of
+ constant <a href="../../property_map/doc/LvaluePropertyMap.html">Lvalue
+ Property Map</a>. The key type of the map must be the graph's edge
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(edge_reverse, g)</tt>
+</blockquote>
+
+IN: <tt>weight_map(WeightMap w_map)</tt>
+<blockquote>
+ The weight or ``cost'' of each edge in the graph. The weights
+ must all be non-negative, and the algorithm will throw a
+ negative_edge
+ exception if one of the edges is negative.
+ The type <tt>WeightMap</tt> must be a model of
+ Readable Property Map. The edge descriptor type of
+ the graph needs to be usable as the key type for the weight
+ map. The value type for this map must be
+ the same as the value type of the distance map.<br>
+ <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
+
+</blockquote>
+
+UTIL: <tt>predecessor_map(PredEdgeMap pred)</tt>
+<blockquote>
+ Use by the algorithm to store augmenting paths. The map must be a
+ model of mutable <a
+ href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property Map</a>.
+ The key type must be the graph's vertex descriptor type and the
+ value type must be the graph's edge descriptor type.<br>
+
+ <b>Default:</b> an <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a <tt>std::vector</tt>
+ of edge descriptors of size <tt>num_vertices(g)</tt> and
+ using the <tt>i_map</tt> for the index map.
+</blockquote>
+
+UTIL: <tt>distance_map(DistanceMap d_map)</tt>
+<blockquote>
+ The shortest path weight from the source vertex <tt>s</tt> to each
+ vertex in the graph <tt>g</tt> is recorded in this property map. The
+ shortest path weight is the sum of the edge weights along the
+ shortest path. The type <tt>DistanceMap</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a>. The vertex descriptor type of the graph needs to
+ be usable as the key type of the distance map.
+
+ <b>Default:</b> <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a
+ <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+ <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
+ map.<br>
+
+</blockquote>
+
+UTIL: <tt>distance_map2(DistanceMap2 d_map2)</tt>
+<blockquote>
+ The shortest path computation in iteration nr <i>k</i> uses distances computed in iteration <i>k</i>.
+ The type <tt>DistanceMap2</tt> must be a model of <a
+ href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
+ Property Map</a>. The vertex descriptor type of the graph needs to
+ be usable as the key type of the distance map.
+
+ <b>Default:</b> <a
+ href="../../property_map/doc/iterator_property_map.html">
+ <tt>iterator_property_map</tt></a> created from a
+ <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+ <tt>num_vertices(g)</tt> and using the <tt>i_map</tt> for the index
+ map.<br>
+
+</blockquote>
+
+IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
+<blockquote>
+ Maps each vertex of the graph to a unique integer in the range
+ <tt>[0, num_vertices(g))</tt>. This property map is only needed
+ if the default for the distance or distance2 or predecessor map is used.
+ The vertex index map must be a model of <a
+ href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+ Map</a>. The key type of the map must be the graph's vertex
+ descriptor type.<br>
+ <b>Default:</b> <tt>get(vertex_index, g)</tt>
+ Note: if you use this default, make sure your graph has
+ an internal <tt>vertex_index</tt> property. For example,
+ <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+
+<h3>Complexity</h3>
+In the integer capacity case, if <i>U</i> is the value of the max flow, then the complexity is <i> O(U * (|E| + |V|*log|V|))</i>,
+where <i>O(|E| + |V|*log|V|)</i> is the complexity of the dijkstra algorithm and <i>U</i> is upper bound on number of iteration.
+In many real world cases number of iterations is much smaller than <i>U</i>.
+
+
+<h3>Example</h3>
+
+The program in <a
+href="../example/successive_shortest_path_example.cpp"><tt>example/successive_shortest_path_example.cpp</tt></a>.
+
+<h3>See Also</h3>
+
+cycle_canceling()<br>
+find_flow_cost().
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright © 2013</TD><TD>
+Piotr Wygocki, University of Warsaw (<A HREF="mailto:wygos_at_[hidden]">wygos at mimuw.edu.pl</A>)
+</TD></TR></TABLE>
+
+</BODY>
+</HTML>
+<!-- LocalWords: HTML Siek Edmonds BGCOLOR ffffff ee VLINK ALINK ff IMG SRC
+ -->
+<!-- LocalWords: gif ALT BR sec edmonds karp TT DIV CELLPADDING TR TD PRE lt
+ -->
+<!-- LocalWords: typename VertexListGraph CapacityEdgeMap ReverseEdgeMap gt
+ -->
+<!-- LocalWords: ResidualCapacityEdgeMap VertexIndexMap src rev ColorMap pred
+ -->
+<!-- LocalWords: PredEdgeMap tt href html hpp ul li nbsp br LvaluePropertyMap
+ -->
+<!-- LocalWords: num ColorValue DIMACS cpp pre config iostream dimacs int std
+ -->
+<!-- LocalWords: namespace vecS directedS cout endl iter ei HR valign nowrap
+ -->
+<!-- LocalWords: jeremy siek htm Univ mailto jsiek lsc edu
+p -->
+
Modified: trunk/libs/graph/example/Jamfile.v2
==============================================================================
--- trunk/libs/graph/example/Jamfile.v2 Sat Aug 31 15:54:11 2013 (r85535)
+++ trunk/libs/graph/example/Jamfile.v2 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -52,4 +52,6 @@
exe sloan_ordering : sloan_ordering.cpp ;
exe hawick_circuits : hawick_circuits.cpp ;
exe edge_coloring : edge_coloring.cpp ;
+exe successive_shortest_path_example : successive_shortest_path_example.cpp ;
+exe cycle_canceling_example : cycle_canceling_example.cpp ;
Added: trunk/libs/graph/example/cycle_canceling_example.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/example/cycle_canceling_example.cpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,19 @@
+#include <boost/graph/cycle_canceling.hpp>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
+
+#include "../test/min_cost_max_flow_utils.hpp"
+
+
+int main() {
+ unsigned s,t;
+ boost::SampleGraph::Graph g
+ = boost::SampleGraph::getSampleGraph(s, t);
+
+ boost::edmonds_karp_max_flow(g, s, t);
+ boost::cycle_canceling(g);
+
+ int cost = boost::find_flow_cost(g);
+ assert(cost == 29);
+ return 0;
+}
+
Added: trunk/libs/graph/example/successive_shortest_path_example.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/example/successive_shortest_path_example.cpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,21 @@
+#include <boost/graph/successive_shortest_path.hpp>
+#include <boost/graph/find_flow_cost.hpp>
+
+#include "../test/min_cost_max_flow_utils.hpp"
+
+
+int main() {
+ unsigned s,t;
+ boost::SampleGraph::Graph g
+ = boost::SampleGraph::getSampleGraph(s, t);
+
+ boost::successive_shortest_path(g, s, t);
+
+ int cost = boost::find_flow_cost(g);
+ assert(cost == 29);
+
+ return 0;
+}
+
+
+
Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2 Sat Aug 31 15:54:11 2013 (r85535)
+++ trunk/libs/graph/test/Jamfile.v2 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -128,6 +128,8 @@
[ compile filtered_graph_properties_dijkstra.cpp ]
[ run vf2_sub_graph_iso_test.cpp ]
[ run hawick_circuits.cpp ]
+ [ run successive_shortest_path_test.cpp ../../test/build//boost_unit_test_framework/<link>static ]
+ [ run cycle_canceling_test.cpp ../../test/build//boost_unit_test_framework/<link>static ]
;
# Run SDB tests only when -sSDB= is set.
Added: trunk/libs/graph/test/cycle_canceling_test.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/test/cycle_canceling_test.cpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,51 @@
+#define BOOST_TEST_MODULE cycle_canceling_test
+
+#include <boost/test/unit_test.hpp>
+
+#include <boost/graph/cycle_canceling.hpp>
+#include <boost/graph/edmonds_karp_max_flow.hpp>
+
+#include "min_cost_max_flow_utils.hpp"
+
+
+BOOST_AUTO_TEST_CASE(cycle_canceling_def_test) {
+ unsigned s,t;
+ boost::SampleGraph::Graph g
+ = boost::SampleGraph::getSampleGraph(s, t);
+
+ boost::edmonds_karp_max_flow(g, s, t);
+ boost::cycle_canceling(g);
+
+ int cost = boost::find_flow_cost(g);
+ BOOST_CHECK_EQUAL(cost, 29);
+}
+
+BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
+ unsigned s,t;
+ boost::SampleGraph::Graph g
+ = boost::SampleGraph::getSampleGraph2(s, t);
+
+ boost::edmonds_karp_max_flow(g, s, t);
+ boost::cycle_canceling(g);
+
+ int cost = boost::find_flow_cost(g);
+ BOOST_CHECK_EQUAL(cost, 7);
+}
+
+BOOST_AUTO_TEST_CASE(cycle_canceling_test) {
+ unsigned s,t;
+ typedef boost::SampleGraph::Graph Graph;
+ Graph g = boost::SampleGraph::getSampleGraph(s, t);
+
+ int N = num_vertices(g);
+ std::vector<int> dist(N);
+ typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
+ std::vector<edge_descriptor> pred(N);
+
+ boost::edmonds_karp_max_flow(g, s, t);
+ boost::cycle_canceling(g, boost::distance_map(&dist[0]).predecessor_map(&pred[0]).vertex_index_map(boost::identity_property_map()));
+
+ int cost = boost::find_flow_cost(g);
+ BOOST_CHECK_EQUAL(cost, 29);
+}
+
Added: trunk/libs/graph/test/min_cost_max_flow_utils.hpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/test/min_cost_max_flow_utils.hpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,128 @@
+/**
+ * @file sample_graph_undirected.hpp
+ * @brief
+ * @author Piotr Wygocki
+ * @version 1.0
+ * @date 2013-06-17
+ */
+#ifndef SAMPLE_GRAPH_UNDIRECTED_HPP
+#define SAMPLE_GRAPH_UNDIRECTED_HPP
+
+#include <boost/graph/adjacency_list.hpp>
+
+
+namespace boost {
+struct SampleGraph {
+ typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
+
+ typedef adjacency_list < listS, vecS, directedS, no_property,
+ property < edge_capacity_t, long,
+ property < edge_residual_capacity_t, long,
+ property < edge_reverse_t, Traits::edge_descriptor,
+ property <edge_weight_t, long>
+ >
+ >
+ > > Graph;
+ typedef property_map < Graph, edge_capacity_t >::type Capacity;
+ typedef property_map < Graph, edge_residual_capacity_t >::type ResidualCapacity;
+ typedef property_map < Graph, edge_weight_t >::type Weight;
+
+
+ template <typename Graph, typename Weight, typename Capacity, typename Reversed, typename ResidualCapacity>
+ class EdgeAdder {
+ public:
+ EdgeAdder(Graph & g, Weight & w, Capacity & c, Reversed & rev, ResidualCapacity & residualCapacity)
+ : m_g(g), m_w(w), m_cap(c), m_resCap(residualCapacity), m_rev(rev) {}
+ void addEdge(int v, int w, int weight, int capacity) {
+ Traits::edge_descriptor e,f;
+ e = add(v, w, weight, capacity);
+ f = add(w, v, -weight, 0);
+ m_rev[e] = f;
+ m_rev[f] = e;
+ }
+ private:
+ Traits::edge_descriptor add(int v, int w, int weight, int capacity) {
+ bool b;
+ Traits::edge_descriptor e;
+ boost::tie(e, b) = add_edge(v, w, m_g);
+ assert(b);
+ m_cap[e] = capacity;
+ m_w[e] = weight;
+ return e;
+ }
+ Graph & m_g;
+ Weight & m_w;
+ Capacity & m_cap;
+ ResidualCapacity & m_resCap;
+ Reversed & m_rev;
+ };
+
+
+ static Graph getSampleGraph(unsigned & s, unsigned & t) {
+ const boost::graph_traits<Graph>::vertices_size_type N(6);
+ typedef property_map < Graph, edge_reverse_t >::type Reversed;
+
+ Graph g(N);
+ Capacity capacity = get(edge_capacity, g);
+ Reversed rev = get(edge_reverse, g);
+ ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
+ Weight weight = get(edge_weight, g);
+
+ s = 0;
+ t = 5;
+
+ EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity>
+ ea(g, weight, capacity, rev, residual_capacity);
+
+ ea.addEdge(0, 1, 4 ,2);
+ ea.addEdge(0, 2, 2 ,2);
+
+ ea.addEdge(1, 3, 2 ,2);
+ ea.addEdge(1, 4, 1 ,1);
+ ea.addEdge(2, 3, 1 ,1);
+ ea.addEdge(2, 4, 1 ,1);
+
+ ea.addEdge(3, 5, 4 ,20);
+ ea.addEdge(4, 5, 2 ,20);
+
+ return g;
+ }
+
+ static Graph getSampleGraph2(unsigned & s, unsigned & t) {
+ const boost::graph_traits<Graph>::vertices_size_type N(5);
+ typedef property_map < Graph, edge_reverse_t >::type Reversed;
+
+ Graph g(N);
+ Capacity capacity = get(edge_capacity, g);
+ Reversed rev = get(edge_reverse, g);
+ ResidualCapacity residual_capacity = get(edge_residual_capacity, g);
+ Weight weight = get(edge_weight, g);
+
+ s = 0;
+ t = 4;
+
+ EdgeAdder<Graph, Weight, Capacity, Reversed, ResidualCapacity>
+ ea(g, weight, capacity, rev, residual_capacity);
+
+ ea.addEdge(0, 1, 4 ,2);
+ ea.addEdge(0, 2, 2 ,2);
+ ea.addEdge(1, 2, 2 ,2);
+ ea.addEdge(2, 3, 1 ,1);
+ ea.addEdge(2, 4, 1 ,1);
+ ea.addEdge(3, 4, 1 ,1);
+
+
+ ea.addEdge(1, 0, 2 ,2);
+ ea.addEdge(2, 0, 1 ,1);
+ ea.addEdge(2, 1, 5 ,2);
+ ea.addEdge(3, 2, 1 ,1);
+ ea.addEdge(4, 2, 2 ,2);
+ ea.addEdge(4, 3, 1 ,3);
+
+ return g;
+ }
+};
+} //boost
+
+#endif /* SAMPLE_GRAPH_UNDIRECTED_HPP */
+
Added: trunk/libs/graph/test/successive_shortest_path_test.cpp
==============================================================================
--- /dev/null 00:00:00 1970 (empty, because file is newly added)
+++ trunk/libs/graph/test/successive_shortest_path_test.cpp 2013-08-31 16:09:11 EDT (Sat, 31 Aug 2013) (r85536)
@@ -0,0 +1,55 @@
+#define BOOST_TEST_MODULE successive_shortest_path_test
+
+#include <boost/test/unit_test.hpp>
+
+#include <boost/graph/successive_shortest_path.hpp>
+#include <boost/graph/find_flow_cost.hpp>
+
+#include "min_cost_max_flow_utils.hpp"
+
+
+BOOST_AUTO_TEST_CASE(path_augmentation_def_test) {
+ unsigned s,t;
+ boost::SampleGraph::Graph g
+ = boost::SampleGraph::getSampleGraph(s, t);
+
+ boost::successive_shortest_path(g, s, t);
+
+ int cost = boost::find_flow_cost(g);
+ BOOST_CHECK_EQUAL(cost, 29);
+}
+
+BOOST_AUTO_TEST_CASE(path_augmentation_def_test2) {
+ unsigned s,t;
+ boost::SampleGraph::Graph g
+ = boost::SampleGraph::getSampleGraph2(s, t);
+
+ boost::successive_shortest_path(g, s, t);
+
+ int cost = boost::find_flow_cost(g);
+ BOOST_CHECK_EQUAL(cost, 7);
+}
+
+BOOST_AUTO_TEST_CASE(path_augmentation_test) {
+ unsigned s,t;
+ typedef boost::SampleGraph::Graph Graph;
+ Graph g = boost::SampleGraph::getSampleGraph(s, t);
+
+ int N = boost::num_vertices(g);
+ std::vector<int> dist(N);
+ std::vector<int> dist_prev(N);
+ typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
+ std::vector<edge_descriptor> pred(N);
+
+
+ boost::successive_shortest_path(g, s, t,
+ boost::distance_map(&dist[0]).
+ predecessor_map(&pred[0]).
+ distance_map2(&dist_prev[0]).
+ vertex_index_map(boost::identity_property_map()));
+
+ int cost = boost::find_flow_cost(g);
+ BOOST_CHECK_EQUAL(cost, 29);
+}
+
+
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk