//=======================================================================
// 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 */