ceph/src/boost/libs/graph/include/boost/graph/r_c_shortest_paths.hpp

   1 // r_c_shortest_paths.hpp header file
   2
   3 // Copyright Michael Drexl 2005, 2006.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 // (See accompanying file LICENSE_1_0.txt or copy at
   6 // http://boost.org/LICENSE_1_0.txt)
   7
   8 #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
   9 #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
  10
  11 #include <map>
  12 #include <queue>
  13 #include <vector>
  14 #include <list>
  15
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <boost/graph/iteration_macros.hpp>
  18 #include <boost/property_map/property_map.hpp>
  19
  20 namespace boost {
  21
  22 // r_c_shortest_paths_label struct
  23 template<class Graph, class Resource_Container>
  24 struct r_c_shortest_paths_label
  25 {
  26   r_c_shortest_paths_label
  27   ( const unsigned long n,
  28     const Resource_Container& rc = Resource_Container(),
  29     const r_c_shortest_paths_label* const pl = 0,
  30     const typename graph_traits<Graph>::edge_descriptor& ed =
  31       graph_traits<Graph>::edge_descriptor(),
  32     const typename graph_traits<Graph>::vertex_descriptor& vd =
  33       graph_traits<Graph>::vertex_descriptor() )
  34   : num( n ),
  35     cumulated_resource_consumption( rc ),
  36     p_pred_label( pl ),
  37     pred_edge( ed ),
  38     resident_vertex( vd ),
  39     b_is_dominated( false ),
  40     b_is_processed( false ),
  41     b_is_valid( true )
  42   {}
  43   r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other )
  44   {
  45     if( this == &other )
  46       return *this;
  47     this->~r_c_shortest_paths_label();
  48     new( this ) r_c_shortest_paths_label( other );
  49     return *this;
  50   }
  51   const unsigned long num;
  52   Resource_Container cumulated_resource_consumption;
  53   const r_c_shortest_paths_label* const p_pred_label;
  54   const typename graph_traits<Graph>::edge_descriptor pred_edge;
  55   const typename graph_traits<Graph>::vertex_descriptor resident_vertex;
  56   bool b_is_dominated;
  57   bool b_is_processed;
  58   bool b_is_valid;
  59 }; // r_c_shortest_paths_label
  60
  61 template<class Graph, class Resource_Container>
  62 inline bool operator==
  63 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
  64   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
  65 {
  66   assert (l1.b_is_valid && l2.b_is_valid);
  67   return
  68     l1.cumulated_resource_consumption == l2.cumulated_resource_consumption;
  69 }
  70
  71 template<class Graph, class Resource_Container>
  72 inline bool operator!=
  73 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
  74   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
  75 {
  76   assert (l1.b_is_valid && l2.b_is_valid);
  77   return
  78     !( l1 == l2 );
  79 }
  80
  81 template<class Graph, class Resource_Container>
  82 inline bool operator<
  83 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
  84   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
  85 {
  86   assert (l1.b_is_valid && l2.b_is_valid);
  87   return
  88     l1.cumulated_resource_consumption < l2.cumulated_resource_consumption;
  89 }
  90
  91 template<class Graph, class Resource_Container>
  92 inline bool operator>
  93 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
  94   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
  95 {
  96   assert (l1.b_is_valid && l2.b_is_valid);
  97   return
  98     l2.cumulated_resource_consumption < l1.cumulated_resource_consumption;
  99 }
 100
 101 template<class Graph, class Resource_Container>
 102 inline bool operator<=
 103 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
 104   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
 105 {
 106   assert (l1.b_is_valid && l2.b_is_valid);
 107   return
 108     l1 < l2 || l1 == l2;
 109 }
 110
 111 template<class Graph, class Resource_Container>
 112 inline bool operator>=
 113 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
 114   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
 115 {
 116   assert (l1.b_is_valid && l2.b_is_valid);
 117   return l2 < l1 || l1 == l2;
 118 }
 119
 120 namespace detail {
 121
 122 // ks_smart_pointer class
 123 // from:
 124 // Kuhlins, S.; Schader, M. (1999):
 125 // Die C++-Standardbibliothek
 126 // Springer, Berlin
 127 // p. 333 f.
 128 template<class T>
 129 class ks_smart_pointer
 130 {
 131 public:
 132   ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {}
 133   ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {}
 134   ks_smart_pointer& operator=( const ks_smart_pointer& other )
 135     { pt = other.pt; return *this; }
 136   ~ks_smart_pointer() {}
 137   T& operator*() const { return *pt; }
 138   T* operator->() const { return pt; }
 139   T* get() const { return pt; }
 140   operator T*() const { return pt; }
 141   friend bool operator==( const ks_smart_pointer& t,
 142                           const ks_smart_pointer& u )
 143     { return *t.pt == *u.pt; }
 144   friend bool operator!=( const ks_smart_pointer& t,
 145                           const ks_smart_pointer& u )
 146     { return *t.pt != *u.pt; }
 147   friend bool operator<( const ks_smart_pointer& t,
 148                          const ks_smart_pointer& u )
 149     { return *t.pt < *u.pt; }
 150   friend bool operator>( const ks_smart_pointer& t,
 151                          const ks_smart_pointer& u )
 152     { return *t.pt > *u.pt; }
 153   friend bool operator<=( const ks_smart_pointer& t,
 154                           const ks_smart_pointer& u )
 155     { return *t.pt <= *u.pt; }
 156   friend bool operator>=( const ks_smart_pointer& t,
 157                           const ks_smart_pointer& u )
 158     { return *t.pt >= *u.pt; }
 159 private:
 160   T* pt;
 161 }; // ks_smart_pointer
 162
 163
 164 // r_c_shortest_paths_dispatch function (body/implementation)
 165 template<class Graph,
 166          class VertexIndexMap,
 167          class EdgeIndexMap,
 168          class Resource_Container,
 169          class Resource_Extension_Function,
 170          class Dominance_Function,
 171          class Label_Allocator,
 172          class Visitor>
 173 void r_c_shortest_paths_dispatch
 174 ( const Graph& g,
 175   const VertexIndexMap& vertex_index_map,
 176   const EdgeIndexMap& /*edge_index_map*/,
 177   typename graph_traits<Graph>::vertex_descriptor s,
 178   typename graph_traits<Graph>::vertex_descriptor t,
 179   // each inner vector corresponds to a pareto-optimal path
 180   std::vector
 181     <std::vector
 182       <typename graph_traits
 183         <Graph>::edge_descriptor> >& pareto_optimal_solutions,
 184   std::vector
 185     <Resource_Container>& pareto_optimal_resource_containers,
 186   bool b_all_pareto_optimal_solutions,
 187   // to initialize the first label/resource container
 188   // and to carry the type information
 189   const Resource_Container& rc,
 190   Resource_Extension_Function& ref,
 191   Dominance_Function& dominance,
 192   // to specify the memory management strategy for the labels
 193   Label_Allocator /*la*/,
 194   Visitor vis )
 195 {
 196   pareto_optimal_resource_containers.clear();
 197   pareto_optimal_solutions.clear();
 198
 199   size_t i_label_num = 0;
 200   typedef
 201     typename
 202       Label_Allocator::template rebind
 203         <r_c_shortest_paths_label
 204           <Graph, Resource_Container> >::other LAlloc;
 205   LAlloc l_alloc;
 206   typedef
 207     ks_smart_pointer
 208       <r_c_shortest_paths_label<Graph, Resource_Container> > Splabel;
 209   std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> >
 210     unprocessed_labels;
 211
 212   bool b_feasible = true;
 213   r_c_shortest_paths_label<Graph, Resource_Container>* first_label =
 214     l_alloc.allocate( 1 );
 215   l_alloc.construct
 216     ( first_label,
 217       r_c_shortest_paths_label
 218         <Graph, Resource_Container>( i_label_num++,
 219                                      rc,
 220                                      0,
 221                                      typename graph_traits<Graph>::
 222                                        edge_descriptor(),
 223                                      s ) );
 224
 225   Splabel splabel_first_label = Splabel( first_label );
 226   unprocessed_labels.push( splabel_first_label );
 227   std::vector<std::list<Splabel> > vec_vertex_labels_data( num_vertices( g ) );
 228   iterator_property_map<typename std::vector<std::list<Splabel> >::iterator,
 229                         VertexIndexMap>
 230     vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
 231   vec_vertex_labels[s].push_back( splabel_first_label );
 232   typedef
 233     std::vector<typename std::list<Splabel>::iterator>
 234     vec_last_valid_positions_for_dominance_data_type;
 235   vec_last_valid_positions_for_dominance_data_type
 236     vec_last_valid_positions_for_dominance_data( num_vertices( g ) );
 237   iterator_property_map<
 238       typename vec_last_valid_positions_for_dominance_data_type::iterator,
 239       VertexIndexMap>
 240     vec_last_valid_positions_for_dominance
 241       (vec_last_valid_positions_for_dominance_data.begin(),
 242        vertex_index_map);
 243   BGL_FORALL_VERTICES_T(v, g, Graph) {
 244     put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin());
 245   }
 246   std::vector<size_t> vec_last_valid_index_for_dominance_data( num_vertices( g ), 0 );
 247   iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap>
 248     vec_last_valid_index_for_dominance
 249       (vec_last_valid_index_for_dominance_data.begin(), vertex_index_map);
 250   std::vector<bool>
 251     b_vec_vertex_already_checked_for_dominance_data( num_vertices( g ), false );
 252   iterator_property_map<std::vector<bool>::iterator, VertexIndexMap>
 253     b_vec_vertex_already_checked_for_dominance
 254       (b_vec_vertex_already_checked_for_dominance_data.begin(),
 255        vertex_index_map);
 256
 257   while( !unprocessed_labels.empty()  && vis.on_enter_loop(unprocessed_labels, g) )
 258   {
 259     Splabel cur_label = unprocessed_labels.top();
 260     assert (cur_label->b_is_valid);
 261     unprocessed_labels.pop();
 262     vis.on_label_popped( *cur_label, g );
 263     // an Splabel object in unprocessed_labels and the respective Splabel
 264     // object in the respective list<Splabel> of vec_vertex_labels share their
 265     // embedded r_c_shortest_paths_label object
 266     // to avoid memory leaks, dominated
 267     // r_c_shortest_paths_label objects are marked and deleted when popped
 268     // from unprocessed_labels, as they can no longer be deleted at the end of
 269     // the function; only the Splabel object in unprocessed_labels still
 270     // references the r_c_shortest_paths_label object
 271     // this is also for efficiency, because the else branch is executed only
 272     // if there is a chance that extending the
 273     // label leads to new undominated labels, which in turn is possible only
 274     // if the label to be extended is undominated
 275     assert (cur_label->b_is_valid);
 276     if( !cur_label->b_is_dominated )
 277     {
 278       typename boost::graph_traits<Graph>::vertex_descriptor
 279         i_cur_resident_vertex = cur_label->resident_vertex;
 280       std::list<Splabel>& list_labels_cur_vertex =
 281         get(vec_vertex_labels, i_cur_resident_vertex);
 282       if( list_labels_cur_vertex.size() >= 2
 283           && vec_last_valid_index_for_dominance[i_cur_resident_vertex]
 284                < list_labels_cur_vertex.size() )
 285       {
 286         typename std::list<Splabel>::iterator outer_iter =
 287           list_labels_cur_vertex.begin();
 288         bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = false;
 289         while( outer_iter != list_labels_cur_vertex.end() )
 290         {
 291           Splabel cur_outer_splabel = *outer_iter;
 292           assert (cur_outer_splabel->b_is_valid);
 293           typename std::list<Splabel>::iterator inner_iter = outer_iter;
 294           if( !b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
 295               && outer_iter ==
 296                    get(vec_last_valid_positions_for_dominance,
 297                        i_cur_resident_vertex) )
 298             b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true;
 299           if( !get(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex)
 300               || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance )
 301           {
 302             ++inner_iter;
 303           }
 304           else
 305           {
 306             inner_iter =
 307               get(vec_last_valid_positions_for_dominance,
 308                   i_cur_resident_vertex);
 309             ++inner_iter;
 310           }
 311           bool b_outer_iter_erased = false;
 312           while( inner_iter != list_labels_cur_vertex.end() )
 313           {
 314             Splabel cur_inner_splabel = *inner_iter;
 315             assert (cur_inner_splabel->b_is_valid);
 316             if( dominance( cur_outer_splabel->
 317                              cumulated_resource_consumption,
 318                            cur_inner_splabel->
 319                              cumulated_resource_consumption ) )
 320             {
 321               typename std::list<Splabel>::iterator buf = inner_iter;
 322               ++inner_iter;
 323               list_labels_cur_vertex.erase( buf );
 324               if( cur_inner_splabel->b_is_processed )
 325               {
 326                 cur_inner_splabel->b_is_valid = false;
 327                 l_alloc.destroy( cur_inner_splabel.get() );
 328                 l_alloc.deallocate( cur_inner_splabel.get(), 1 );
 329               }
 330               else
 331                 cur_inner_splabel->b_is_dominated = true;
 332               continue;
 333             }
 334             else
 335               ++inner_iter;
 336             if( dominance( cur_inner_splabel->
 337                              cumulated_resource_consumption,
 338                            cur_outer_splabel->
 339                              cumulated_resource_consumption ) )
 340             {
 341               typename std::list<Splabel>::iterator buf = outer_iter;
 342               ++outer_iter;
 343               list_labels_cur_vertex.erase( buf );
 344               b_outer_iter_erased = true;
 345               assert (cur_outer_splabel->b_is_valid);
 346               if( cur_outer_splabel->b_is_processed )
 347               {
 348                 cur_outer_splabel->b_is_valid = false;
 349                 l_alloc.destroy( cur_outer_splabel.get() );
 350                 l_alloc.deallocate( cur_outer_splabel.get(), 1 );
 351               }
 352               else
 353                 cur_outer_splabel->b_is_dominated = true;
 354               break;
 355             }
 356           }
 357           if( !b_outer_iter_erased )
 358             ++outer_iter;
 359         }
 360         if( list_labels_cur_vertex.size() > 1 )
 361           put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
 362             (--(list_labels_cur_vertex.end())));
 363         else
 364           put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
 365             list_labels_cur_vertex.begin());
 366         put(b_vec_vertex_already_checked_for_dominance,
 367             i_cur_resident_vertex, true);
 368         put(vec_last_valid_index_for_dominance, i_cur_resident_vertex,
 369           list_labels_cur_vertex.size() - 1);
 370       }
 371     }
 372     assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid);
 373     if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t )
 374     {
 375       // the devil don't sleep
 376       if( cur_label->b_is_dominated )
 377       {
 378         cur_label->b_is_valid = false;
 379         l_alloc.destroy( cur_label.get() );
 380         l_alloc.deallocate( cur_label.get(), 1 );
 381       }
 382       while( unprocessed_labels.size() )
 383       {
 384         Splabel l = unprocessed_labels.top();
 385         assert (l->b_is_valid);
 386         unprocessed_labels.pop();
 387         // delete only dominated labels, because nondominated labels are
 388         // deleted at the end of the function
 389         if( l->b_is_dominated )
 390         {
 391           l->b_is_valid = false;
 392           l_alloc.destroy( l.get() );
 393           l_alloc.deallocate( l.get(), 1 );
 394         }
 395       }
 396       break;
 397     }
 398     if( !cur_label->b_is_dominated )
 399     {
 400       cur_label->b_is_processed = true;
 401       vis.on_label_not_dominated( *cur_label, g );
 402       typename graph_traits<Graph>::vertex_descriptor cur_vertex =
 403         cur_label->resident_vertex;
 404       typename graph_traits<Graph>::out_edge_iterator oei, oei_end;
 405       for( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g );
 406            oei != oei_end;
 407            ++oei )
 408       {
 409         b_feasible = true;
 410         r_c_shortest_paths_label<Graph, Resource_Container>* new_label =
 411           l_alloc.allocate( 1 );
 412         l_alloc.construct( new_label,
 413                            r_c_shortest_paths_label
 414                              <Graph, Resource_Container>
 415                                ( i_label_num++,
 416                                  cur_label->cumulated_resource_consumption,
 417                                  cur_label.get(),
 418                                  *oei,
 419                                  target( *oei, g ) ) );
 420         b_feasible =
 421           ref( g,
 422                new_label->cumulated_resource_consumption,
 423                new_label->p_pred_label->cumulated_resource_consumption,
 424                new_label->pred_edge );
 425
 426         if( !b_feasible )
 427         {
 428           vis.on_label_not_feasible( *new_label, g );
 429           new_label->b_is_valid = false;
 430           l_alloc.destroy( new_label );
 431           l_alloc.deallocate( new_label, 1 );
 432         }
 433         else
 434         {
 435           const r_c_shortest_paths_label<Graph, Resource_Container>&
 436             ref_new_label = *new_label;
 437           vis.on_label_feasible( ref_new_label, g );
 438           Splabel new_sp_label( new_label );
 439           vec_vertex_labels[new_sp_label->resident_vertex].
 440             push_back( new_sp_label );
 441           unprocessed_labels.push( new_sp_label );
 442         }
 443       }
 444     }
 445     else
 446     {
 447       assert (cur_label->b_is_valid);
 448       vis.on_label_dominated( *cur_label, g );
 449       cur_label->b_is_valid = false;
 450       l_alloc.destroy( cur_label.get() );
 451       l_alloc.deallocate( cur_label.get(), 1 );
 452     }
 453   }
 454   std::list<Splabel> dsplabels = get(vec_vertex_labels, t);
 455   typename std::list<Splabel>::const_iterator csi = dsplabels.begin();
 456   typename std::list<Splabel>::const_iterator csi_end = dsplabels.end();
 457   // if d could be reached from o
 458   if( !dsplabels.empty() )
 459   {
 460     for( ; csi != csi_end; ++csi )
 461     {
 462       std::vector<typename graph_traits<Graph>::edge_descriptor>
 463         cur_pareto_optimal_path;
 464       const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label =
 465         (*csi).get();
 466       assert (p_cur_label->b_is_valid);
 467       pareto_optimal_resource_containers.
 468         push_back( p_cur_label->cumulated_resource_consumption );
 469       while( p_cur_label->num != 0 )
 470       {
 471         cur_pareto_optimal_path.push_back( p_cur_label->pred_edge );
 472         p_cur_label = p_cur_label->p_pred_label;
 473         assert (p_cur_label->b_is_valid);
 474       }
 475       pareto_optimal_solutions.push_back( cur_pareto_optimal_path );
 476       if( !b_all_pareto_optimal_solutions )
 477         break;
 478     }
 479   }
 480
 481   BGL_FORALL_VERTICES_T(i, g, Graph) {
 482     const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
 483     csi_end = list_labels_cur_vertex.end();
 484     for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi )
 485     {
 486       assert ((*csi)->b_is_valid);
 487       (*csi)->b_is_valid = false;
 488       l_alloc.destroy( (*csi).get() );
 489       l_alloc.deallocate( (*csi).get(), 1 );
 490     }
 491   }
 492 } // r_c_shortest_paths_dispatch
 493
 494 } // detail
 495
 496 // default_r_c_shortest_paths_visitor struct
 497 struct default_r_c_shortest_paths_visitor
 498 {
 499   template<class Label, class Graph>
 500   void on_label_popped( const Label&, const Graph& ) {}
 501   template<class Label, class Graph>
 502   void on_label_feasible( const Label&, const Graph& ) {}
 503   template<class Label, class Graph>
 504   void on_label_not_feasible( const Label&, const Graph& ) {}
 505   template<class Label, class Graph>
 506   void on_label_dominated( const Label&, const Graph& ) {}
 507   template<class Label, class Graph>
 508   void on_label_not_dominated( const Label&, const Graph& ) {}
 509   template<class Queue, class Graph>
 510   bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;}
 511 }; // default_r_c_shortest_paths_visitor
 512
 513
 514 // default_r_c_shortest_paths_allocator
 515 typedef
 516   std::allocator<int> default_r_c_shortest_paths_allocator;
 517 // default_r_c_shortest_paths_allocator
 518
 519
 520 // r_c_shortest_paths functions (handle/interface)
 521 // first overload:
 522 // - return all pareto-optimal solutions
 523 // - specify Label_Allocator and Visitor arguments
 524 template<class Graph,
 525          class VertexIndexMap,
 526          class EdgeIndexMap,
 527          class Resource_Container,
 528          class Resource_Extension_Function,
 529          class Dominance_Function,
 530          class Label_Allocator,
 531          class Visitor>
 532 void r_c_shortest_paths
 533 ( const Graph& g,
 534   const VertexIndexMap& vertex_index_map,
 535   const EdgeIndexMap& edge_index_map,
 536   typename graph_traits<Graph>::vertex_descriptor s,
 537   typename graph_traits<Graph>::vertex_descriptor t,
 538   // each inner vector corresponds to a pareto-optimal path
 539   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >&
 540     pareto_optimal_solutions,
 541   std::vector<Resource_Container>& pareto_optimal_resource_containers,
 542   // to initialize the first label/resource container
 543   // and to carry the type information
 544   const Resource_Container& rc,
 545   const Resource_Extension_Function& ref,
 546   const Dominance_Function& dominance,
 547   // to specify the memory management strategy for the labels
 548   Label_Allocator la,
 549   Visitor vis )
 550 {
 551   r_c_shortest_paths_dispatch( g,
 552                                vertex_index_map,
 553                                edge_index_map,
 554                                s,
 555                                t,
 556                                pareto_optimal_solutions,
 557                                pareto_optimal_resource_containers,
 558                                true,
 559                                rc,
 560                                ref,
 561                                dominance,
 562                                la,
 563                                vis );
 564 }
 565
 566 // second overload:
 567 // - return only one pareto-optimal solution
 568 // - specify Label_Allocator and Visitor arguments
 569 template<class Graph,
 570          class VertexIndexMap,
 571          class EdgeIndexMap,
 572          class Resource_Container,
 573          class Resource_Extension_Function,
 574          class Dominance_Function,
 575          class Label_Allocator,
 576          class Visitor>
 577 void r_c_shortest_paths
 578 ( const Graph& g,
 579   const VertexIndexMap& vertex_index_map,
 580   const EdgeIndexMap& edge_index_map,
 581   typename graph_traits<Graph>::vertex_descriptor s,
 582   typename graph_traits<Graph>::vertex_descriptor t,
 583   std::vector<typename graph_traits<Graph>::edge_descriptor>&
 584     pareto_optimal_solution,
 585   Resource_Container& pareto_optimal_resource_container,
 586   // to initialize the first label/resource container
 587   // and to carry the type information
 588   const Resource_Container& rc,
 589   const Resource_Extension_Function& ref,
 590   const Dominance_Function& dominance,
 591   // to specify the memory management strategy for the labels
 592   Label_Allocator la,
 593   Visitor vis )
 594 {
 595   // each inner vector corresponds to a pareto-optimal path
 596   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >
 597     pareto_optimal_solutions;
 598   std::vector<Resource_Container> pareto_optimal_resource_containers;
 599   r_c_shortest_paths_dispatch( g,
 600                                vertex_index_map,
 601                                edge_index_map,
 602                                s,
 603                                t,
 604                                pareto_optimal_solutions,
 605                                pareto_optimal_resource_containers,
 606                                false,
 607                                rc,
 608                                ref,
 609                                dominance,
 610                                la,
 611                                vis );
 612   if (!pareto_optimal_solutions.empty()) {
 613     pareto_optimal_solution = pareto_optimal_solutions[0];
 614     pareto_optimal_resource_container = pareto_optimal_resource_containers[0];
 615   }
 616 }
 617
 618 // third overload:
 619 // - return all pareto-optimal solutions
 620 // - use default Label_Allocator and Visitor
 621 template<class Graph,
 622          class VertexIndexMap,
 623          class EdgeIndexMap,
 624          class Resource_Container,
 625          class Resource_Extension_Function,
 626          class Dominance_Function>
 627 void r_c_shortest_paths
 628 ( const Graph& g,
 629   const VertexIndexMap& vertex_index_map,
 630   const EdgeIndexMap& edge_index_map,
 631   typename graph_traits<Graph>::vertex_descriptor s,
 632   typename graph_traits<Graph>::vertex_descriptor t,
 633   // each inner vector corresponds to a pareto-optimal path
 634   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >&
 635     pareto_optimal_solutions,
 636   std::vector<Resource_Container>& pareto_optimal_resource_containers,
 637   // to initialize the first label/resource container
 638   // and to carry the type information
 639   const Resource_Container& rc,
 640   const Resource_Extension_Function& ref,
 641   const Dominance_Function& dominance )
 642 {
 643   r_c_shortest_paths_dispatch( g,
 644                                vertex_index_map,
 645                                edge_index_map,
 646                                s,
 647                                t,
 648                                pareto_optimal_solutions,
 649                                pareto_optimal_resource_containers,
 650                                true,
 651                                rc,
 652                                ref,
 653                                dominance,
 654                                default_r_c_shortest_paths_allocator(),
 655                                default_r_c_shortest_paths_visitor() );
 656 }
 657
 658 // fourth overload:
 659 // - return only one pareto-optimal solution
 660 // - use default Label_Allocator and Visitor
 661 template<class Graph,
 662          class VertexIndexMap,
 663          class EdgeIndexMap,
 664          class Resource_Container,
 665          class Resource_Extension_Function,
 666          class Dominance_Function>
 667 void r_c_shortest_paths
 668 ( const Graph& g,
 669   const VertexIndexMap& vertex_index_map,
 670   const EdgeIndexMap& edge_index_map,
 671   typename graph_traits<Graph>::vertex_descriptor s,
 672   typename graph_traits<Graph>::vertex_descriptor t,
 673   std::vector<typename graph_traits<Graph>::edge_descriptor>&
 674     pareto_optimal_solution,
 675   Resource_Container& pareto_optimal_resource_container,
 676   // to initialize the first label/resource container
 677   // and to carry the type information
 678   const Resource_Container& rc,
 679   const Resource_Extension_Function& ref,
 680   const Dominance_Function& dominance )
 681 {
 682   // each inner vector corresponds to a pareto-optimal path
 683   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >
 684     pareto_optimal_solutions;
 685   std::vector<Resource_Container> pareto_optimal_resource_containers;
 686   r_c_shortest_paths_dispatch( g,
 687                                vertex_index_map,
 688                                edge_index_map,
 689                                s,
 690                                t,
 691                                pareto_optimal_solutions,
 692                                pareto_optimal_resource_containers,
 693                                false,
 694                                rc,
 695                                ref,
 696                                dominance,
 697                                default_r_c_shortest_paths_allocator(),
 698                                default_r_c_shortest_paths_visitor() );
 699   if (!pareto_optimal_solutions.empty()) {
 700     pareto_optimal_solution = pareto_optimal_solutions[0];
 701     pareto_optimal_resource_container = pareto_optimal_resource_containers[0];
 702   }
 703 }
 704 // r_c_shortest_paths
 705
 706
 707 // check_r_c_path function
 708 template<class Graph,
 709          class Resource_Container,
 710          class Resource_Extension_Function>
 711 void check_r_c_path( const Graph& g,
 712                      const std::vector
 713                        <typename graph_traits
 714                          <Graph>::edge_descriptor>& ed_vec_path,
 715                      const Resource_Container& initial_resource_levels,
 716                      // if true, computed accumulated final resource levels must
 717                      // be equal to desired_final_resource_levels
 718                      // if false, computed accumulated final resource levels must
 719                      // be less than or equal to desired_final_resource_levels
 720                      bool b_result_must_be_equal_to_desired_final_resource_levels,
 721                      const Resource_Container& desired_final_resource_levels,
 722                      Resource_Container& actual_final_resource_levels,
 723                      const Resource_Extension_Function& ref,
 724                      bool& b_is_a_path_at_all,
 725                      bool& b_feasible,
 726                      bool& b_correctly_extended,
 727                      typename graph_traits<Graph>::edge_descriptor&
 728                        ed_last_extended_arc )
 729 {
 730   size_t i_size_ed_vec_path = ed_vec_path.size();
 731   std::vector<typename graph_traits<Graph>::edge_descriptor> buf_path;
 732   if( i_size_ed_vec_path == 0 )
 733     b_feasible = true;
 734   else
 735   {
 736     if( i_size_ed_vec_path == 1
 737         || target( ed_vec_path[0], g ) == source( ed_vec_path[1], g ) )
 738       buf_path = ed_vec_path;
 739     else
 740       for( size_t i = i_size_ed_vec_path ; i > 0; --i )
 741         buf_path.push_back( ed_vec_path[i - 1] );
 742     for( size_t i = 0; i < i_size_ed_vec_path - 1; ++i )
 743     {
 744       if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) )
 745       {
 746         b_is_a_path_at_all = false;
 747         b_feasible = false;
 748         b_correctly_extended = false;
 749         return;
 750       }
 751     }
 752   }
 753   b_is_a_path_at_all = true;
 754   b_feasible = true;
 755   b_correctly_extended = false;
 756   Resource_Container current_resource_levels = initial_resource_levels;
 757   actual_final_resource_levels = current_resource_levels;
 758   for( size_t i = 0; i < i_size_ed_vec_path; ++i )
 759   {
 760     ed_last_extended_arc = buf_path[i];
 761     b_feasible = ref( g,
 762                       actual_final_resource_levels,
 763                       current_resource_levels,
 764                       buf_path[i] );
 765     current_resource_levels = actual_final_resource_levels;
 766     if( !b_feasible )
 767       return;
 768   }
 769   if( b_result_must_be_equal_to_desired_final_resource_levels )
 770     b_correctly_extended =
 771      actual_final_resource_levels == desired_final_resource_levels ?
 772        true : false;
 773   else
 774   {
 775     if( actual_final_resource_levels < desired_final_resource_levels
 776         || actual_final_resource_levels == desired_final_resource_levels )
 777       b_correctly_extended = true;
 778   }
 779 } // check_path
 780
 781 } // namespace
 782
 783 #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP