Edit: /usr/include/boost/graph/successive_shortest_path_nonnegative_weights.hpp (10413B)
//=======================================================================
// 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
#include
#include
#include
#include
#include
#include
#include
#include
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 */