[Boost-commit] svn:boost r44717 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test

From: dgregor_at_[hidden]
Date: 2008-04-22 08:24:26

Author: dgregor
Date: 2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
New Revision: 44717
URL: http://svn.boost.org/trac/boost/changeset/44717

Log:
Resource-constrained shortest paths, from Michael Drexl
Added:
   trunk/boost/graph/r_c_shortest_paths.hpp   (contents, props changed)
   trunk/libs/graph/doc/r_c_shortest_paths.html   (contents, props changed)
   trunk/libs/graph/example/r_c_shortest_paths_example.cpp   (contents, props changed)
   trunk/libs/graph/test/r_c_shortest_paths_test.cpp   (contents, props changed)
Text files modified: 
   trunk/libs/graph/doc/history.html           |     6 ++++++                                  
   trunk/libs/graph/doc/table_of_contents.html |     1 +                                       
   trunk/libs/graph/test/Jamfile.v2            |     2 ++                                      
   3 files changed, 9 insertions(+), 0 deletions(-)

Added: trunk/boost/graph/r_c_shortest_paths.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/r_c_shortest_paths.hpp	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -0,0 +1,729 @@
+// 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>
+
+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 )
+  {}
+  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;
+}; // 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;
+}
+
+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 )
+{
+  pareto_optimal_resource_containers.clear();
+  pareto_optimal_solutions.clear();
+
+  unsigned long i_label_num = 0;
+  typedef 
+    typename 
+      Label_Allocator::template rebind
+        <r_c_shortest_paths_label
+          <Graph, Resource_Container> >::other LAlloc;
+  LAlloc l_alloc;
+  typedef 
+    ks_smart_pointer
+      <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;
+  r_c_shortest_paths_label<Graph, Resource_Container>* first_label = 
+    l_alloc.allocate( 1 );
+  l_alloc.construct
+    ( first_label, 
+      r_c_shortest_paths_label
+        <Graph, Resource_Container>( i_label_num++, 
+                                     rc, 
+                                     0, 
+                                     typename graph_traits<Graph>::
+                                       edge_descriptor(), 
+                                     s ) );
+
+  Splabel splabel_first_label = Splabel( first_label );
+  unprocessed_labels.push( splabel_first_label );
+  std::vector<std::list<Splabel> > vec_vertex_labels( num_vertices( g ) );
+  vec_vertex_labels[vertex_index_map[s]].push_back( splabel_first_label );
+  std::vector<typename std::list<Splabel>::iterator> 
+    vec_last_valid_positions_for_dominance( num_vertices( g ) );
+  for( int i = 0; i < static_cast<int>( num_vertices( g ) ); ++i )
+    vec_last_valid_positions_for_dominance[i] = vec_vertex_labels[i].begin();
+  std::vector<int> vec_last_valid_index_for_dominance( num_vertices( g ), 0 );
+  std::vector<bool> 
+    b_vec_vertex_already_checked_for_dominance( num_vertices( g ), false );
+  while( unprocessed_labels.size() )
+  {
+    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 )
+    {
+      int i_cur_resident_vertex_num = cur_label->resident_vertex;
+      std::list<Splabel>& list_labels_cur_vertex = 
+        vec_vertex_labels[i_cur_resident_vertex_num];
+      if( static_cast<int>( list_labels_cur_vertex.size() ) >= 2 
+          && vec_last_valid_index_for_dominance[i_cur_resident_vertex_num] 
+               < static_cast<int>( 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 == 
+                   vec_last_valid_positions_for_dominance
+                     [i_cur_resident_vertex_num] )
+            b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true;
+          if( !b_vec_vertex_already_checked_for_dominance
+                [i_cur_resident_vertex_num] 
+              || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance )
+          {
+            ++inner_iter;
+          }
+          else
+          {
+            inner_iter = 
+              vec_last_valid_positions_for_dominance
+                [i_cur_resident_vertex_num];
+            ++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 )
+              {
+                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 ) )
+            {
+              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 )
+              {
+                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( static_cast<int>( list_labels_cur_vertex.size() ) > 1 )
+          vec_last_valid_positions_for_dominance[i_cur_resident_vertex_num] = 
+            (--(list_labels_cur_vertex.end()));
+        else
+          vec_last_valid_positions_for_dominance[i_cur_resident_vertex_num] = 
+            list_labels_cur_vertex.begin();
+        b_vec_vertex_already_checked_for_dominance
+          [i_cur_resident_vertex_num] = true;
+        vec_last_valid_index_for_dominance[i_cur_resident_vertex_num] = 
+          static_cast<int>( 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 )
+      {
+        l_alloc.destroy( cur_label.get() );
+        l_alloc.deallocate( cur_label.get(), 1 );
+      }
+      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_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 );
+      typename graph_traits<Graph>::vertex_descriptor cur_vertex = 
+        cur_label->resident_vertex;
+      typename graph_traits<Graph>::out_edge_iterator oei, oei_end;
+      for( 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 );
+          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[vertex_index_map[new_sp_label->resident_vertex]].
+            push_back( new_sp_label );
+          unprocessed_labels.push( new_sp_label );
+        }
+      }
+    }
+    else
+    {
+      vis.on_label_dominated( *cur_label, g );
+      l_alloc.destroy( cur_label.get() );
+      l_alloc.deallocate( cur_label.get(), 1 );
+    }
+  }
+  std::list<Splabel> dsplabels = vec_vertex_labels[vertex_index_map[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.size() )
+  {
+    for( ; csi != csi_end; ++csi )
+    {
+      std::vector<typename graph_traits<Graph>::edge_descriptor> 
+        cur_pareto_optimal_path;
+      const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label = 
+        (*csi).get();
+      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;
+      }
+      pareto_optimal_solutions.push_back( cur_pareto_optimal_path );
+      if( !b_all_pareto_optimal_solutions )
+        break;
+    }
+  }
+
+  int i_size = static_cast<int>( vec_vertex_labels.size() );
+  for( int i = 0; i < i_size; ++i )
+  {
+    const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
+    csi_end = list_labels_cur_vertex.end();
+    for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi )
+    {
+      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& l, const Graph& g ) {}
+  template<class Label, class Graph>
+  void on_label_feasible( const Label& l, const Graph& g ) {}
+  template<class Label, class Graph>
+  void on_label_not_feasible( const Label& l, const Graph& g ) {}
+  template<class Label, class Graph>
+  void on_label_dominated( const Label& l, const Graph& g ) {}
+  template<class Label, class Graph>
+  void on_label_not_dominated( const Label& l, const Graph& g ) {}
+}; // 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 );
+  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() );
+  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 )
+{
+  int i_size_ed_vec_path = static_cast<int>( 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( int i = i_size_ed_vec_path - 1; i >= 0; --i )
+        buf_path.push_back( ed_vec_path[i] );
+    for( int 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( int 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

Modified: trunk/libs/graph/doc/history.html
==============================================================================
--- trunk/libs/graph/doc/history.html	(original)
+++ trunk/libs/graph/doc/history.html	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -78,6 +78,12 @@
 <ul>
   <a name="1.35.0"></a><li>Version 1.35.0<br><b>New algorithms and components</b>
     <ul>
+      <li>r_c_shortest_paths, resource-constrained shortest paths, from Michael Drexl.</li>
+    </ul>
+  </li>
+
+  <a name="1.35.0"></a><li>Version 1.35.0<br><b>New algorithms and components</b>
+    <ul>
       <li>kolmogorov_max_flow, from Stephan Diederich as part of the 2006 Google Summer of Code.</li>
       <li>read_dimacs_max_flow and write_dimacs_max_flow for max-flow problems, from Stephan Diederich.</li>
       <li>read_graphml and write_graphml for GraphML input/output, from Tiago de Paula Peixoto.</li>

Added: trunk/libs/graph/doc/r_c_shortest_paths.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/r_c_shortest_paths.html	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -0,0 +1,576 @@
+<html>
+<!--
+  -- Copyright (c) Michael Drexl 2006
+  --
+  -- Permission to use, copy, modify, and distribute this software
+  -- and its documentation for any purpose is hereby granted without fee,
+  -- provided that the above copyright notice appears in all copies and
+  -- that both that copyright notice and this permission notice appear
+  -- in supporting documentation.  Michael Drexl makes no
+  -- representations about the suitability of this software for any
+  -- purpose.  It is provided "as is" without express or implied warranty.
+  -->
+<head>
+<title>Boost Graph Library: Resource-Constrained Shortest Paths</title>
+<body bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b" 
+        alink="#ff0000"> 
+<img src="../../../boost.png" 
+     alt="C++ Boost" width="277" height="86"> 
+
+<br Clear>
+
+<h1><a name="sec:espprc"></a>
+<tt>r_c_shortest_paths</tt>
+</h1>
+
+<p>
+<pre>
+
+template&lt;class Graph,
+         class VertexIndexMap,
+         class EdgeIndexMap,
+         class Resource_Container,
+         class Resource_Extension_Function,
+         class Dominance_Function,
+         class Label_Allocator,
+         class Visitor&gt;
+void r_c_shortest_paths( const Graph&amp; g,
+                         const VertexIndexMap&amp; vertex_index_map,
+                         const EdgeIndexMap&amp; edge_index_map,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor t,
+                         std::vector&lt;std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; &gt;&amp; pareto_optimal_solutions,
+                         std::vector&lt;Resource_Container&gt;&amp; pareto_optimal_resource_containers,
+                         const Resource_Container&amp; rc,
+                         const Resource_Extension_Function&amp; ref,
+                         const Dominance_Function&amp; dominance,
+                         Label_Allocator la,
+                         Visitor vis )
+
+template&lt;class Graph,
+         class VertexIndexMap,
+         class EdgeIndexMap,
+         class Resource_Container,
+         class Resource_Extension_Function,
+         class Dominance_Function,
+         class Label_Allocator,
+         class Visitor&gt;
+void r_c_shortest_paths( const Graph&amp; g,
+                         const VertexIndexMap&amp; vertex_index_map,
+                         const EdgeIndexMap&amp; edge_index_map,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor t,
+                         std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt;&amp; pareto_optimal_solution,
+                         Resource_Container&gt;&amp; pareto_optimal_resource_container,
+                         const Resource_Container&amp; rc,
+                         const Resource_Extension_Function&amp; ref,
+                         const Dominance_Function&amp; dominance,
+                         Label_Allocator la,
+                         Visitor vis )
+
+template&lt;class Graph,
+         class VertexIndexMap,
+         class EdgeIndexMap,
+         class Resource_Container,
+         class Resource_Extension_Function,
+         class Dominance_Function&gt;
+void r_c_shortest_paths( const Graph&amp; g,
+                         const VertexIndexMap&amp; vertex_index_map,
+                         const EdgeIndexMap&amp; edge_index_map,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor t,
+                         std::vector&lt;std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; &gt;&amp; pareto_optimal_solutions,
+                         std::vector&lt;Resource_Container&gt;&amp; pareto_optimal_resource_containers,
+                         const Resource_Container&amp; rc,
+                         const Resource_Extension_Function&amp; ref,
+                         const Dominance_Function&amp; dominance )
+
+template&lt;class Graph,
+         class VertexIndexMap,
+         class EdgeIndexMap,
+         class Resource_Container,
+         class Resource_Extension_Function,
+         class Dominance_Function&gt;
+void r_c_shortest_paths( const Graph&amp; g,
+                         const VertexIndexMap&amp; vertex_index_map,
+                         const EdgeIndexMap&amp; edge_index_map,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor s,
+                         typename graph_traits&lt;Graph&gt;::vertex_descriptor t,
+                         std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt;&amp; pareto_optimal_solution,
+                         Resource_Container&gt;&amp; pareto_optimal_resource_container,
+                         const Resource_Container&amp; rc,
+                         const Resource_Extension_Function&amp; ref,
+                         const Dominance_Function&amp; dominance )
+
+</pre>
+
+<h3>Introduction and Problem Description</h3>
+
+The shortest path problem with resource constraints (SPPRC) seeks a shortest (cheapest, fastest) path in a directed graph with arbitrary arc lengths (travel times, costs) from an origin node to a destination node subject to one or more resource constraints. For example, one might seek a path of minimum length from <i>s</i> to <i>t</i> subject to the constraints that
+<ul>
+<li>
+the total travel time must not exceed some upper bound and/or
+<li>
+the total amount of some good that has to be picked up at the vertices along the path be less than or equal to some capacity limit and/or
+<li>
+if two vertices <i>i</i> and <i>j</i> are visited on a path, then <i>i</i> must be visited before <i>j</i>
+<li>
+etc.
+</ul>
+
+<p>
+The problem is NP-hard in the strong sense. If the path need not be elementary, i.e., if it is allowed that vertices are visited more than once, the problem can be solved in pseudopolynomial time. A central aspect is that two (partial) paths in an SPPRC can be incomparable, contrary to the SPP without resource constraints. This makes the SPPRC similar to a multi-criteria decision problem.<br>
+A recent survey on the problem is:<br>
+Irnich, S.; Desaulniers, G. (2005):<br>
+Shortest Path Problems with Resource Constraints<br>
+in:<br>
+Desaulniers, G.; Desrosiers, J.; Solomon, M. (eds.) (2005):<br>
+Column Generation<br>
+Springer, New York, pp. 33&ndash;65<br>
+(available online <a href="http://www.dpor.rwth-aachen.de/de/publikationen/pdf/or_2004-01.pdf">
+here</a>)
+<p>
+
+<p>
+The present document cannot give a complete introduction to SPPRCs. To get a thorough understanding of the problem, the reader is referred to the above paper. However, to understand the algorithm and its implementation, it is necessary to explain some fundamental ideas and point out the differences to a labelling algorithm for the shortest path problem without resource constraints (SPP).
+</p>
+
+<p>
+The standard solution technique for SPPRCs is a labelling algorithm based on dynamic programming. This approach uses the concepts of <i>resources</i> and <i>resource extension functions</i>. A resource is an arbitrarily scaled one-dimensional piece of information that can be determined or measured at the vertices of a directed walk in a graph. Examples are cost, time, load, or the information &lsquo;Is a vertex <i>i</i> visited on the current path?&rsquo;. A resource is <i>constrained</i> if there is at least one vertex in the graph where the resource must not take all possible values. The <i>resource window</i> of a resource at a vertex is the set of allowed values for the resource at this vertex.
+</p>
+
+<p>
+A resource extension function is defined on each arc in a graph for each resource considered. A resource extension function for a resource maps the set of all possible vectors (in a mathematical sense, not to be confused with a <tt>std::vector</tt>) of resource values at the source of an arc to the set of possible values of the resource at the target of the arc. This means that the value of a resource at a vertex may depend on the values of one or more other resources at the preceding vertex.
+</p>
+
+<p>
+<i>Labels</i> are used to store the information on the resource values for partial paths. A label in an SPPRC labelling algorithm is not a mere triple of resident vertex, current cost and predecessor vertex, as it is the case in labelling algorithms for the SPP. A label for an SPPRC labelling algorithm stores its resident vertex, its predecessor <i>arc</i> over which it has been extended, its predecessor label, and its current vector of resource values. The criterion to be minimized (cost, travel time, travel distance, whatsoever) is also treated as a (possibly unconstrained) resource. It is necessary to store the predecessor arc instead of the predecessor vertex, because, due to the resource constraints, one can not assume that the underlying graph is simple. Labels reside at vertices, and they are propagated via resource extension functions when they are extended along an arc. An <i>extension</i> of a label along an arc (<i>i</i>, <i>j</i>) is <i>feasible</i> if the resulting label <i>l</i> at <i>j</i> is
 feasible, which is the case if and only if all resource values of <i>l</i> are within their resource windows.
+</p>
+
+<p>
+To keep the number of labels as small as possible, it is decisive to perform a <i>dominance step</i> for eliminating unnecessary labels. A label <i>l</i><sub>1</sub> <i>dominates</i> a label <i>l</i><sub>2</sub> if both reside at the same vertex and if, for each feasible extension of <i>l</i><sub>2</sub>, there is also a feasible extension of <i>l</i><sub>1</sub> where the value of each cardinally scaled resource is less than or equal to the value of the resource in the extension of <i>l</i><sub>2</sub>, and where the value of each nominally scaled resource is equal to the value of the resource in the extension of <i>l</i><sub>2</sub>. Dominated labels need not be extended. A label which is not dominated by any other label is called undominated or Pareto-optimal. The application of the dominance principle is optional&mdash;at least from a theoretical perspective.
+</p>
+
+<p>
+The implementation is a label-setting algorithm. This means that there must be one or more resources whose cumulated consumption(s) after extension is/are always at least as high as before. This is similar to the Dijkstra algorithm for the SPP without resource constraints where the distance measure must be non-negative. It is sufficient if there is one resource with a non-negative resource consumption along all arcs (for example, non-negative arc lengths or non-negative arc traversal times).
+</p>
+
+<h3>Concepts</h3>
+
+<h4>ResourceContainer</h4>
+
+<p>
+A type modelling the ResourceContainer concept is used to store the current resource consumptions of a label.
+</p>
+
+<p>
+<b>Refinement of</b><br>
+DefaultConstructible, CopyConstructible, Assignable, LessThanComparable, EqualityComparable
+</p>
+
+<p>
+<b>Valid Expressions</b><br>
+See ResourceExtensionFunction concept.
+</p>
+
+<a name="Label"><h4>Label</h4></a>
+
+<p>
+This concept defines the interface for a label in the <tt>r_c_shortest_paths</tt> functions. It is a design decision not to parameterize the functions on the type of label. The type <tt>template&lt;class Graph, class Resource_Container&gt struct r_c_shortest_paths_label</tt> is used to model this concept.
+</p>
+
+<p>
+<b>Valid Expressions</b><br>
+If <tt>label</tt> is an object of type <tt>r_c_shortest_paths_label</tt>, the following expressions are valid:<br>
+<table border>
+<tr>
+<td>
+<tt>label.num</tt>
+</td>
+<td>
+Returns an unsigned integer value specifying the number of the label. Labels are numbered consecutively in order of their creation.
+</td>
+</tr>
+<tr>
+<td>
+<tt>label.cumulated_resource_consumption</tt>
+</td>
+<td>
+Returns the object associated with <tt>label</tt> modelling the ResourceContainer concept.
+</td>
+</tr>
+<tr>
+<td>
+<tt>label.p_pred_label</tt>
+</td>
+<td>
+Returns a <tt>const</tt> pointer to the predecessor label, i.e., to the label whose extension along <tt>label.pred_edge</tt> yielded the <tt>label} object</tt>.
+</td>
+</tr>
+<tr>
+<td>
+<tt>label.pred_edge</tt>
+</td>
+<td>
+Returns an edge descriptor for the arc along which <tt>label.p_pred_label</tt> was extended to yield the <tt>label</tt> object.
+</td>
+</tr>
+<tr>
+<td>
+<tt>label.resident_vertex</tt>
+</td>
+<td>
+Returns a vertex descriptor for the vertex at which the <tt>label</tt> object resides.
+</td>
+</tr>
+<tr>
+<td>
+<tt>label.b_is_dominated</tt>
+</td>
+<td>
+Returns a boolean value indicating whether the <tt>label</tt> object is dominated by some other label residing at the vertex <tt>label.resident_vertex</tt>. Is useful only after dominance checking has been performed, i.e. only in the visitor functions <tt>on_label_dominated</tt> and <tt>on_label_not_dominated</tt> (see below).
+</td>
+</tr>
+</table>
+
+<p>
+<b>Invariants</b><br>
+Every <tt>r_c_shortest_paths_label</tt> object, except for the first label, has a valid (not null) <tt>p_pred_label</tt> pointer and a valid <tt>pred_edge</tt> member. The <tt>p_pred_label</tt> pointer of the label with <tt>num</tt> member equal to zero is a null pointer, and the <tt>pred_edge</tt> member of this label is a default-constructed edge descriptor.
+</p>
+
+<a name="ResourceExtensionFunction"><h4>ResourceExtensionFunction</h4></a>
+
+<p>
+A model of the ResourceExtensionFunction concept is used to specify how a label is to be extended along an arc.
+</p>
+
+<p>
+<b>Valid Expressions</b><br>
+If <tt>ref</tt> models the ResourceExtensionFunction concept, and if the type <tt>Resource_Container</tt> models the ResourceContainer concept, the following expression is valid:<br>
+<table border>
+<tr>
+<td>
+<pre>
+bool b = ref( const Graph&amp; g,
+              Resource_Container&amp; new_cont,
+              const Resource_Container&amp; old_cont,
+              graph_traits&lt;Graph&gt;::edge_descriptor ed )
+</pre>
+</td>
+<td>
+<tt>ref</tt> must return <tt>true</tt> if and only if the extension is feasible, i.e., if <tt>new_cont</tt> fulfills all resource constraints at the target vertex of <tt>ed</tt>.
+</td>
+</tr>
+</table>
+Moreover, a reference to a type modelling the ResourceExtensionFunction concept can be passed as a parameter to <tt>r_c_shortest_paths</tt>, see above.<br>
+</p>
+
+<p>
+Hence, a type modelling the ResourceExtensionFunction concept is likely to be a function or a function object.
+</p>
+
+<p>
+<b>Invariants</b><br>
+If <tt>ref</tt> models the ResourceExtensionFunction concept, and if the type <tt>Resource_Container</tt> models the ResourceContainer concept, after the call
+<pre>
+ref( const Graph&amp; g,
+     Resource_Container&amp; new_cont,
+     const Resource_Container&amp; old_cont,
+     graph_traits&lt;Graph&gt;::edge_descriptor )
+</pre>
+the expression <tt>old_cont &lt;= new_cont</tt> evaluates to <tt>true</tt>.<br>
+This is because, as stated above, the implementation is a label-setting algorithm. Therefore, the Less-Than operator for ResourceContainer must compare one or more resource(s) whose resource consumption(s) along any arc is/are non-decreasing in order for the algorithm to work properly.
+</p>
+
+<h4>DominanceFunction</h4>
+
+<p>
+A model of DominanceFunction is used to specify a dominance relation between two labels.
+</p>
+
+<p>
+<b>Refinement of</b><br>
+BinaryPredicate
+</p>
+
+<p>
+<b>Valid Expressions</b><br>
+If <tt>dominance</tt> models the DominanceFunction concept, and if the type <tt>Resource_Container</tt> models the ResourceContainer concept, the following expression is valid:
+<table border>
+<tr>
+<td>
+<pre>
+bool b = dominance(const Resource_Container&amp; rc1, const Resource_Container&amp; rc2)
+</pre>
+</td>
+<td>
+<tt>dominance</tt> must return <tt>true</tt> if and only if <tt>rc1</tt> dominates <tt>rc2</tt>.
+</td>
+</tr>
+</table>
+Moreover, a reference to a type modelling the DominanceFunction concept can be passed as a parameter to <tt>r_c_shortest_paths</tt>, see above.
+</p>
+
+<p>
+<b>Invariants</b><br>
+A type modelling the DominanceFunction concept must return <tt>true</tt> if and only if <tt>rc1<=rc2</tt>. It must <i>not</i> return <tt>false</tt> if <tt>rc1==rc2</tt>. Then, it is guaranteed that no two labels with identical resource consumption dominate each other and are both considered as dominated by the <tt>r_c_shortest_paths</tt> functions.
+</p>
+
+<a name="ResourceConstrainedShortestPathsVisitor"><h4>ResourceConstrainedShortestPathsVisitor</h4></a>
+
+<p>
+This concept defines the visitor interface for <tt>r_c_shortest_paths</tt>. A user can define a type with this interface and pass an object of this type to <tt>r_c_shortest_paths</tt> to perform user-defined actions at the event points of the algorithm. Note that the object is passed by value.
+</p>
+
+<p>
+<b>Refinement of</b><br>
+DefaultConstructible, CopyConstructible
+</p>
+
+<p>
+<b>Valid Expressions</b><br>
+If <tt>vis</tt> is an object of a type modelling the ResourceConstrainedShortestPathsVisitor concept, and if <tt>g</tt> is an object of a type <tt>Graph</tt> modelling the IncidenceGraph and the PropertyGraph concepts, and if it is a directed graph, and if <tt>l</tt> is an object of a type <tt>Label</tt> modelling the Label concept, the following expressions are valid:<br>
+<table border>
+<tr>
+<td>
+<tt>vis.on_label_popped( const Label&amp; l, const Graph&amp; g )</tt>
+</td>
+</tr>
+<tr>
+<td>
+<tt>vis.on_label_feasible( const Label&amp; l, const Graph&amp; g )</tt>
+</td>
+</tr>
+<tr>
+<td>
+<tt>vis.on_label_not_feasible( const Label&amp; l, const Graph&amp; g )</tt>
+</td>
+</tr>
+<tr>
+<td>
+<tt>vis.on_label_dominated( const Label&amp; l, const Graph&amp; g )</tt>
+</td>
+</tr>
+<tr>
+<td>
+<tt>vis.on_label_not_dominated( const Label&amp; l, const Graph&amp; g )</tt>
+</td>
+</tr>
+</table>
+See the description of the Label concept for the interface of a Label. See the algorithm description for information on when these functions are called.
+<p>
+
+<a name="FunctionsDescription"><h3>Functions Description</h3></a>
+
+<p>
+The functions are an implementation of a priority-queue-based label-setting algorithm. At each iteration, the algorithm picks a label <i>l</i> from a priority queue (the set of unprocessed labels) and checks it for dominance against the current set of labels at the vertex <i>i</i> where <i>l</i> resides. If <i>l</i> is dominated by some other label residing at <i>i</i>, <i>l</i> is deleted from the set of labels residing at <i>i</i>. If <i>l</i> is undominated, it is extended along all out-edges of <i>i</i>. Each resulting new label is checked for feasibility, and if it is feasible, it is added to the set of unprocessed labels and to the set of labels residing at the respective successor vertex of <i>i</i>. If a new label is not feasible, it is discarded. The algorithm stops when there are no more unprocessed labels. It then checks whether the destination vertex could be reached (which may not be the case even for a strongly connected graph because of the resource constraints), constructs one or all Pareto-
optimal (i.e., undominated) <i>s</i>-<i>t</i>-path(s) and returns. A pseudo-code of the algorithm follows.
+</p>
+
+<pre>
+r_c_shortest_paths( g,
+                    vertex_index_map,
+                    edge_index_map,
+                    s,
+                    t,
+                    pareto_optimal_solutions,
+                    pareto_optimal_resource_containers,
+                    rc,
+                    ref,
+                    dominance,
+                    la,
+                    vis )
+{
+  Label first_label, cur_label, new_label
+  Set of Labels unprocessed_labels, labels_cur_vertex
+  initialize first_label with rc
+  INSERT(unprocessed_labels, first_label)
+  <b>while</b>(unprocessed_labels != &Oslash;)
+    cur_label := EXTRACTMIN(unprocessed_labels)                      &#9665; vis.on_label_popped(cur_label)
+    <b>if</b>(cur_label is not dominated)
+      vertex i = ResidentVertex(cur_label)
+      perform pairwise dominance check over labels resident at i
+      mark all dominated labels as dominated
+      DELETE all labels which are dominated AND processed
+    <b>if</b>(cur_label is not dominated)                                   &#9665; vis.on_label_not_dominated(cur_label)
+      mark cur_label as processed
+      <b>for each</b> arc (i, j) in the forward star of i
+        new_label := ref(cur_label)
+        <b>if</b>(new_label is not feasible)                                &#9665; vis.on_label_not_feasible(new_label)
+          DELETE(new_label)
+        <b>else</b>                                                         &#9665; vis.on_label_feasible(new_label)
+          INSERT(unprocessed_labels, new_label)
+          INSERT(set of labels resident at j,new_label)
+    <b>else</b>                                                             &#9665; vis.on_label_dominated(cur_label)
+      DELETE(cur_label)
+  <b>if</b>(t could be reached from s)
+    <b>for each</b> label resident at t
+      INSERT(pareto_optimal_resource_containers, label.resource_container)
+      recursively construct pareto_optimal_path
+      INSERT(pareto_optimal_solutions, pareto_optimal_path)
+      <b>if</b>(only one Pareto-optimal solution is sought)
+        BREAK
+}
+</pre>
+
+<h3>Where Defined</h3>
+
+boost/graph/r_c_shortest_paths.hpp
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph&amp; g</tt>
+<blockquote>
+The graph object on which the algorithm is applied. The type <tt>Graph</tt> must be directed and must be a model of Incidence Graph and PropertyGraph.
+</blockquote>
+IN: <tt>const VertexIndexMap&amp; vertex_index_map</tt>
+<blockquote>
+A ReadablePropertyMap mapping vertex descriptors to integers in [0, <tt>num_vertices(g)</tt>).
+</blockquote>
+IN: <tt>const EdgeIndexMap&amp; edge_index_map</tt>
+<blockquote>
+A ReadablePropertyMap mapping edge descriptors to integers in [0, <tt>num_edges(g)</tt>).
+</blockquote>
+IN: <tt>typename graph_traits&lt;Graph&gt;::vertex_descriptor s</tt>
+<blockquote>
+A vertex descriptor describing the start vertex of the path.
+</blockquote>
+IN: <tt>typename graph_traits&lt;Graph&gt;::vertex_descriptor t</tt>
+<blockquote>
+A vertex descriptor describing the end vertex of the path.
+</blockquote>
+OUT: <tt>std::vector&lt;std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt; &gt;&amp;
+pareto_optimal_solutions</tt>
+<blockquote>
+A container for storing the Pareto-optimal (undominated) solutions (<i>s</i>-<i>t</i>-paths) in the overloads where all Pareto-optimal solutions are returned. The paths are returned as sequences of edge descriptors in reverse order (from <tt>t</tt> to <tt>s</tt>).
+</blockquote>
+OUT: <tt>std::vector&lt;Resource_Container&gt;&amp; pareto_optimal_resource_containers</tt>
+<blockquote>
+A container for storing the Pareto-optimal resource containers in the overloads where all Pareto-optimal solutions are returned.
+</blockquote>
+OUT: <tt>std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt;&amp; 
+pareto_optimal_solution</tt>
+<blockquote>
+A container for storing the first Pareto-optimal (undominated) solution (<i>s</i>-<i>t</i>-path) in the overloads where only one Pareto-optimal solution is returned. The path is returned as a sequence of edge descriptors in reverse order (from <tt>t</tt> to <tt>s</tt>).
+</blockquote>
+OUT: <tt>Resource_Container&amp; pareto_optimal_resource_container</tt>
+<blockquote>
+A <tt>Resource_Container</tt> object for storing the Pareto-optimal resource container corresponding to the first Pareto-optimal path in the overloads where only one Pareto-optimal solution is returned.
+</blockquote>
+IN: <tt>const Resource_Container&amp; rc</tt>
+<blockquote>
+An object specifying the initial resource consumptions at vertex <tt>s</tt>. The type <tt>Resource_Container</tt> must be a model of the ResourceContainer concept.
+</blockquote>
+IN: <tt>Resource_Extension_Function&amp; ref</tt>
+<blockquote>
+A function object or function pointer or function specifying how a label is to be extended along an arc. The type <tt>Resource_Extension_Function</tt> must be a model of the ResourceExtensionFunction concept.
+</blockquote>
+IN: <tt>Dominance_Function&amp; dominance</tt>
+<blockquote>
+A function object or function pointer or function specifying a dominance relation between two labels. The type <tt>Dominance_Function</tt> must be a model of the DominanceFunction concept.
+</blockquote>
+IN: <tt>Label_Allocator la</tt>
+<blockquote>
+An object of type <tt>Label_Allocator</tt> specifying a strategy for the memory management of the labels. It must offer the same interface as <tt>std::allocator<lt;r_c_shortest_paths_label&lt;Graph, Resource_Container&gt; &gt;</tt>. There is a default type <tt>default_r_c_shortest_paths_allocator</tt> for this parameter using the STL standard allocator. If the third or the fourth overload of the function is used, an object of this type is used as <tt>Label_Allocator</tt> parameter. If the first or the second overload is used, one must specify both a <tt>Label_Allocator</tt> and a <tt>Visitor</tt> parameter. If one wants to develop a user-defined type only for <tt>Visitor</tt>, one can use <tt>default_r_c_shortest_paths_allocator</tt> as <tt>Label_Allocator</tt> parameter. If one wants to use a specialized allocator, one can specify an arbitrary type as template parameter for the value type to the allocator; it is rebound to the correct type.
+</blockquote>
+IN: <tt>Visitor vis</tt>
+<blockquote>
+A visitor object specifying what operations are to be performed at the event points in the algorithm. The type <tt>Visitor</tt> must be a model of the ResourceConstrainedShortestPathsVisitor concept. There is a default type <tt>default_r_c_shortest_paths_visitor</tt> for this parameter with empty function bodies. If the third or the fourth overload of the function is used, an object of this type is used as <tt>Visitor</tt> parameter. If the first or the second overload is used, one must specify both a <tt>Label_Allocator</tt> and a <tt>Visitor</tt> parameter. If one wants to use only a specialized allocator, one can use <tt>default_r_c_shortest_paths_visitor</tt> as <tt>Visitor</tt> parameter.
+</blockquote>
+
+<h4>Preconditions</h4>
+
+<ul>
+<li>
+<tt>s</tt> and <tt>t</tt> are valid vertex descriptors for <tt>g</tt>.
+<li>
+<tt>rc</tt> is within the resource windows at <tt>s</tt>, i.e., it constitutes a feasible <tt>Resource_Container</tt> object at <tt>s</tt> (see discussion).
+</ul>
+
+<h4>Throws</h4>
+
+<p>
+The function itself does not throw any exceptions. However, depending on the template parameters, exceptions may be thrown from within the function.
+</p>
+
+<h4>Complexity</h4>
+
+<p>
+The time complexity is problem-dependent. For a non-elementary problem or for a problem on a graph without negative cycles, the complexity is polynomial in the number of vertices and edges and a term dependent on the resources and resource extension functions used. For the elementary problem on a graph with negative cycles, the complexity is exponential in the number of vertices and edges and a term dependent on the resources and resource extension functions used.
+</p>
+
+<a name="Discussion"><h3>Discussion</h3></a>
+
+<p>
+The function leaves a lot of work to the user. It is almost like a small framework for SPPRCs. This, however, is a property inherent to the problem. It is entirely up to the user to make sure that he stores the &lsquo;right&rsquo; resources in his resource container object, that the resource extension function extends a label in the desired way, and that the dominance function declares the &lsquo;right&rsquo; labels as dominated and not dominated. In particular, the precondition that the initial ResourceContainer object supplied to the function must be feasible is as important as it is unpleasant. The implementation does not check this and, hence, sacrifices comfort for genericity here. It was a design decision not to make any assumptions with respect to the relationship between the type modelling ResourceContainer and the vertex properties of the graph type.
+</p>
+
+<p>
+In case the underlying graph does not contain negative cycles (cycles with overall negative resource consumption for the unconstrained resource whose consumption is to be minimized, such as cost or distance), the resulting paths will always be elementary, i.e., without repetitions of vertices. In the presence of negative cycles, the algorithm is finite if there is at least one strictly increasing resource, i.e., one resource with strictly positive resource consumption on all arcs (this is a sufficient condition). Otherwise, one must provide a customized type for the ResourceContainer concept to ensure finiteness. See, for example<br>
+Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C. (2004):<br>
+An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints: Application to Some Vehicle Routing Problems<br>
+Networks, vol. 44, pp. 216&ndash;229.
+</p>
+
+<p>
+Experience shows that for &lsquo;small&rsquo; resource containers, it may be useful to try a specialized small object allocator, e.g., from the Boost Pool library. For larger resource containers (i.e., for a large number of resources), the default allocator is the right choice.
+</p>
+
+<p>
+There is a utility function called <tt>check_path</tt> that can be used for debugging purposes, if <tt>r_c_shortest_paths</tt> returns a path as feasible and Pareto-optimal and the user is of the opinion that the path is either infeasible or not optimal:
+<pre>
+template&lt;class Graph,
+         class Resource_Container,
+         class Resource_Extension_Function&gt;
+void check_r_c_path( const Graph&amp; g,
+                     const std::vector&lt;typename graph_traits&lt;Graph&gt;::edge_descriptor&gt;&amp; ed_vec_path,
+                     const Resource_Container&amp; initial_resource_levels,
+                     bool b_result_must_be_equal_to_desired_final_resource_levels,
+                     const Resource_Container&amp; desired_final_resource_levels,
+                     Resource_Container&amp; actual_final_resource_levels,
+                     const Resource_Extension_Function&amp; ref,
+                     bool&amp; b_is_a_path_at_all,
+                     bool&amp; b_feasible,
+                     bool&amp; b_correctly_extended,
+                     typename graph_traits&lt;Graph&gt;::edge_descriptor&amp;
+                     ed_last_extended_arc )
+</pre>
+</p>
+
+The boolean parameters have the following meaning:
+<ul>
+<li>
+If <tt>b_result_must_be_equal_to_desired_final_resource_levels==true</tt>, computed accumulated final resource levels must be equal to <tt>desired_final_resource_levels</tt>.
+<li>
+If <tt>b_result_must_be_equal_to_desired_final_resource_levels==false</tt>, computed accumulated final resource levels must be less than or equal to <tt>desired_final_resource_levels</tt>.
+<li>
+<tt>b_is_a_path_at_all==true</tt> if and only if <tt>ed_vec_path</tt> specifies a walk in a graph-theoretical sense, i.e., a sequence of arcs where the target of an arc is the source of the next arc, or a reverse walk, where the source of one arc is the target of the next arc. Note that in the world of resource-constrained shortest paths, a path need not be elementary: Repetitions of vertices or arcs are allowed. When the graph does not have any cycles of negative cost (traversal cost, travel time etc.), the paths returned by <tt>r_c_shortest_paths</tt> will be elementary. Otherwise, one must use appropriate resource containers and resource extension and dominance functions (see the abovementioned references).
+<li>
+<tt>b_feasible==true</tt> if and only if <tt>b_is_a_path_at_all==true</tt> and all resource windows at all vertices along the path are maintained.
+<li>
+When <tt>b_result_must_be_equal_to_desired_final_resource_levels==true</tt> (<tt>false</tt>), <tt>b_correctly_extended==true</tt> if and only if <tt>b_feasible==true</tt> and the computed resource levels at the end of the path are equal to (less than or equal to) the desired final resource levels as specified in <tt>desired_final_resource_levels</tt>.
+</ul>
+
+<p>
+<tt>ed_last_extended_arc</tt> stores the edge descriptor of the last extended arc. If <tt>ed_vec_path</tt> is a path of positive length and <tt>b_feasible==false</tt>, <tt>ed_last_extended_arc</tt> is the edge descriptor of the arc at whose target vertex the first violation of a resource window occured.
+</p>
+
+<h3>Examples</h3>
+
+<p>
+The file <a href="../example/r_c_shortest_paths_example.cpp">
+<rr>example/r_c_shortest_paths_example.cpp</tt></a> provides examples for how SPPRCs can be solved with the <tt>r_c_shortest_paths</tt> functions. There is an example for an SPP without resource constraints and an example for a shortest path problem with time windows.<br>
+It is obvious that one would not use the algorithm for SPPs without resource constraints, because there are faster algorithms for this problem, but one would expect a code for the SPP with resource constraints to be able to handle such a case.
+</p>
+
+<br>
+<hr>
+<table>
+<tr valign=top>
+<td
+nowrap>Copyright &copy 2006</td>
+<td>
+Michael Drexl (michaeldrexl at web dot de)
+</td></tr></table>
+
+</body>
+</html>

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html	(original)
+++ trunk/libs/graph/doc/table_of_contents.html	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -143,6 +143,7 @@
                     <LI><A
                     href="./johnson_all_pairs_shortest.html"><tt>johnson_all_pairs_shortest_paths</tt></A>
                     <li>floyd_warshall_all_pairs_shortest_paths</li>
+                    <li>r_c_shortest_paths - resource-constrained shortest paths</li>
                   </OL>
                 <LI>Minimum Spanning Tree Algorithms
                   <OL>

Added: trunk/libs/graph/example/r_c_shortest_paths_example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/r_c_shortest_paths_example.cpp	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -0,0 +1,354 @@
+// 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)
+
+// Example use of the resource-constrained shortest paths algorithm.
+#include <boost/config.hpp>
+
+#ifdef BOOST_MSVC
+#  pragma warning(disable: 4267)
+#endif
+
+#include <boost/graph/adjacency_list.hpp>
+
+#include <boost/graph/r_c_shortest_paths.hpp>
+#include <iostream>
+
+using namespace boost;
+
+struct SPPRC_Example_Graph_Vert_Prop
+{
+  SPPRC_Example_Graph_Vert_Prop( int n = 0, int e = 0, int l = 0 ) 
+  : num( n ), eat( e ), lat( l ) {}
+  int num;
+  // earliest arrival time
+  int eat;
+  // latest arrival time
+  int lat;
+};
+
+struct SPPRC_Example_Graph_Arc_Prop
+{
+  SPPRC_Example_Graph_Arc_Prop( int n = 0, int c = 0, int t = 0 ) 
+  : num( n ), cost( c ), time( t ) {}
+  int num;
+  // traversal cost
+  int cost;
+  // traversal time
+  int time;
+};
+
+typedef adjacency_list<vecS, 
+                       vecS, 
+                       directedS, 
+                       SPPRC_Example_Graph_Vert_Prop, 
+                       SPPRC_Example_Graph_Arc_Prop> 
+  SPPRC_Example_Graph;
+
+// data structures for spp without resource constraints:
+// ResourceContainer model
+struct spp_no_rc_res_cont
+{
+  spp_no_rc_res_cont( int c = 0 ) : cost( c ) {};
+  spp_no_rc_res_cont& operator=( const spp_no_rc_res_cont& other )
+  {
+    if( this == &other )
+      return *this;
+    this->~spp_no_rc_res_cont();
+    new( this ) spp_no_rc_res_cont( other );
+    return *this;
+  }
+  int cost;
+};
+
+bool operator==( const spp_no_rc_res_cont& res_cont_1, 
+                 const spp_no_rc_res_cont& res_cont_2 )
+{
+  return ( res_cont_1.cost == res_cont_2.cost );
+}
+
+bool operator<( const spp_no_rc_res_cont& res_cont_1, 
+                const spp_no_rc_res_cont& res_cont_2 )
+{
+  return ( res_cont_1.cost < res_cont_2.cost );
+}
+
+// ResourceExtensionFunction model
+class ref_no_res_cont
+{
+public:
+  inline bool operator()( const SPPRC_Example_Graph& g, 
+                          spp_no_rc_res_cont& new_cont, 
+                          const spp_no_rc_res_cont& old_cont, 
+                          graph_traits
+                            <SPPRC_Example_Graph>::edge_descriptor ed ) const
+  {
+    new_cont.cost = old_cont.cost + g[ed].cost;
+    return true;
+  }
+};
+
+// DominanceFunction model
+class dominance_no_res_cont
+{
+public:
+  inline bool operator()( const spp_no_rc_res_cont& res_cont_1, 
+                          const spp_no_rc_res_cont& res_cont_2 ) const
+  {
+    // must be "<=" here!!!
+    // must NOT be "<"!!!
+    return res_cont_1.cost <= res_cont_2.cost;
+    // this is not a contradiction to the documentation
+    // the documentation says:
+    // "A label $l_1$ dominates a label $l_2$ if and only if both are resident 
+    // at the same vertex, and if, for each resource, the resource consumption 
+    // of $l_1$ is less than or equal to the resource consumption of $l_2$, 
+    // and if there is at least one resource where $l_1$ has a lower resource 
+    // consumption than $l_2$."
+    // one can think of a new label with a resource consumption equal to that 
+    // of an old label as being dominated by that old label, because the new 
+    // one will have a higher number and is created at a later point in time, 
+    // so one can implicitly use the number or the creation time as a resource 
+    // for tie-breaking
+  }
+};
+// end data structures for spp without resource constraints:
+
+// data structures for shortest path problem with time windows (spptw)
+// ResourceContainer model
+struct spp_spptw_res_cont
+{
+  spp_spptw_res_cont( int c = 0, int t = 0 ) : cost( c ), time( t ) {}
+  spp_spptw_res_cont& operator=( const spp_spptw_res_cont& other )
+  {
+    if( this == &other )
+      return *this;
+    this->~spp_spptw_res_cont();
+    new( this ) spp_spptw_res_cont( other );
+    return *this;
+  }
+  int cost;
+  int time;
+};
+
+bool operator==( const spp_spptw_res_cont& res_cont_1, 
+                 const spp_spptw_res_cont& res_cont_2 )
+{
+  return ( res_cont_1.cost == res_cont_2.cost 
+           && res_cont_1.time == res_cont_2.time );
+}
+
+bool operator<( const spp_spptw_res_cont& res_cont_1, 
+                const spp_spptw_res_cont& res_cont_2 )
+{
+  if( res_cont_1.cost > res_cont_2.cost )
+    return false;
+  if( res_cont_1.cost == res_cont_2.cost )
+    return res_cont_1.time < res_cont_2.time;
+  return true;
+}
+
+// ResourceExtensionFunction model
+class ref_spptw
+{
+public:
+  inline bool operator()( const SPPRC_Example_Graph& g, 
+                          spp_spptw_res_cont& new_cont, 
+                          const spp_spptw_res_cont& old_cont, 
+                          graph_traits
+                            <SPPRC_Example_Graph>::edge_descriptor ed ) const
+  {
+    const SPPRC_Example_Graph_Arc_Prop& arc_prop = 
+      get( edge_bundle, g )[ed];
+    const SPPRC_Example_Graph_Vert_Prop& vert_prop = 
+      get( vertex_bundle, g )[target( ed, g )];
+    new_cont.cost = old_cont.cost + arc_prop.cost;
+    int& i_time = new_cont.time;
+    i_time = old_cont.time + arc_prop.time;
+    i_time < vert_prop.eat ? i_time = vert_prop.eat : 0;
+    return i_time <= vert_prop.lat ? true : false;
+  }
+};
+
+// DominanceFunction model
+class dominance_spptw
+{
+public:
+  inline bool operator()( const spp_spptw_res_cont& res_cont_1, 
+                          const spp_spptw_res_cont& res_cont_2 ) const
+  {
+    // must be "<=" here!!!
+    // must NOT be "<"!!!
+    return res_cont_1.cost <= res_cont_2.cost 
+           && res_cont_1.time <= res_cont_2.time;
+    // this is not a contradiction to the documentation
+    // the documentation says:
+    // "A label $l_1$ dominates a label $l_2$ if and only if both are resident 
+    // at the same vertex, and if, for each resource, the resource consumption 
+    // of $l_1$ is less than or equal to the resource consumption of $l_2$, 
+    // and if there is at least one resource where $l_1$ has a lower resource 
+    // consumption than $l_2$."
+    // one can think of a new label with a resource consumption equal to that 
+    // of an old label as being dominated by that old label, because the new 
+    // one will have a higher number and is created at a later point in time, 
+    // so one can implicitly use the number or the creation time as a resource 
+    // for tie-breaking
+  }
+};
+// end data structures for shortest path problem with time windows (spptw)
+
+// example graph structure and cost from 
+// http://www.boost.org/libs/graph/example/dijkstra-example.cpp
+const int num_nodes = 5;
+enum nodes { A, B, C, D, E };
+char name[] = "ABCDE";
+
+int main()
+{
+  SPPRC_Example_Graph g;
+
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( A, 0, 0 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( B, 5, 20 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( C, 6, 10 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( D, 3, 12 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( E, 0, 100 ), g );
+
+  add_edge( A, C, SPPRC_Example_Graph_Arc_Prop( 0, 1, 5 ), g );
+  add_edge( B, B, SPPRC_Example_Graph_Arc_Prop( 1, 2, 5 ), g );
+  add_edge( B, D, SPPRC_Example_Graph_Arc_Prop( 2, 1, 2 ), g );
+  add_edge( B, E, SPPRC_Example_Graph_Arc_Prop( 3, 2, 7 ), g );
+  add_edge( C, B, SPPRC_Example_Graph_Arc_Prop( 4, 7, 3 ), g );
+  add_edge( C, D, SPPRC_Example_Graph_Arc_Prop( 5, 3, 8 ), g );
+  add_edge( D, E, SPPRC_Example_Graph_Arc_Prop( 6, 1, 3 ), g );
+  add_edge( E, A, SPPRC_Example_Graph_Arc_Prop( 7, 1, 5 ), g );
+  add_edge( E, B, SPPRC_Example_Graph_Arc_Prop( 8, 1, 4 ), g );
+
+
+  // the unique shortest path from A to E in the dijkstra-example.cpp is 
+  // A -> C -> D -> E
+  // its length is 5
+  // the following code also yields this result
+
+  // with the above time windows, this path is infeasible
+  // now, there are two shortest paths that are also feasible with respect to 
+  // the vertex time windows:
+  // A -> C -> B -> D -> E and 
+  // A -> C -> B -> E
+  // however, the latter has a longer total travel time and is therefore not 
+  // pareto-optimal, i.e., it is dominated by the former path
+  // therefore, the code below returns only the former path
+
+  // spp without resource constraints
+  graph_traits<SPPRC_Example_Graph>::vertex_descriptor s = A;
+  graph_traits<SPPRC_Example_Graph>::vertex_descriptor t = E;
+
+  std::vector
+    <std::vector
+      <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > 
+        opt_solutions;
+  std::vector<spp_no_rc_res_cont> pareto_opt_rcs_no_rc;
+
+  r_c_shortest_paths
+  ( g, 
+    get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
+    get( &SPPRC_Example_Graph_Arc_Prop::num, g ), 
+    s, 
+    t, 
+    opt_solutions, 
+    pareto_opt_rcs_no_rc, 
+    spp_no_rc_res_cont( 0 ), 
+    ref_no_res_cont(), 
+    dominance_no_res_cont(), 
+    std::allocator
+      <r_c_shortest_paths_label
+        <SPPRC_Example_Graph, spp_no_rc_res_cont> >(), 
+    default_r_c_shortest_paths_visitor() );
+
+  std::cout << "SPP without resource constraints:" << std::endl;
+  std::cout << "Number of optimal solutions: ";
+  std::cout << static_cast<int>( opt_solutions.size() ) << std::endl;
+  for( int i = 0; i < static_cast<int>( opt_solutions.size() ); ++i )
+  {
+    std::cout << "The " << i << "th shortest path from A to E is: ";
+    std::cout << std::endl;
+    for( int j = static_cast<int>( opt_solutions[i].size() ) - 1; j >= 0; --j )
+      std::cout << name[source( opt_solutions[i][j], g )] << std::endl;
+    std::cout << "E" << std::endl;
+    std::cout << "Length: " << pareto_opt_rcs_no_rc[i].cost << std::endl;
+  }
+  std::cout << std::endl;
+
+  // spptw
+  std::vector
+    <std::vector
+      <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > 
+        opt_solutions_spptw;
+  std::vector<spp_spptw_res_cont> pareto_opt_rcs_spptw;
+
+  r_c_shortest_paths
+  ( g, 
+    get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
+    get( &SPPRC_Example_Graph_Arc_Prop::num, g ), 
+    s, 
+    t, 
+    opt_solutions_spptw, 
+    pareto_opt_rcs_spptw, 
+    spp_spptw_res_cont( 0, 0 ), 
+    ref_spptw(), 
+    dominance_spptw(), 
+    std::allocator
+      <r_c_shortest_paths_label
+        <SPPRC_Example_Graph, spp_spptw_res_cont> >(), 
+          default_r_c_shortest_paths_visitor() );
+
+  std::cout << "SPP with time windows:" << std::endl;
+  std::cout << "Number of optimal solutions: ";
+  std::cout << static_cast<int>( opt_solutions.size() ) << std::endl;
+  for( int i = 0; i < static_cast<int>( opt_solutions.size() ); ++i )
+  {
+    std::cout << "The " << i << "th shortest path from A to E is: ";
+    std::cout << std::endl;
+    for( int j = static_cast<int>( opt_solutions_spptw[i].size() ) - 1; 
+         j >= 0; 
+         --j )
+      std::cout << name[source( opt_solutions_spptw[i][j], g )] << std::endl;
+    std::cout << "E" << std::endl;
+    std::cout << "Length: " << pareto_opt_rcs_spptw[i].cost << std::endl;
+    std::cout << "Time: " << pareto_opt_rcs_spptw[i].time << std::endl;
+  }
+
+  // utility function check_r_c_path example
+  std::cout << std::endl;
+  bool b_is_a_path_at_all = false;
+  bool b_feasible = false; 
+  bool b_correctly_extended = false;
+  spp_spptw_res_cont actual_final_resource_levels( 0, 0 );
+  graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc;
+  check_r_c_path( g, 
+                  opt_solutions_spptw[0], 
+                  spp_spptw_res_cont( 0, 0 ), 
+                  true, 
+                  pareto_opt_rcs_spptw[0], 
+                  actual_final_resource_levels, 
+                  ref_spptw(), 
+                  b_is_a_path_at_all, 
+                  b_feasible, 
+                  b_correctly_extended, 
+                  ed_last_extended_arc );
+  if( !b_is_a_path_at_all )
+    std::cout << "Not a path." << std::endl;
+  if( !b_feasible )
+    std::cout << "Not a feasible path." << std::endl;
+  if( !b_correctly_extended )
+    std::cout << "Not correctly extended." << std::endl;
+  if( b_is_a_path_at_all && b_feasible && b_correctly_extended )
+  {
+    std::cout << "Actual final resource levels:" << std::endl;
+    std::cout << "Length: " << actual_final_resource_levels.cost << std::endl;
+    std::cout << "Time: " << actual_final_resource_levels.time << std::endl;
+    std::cout << "OK." << std::endl;
+  }
+
+  return 0;
+}

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -133,6 +133,8 @@
         ../../system/build
         : $(PLANAR_INPUT_FILES) ]
 
+    [ run r_c_shortest_paths_test.cpp ]
+
     $(optional_tests)
     ;
 

Added: trunk/libs/graph/test/r_c_shortest_paths_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/r_c_shortest_paths_test.cpp	2008-04-22 08:24:25 EDT (Tue, 22 Apr 2008)
@@ -0,0 +1,641 @@
+// 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)
+
+#include <boost/config.hpp>
+
+#ifdef BOOST_MSVC
+#  pragma warning(disable: 4267)
+#endif
+
+#include <boost/graph/adjacency_list.hpp>
+//#include <boost/graph/dijkstra_shortest_paths.hpp>
+
+#include <boost/graph/r_c_shortest_paths.hpp>
+#include <iostream>
+#include <boost/test/minimal.hpp>
+
+using namespace boost;
+
+struct SPPRC_Example_Graph_Vert_Prop
+{
+  SPPRC_Example_Graph_Vert_Prop( int n = 0, int e = 0, int l = 0 ) 
+  : num( n ), eat( e ), lat( l ) {}
+  int num;
+  // earliest arrival time
+  int eat;
+  // latest arrival time
+  int lat;
+};
+
+struct SPPRC_Example_Graph_Arc_Prop
+{
+  SPPRC_Example_Graph_Arc_Prop( int n = 0, int c = 0, int t = 0 ) 
+  : num( n ), cost( c ), time( t ) {}
+  int num;
+  // traversal cost
+  int cost;
+  // traversal time
+  int time;
+};
+
+typedef adjacency_list<vecS, 
+                       vecS, 
+                       directedS, 
+                       SPPRC_Example_Graph_Vert_Prop, 
+                       SPPRC_Example_Graph_Arc_Prop> 
+  SPPRC_Example_Graph;
+
+// data structures for spp without resource constraints:
+// ResourceContainer model
+struct spp_no_rc_res_cont
+{
+  spp_no_rc_res_cont( int c = 0 ) : cost( c ) {};
+  spp_no_rc_res_cont& operator=( const spp_no_rc_res_cont& other )
+  {
+    if( this == &other )
+      return *this;
+    this->~spp_no_rc_res_cont();
+    new( this ) spp_no_rc_res_cont( other );
+    return *this;
+  }
+  int cost;
+};
+
+bool operator==( const spp_no_rc_res_cont& res_cont_1, 
+                 const spp_no_rc_res_cont& res_cont_2 )
+{
+  return ( res_cont_1.cost == res_cont_2.cost );
+}
+
+bool operator<( const spp_no_rc_res_cont& res_cont_1, 
+                const spp_no_rc_res_cont& res_cont_2 )
+{
+  return ( res_cont_1.cost < res_cont_2.cost );
+}
+
+// ResourceExtensionFunction model
+class ref_no_res_cont
+{
+public:
+  inline bool operator()( const SPPRC_Example_Graph& g, 
+                          spp_no_rc_res_cont& new_cont, 
+                          const spp_no_rc_res_cont& old_cont, 
+                          graph_traits
+                            <SPPRC_Example_Graph>::edge_descriptor ed ) const
+  {
+    new_cont.cost = old_cont.cost + g[ed].cost;
+    return true;
+  }
+};
+
+// DominanceFunction model
+class dominance_no_res_cont
+{
+public:
+  inline bool operator()( const spp_no_rc_res_cont& res_cont_1, 
+                          const spp_no_rc_res_cont& res_cont_2 ) const
+  {
+    // must be "<=" here!!!
+    // must NOT be "<"!!!
+    return res_cont_1.cost <= res_cont_2.cost;
+    // this is not a contradiction to the documentation
+    // the documentation says:
+    // "A label $l_1$ dominates a label $l_2$ if and only if both are resident 
+    // at the same vertex, and if, for each resource, the resource consumption 
+    // of $l_1$ is less than or equal to the resource consumption of $l_2$, 
+    // and if there is at least one resource where $l_1$ has a lower resource 
+    // consumption than $l_2$."
+    // one can think of a new label with a resource consumption equal to that 
+    // of an old label as being dominated by that old label, because the new 
+    // one will have a higher number and is created at a later point in time, 
+    // so one can implicitly use the number or the creation time as a resource 
+    // for tie-breaking
+  }
+};
+// end data structures for spp without resource constraints:
+
+// data structures for shortest path problem with time windows (spptw)
+// ResourceContainer model
+struct spp_spptw_res_cont
+{
+  spp_spptw_res_cont( int c = 0, int t = 0 ) : cost( c ), time( t ) {}
+  spp_spptw_res_cont& operator=( const spp_spptw_res_cont& other )
+  {
+    if( this == &other )
+      return *this;
+    this->~spp_spptw_res_cont();
+    new( this ) spp_spptw_res_cont( other );
+    return *this;
+  }
+  int cost;
+  int time;
+};
+
+bool operator==( const spp_spptw_res_cont& res_cont_1, 
+                 const spp_spptw_res_cont& res_cont_2 )
+{
+  return ( res_cont_1.cost == res_cont_2.cost 
+           && res_cont_1.time == res_cont_2.time );
+}
+
+bool operator<( const spp_spptw_res_cont& res_cont_1, 
+                const spp_spptw_res_cont& res_cont_2 )
+{
+  if( res_cont_1.cost > res_cont_2.cost )
+    return false;
+  if( res_cont_1.cost == res_cont_2.cost )
+    return res_cont_1.time < res_cont_2.time;
+  return true;
+}
+
+// ResourceExtensionFunction model
+class ref_spptw
+{
+public:
+  inline bool operator()( const SPPRC_Example_Graph& g, 
+                          spp_spptw_res_cont& new_cont, 
+                          const spp_spptw_res_cont& old_cont, 
+                          graph_traits
+                            <SPPRC_Example_Graph>::edge_descriptor ed ) const
+  {
+    const SPPRC_Example_Graph_Arc_Prop& arc_prop = 
+      get( edge_bundle, g )[ed];
+    const SPPRC_Example_Graph_Vert_Prop& vert_prop = 
+      get( vertex_bundle, g )[target( ed, g )];
+    new_cont.cost = old_cont.cost + arc_prop.cost;
+    int& i_time = new_cont.time;
+    i_time = old_cont.time + arc_prop.time;
+    i_time < vert_prop.eat ? i_time = vert_prop.eat : 0;
+    return i_time <= vert_prop.lat ? true : false;
+  }
+};
+
+// DominanceFunction model
+class dominance_spptw
+{
+public:
+  inline bool operator()( const spp_spptw_res_cont& res_cont_1, 
+                          const spp_spptw_res_cont& res_cont_2 ) const
+  {
+    // must be "<=" here!!!
+    // must NOT be "<"!!!
+    return res_cont_1.cost <= res_cont_2.cost 
+           && res_cont_1.time <= res_cont_2.time;
+    // this is not a contradiction to the documentation
+    // the documentation says:
+    // "A label $l_1$ dominates a label $l_2$ if and only if both are resident 
+    // at the same vertex, and if, for each resource, the resource consumption 
+    // of $l_1$ is less than or equal to the resource consumption of $l_2$, 
+    // and if there is at least one resource where $l_1$ has a lower resource 
+    // consumption than $l_2$."
+    // one can think of a new label with a resource consumption equal to that 
+    // of an old label as being dominated by that old label, because the new 
+    // one will have a higher number and is created at a later point in time, 
+    // so one can implicitly use the number or the creation time as a resource 
+    // for tie-breaking
+  }
+};
+// end data structures for shortest path problem with time windows (spptw)
+
+int test_main(int argc, char* argv[])
+{
+  SPPRC_Example_Graph g;
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000000000 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 56, 142 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 1000000000 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 89, 178 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 4, 0, 1000000000 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 5, 49, 76 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 6, 0, 1000000000 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 7, 98, 160 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 8, 0, 1000000000 ), g );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 9, 90, 158 ), g );
+  add_edge( 0, 7, SPPRC_Example_Graph_Arc_Prop( 6, 33, 2 ), g );
+  add_edge( 0, 6, SPPRC_Example_Graph_Arc_Prop( 5, 31, 6 ), g );
+  add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 3, 14, 4 ), g );
+  add_edge( 0, 1, SPPRC_Example_Graph_Arc_Prop( 0, 43, 8 ), g );
+  add_edge( 0, 4, SPPRC_Example_Graph_Arc_Prop( 4, 28, 10 ), g );
+  add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 1, 31, 10 ), g );
+  add_edge( 0, 3, SPPRC_Example_Graph_Arc_Prop( 2, 1, 7 ), g );
+  add_edge( 0, 9, SPPRC_Example_Graph_Arc_Prop( 7, 25, 9 ), g );
+  add_edge( 1, 0, SPPRC_Example_Graph_Arc_Prop( 8, 37, 4 ), g );
+  add_edge( 1, 6, SPPRC_Example_Graph_Arc_Prop( 9, 7, 3 ), g );
+  add_edge( 2, 6, SPPRC_Example_Graph_Arc_Prop( 12, 6, 7 ), g );
+  add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 10, 13, 7 ), g );
+  add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 11, 49, 9 ), g );
+  add_edge( 2, 8, SPPRC_Example_Graph_Arc_Prop( 13, 47, 5 ), g );
+  add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 17, 5, 10 ), g );
+  add_edge( 3, 1, SPPRC_Example_Graph_Arc_Prop( 15, 47, 1 ), g );
+  add_edge( 3, 2, SPPRC_Example_Graph_Arc_Prop( 16, 26, 9 ), g );
+  add_edge( 3, 9, SPPRC_Example_Graph_Arc_Prop( 21, 24, 10 ), g );
+  add_edge( 3, 7, SPPRC_Example_Graph_Arc_Prop( 20, 50, 10 ), g );
+  add_edge( 3, 0, SPPRC_Example_Graph_Arc_Prop( 14, 41, 4 ), g );
+  add_edge( 3, 6, SPPRC_Example_Graph_Arc_Prop( 19, 6, 1 ), g );
+  add_edge( 3, 4, SPPRC_Example_Graph_Arc_Prop( 18, 8, 1 ), g );
+  add_edge( 4, 5, SPPRC_Example_Graph_Arc_Prop( 26, 38, 4 ), g );
+  add_edge( 4, 9, SPPRC_Example_Graph_Arc_Prop( 27, 32, 10 ), g );
+  add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 24, 40, 3 ), g );
+  add_edge( 4, 0, SPPRC_Example_Graph_Arc_Prop( 22, 7, 3 ), g );
+  add_edge( 4, 3, SPPRC_Example_Graph_Arc_Prop( 25, 28, 9 ), g );
+  add_edge( 4, 2, SPPRC_Example_Graph_Arc_Prop( 23, 39, 6 ), g );
+  add_edge( 5, 8, SPPRC_Example_Graph_Arc_Prop( 32, 6, 2 ), g );
+  add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 30, 26, 10 ), g );
+  add_edge( 5, 0, SPPRC_Example_Graph_Arc_Prop( 28, 38, 9 ), g );
+  add_edge( 5, 2, SPPRC_Example_Graph_Arc_Prop( 31, 48, 10 ), g );
+  add_edge( 5, 9, SPPRC_Example_Graph_Arc_Prop( 33, 49, 2 ), g );
+  add_edge( 5, 1, SPPRC_Example_Graph_Arc_Prop( 29, 22, 7 ), g );
+  add_edge( 6, 1, SPPRC_Example_Graph_Arc_Prop( 34, 15, 7 ), g );
+  add_edge( 6, 7, SPPRC_Example_Graph_Arc_Prop( 35, 20, 3 ), g );
+  add_edge( 7, 9, SPPRC_Example_Graph_Arc_Prop( 40, 1, 3 ), g );
+  add_edge( 7, 0, SPPRC_Example_Graph_Arc_Prop( 36, 23, 5 ), g );
+  add_edge( 7, 6, SPPRC_Example_Graph_Arc_Prop( 38, 36, 2 ), g );
+  add_edge( 7, 6, SPPRC_Example_Graph_Arc_Prop( 39, 18, 10 ), g );
+  add_edge( 7, 2, SPPRC_Example_Graph_Arc_Prop( 37, 2, 1 ), g );
+  add_edge( 8, 5, SPPRC_Example_Graph_Arc_Prop( 46, 36, 5 ), g );
+  add_edge( 8, 1, SPPRC_Example_Graph_Arc_Prop( 42, 13, 10 ), g );
+  add_edge( 8, 0, SPPRC_Example_Graph_Arc_Prop( 41, 40, 5 ), g );
+  add_edge( 8, 1, SPPRC_Example_Graph_Arc_Prop( 43, 32, 8 ), g );
+  add_edge( 8, 6, SPPRC_Example_Graph_Arc_Prop( 47, 25, 1 ), g );
+  add_edge( 8, 2, SPPRC_Example_Graph_Arc_Prop( 44, 44, 3 ), g );
+  add_edge( 8, 3, SPPRC_Example_Graph_Arc_Prop( 45, 11, 9 ), g );
+  add_edge( 9, 0, SPPRC_Example_Graph_Arc_Prop( 48, 41, 5 ), g );
+  add_edge( 9, 1, SPPRC_Example_Graph_Arc_Prop( 49, 44, 7 ), g );
+  
+  // spp without resource constraints
+
+  std::vector
+    <std::vector
+      <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > 
+        opt_solutions;
+  std::vector<spp_no_rc_res_cont> pareto_opt_rcs_no_rc;
+  std::vector<int> i_vec_opt_solutions_spp_no_rc;
+  //std::cout << "r_c_shortest_paths:" << std::endl;
+  for( int s = 0; s < 10; ++s )
+  {
+    for( int t = 0; t < 10; ++t )
+    {
+      r_c_shortest_paths
+      ( g, 
+        get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
+        get( &SPPRC_Example_Graph_Arc_Prop::num, g ), 
+        s, 
+        t, 
+        opt_solutions, 
+        pareto_opt_rcs_no_rc, 
+        spp_no_rc_res_cont( 0 ), 
+        ref_no_res_cont(), 
+        dominance_no_res_cont(), 
+        std::allocator
+          <r_c_shortest_paths_label
+            <SPPRC_Example_Graph, spp_no_rc_res_cont> >(), 
+        default_r_c_shortest_paths_visitor() );
+      i_vec_opt_solutions_spp_no_rc.push_back( pareto_opt_rcs_no_rc[0].cost );
+      //std::cout << "From " << s << " to " << t << ": ";
+      //std::cout << pareto_opt_rcs_no_rc[0].cost << std::endl;
+    }
+  }
+
+  //std::vector<graph_traits<SPPRC_Example_Graph>::vertex_descriptor> 
+  //  p( num_vertices( g ) );
+  //std::vector<int> d( num_vertices( g ) );
+  //std::vector<int> i_vec_dijkstra_distances;
+  //std::cout << "Dijkstra:" << std::endl;
+  //for( int s = 0; s < 10; ++s )
+  //{
+  //  dijkstra_shortest_paths( g, 
+  //                           s, 
+  //                           &p[0], 
+  //                           &d[0], 
+  //                           get( &SPPRC_Example_Graph_Arc_Prop::cost, g ), 
+  //                           get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
+  //                           std::less<int>(), 
+  //                           closed_plus<int>(), 
+  //                           (std::numeric_limits<int>::max)(), 
+  //                           0, 
+  //                           default_dijkstra_visitor() );
+  //  for( int t = 0; t < 10; ++t )
+  //  {
+  //    i_vec_dijkstra_distances.push_back( d[t] );
+  //    std::cout << "From " << s << " to " << t << ": " << d[t] << std::endl;
+  //  }
+  //}
+
+  std::vector<int> i_vec_correct_solutions;
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 22 );
+  i_vec_correct_solutions.push_back( 27 );
+  i_vec_correct_solutions.push_back( 1 );
+  i_vec_correct_solutions.push_back( 6 );
+  i_vec_correct_solutions.push_back( 44 );
+  i_vec_correct_solutions.push_back( 7 );
+  i_vec_correct_solutions.push_back( 27 );
+  i_vec_correct_solutions.push_back( 50 );
+  i_vec_correct_solutions.push_back( 25 );
+  i_vec_correct_solutions.push_back( 37 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 29 );
+  i_vec_correct_solutions.push_back( 38 );
+  i_vec_correct_solutions.push_back( 43 );
+  i_vec_correct_solutions.push_back( 81 );
+  i_vec_correct_solutions.push_back( 7 );
+  i_vec_correct_solutions.push_back( 27 );
+  i_vec_correct_solutions.push_back( 76 );
+  i_vec_correct_solutions.push_back( 28 );
+  i_vec_correct_solutions.push_back( 25 );
+  i_vec_correct_solutions.push_back( 21 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 13 );
+  i_vec_correct_solutions.push_back( 18 );
+  i_vec_correct_solutions.push_back( 56 );
+  i_vec_correct_solutions.push_back( 6 );
+  i_vec_correct_solutions.push_back( 26 );
+  i_vec_correct_solutions.push_back( 47 );
+  i_vec_correct_solutions.push_back( 27 );
+  i_vec_correct_solutions.push_back( 12 );
+  i_vec_correct_solutions.push_back( 21 );
+  i_vec_correct_solutions.push_back( 26 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 5 );
+  i_vec_correct_solutions.push_back( 43 );
+  i_vec_correct_solutions.push_back( 6 );
+  i_vec_correct_solutions.push_back( 26 );
+  i_vec_correct_solutions.push_back( 49 );
+  i_vec_correct_solutions.push_back( 24 );
+  i_vec_correct_solutions.push_back( 7 );
+  i_vec_correct_solutions.push_back( 29 );
+  i_vec_correct_solutions.push_back( 34 );
+  i_vec_correct_solutions.push_back( 8 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 38 );
+  i_vec_correct_solutions.push_back( 14 );
+  i_vec_correct_solutions.push_back( 34 );
+  i_vec_correct_solutions.push_back( 44 );
+  i_vec_correct_solutions.push_back( 32 );
+  i_vec_correct_solutions.push_back( 29 );
+  i_vec_correct_solutions.push_back( 19 );
+  i_vec_correct_solutions.push_back( 26 );
+  i_vec_correct_solutions.push_back( 17 );
+  i_vec_correct_solutions.push_back( 22 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 23 );
+  i_vec_correct_solutions.push_back( 43 );
+  i_vec_correct_solutions.push_back( 6 );
+  i_vec_correct_solutions.push_back( 41 );
+  i_vec_correct_solutions.push_back( 43 );
+  i_vec_correct_solutions.push_back( 15 );
+  i_vec_correct_solutions.push_back( 22 );
+  i_vec_correct_solutions.push_back( 35 );
+  i_vec_correct_solutions.push_back( 40 );
+  i_vec_correct_solutions.push_back( 78 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 20 );
+  i_vec_correct_solutions.push_back( 69 );
+  i_vec_correct_solutions.push_back( 21 );
+  i_vec_correct_solutions.push_back( 23 );
+  i_vec_correct_solutions.push_back( 23 );
+  i_vec_correct_solutions.push_back( 2 );
+  i_vec_correct_solutions.push_back( 15 );
+  i_vec_correct_solutions.push_back( 20 );
+  i_vec_correct_solutions.push_back( 58 );
+  i_vec_correct_solutions.push_back( 8 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 49 );
+  i_vec_correct_solutions.push_back( 1 );
+  i_vec_correct_solutions.push_back( 23 );
+  i_vec_correct_solutions.push_back( 13 );
+  i_vec_correct_solutions.push_back( 37 );
+  i_vec_correct_solutions.push_back( 11 );
+  i_vec_correct_solutions.push_back( 16 );
+  i_vec_correct_solutions.push_back( 36 );
+  i_vec_correct_solutions.push_back( 17 );
+  i_vec_correct_solutions.push_back( 37 );
+  i_vec_correct_solutions.push_back( 0 );
+  i_vec_correct_solutions.push_back( 35 );
+  i_vec_correct_solutions.push_back( 41 );
+  i_vec_correct_solutions.push_back( 44 );
+  i_vec_correct_solutions.push_back( 68 );
+  i_vec_correct_solutions.push_back( 42 );
+  i_vec_correct_solutions.push_back( 47 );
+  i_vec_correct_solutions.push_back( 85 );
+  i_vec_correct_solutions.push_back( 48 );
+  i_vec_correct_solutions.push_back( 68 );
+  i_vec_correct_solutions.push_back( 91 );
+  i_vec_correct_solutions.push_back( 0 );
+  BOOST_CHECK(i_vec_opt_solutions_spp_no_rc.size() == i_vec_correct_solutions.size() );
+  for( int i = 0; i < static_cast<int>( i_vec_correct_solutions.size() ); ++i )
+    BOOST_CHECK( i_vec_opt_solutions_spp_no_rc[i] == i_vec_correct_solutions[i] );
+
+  // spptw
+  std::vector
+    <std::vector
+      <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > 
+        opt_solutions_spptw;
+  std::vector<spp_spptw_res_cont> pareto_opt_rcs_spptw;
+  std::vector
+    <std::vector
+      <std::vector
+        <std::vector
+          <graph_traits<SPPRC_Example_Graph>::edge_descriptor> > > > 
+            vec_vec_vec_vec_opt_solutions_spptw( 10 );
+
+  for( int s = 0; s < 10; ++s )
+  {
+    for( int t = 0; t < 10; ++t )
+    {
+      r_c_shortest_paths
+      ( g, 
+        get( &SPPRC_Example_Graph_Vert_Prop::num, g ), 
+        get( &SPPRC_Example_Graph_Arc_Prop::num, g ), 
+        s, 
+        t, 
+        opt_solutions_spptw, 
+        pareto_opt_rcs_spptw, 
+        // be careful, do not simply take 0 as initial value for time
+        spp_spptw_res_cont( 0, g[s].eat ), 
+        ref_spptw(), 
+        dominance_spptw(), 
+        std::allocator
+          <r_c_shortest_paths_label
+            <SPPRC_Example_Graph, spp_spptw_res_cont> >(), 
+        default_r_c_shortest_paths_visitor() );
+      vec_vec_vec_vec_opt_solutions_spptw[s].push_back( opt_solutions_spptw );
+      if( opt_solutions_spptw.size() )
+      {
+        bool b_is_a_path_at_all = false;
+        bool b_feasible = false; 
+        bool b_correctly_extended = false;
+        spp_spptw_res_cont actual_final_resource_levels( 0, 0 );
+        graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc;
+        check_r_c_path( g, 
+                        opt_solutions_spptw[0], 
+                        spp_spptw_res_cont( 0, g[s].eat ), 
+                        true, 
+                        pareto_opt_rcs_spptw[0], 
+                        actual_final_resource_levels, 
+                        ref_spptw(), 
+                        b_is_a_path_at_all, 
+                        b_feasible, 
+                        b_correctly_extended, 
+                        ed_last_extended_arc );
+        BOOST_CHECK(b_is_a_path_at_all && b_feasible && b_correctly_extended);
+        b_is_a_path_at_all = false;
+        b_feasible = false; 
+        b_correctly_extended = false;
+        spp_spptw_res_cont actual_final_resource_levels2( 0, 0 );
+        graph_traits<SPPRC_Example_Graph>::edge_descriptor ed_last_extended_arc2;
+        check_r_c_path( g, 
+                        opt_solutions_spptw[0], 
+                        spp_spptw_res_cont( 0, g[s].eat ), 
+                        false, 
+                        pareto_opt_rcs_spptw[0], 
+                        actual_final_resource_levels2, 
+                        ref_spptw(), 
+                        b_is_a_path_at_all, 
+                        b_feasible, 
+                        b_correctly_extended, 
+                        ed_last_extended_arc2 );
+        BOOST_CHECK(b_is_a_path_at_all && b_feasible && b_correctly_extended);
+      }
+    }
+  }
+
+  std::vector<int> i_vec_correct_num_solutions_spptw;
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 0 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 5 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 0 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 0 );
+  i_vec_correct_num_solutions_spptw.push_back( 2 );
+  i_vec_correct_num_solutions_spptw.push_back( 3 );
+  i_vec_correct_num_solutions_spptw.push_back( 4 );
+  i_vec_correct_num_solutions_spptw.push_back( 1 );
+  for( int s = 0; s < 10; ++s )
+    for( int t = 0; t < 10; ++t )
+      BOOST_CHECK( static_cast<int>
+            ( vec_vec_vec_vec_opt_solutions_spptw[s][t].size() ) == 
+                   i_vec_correct_num_solutions_spptw[10 * s + t] );
+
+  // one pareto-optimal solution
+  SPPRC_Example_Graph g2;
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 0, 0, 1000000000 ), g2 );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 1, 0, 1000000000 ), g2 );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 2, 0, 1000000000 ), g2 );
+  add_vertex( SPPRC_Example_Graph_Vert_Prop( 3, 0, 1000000000 ), g2 );
+  add_edge( 0, 1, SPPRC_Example_Graph_Arc_Prop( 0, 1, 1 ), g2 );
+  add_edge( 0, 2, SPPRC_Example_Graph_Arc_Prop( 1, 2, 1 ), g2 );
+  add_edge( 1, 3, SPPRC_Example_Graph_Arc_Prop( 2, 3, 1 ), g2 );
+  add_edge( 2, 3, SPPRC_Example_Graph_Arc_Prop( 3, 1, 1 ), g2 );
+  std::vector<graph_traits<SPPRC_Example_Graph>::edge_descriptor> opt_solution;
+  spp_spptw_res_cont pareto_opt_rc;
+  r_c_shortest_paths( g2, 
+                      get( &SPPRC_Example_Graph_Vert_Prop::num, g2 ), 
+                      get( &SPPRC_Example_Graph_Arc_Prop::num, g2 ), 
+                      0, 
+                      3, 
+                      opt_solution, 
+                      pareto_opt_rc, 
+                      spp_spptw_res_cont( 0, 0 ), 
+                      ref_spptw(), 
+                      dominance_spptw(), 
+                      std::allocator
+                        <r_c_shortest_paths_label
+                          <SPPRC_Example_Graph, spp_spptw_res_cont> >(), 
+                      default_r_c_shortest_paths_visitor() );
+
+  BOOST_CHECK(pareto_opt_rc.cost == 3);
+
+  return 0;
+}