// r_c_shortest_paths.hpp header file

// Copyright Michael Drexl 2005, 2006.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
#define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP

#include <map>
#include <queue>
#include <vector>
#include <list>

#include <boost/make_shared.hpp>
#include <boost/enable_shared_from_this.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/property_map/property_map.hpp>

namespace boost
{

// r_c_shortest_paths_label struct
template < class Graph, class Resource_Container >
struct r_c_shortest_paths_label
: public boost::enable_shared_from_this<
      r_c_shortest_paths_label< Graph, Resource_Container > >
{
    r_c_shortest_paths_label(const unsigned long n,
        const Resource_Container& rc = Resource_Container(),
        const boost::shared_ptr<
            r_c_shortest_paths_label< Graph, Resource_Container > >
            pl
        = boost::shared_ptr<
            r_c_shortest_paths_label< Graph, Resource_Container > >(),
        const typename graph_traits< Graph >::edge_descriptor& ed
        = graph_traits< Graph >::edge_descriptor(),
        const typename graph_traits< Graph >::vertex_descriptor& vd
        = graph_traits< Graph >::vertex_descriptor())
    : num(n)
    , cumulated_resource_consumption(rc)
    , p_pred_label(pl)
    , pred_edge(ed)
    , resident_vertex(vd)
    , b_is_dominated(false)
    , b_is_processed(false)
    {
    }

    r_c_shortest_paths_label& operator=(const r_c_shortest_paths_label& other)
    {
        if (this == &other)
            return *this;
        this->~r_c_shortest_paths_label();
        new (this) r_c_shortest_paths_label(other);
        return *this;
    }
    const unsigned long num;
    Resource_Container cumulated_resource_consumption;
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >
        p_pred_label;
    const typename graph_traits< Graph >::edge_descriptor pred_edge;
    const typename graph_traits< Graph >::vertex_descriptor resident_vertex;
    bool b_is_dominated;
    bool b_is_processed;
}; // r_c_shortest_paths_label

template < class Graph, class Resource_Container >
inline bool operator==(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l1.cumulated_resource_consumption
        == l2.cumulated_resource_consumption;
}

template < class Graph, class Resource_Container >
inline bool operator!=(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return !(l1 == l2);
}

template < class Graph, class Resource_Container >
inline bool operator<(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l1.cumulated_resource_consumption
        < l2.cumulated_resource_consumption;
}

template < class Graph, class Resource_Container >
inline bool operator>(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l2.cumulated_resource_consumption
        < l1.cumulated_resource_consumption;
}

template < class Graph, class Resource_Container >
inline bool operator<=(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l1 < l2 || l1 == l2;
}

template < class Graph, class Resource_Container >
inline bool operator>=(
    const r_c_shortest_paths_label< Graph, Resource_Container >& l1,
    const r_c_shortest_paths_label< Graph, Resource_Container >& l2)
{
    return l2 < l1 || l1 == l2;
}

template < typename Graph, typename Resource_Container >
inline bool operator<(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t < *u;
}

template < typename Graph, typename Resource_Container >
inline bool operator<=(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t <= *u;
}

template < typename Graph, typename Resource_Container >
inline bool operator>(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t > *u;
}

template < typename Graph, typename Resource_Container >
inline bool operator>=(
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& t,
    const boost::shared_ptr<
        r_c_shortest_paths_label< Graph, Resource_Container > >& u)
{
    return *t >= *u;
}

namespace detail
{

