[ceph.git] / ceph / src / boost / boost / graph / successive_shortest_path_nonnegative_weights.hpp

//=======================================================================
// 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 */
Commit	Line	Data
7c673cae FG	1	//=======================================================================
7c673cae FG	2	// Copyright 2013 University of Warsaw.
92f5a8d4	3	// Authors: Piotr Wygocki
7c673cae FG	4	//
	5	// Distributed under the Boost Software License, Version 1.0. (See
	6	// accompanying file LICENSE_1_0.txt or copy at
	7	// http://www.boost.org/LICENSE_1_0.txt)
	8	//=======================================================================
	9	//
	10	//This algorithm is described in "Network Flows: Theory, Algorithms, and Applications"
	11	// by Ahuja, Magnanti, Orlin.
	12
	13	#ifndef BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
92f5a8d4	14	#define BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP
7c673cae FG	15
	16	#include <numeric>
	17
	18	#include <boost/property_map/property_map.hpp>
	19	#include <boost/graph/graph_traits.hpp>
	20	#include <boost/graph/graph_concepts.hpp>
	21	#include <boost/pending/indirect_cmp.hpp>
7c673cae FG	22	#include <boost/graph/dijkstra_shortest_paths.hpp>
	23	#include <boost/graph/properties.hpp>
	24	#include <boost/graph/iteration_macros.hpp>
	25	#include <boost/graph/detail/augment.hpp>
	26
	27	namespace boost {
	28
	29
	30	namespace detail {
92f5a8d4	31
7c673cae	32	template <class Graph, class Weight, class Distance, class Reversed>
92f5a8d4	33	class MapReducedWeight :
7c673cae FG	34	public put_get_helper<typename property_traits<Weight>::value_type, MapReducedWeight<Graph, Weight, Distance, Reversed> > {
	35	typedef graph_traits<Graph> gtraits;
	36	public:
	37	typedef boost::readable_property_map_tag category;
	38	typedef typename property_traits<Weight>::value_type value_type;
	39	typedef value_type reference;
	40	typedef typename gtraits::edge_descriptor key_type;
92f5a8d4	41	MapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) :
7c673cae FG	42	g_(g), weight_(w), distance_(d), rev_(r) {}
	43
	44	reference operator[](key_type v) const {
92f5a8d4	45	return get(distance_, source(v, g_)) - get(distance_,target(v, g_)) + get(weight_, v);
7c673cae FG	46	}
	47	private:
	48	const Graph & g_;
	49	Weight weight_;
	50	Distance distance_;
	51	Reversed rev_;
	52	};
	53
	54	template <class Graph, class Weight, class Distance, class Reversed>
92f5a8d4	55	MapReducedWeight<Graph, Weight, Distance, Reversed>
7c673cae FG	56	make_mapReducedWeight(const Graph & g, Weight w, Distance d, Reversed r) {
	57	return MapReducedWeight<Graph, Weight, Distance, Reversed>(g, w, d, r);
	58	}
	59
	60	}//detail
	61
	62
	63	template <class Graph, class Capacity, class ResidualCapacity, class Reversed, class Pred, class Weight, class Distance, class Distance2, class VertexIndex>
	64	void successive_shortest_path_nonnegative_weights(
92f5a8d4 TL	65	const Graph &g,
92f5a8d4 TL	66	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	67	typename graph_traits<Graph>::vertex_descriptor t,
	68	Capacity capacity,
	69	ResidualCapacity residual_capacity,
92f5a8d4	70	Weight weight,
7c673cae FG	71	Reversed rev,
7c673cae FG	72	VertexIndex index,
92f5a8d4	73	Pred pred,
7c673cae FG	74	Distance distance,
	75	Distance2 distance_prev) {
	76	filtered_graph<const Graph, is_residual_edge<ResidualCapacity> >
	77	gres = detail::residual_graph(g, residual_capacity);
	78	typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
92f5a8d4	79
7c673cae FG	80	BGL_FORALL_EDGES_T(e, g, Graph) {
	81	put(residual_capacity, e, get(capacity, e));
	82	}
	83
	84	BGL_FORALL_VERTICES_T(v, g, Graph) {
	85	put(distance_prev, v, 0);
	86	}
	87
	88	while(true) {
	89	BGL_FORALL_VERTICES_T(v, g, Graph) {
	90	put(pred, v, edge_descriptor());
	91	}
92f5a8d4	92	dijkstra_shortest_paths(gres, s,
7c673cae FG	93	weight_map(detail::make_mapReducedWeight(gres, weight, distance_prev, rev)).
	94	distance_map(distance).
	95	vertex_index_map(index).
	96	visitor(make_dijkstra_visitor(record_edge_predecessors(pred, on_edge_relaxed()))));
	97
	98	if(get(pred, t) == edge_descriptor()) {
	99	break;
	100	}
	101
	102	BGL_FORALL_VERTICES_T(v, g, Graph) {
	103	put(distance_prev, v, get(distance_prev, v) + get(distance, v));
	104	}
	105
	106	detail::augment(g, s, t, pred, residual_capacity, rev);
	107	}
	108	}
	109
	110	//in this namespace argument dispatching tak place
	111	namespace detail {
	112
	113	template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class Distance2, class VertexIndex>
	114	void successive_shortest_path_nonnegative_weights_dispatch3(
92f5a8d4 TL	115	const Graph &g,
92f5a8d4 TL	116	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	117	typename graph_traits<Graph>::vertex_descriptor t,
	118	Capacity capacity,
	119	ResidualCapacity residual_capacity,
	120	Weight weight,
	121	Reversed rev,
	122	VertexIndex index,
	123	Pred pred,
	124	Distance dist,
	125	Distance2 dist_pred) {
	126	successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, dist_pred);
	127	}
	128
	129	//setting default distance map
	130	template <class Graph, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
	131	void successive_shortest_path_nonnegative_weights_dispatch3(
92f5a8d4 TL	132	Graph &g,
92f5a8d4 TL	133	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	134	typename graph_traits<Graph>::vertex_descriptor t,
	135	Capacity capacity,
	136	ResidualCapacity residual_capacity,
	137	Weight weight,
	138	Reversed rev,
	139	VertexIndex index,
	140	Pred pred,
	141	Distance dist,
	142	param_not_found) {
	143	typedef typename property_traits<Weight>::value_type D;
	144
	145	std::vector<D> d_map(num_vertices(g));
	146
	147	successive_shortest_path_nonnegative_weights(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist,
	148	make_iterator_property_map(d_map.begin(), index));
	149	}
	150
	151	template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class Distance, class VertexIndex>
	152	void successive_shortest_path_nonnegative_weights_dispatch2(
92f5a8d4 TL	153	Graph &g,
92f5a8d4 TL	154	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	155	typename graph_traits<Graph>::vertex_descriptor t,
	156	Capacity capacity,
	157	ResidualCapacity residual_capacity,
	158	Weight weight,
	159	Reversed rev,
	160	VertexIndex index,
	161	Pred pred,
	162	Distance dist,
	163	const bgl_named_params<P, T, R>& params) {
	164	successive_shortest_path_nonnegative_weights_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred, dist, get_param(params, vertex_distance2));
	165	}
	166
	167	//setting default distance map
	168	template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
	169	void successive_shortest_path_nonnegative_weights_dispatch2(
92f5a8d4 TL	170	Graph &g,
92f5a8d4 TL	171	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	172	typename graph_traits<Graph>::vertex_descriptor t,
	173	Capacity capacity,
	174	ResidualCapacity residual_capacity,
	175	Weight weight,
	176	Reversed rev,
	177	VertexIndex index,
	178	Pred pred,
92f5a8d4	179	param_not_found,
7c673cae FG	180	const bgl_named_params<P, T, R>& params) {
	181	typedef typename property_traits<Weight>::value_type D;
	182
	183	std::vector<D> d_map(num_vertices(g));
	184
	185	successive_shortest_path_nonnegative_weights_dispatch3(g, s, t, capacity, residual_capacity, weight, rev, index, pred,
	186	make_iterator_property_map(d_map.begin(), index),
	187	get_param(params, vertex_distance2));
	188	}
	189
	190	template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class Pred, class VertexIndex>
	191	void successive_shortest_path_nonnegative_weights_dispatch1(
92f5a8d4 TL	192	Graph &g,
92f5a8d4 TL	193	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	194	typename graph_traits<Graph>::vertex_descriptor t,
	195	Capacity capacity,
	196	ResidualCapacity residual_capacity,
92f5a8d4	197	Weight weight,
7c673cae FG	198	Reversed rev,
	199	VertexIndex index,
	200	Pred pred,
	201	const bgl_named_params<P, T, R>& params) {
	202	successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index, pred,
	203	get_param(params, vertex_distance), params);
	204	}
	205
	206	//setting default predecessors map
	207	template <class Graph, class P, class T, class R, class Capacity, class ResidualCapacity, class Weight, class Reversed, class VertexIndex>
	208	void successive_shortest_path_nonnegative_weights_dispatch1(
92f5a8d4 TL	209	Graph &g,
92f5a8d4 TL	210	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	211	typename graph_traits<Graph>::vertex_descriptor t,
	212	Capacity capacity,
	213	ResidualCapacity residual_capacity,
92f5a8d4	214	Weight weight,
7c673cae FG	215	Reversed rev,
	216	VertexIndex index,
	217	param_not_found,
	218	const bgl_named_params<P, T, R>& params) {
	219	typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
	220	std::vector<edge_descriptor> pred_vec(num_vertices(g));
	221
92f5a8d4	222	successive_shortest_path_nonnegative_weights_dispatch2(g, s, t, capacity, residual_capacity, weight, rev, index,
7c673cae	223	make_iterator_property_map(pred_vec.begin(), index),
92f5a8d4	224	get_param(params, vertex_distance), params);
7c673cae FG	225	}
	226
	227	}//detail
	228
	229
	230	template <class Graph, class P, class T, class R>
	231	void successive_shortest_path_nonnegative_weights(
92f5a8d4 TL	232	Graph &g,
92f5a8d4 TL	233	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	234	typename graph_traits<Graph>::vertex_descriptor t,
7c673cae FG	235	const bgl_named_params<P, T, R>& params) {
92f5a8d4 TL	236
92f5a8d4 TL	237	return detail::successive_shortest_path_nonnegative_weights_dispatch1(g, s, t,
7c673cae	238	choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
92f5a8d4	239	choose_pmap(get_param(params, edge_residual_capacity),
7c673cae FG	240	g, edge_residual_capacity),
	241	choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
	242	choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
	243	choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
92f5a8d4	244	get_param(params, vertex_predecessor),
7c673cae FG	245	params);
	246	}
	247
	248	template <class Graph>
	249	void successive_shortest_path_nonnegative_weights(
	250	Graph &g,
92f5a8d4	251	typename graph_traits<Graph>::vertex_descriptor s,
7c673cae FG	252	typename graph_traits<Graph>::vertex_descriptor t) {
	253	bgl_named_params<int, buffer_param_t> params(0);
	254	successive_shortest_path_nonnegative_weights(g, s, t, params);
	255	}
	256
	257
	258	}//boost
	259	#endif /* BOOST_GRAPH_SUCCESSIVE_SHORTEST_PATH_HPP */