//=======================================================================
|
// 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/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_nonnegative_weights(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_nonnegative_weights_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_nonnegative_weights(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_nonnegative_weights_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_nonnegative_weights(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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights_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_nonnegative_weights(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_nonnegative_weights_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_nonnegative_weights(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_nonnegative_weights(g, s, t, params);
|
}
|
|
} // boost
|
#endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */
|