    // r_c_shortest_paths_dispatch function (body/implementation)
    template < class Graph, class VertexIndexMap, class EdgeIndexMap,
        class Resource_Container, class Resource_Extension_Function,
        class Dominance_Function, class Label_Allocator, class Visitor >
    void r_c_shortest_paths_dispatch(const Graph& g,
        const VertexIndexMap& vertex_index_map,
        const EdgeIndexMap& /*edge_index_map*/,
        typename graph_traits< Graph >::vertex_descriptor s,
        typename graph_traits< Graph >::vertex_descriptor t,
        // each inner vector corresponds to a pareto-optimal path
        std::vector<
            std::vector< typename graph_traits< Graph >::edge_descriptor > >&
            pareto_optimal_solutions,
        std::vector< Resource_Container >& pareto_optimal_resource_containers,
        bool b_all_pareto_optimal_solutions,
        // to initialize the first label/resource container
        // and to carry the type information
        const Resource_Container& rc, Resource_Extension_Function& ref,
        Dominance_Function& dominance,
        // to specify the memory management strategy for the labels
        Label_Allocator /*la*/, Visitor vis)
    {
        pareto_optimal_resource_containers.clear();
        pareto_optimal_solutions.clear();

        size_t i_label_num = 0;
#if defined(BOOST_NO_CXX11_ALLOCATOR)
        typedef typename Label_Allocator::template rebind<
            r_c_shortest_paths_label< Graph, Resource_Container > >::other
            LAlloc;
#else
        typedef typename std::allocator_traits< Label_Allocator >::
            template rebind_alloc<
                r_c_shortest_paths_label< Graph, Resource_Container > >
                LAlloc;
        typedef std::allocator_traits< LAlloc > LTraits;
#endif
        LAlloc l_alloc;
        typedef boost::shared_ptr<
            r_c_shortest_paths_label< Graph, Resource_Container > >
            Splabel;
        std::priority_queue< Splabel, std::vector< Splabel >,
            std::greater< Splabel > >
            unprocessed_labels;

        bool b_feasible = true;
        Splabel splabel_first_label = boost::allocate_shared<
            r_c_shortest_paths_label< Graph, Resource_Container > >(l_alloc,
            i_label_num++, rc,
            boost::shared_ptr<
                r_c_shortest_paths_label< Graph, Resource_Container > >(),
            typename graph_traits< Graph >::edge_descriptor(), s);

        unprocessed_labels.push(splabel_first_label);
        std::vector< std::list< Splabel > > vec_vertex_labels_data(
            num_vertices(g));
        iterator_property_map<
            typename std::vector< std::list< Splabel > >::iterator,
            VertexIndexMap >
            vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
        vec_vertex_labels[s].push_back(splabel_first_label);
        typedef std::vector< typename std::list< Splabel >::iterator >
            vec_last_valid_positions_for_dominance_data_type;
        vec_last_valid_positions_for_dominance_data_type
            vec_last_valid_positions_for_dominance_data(num_vertices(g));
        iterator_property_map<
            typename vec_last_valid_positions_for_dominance_data_type::iterator,
            VertexIndexMap >
            vec_last_valid_positions_for_dominance(
                vec_last_valid_positions_for_dominance_data.begin(),
                vertex_index_map);
        BGL_FORALL_VERTICES_T(v, g, Graph)
        {
            put(vec_last_valid_positions_for_dominance, v,
                vec_vertex_labels[v].begin());
        }
        std::vector< size_t > vec_last_valid_index_for_dominance_data(
            num_vertices(g), 0);
        iterator_property_map< std::vector< size_t >::iterator, VertexIndexMap >
            vec_last_valid_index_for_dominance(
                vec_last_valid_index_for_dominance_data.begin(),
                vertex_index_map);
        std::vector< bool > b_vec_vertex_already_checked_for_dominance_data(
            num_vertices(g), false);
        iterator_property_map< std::vector< bool >::iterator, VertexIndexMap >
            b_vec_vertex_already_checked_for_dominance(
                b_vec_vertex_already_checked_for_dominance_data.begin(),
                vertex_index_map);

        while (!unprocessed_labels.empty()
            && vis.on_enter_loop(unprocessed_labels, g))
        {
            Splabel cur_label = unprocessed_labels.top();
            unprocessed_labels.pop();
            vis.on_label_popped(*cur_label, g);
            // an Splabel object in unprocessed_labels and the respective
            // Splabel object in the respective list<Splabel> of
            // vec_vertex_labels share their embedded r_c_shortest_paths_label
            // object to avoid memory leaks, dominated r_c_shortest_paths_label
            // objects are marked and deleted when popped from
            // unprocessed_labels, as they can no longer be deleted at the end
            // of the function; only the Splabel object in unprocessed_labels
            // still references the r_c_shortest_paths_label object this is also
            // for efficiency, because the else branch is executed only if there
            // is a chance that extending the label leads to new undominated
            // labels, which in turn is possible only if the label to be
            // extended is undominated
            if (!cur_label->b_is_dominated)
            {
                typename boost::graph_traits< Graph >::vertex_descriptor
                    i_cur_resident_vertex
                    = cur_label->resident_vertex;
                std::list< Splabel >& list_labels_cur_vertex
                    = get(vec_vertex_labels, i_cur_resident_vertex);
                if (list_labels_cur_vertex.size() >= 2
                    && vec_last_valid_index_for_dominance[i_cur_resident_vertex]
                        < list_labels_cur_vertex.size())
                {
                    typename std::list< Splabel >::iterator outer_iter
                        = list_labels_cur_vertex.begin();
                    bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
                        = false;
                    while (outer_iter != list_labels_cur_vertex.end())
                    {
                        Splabel cur_outer_splabel = *outer_iter;
                        typename std::list< Splabel >::iterator inner_iter
                            = outer_iter;
                        if (!b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
                            && outer_iter
                                == get(vec_last_valid_positions_for_dominance,
                                    i_cur_resident_vertex))
                            b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
                                = true;
                        if (!get(b_vec_vertex_already_checked_for_dominance,
                                i_cur_resident_vertex)
                            || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance)
                        {
                            ++inner_iter;
                        }
                        else
                        {
                            inner_iter
                                = get(vec_last_valid_positions_for_dominance,
                                    i_cur_resident_vertex);
                            ++inner_iter;
                        }
                        bool b_outer_iter_erased = false;
                        while (inner_iter != list_labels_cur_vertex.end())
                        {
                            Splabel cur_inner_splabel = *inner_iter;
                            if (dominance(cur_outer_splabel
                                              ->cumulated_resource_consumption,
                                    cur_inner_splabel
                                        ->cumulated_resource_consumption))
                            {
                                typename std::list< Splabel >::iterator buf
                                    = inner_iter;
                                ++inner_iter;
                                list_labels_cur_vertex.erase(buf);
                                if (cur_inner_splabel->b_is_processed)
                                {
                                    cur_inner_splabel.reset();
                                }
                                else
                                    cur_inner_splabel->b_is_dominated = true;
                                continue;
                            }
                            else
                                ++inner_iter;
                            if (dominance(cur_inner_splabel
                                              ->cumulated_resource_consumption,
                                    cur_outer_splabel
                                        ->cumulated_resource_consumption))
                            {
                                typename std::list< Splabel >::iterator buf
                                    = outer_iter;
                                ++outer_iter;
                                list_labels_cur_vertex.erase(buf);
                                b_outer_iter_erased = true;
                                if (cur_outer_splabel->b_is_processed)
                                {
                                    cur_outer_splabel.reset();
                                }
                                else
                                    cur_outer_splabel->b_is_dominated = true;
                                break;
                            }
                        }
                        if (!b_outer_iter_erased)
                            ++outer_iter;
                    }
                    if (list_labels_cur_vertex.size() > 1)
                        put(vec_last_valid_positions_for_dominance,
                            i_cur_resident_vertex,
                            (--(list_labels_cur_vertex.end())));
                    else
                        put(vec_last_valid_positions_for_dominance,
                            i_cur_resident_vertex,
                            list_labels_cur_vertex.begin());
                    put(b_vec_vertex_already_checked_for_dominance,
                        i_cur_resident_vertex, true);
                    put(vec_last_valid_index_for_dominance,
                        i_cur_resident_vertex,
                        list_labels_cur_vertex.size() - 1);
                }
            }
            if (!b_all_pareto_optimal_solutions
                && cur_label->resident_vertex == t)
            {
                // the devil don't sleep
                if (cur_label->b_is_dominated)
                {
                    cur_label.reset();
                }
                while (unprocessed_labels.size())
                {
                    Splabel l = unprocessed_labels.top();
                    unprocessed_labels.pop();
                    // delete only dominated labels, because nondominated labels
                    // are deleted at the end of the function
                    if (l->b_is_dominated)
                    {
                        l.reset();
                    }
                }
                break;
            }
            if (!cur_label->b_is_dominated)
            {
                cur_label->b_is_processed = true;
                vis.on_label_not_dominated(*cur_label, g);
                typename graph_traits< Graph >::vertex_descriptor cur_vertex
                    = cur_label->resident_vertex;
                typename graph_traits< Graph >::out_edge_iterator oei, oei_end;
                for (boost::tie(oei, oei_end) = out_edges(cur_vertex, g);
                     oei != oei_end; ++oei)
                {
                    b_feasible = true;
                    Splabel new_label = boost::allocate_shared<
                        r_c_shortest_paths_label< Graph, Resource_Container > >(
                        l_alloc, i_label_num++,
                        cur_label->cumulated_resource_consumption, cur_label,
                        *oei, target(*oei, g));
                    b_feasible = ref(g,
                        new_label->cumulated_resource_consumption,
                        new_label->p_pred_label->cumulated_resource_consumption,
                        new_label->pred_edge);

                    if (!b_feasible)
                    {
                        vis.on_label_not_feasible(*new_label, g);
                        new_label.reset();
                    }
                    else
                    {
                        vis.on_label_feasible(*new_label, g);
                        vec_vertex_labels[new_label->resident_vertex].push_back(
                            new_label);
                        unprocessed_labels.push(new_label);
                    }
                }
            }
            else
            {
                vis.on_label_dominated(*cur_label, g);
                cur_label.reset();
            }
        }
        std::list< Splabel > dsplabels = get(vec_vertex_labels, t);
        typename std::list< Splabel >::const_iterator csi = dsplabels.begin();
        typename std::list< Splabel >::const_iterator csi_end = dsplabels.end();
        // if d could be reached from o
        if (!dsplabels.empty())
        {
            for (; csi != csi_end; ++csi)
            {
                std::vector< typename graph_traits< Graph >::edge_descriptor >
                    cur_pareto_optimal_path;
                boost::shared_ptr<
                    r_c_shortest_paths_label< Graph, Resource_Container > >
                    p_cur_label = *csi;
                pareto_optimal_resource_containers.push_back(
                    p_cur_label->cumulated_resource_consumption);
                while (p_cur_label->num != 0)
                {
                    cur_pareto_optimal_path.push_back(p_cur_label->pred_edge);
                    p_cur_label = p_cur_label->p_pred_label;

                    // assertion b_is_valid beyond this point is not correct if
                    // the domination function requires resource levels to be
                    // strictly greater than existing values
                    //
                    // Example
                    // Customers
                    // id   min_arrival   max_departure
                    //  2             0             974
                    //  3             0             972
                    //  4             0             964
                    //  5           678             801
                    //
                    // Path A: 2-3-4-5 (times: 0-16-49-84-678)
                    // Path B: 3-2-4-5 (times: 0-18-51-62-678)
                    // The partial path 3-2-4 dominates the other partial path
                    // 2-3-4, though the path 3-2-4-5 does not strictly dominate
                    // the path 2-3-4-5
                }
                pareto_optimal_solutions.push_back(cur_pareto_optimal_path);
                if (!b_all_pareto_optimal_solutions)
                    break;
            }
        }

        BGL_FORALL_VERTICES_T(i, g, Graph)
        {
            std::list< Splabel >& list_labels_cur_vertex = vec_vertex_labels[i];
            typename std::list< Splabel >::iterator si
                = list_labels_cur_vertex.begin();
            const typename std::list< Splabel >::iterator si_end
                = list_labels_cur_vertex.end();
            for (; si != si_end; ++si)
            {
                (*si).reset();
            }
        }
    } // r_c_shortest_paths_dispatch

} // detail

// default_r_c_shortest_paths_visitor struct
struct default_r_c_shortest_paths_visitor
{
    template < class Label, class Graph >
    void on_label_popped(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_feasible(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_not_feasible(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_dominated(const Label&, const Graph&)
    {
    }
    template < class Label, class Graph >
    void on_label_not_dominated(const Label&, const Graph&)
    {
    }
    template < class Queue, class Graph >
    bool on_enter_loop(const Queue& queue, const Graph& graph)
    {
        return true;
    }
}; // default_r_c_shortest_paths_visitor

// default_r_c_shortest_paths_allocator
typedef std::allocator< int > default_r_c_shortest_paths_allocator;
// default_r_c_shortest_paths_allocator

// r_c_shortest_paths functions (handle/interface)
// first overload:
// - return all pareto-optimal solutions
// - specify Label_Allocator and Visitor arguments
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function, class Label_Allocator, class Visitor >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >&
        pareto_optimal_solutions,
    std::vector< Resource_Container >& pareto_optimal_resource_containers,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance,
    // to specify the memory management strategy for the labels
    Label_Allocator la, Visitor vis)
{
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
        ref, dominance, la, vis);
}

// second overload:
// - return only one pareto-optimal solution
// - specify Label_Allocator and Visitor arguments
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function, class Label_Allocator, class Visitor >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    std::vector< typename graph_traits< Graph >::edge_descriptor >&
        pareto_optimal_solution,
    Resource_Container& pareto_optimal_resource_container,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance,
    // to specify the memory management strategy for the labels
    Label_Allocator la, Visitor vis)
{
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >
        pareto_optimal_solutions;
    std::vector< Resource_Container > pareto_optimal_resource_containers;
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
        ref, dominance, la, vis);
    if (!pareto_optimal_solutions.empty())
    {
        pareto_optimal_solution = pareto_optimal_solutions[0];
        pareto_optimal_resource_container
            = pareto_optimal_resource_containers[0];
    }
}

