// 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 <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
{
  r_c_shortest_paths_label
  ( const unsigned long n, 
    const Resource_Container& rc = Resource_Container(), 
    const r_c_shortest_paths_label* const pl = 0, 
    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 ),
    b_is_valid( true )
  {}
  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 r_c_shortest_paths_label* const 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;
  bool b_is_valid;
}; // 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 )
{
  assert (l1.b_is_valid && l2.b_is_valid);
  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 )
{
  assert (l1.b_is_valid && l2.b_is_valid);
  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 )
{
  assert (l1.b_is_valid && l2.b_is_valid);
  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 )
{
  assert (l1.b_is_valid && l2.b_is_valid);
  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 )
{
  assert (l1.b_is_valid && l2.b_is_valid);
  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 )
{
  assert (l1.b_is_valid && l2.b_is_valid);
  return l2 < l1 || l1 == l2;
}

namespace detail {

// ks_smart_pointer class
// from:
// Kuhlins, S.; Schader, M. (1999):
// Die C++-Standardbibliothek
// Springer, Berlin
// p. 333 f.
template<class T>
class ks_smart_pointer
{
public:
  ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {}
  ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {}
  ks_smart_pointer& operator=( const ks_smart_pointer& other )
    { pt = other.pt; return *this; }
  ~ks_smart_pointer() {}
  T& operator*() const { return *pt; }
  T* operator->() const { return pt; }
  T* get() const { return pt; }
  operator T*() const { return pt; }
  friend bool operator==( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt == *u.pt; }
  friend bool operator!=( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt != *u.pt; }
  friend bool operator<( const ks_smart_pointer& t, 
                         const ks_smart_pointer& u )
    { return *t.pt < *u.pt; }
  friend bool operator>( const ks_smart_pointer& t, 
                         const ks_smart_pointer& u )
    { return *t.pt > *u.pt; }
  friend bool operator<=( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt <= *u.pt; }
  friend bool operator>=( const ks_smart_pointer& t, 
                          const ks_smart_pointer& u )
    { return *t.pt >= *u.pt; }
private:
  T* pt;
}; // ks_smart_pointer


// 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 )
{
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  typedef typename graph_traits<Graph>::edge_descriptor Edge;
  typedef typename graph_traits<Graph>::out_edge_iterator Oei;
  typedef typename Label_Allocator::template rebind<r_c_shortest_paths_label<Graph, Resource_Container>>::other LAlloc;
  
  typedef r_c_shortest_paths_label<Graph, Resource_Container> ValSplabel;
  typedef ks_smart_pointer<ValSplabel> Splabel;
  typedef std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel>> SplabelQueue;
  
  typedef std::list<Splabel> SplabelList;
  typedef typename std::list<Splabel>::iterator SplabelListIter;
  typedef typename std::list<Splabel>::const_iterator SplabelListConstIter;
  
  typedef std::vector<std::list<Splabel>> SplabelData;
  typedef iterator_property_map<typename SplabelData::iterator, VertexIndexMap> SplabelDataPM;
  
  typedef std::vector<SplabelListIter> SplabelValidPos;
  typedef iterator_property_map<typename SplabelValidPos::iterator, VertexIndexMap> SplabelValidPosPM;
  
  typedef std::vector<size_t> SplabelIndex;
  typedef iterator_property_map<typename SplabelIndex::iterator, VertexIndexMap> SplabelIndexPM;
  
  typedef std::vector<bool> SplabelChecked;
  typedef iterator_property_map<typename SplabelChecked::iterator, VertexIndexMap> SplabelCheckedPM;
    
  pareto_optimal_resource_containers.clear();
  pareto_optimal_solutions.clear();

  size_t i_label_num = 0;
  LAlloc l_alloc;
  SplabelQueue unprocessed_labels;

  bool b_feasible = true;
  
  ValSplabel* first_label = l_alloc.allocate(1);
  l_alloc.construct(first_label, ValSplabel(i_label_num++,rc, 0, Edge(), s));

  Splabel splabel_first_label = Splabel(first_label);
  
  unprocessed_labels.push(splabel_first_label);
  
  SplabelData vec_vertex_labels_data(num_vertices(g));
  SplabelDataPM vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
  
  vec_vertex_labels[s].push_back(splabel_first_label);
  
  SplabelValidPos vec_last_valid_positions_for_dominance_data(num_vertices(g));
  SplabelValidPosPM 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());
  }
  
  SplabelIndex vec_last_valid_index_for_dominance_data(num_vertices(g), 0);
  SplabelIndexPM vec_last_valid_index_for_dominance(vec_last_valid_index_for_dominance_data.begin(), vertex_index_map);
  
  SplabelChecked b_vec_vertex_already_checked_for_dominance_data(num_vertices(g), false);
  SplabelCheckedPM 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();
    
    assert(cur_label->b_is_valid);
    
    unprocessed_labels.pop();
    vis.on_label_popped( *cur_label, g );
    
    assert(cur_label->b_is_valid);
    
    /*
      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) {
      Vertex i_cur_resident_vertex = cur_label->resident_vertex;
      SplabelList& 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()) {
        SplabelListIter 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;
          
          assert(cur_outer_splabel->b_is_valid);
          
          SplabelListIter 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;
            
            assert(cur_inner_splabel->b_is_valid);
            
            if(dominance(cur_outer_splabel->cumulated_resource_consumption, cur_inner_splabel->cumulated_resource_consumption)) {
              SplabelListIter buf = inner_iter;
              ++inner_iter;
              
              list_labels_cur_vertex.erase(buf);
              
              if(cur_inner_splabel->b_is_processed) {
                std::cerr << "Deleting dominated label: " << cur_inner_splabel->num << " (dominated by " << cur_outer_splabel->num << ")" << std::endl;
                
                cur_inner_splabel->b_is_valid = false;
                l_alloc.destroy(cur_inner_splabel.get());
                l_alloc.deallocate(cur_inner_splabel.get(), 1);
              } 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)) {
              SplabelListIter buf = outer_iter;
              ++outer_iter;
              
              list_labels_cur_vertex.erase(buf);
              b_outer_iter_erased = true;
              
              assert(cur_outer_splabel->b_is_valid);
              
              if(cur_outer_splabel->b_is_processed) {
                std::cerr << "Deleting dominated label: " << cur_outer_splabel->num <<  " (dominated by " << cur_inner_splabel->num << ")" << std::endl;
                
                cur_outer_splabel->b_is_valid = false;
                l_alloc.destroy(cur_outer_splabel.get());
                l_alloc.deallocate(cur_outer_splabel.get(), 1);
              } 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);
      }
    }
    
    assert(b_all_pareto_optimal_solutions || cur_label->b_is_valid);
    
    if(!b_all_pareto_optimal_solutions && cur_label->resident_vertex == t) {
      if(cur_label->b_is_dominated) {
        std::cerr << "Current label dominated, destroying " << cur_label->num << std::endl;
        
        cur_label->b_is_valid = false;
        l_alloc.destroy(cur_label.get());
        l_alloc.deallocate(cur_label.get(), 1);
      }
      
      while(unprocessed_labels.size() > 0) {
        Splabel l = unprocessed_labels.top();
        
        assert(l->b_is_valid);
        
        unprocessed_labels.pop();
        
        // Delete only dominated labels.
        // Nondominated labels are deleted at the end of the function
        if(l->b_is_dominated) {
          std::cerr << "Unprocessed label dominated, destroying " << l->num << std::endl;
          
          l->b_is_valid = false;
          l_alloc.destroy(l.get());
          l_alloc.deallocate(l.get(), 1);
        }
      }
      break;
    }
    
    if(!cur_label->b_is_dominated) {
      cur_label->b_is_processed = true;
      vis.on_label_not_dominated(*cur_label, g);
      
      Vertex cur_vertex = cur_label->resident_vertex;
      
      Oei oei, oei_end;
      for(boost::tie(oei, oei_end) = out_edges(cur_vertex, g); oei != oei_end; ++oei) {
        b_feasible = true;
        
        r_c_shortest_paths_label<Graph, Resource_Container>* new_label = l_alloc.allocate(1);
        l_alloc.construct(new_label, r_c_shortest_paths_label<Graph, Resource_Container>(i_label_num++, cur_label->cumulated_resource_consumption, cur_label.get(), *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);
          
          std::cerr << "Extension is not feasible, destroying " << new_label->num << std::endl;
          
          new_label->b_is_valid = false;
          l_alloc.destroy(new_label);
          l_alloc.deallocate(new_label, 1);
        } else {
          const r_c_shortest_paths_label<Graph, Resource_Container>& ref_new_label = *new_label;
          vis.on_label_feasible(ref_new_label, g);
          
          Splabel new_sp_label(new_label);
          
          vec_vertex_labels[new_sp_label->resident_vertex].push_back(new_sp_label);
          unprocessed_labels.push(new_sp_label);
          
          std::cerr << "New label " << new_sp_label->num << " is feasible and extends " << cur_label->num << std::endl;
        }
      }
    } else {
      assert(cur_label->b_is_valid);
      
      vis.on_label_dominated(*cur_label, g);
      
      std::cerr << "Current label dominated, destroying " << cur_label->num << std::endl;
      
      cur_label->b_is_valid = false;
      l_alloc.destroy( cur_label.get() );
      l_alloc.deallocate( cur_label.get(), 1 );
    }
  }
  
  SplabelList dsplabels = get(vec_vertex_labels, t);
  SplabelListConstIter csi = dsplabels.begin();
  SplabelListConstIter csi_end = dsplabels.end();
  
  // At the end of the algorithm, if the sink node could be
  // reached strating from the source node, reconstruct the
  // paths corresponding to pareto-optimal labels.
  if(!dsplabels.empty()) {
    for(; csi != csi_end; ++csi) {
      std::vector<Edge> cur_pareto_optimal_path;
      
      const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label = (*csi).get();
      
      assert(p_cur_label->b_is_valid);
      
      std::cerr << "Walking back a pareto-optimal path: " << p_cur_label->num << " ";
      
      pareto_optimal_resource_containers.push_back(p_cur_label->cumulated_resource_consumption);
      
      // Walk back the path
      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;
        
        assert(p_cur_label->b_is_valid);
        std::cerr << p_cur_label->num << " ";
      }
      
      std::cerr << std::endl;
      
      pareto_optimal_solutions.push_back(cur_pareto_optimal_path);
      
      if(!b_all_pareto_optimal_solutions) {
        break;
      }
    }
  }

  // Final clean-up
  BGL_FORALL_VERTICES_T(i, g, Graph) {
    const SplabelList& list_labels_cur_vertex = vec_vertex_labels[i];
    csi = list_labels_cur_vertex.begin();
    csi_end = list_labels_cur_vertex.end();
    
    for(; csi != csi_end; ++csi) {
      assert ((*csi)->b_is_valid);
      
      std::cerr << "Cleaning up label " << (*csi)->num << std::endl;
      
      (*csi)->b_is_valid = false;
      l_alloc.destroy((*csi).get());
      l_alloc.deallocate((*csi).get(), 1);
    }
  }
} // 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