Boost C++ Libraries

boost/graph/r_c_shortest_paths.hpp

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