// third overload:
// - return all pareto-optimal solutions
// - use default Label_Allocator and Visitor
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >&
        pareto_optimal_solutions,
    std::vector< Resource_Container >& pareto_optimal_resource_containers,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance)
{
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, true, rc,
        ref, dominance, default_r_c_shortest_paths_allocator(),
        default_r_c_shortest_paths_visitor());
}

// fourth overload:
// - return only one pareto-optimal solution
// - use default Label_Allocator and Visitor
template < class Graph, class VertexIndexMap, class EdgeIndexMap,
    class Resource_Container, class Resource_Extension_Function,
    class Dominance_Function >
void r_c_shortest_paths(const Graph& g, const VertexIndexMap& vertex_index_map,
    const EdgeIndexMap& edge_index_map,
    typename graph_traits< Graph >::vertex_descriptor s,
    typename graph_traits< Graph >::vertex_descriptor t,
    std::vector< typename graph_traits< Graph >::edge_descriptor >&
        pareto_optimal_solution,
    Resource_Container& pareto_optimal_resource_container,
    // to initialize the first label/resource container
    // and to carry the type information
    const Resource_Container& rc, const Resource_Extension_Function& ref,
    const Dominance_Function& dominance)
{
    // each inner vector corresponds to a pareto-optimal path
    std::vector<
        std::vector< typename graph_traits< Graph >::edge_descriptor > >
        pareto_optimal_solutions;
    std::vector< Resource_Container > pareto_optimal_resource_containers;
    r_c_shortest_paths_dispatch(g, vertex_index_map, edge_index_map, s, t,
        pareto_optimal_solutions, pareto_optimal_resource_containers, false, rc,
        ref, dominance, default_r_c_shortest_paths_allocator(),
        default_r_c_shortest_paths_visitor());
    if (!pareto_optimal_solutions.empty())
    {
        pareto_optimal_solution = pareto_optimal_solutions[0];
        pareto_optimal_resource_container
            = pareto_optimal_resource_containers[0];
    }
}
// r_c_shortest_paths

// check_r_c_path function
template < class Graph, class Resource_Container,
    class Resource_Extension_Function >
void check_r_c_path(const Graph& g,
    const std::vector< typename graph_traits< Graph >::edge_descriptor >&
        ed_vec_path,
    const Resource_Container& initial_resource_levels,
    // if true, computed accumulated final resource levels must
    // be equal to desired_final_resource_levels
    // if false, computed accumulated final resource levels must
    // be less than or equal to desired_final_resource_levels
    bool b_result_must_be_equal_to_desired_final_resource_levels,
    const Resource_Container& desired_final_resource_levels,
    Resource_Container& actual_final_resource_levels,
    const Resource_Extension_Function& ref, bool& b_is_a_path_at_all,
    bool& b_feasible, bool& b_correctly_extended,
    typename graph_traits< Graph >::edge_descriptor& ed_last_extended_arc)
{
    size_t i_size_ed_vec_path = ed_vec_path.size();
    std::vector< typename graph_traits< Graph >::edge_descriptor > buf_path;
    if (i_size_ed_vec_path == 0)
        b_feasible = true;
    else
    {
        if (i_size_ed_vec_path == 1
            || target(ed_vec_path[0], g) == source(ed_vec_path[1], g))
            buf_path = ed_vec_path;
        else
            for (size_t i = i_size_ed_vec_path; i > 0; --i)
                buf_path.push_back(ed_vec_path[i - 1]);
        for (size_t i = 0; i < i_size_ed_vec_path - 1; ++i)
        {
            if (target(buf_path[i], g) != source(buf_path[i + 1], g))
            {
                b_is_a_path_at_all = false;
                b_feasible = false;
                b_correctly_extended = false;
                return;
            }
        }
    }
    b_is_a_path_at_all = true;
    b_feasible = true;
    b_correctly_extended = false;
    Resource_Container current_resource_levels = initial_resource_levels;
    actual_final_resource_levels = current_resource_levels;
    for (size_t i = 0; i < i_size_ed_vec_path; ++i)
    {
        ed_last_extended_arc = buf_path[i];
        b_feasible = ref(g, actual_final_resource_levels,
            current_resource_levels, buf_path[i]);
        current_resource_levels = actual_final_resource_levels;
        if (!b_feasible)
            return;
    }
    if (b_result_must_be_equal_to_desired_final_resource_levels)
        b_correctly_extended
            = actual_final_resource_levels == desired_final_resource_levels
            ? true
            : false;
    else
    {
        if (actual_final_resource_levels < desired_final_resource_levels
            || actual_final_resource_levels == desired_final_resource_levels)
            b_correctly_extended = true;
    }
} // check_path

} // namespace

#endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP