Chris@16: // r_c_shortest_paths.hpp header file
Chris@16: 
Chris@16: // Copyright Michael Drexl 2005, 2006.
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: // (See accompanying file LICENSE_1_0.txt or copy at 
Chris@16: // http://boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
Chris@16: #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
Chris@16: 
Chris@16: #include <map>
Chris@16: #include <queue>
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@101: #include <boost/graph/iteration_macros.hpp>
Chris@101: #include <boost/property_map/property_map.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: // r_c_shortest_paths_label struct
Chris@16: template<class Graph, class Resource_Container>
Chris@16: struct r_c_shortest_paths_label
Chris@16: {
Chris@16:   r_c_shortest_paths_label
Chris@16:   ( const unsigned long n, 
Chris@16:     const Resource_Container& rc = Resource_Container(), 
Chris@16:     const r_c_shortest_paths_label* const pl = 0, 
Chris@16:     const typename graph_traits<Graph>::edge_descriptor& ed = 
Chris@16:       graph_traits<Graph>::edge_descriptor(), 
Chris@16:     const typename graph_traits<Graph>::vertex_descriptor& vd = 
Chris@16:       graph_traits<Graph>::vertex_descriptor() )
Chris@16:   : num( n ), 
Chris@16:     cumulated_resource_consumption( rc ), 
Chris@16:     p_pred_label( pl ), 
Chris@16:     pred_edge( ed ), 
Chris@16:     resident_vertex( vd ), 
Chris@16:     b_is_dominated( false ), 
Chris@101:     b_is_processed( false ),
Chris@101:     b_is_valid( true )
Chris@16:   {}
Chris@16:   r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other )
Chris@16:   {
Chris@16:     if( this == &other )
Chris@16:       return *this;
Chris@16:     this->~r_c_shortest_paths_label();
Chris@16:     new( this ) r_c_shortest_paths_label( other );
Chris@16:     return *this;
Chris@16:   }
Chris@16:   const unsigned long num;
Chris@16:   Resource_Container cumulated_resource_consumption;
Chris@16:   const r_c_shortest_paths_label* const p_pred_label;
Chris@16:   const typename graph_traits<Graph>::edge_descriptor pred_edge;
Chris@16:   const typename graph_traits<Graph>::vertex_descriptor resident_vertex;
Chris@16:   bool b_is_dominated;
Chris@16:   bool b_is_processed;
Chris@101:   bool b_is_valid;
Chris@16: }; // r_c_shortest_paths_label
Chris@16: 
Chris@16: template<class Graph, class Resource_Container>
Chris@16: inline bool operator==
Chris@16: ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, 
Chris@16:   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
Chris@16: {
Chris@101:   assert (l1.b_is_valid && l2.b_is_valid);
Chris@16:   return 
Chris@16:     l1.cumulated_resource_consumption == l2.cumulated_resource_consumption;
Chris@16: }
Chris@16: 
Chris@16: template<class Graph, class Resource_Container>
Chris@16: inline bool operator!=
Chris@16: ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, 
Chris@16:   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
Chris@16: {
Chris@101:   assert (l1.b_is_valid && l2.b_is_valid);
Chris@16:   return 
Chris@16:     !( l1 == l2 );
Chris@16: }
Chris@16: 
Chris@16: template<class Graph, class Resource_Container>
Chris@16: inline bool operator<
Chris@16: ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, 
Chris@16:   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
Chris@16: {
Chris@101:   assert (l1.b_is_valid && l2.b_is_valid);
Chris@16:   return 
Chris@16:     l1.cumulated_resource_consumption < l2.cumulated_resource_consumption;
Chris@16: }
Chris@16: 
Chris@16: template<class Graph, class Resource_Container>
Chris@16: inline bool operator>
Chris@16: ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, 
Chris@16:   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
Chris@16: {
Chris@101:   assert (l1.b_is_valid && l2.b_is_valid);
Chris@16:   return 
Chris@16:     l2.cumulated_resource_consumption < l1.cumulated_resource_consumption;
Chris@16: }
Chris@16: 
Chris@16: template<class Graph, class Resource_Container>
Chris@16: inline bool operator<=
Chris@16: ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, 
Chris@16:   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
Chris@16: {
Chris@101:   assert (l1.b_is_valid && l2.b_is_valid);
Chris@16:   return 
Chris@16:     l1 < l2 || l1 == l2;
Chris@16: }
Chris@16: 
Chris@16: template<class Graph, class Resource_Container>
Chris@16: inline bool operator>=
Chris@16: ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, 
Chris@16:   const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
Chris@16: {
Chris@101:   assert (l1.b_is_valid && l2.b_is_valid);
Chris@16:   return l2 < l1 || l1 == l2;
Chris@16: }
Chris@16: 
Chris@16: namespace detail {
Chris@16: 
Chris@16: // ks_smart_pointer class
Chris@16: // from:
Chris@16: // Kuhlins, S.; Schader, M. (1999):
Chris@16: // Die C++-Standardbibliothek
Chris@16: // Springer, Berlin
Chris@16: // p. 333 f.
Chris@16: template<class T>
Chris@16: class ks_smart_pointer
Chris@16: {
Chris@16: public:
Chris@16:   ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {}
Chris@16:   ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {}
Chris@16:   ks_smart_pointer& operator=( const ks_smart_pointer& other )
Chris@16:     { pt = other.pt; return *this; }
Chris@16:   ~ks_smart_pointer() {}
Chris@16:   T& operator*() const { return *pt; }
Chris@16:   T* operator->() const { return pt; }
Chris@16:   T* get() const { return pt; }
Chris@16:   operator T*() const { return pt; }
Chris@16:   friend bool operator==( const ks_smart_pointer& t, 
Chris@16:                           const ks_smart_pointer& u )
Chris@16:     { return *t.pt == *u.pt; }
Chris@16:   friend bool operator!=( const ks_smart_pointer& t, 
Chris@16:                           const ks_smart_pointer& u )
Chris@16:     { return *t.pt != *u.pt; }
Chris@16:   friend bool operator<( const ks_smart_pointer& t, 
Chris@16:                          const ks_smart_pointer& u )
Chris@16:     { return *t.pt < *u.pt; }
Chris@16:   friend bool operator>( const ks_smart_pointer& t, 
Chris@16:                          const ks_smart_pointer& u )
Chris@16:     { return *t.pt > *u.pt; }
Chris@16:   friend bool operator<=( const ks_smart_pointer& t, 
Chris@16:                           const ks_smart_pointer& u )
Chris@16:     { return *t.pt <= *u.pt; }
Chris@16:   friend bool operator>=( const ks_smart_pointer& t, 
Chris@16:                           const ks_smart_pointer& u )
Chris@16:     { return *t.pt >= *u.pt; }
Chris@16: private:
Chris@16:   T* pt;
Chris@16: }; // ks_smart_pointer
Chris@16: 
Chris@16: 
Chris@16: // r_c_shortest_paths_dispatch function (body/implementation)
Chris@16: template<class Graph, 
Chris@16:          class VertexIndexMap, 
Chris@16:          class EdgeIndexMap, 
Chris@16:          class Resource_Container, 
Chris@16:          class Resource_Extension_Function, 
Chris@16:          class Dominance_Function, 
Chris@16:          class Label_Allocator, 
Chris@16:          class Visitor>
Chris@16: void r_c_shortest_paths_dispatch
Chris@16: ( const Graph& g, 
Chris@16:   const VertexIndexMap& vertex_index_map, 
Chris@16:   const EdgeIndexMap& /*edge_index_map*/, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor s, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:   // each inner vector corresponds to a pareto-optimal path
Chris@16:   std::vector
Chris@16:     <std::vector
Chris@16:       <typename graph_traits
Chris@16:         <Graph>::edge_descriptor> >& pareto_optimal_solutions, 
Chris@16:   std::vector
Chris@16:     <Resource_Container>& pareto_optimal_resource_containers, 
Chris@16:   bool b_all_pareto_optimal_solutions, 
Chris@16:   // to initialize the first label/resource container 
Chris@16:   // and to carry the type information
Chris@16:   const Resource_Container& rc, 
Chris@16:   Resource_Extension_Function& ref, 
Chris@16:   Dominance_Function& dominance, 
Chris@16:   // to specify the memory management strategy for the labels
Chris@16:   Label_Allocator /*la*/, 
Chris@16:   Visitor vis )
Chris@16: {
Chris@16:   pareto_optimal_resource_containers.clear();
Chris@16:   pareto_optimal_solutions.clear();
Chris@16: 
Chris@16:   size_t i_label_num = 0;
Chris@16:   typedef 
Chris@16:     typename 
Chris@16:       Label_Allocator::template rebind
Chris@16:         <r_c_shortest_paths_label
Chris@16:           <Graph, Resource_Container> >::other LAlloc;
Chris@16:   LAlloc l_alloc;
Chris@16:   typedef 
Chris@16:     ks_smart_pointer
Chris@16:       <r_c_shortest_paths_label<Graph, Resource_Container> > Splabel;
Chris@16:   std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> > 
Chris@16:     unprocessed_labels;
Chris@16: 
Chris@16:   bool b_feasible = true;
Chris@16:   r_c_shortest_paths_label<Graph, Resource_Container>* first_label = 
Chris@16:     l_alloc.allocate( 1 );
Chris@16:   l_alloc.construct
Chris@16:     ( first_label, 
Chris@16:       r_c_shortest_paths_label
Chris@16:         <Graph, Resource_Container>( i_label_num++, 
Chris@16:                                      rc, 
Chris@16:                                      0, 
Chris@16:                                      typename graph_traits<Graph>::
Chris@16:                                        edge_descriptor(), 
Chris@16:                                      s ) );
Chris@16: 
Chris@16:   Splabel splabel_first_label = Splabel( first_label );
Chris@16:   unprocessed_labels.push( splabel_first_label );
Chris@101:   std::vector<std::list<Splabel> > vec_vertex_labels_data( num_vertices( g ) );
Chris@101:   iterator_property_map<typename std::vector<std::list<Splabel> >::iterator,
Chris@101:                         VertexIndexMap>
Chris@101:     vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
Chris@101:   vec_vertex_labels[s].push_back( splabel_first_label );
Chris@101:   typedef
Chris@101:     std::vector<typename std::list<Splabel>::iterator> 
Chris@101:     vec_last_valid_positions_for_dominance_data_type;
Chris@101:   vec_last_valid_positions_for_dominance_data_type
Chris@101:     vec_last_valid_positions_for_dominance_data( num_vertices( g ) );
Chris@101:   iterator_property_map<
Chris@101:       typename vec_last_valid_positions_for_dominance_data_type::iterator,
Chris@101:       VertexIndexMap>
Chris@101:     vec_last_valid_positions_for_dominance
Chris@101:       (vec_last_valid_positions_for_dominance_data.begin(),
Chris@101:        vertex_index_map);
Chris@101:   BGL_FORALL_VERTICES_T(v, g, Graph) {
Chris@101:     put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin());
Chris@101:   }
Chris@101:   std::vector<size_t> vec_last_valid_index_for_dominance_data( num_vertices( g ), 0 );
Chris@101:   iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap>
Chris@101:     vec_last_valid_index_for_dominance
Chris@101:       (vec_last_valid_index_for_dominance_data.begin(), vertex_index_map);
Chris@16:   std::vector<bool> 
Chris@101:     b_vec_vertex_already_checked_for_dominance_data( num_vertices( g ), false );
Chris@101:   iterator_property_map<std::vector<bool>::iterator, VertexIndexMap>
Chris@101:     b_vec_vertex_already_checked_for_dominance
Chris@101:       (b_vec_vertex_already_checked_for_dominance_data.begin(),
Chris@101:        vertex_index_map);
Chris@101: 
Chris@16:   while( !unprocessed_labels.empty()  && vis.on_enter_loop(unprocessed_labels, g) )
Chris@16:   {
Chris@16:     Splabel cur_label = unprocessed_labels.top();
Chris@101:     assert (cur_label->b_is_valid);
Chris@16:     unprocessed_labels.pop();
Chris@16:     vis.on_label_popped( *cur_label, g );
Chris@16:     // an Splabel object in unprocessed_labels and the respective Splabel 
Chris@16:     // object in the respective list<Splabel> of vec_vertex_labels share their 
Chris@16:     // embedded r_c_shortest_paths_label object
Chris@16:     // to avoid memory leaks, dominated 
Chris@16:     // r_c_shortest_paths_label objects are marked and deleted when popped 
Chris@16:     // from unprocessed_labels, as they can no longer be deleted at the end of 
Chris@16:     // the function; only the Splabel object in unprocessed_labels still 
Chris@16:     // references the r_c_shortest_paths_label object
Chris@16:     // this is also for efficiency, because the else branch is executed only 
Chris@16:     // if there is a chance that extending the 
Chris@16:     // label leads to new undominated labels, which in turn is possible only 
Chris@16:     // if the label to be extended is undominated
Chris@101:     assert (cur_label->b_is_valid);
Chris@16:     if( !cur_label->b_is_dominated )
Chris@16:     {
Chris@101:       typename boost::graph_traits<Graph>::vertex_descriptor
Chris@101:         i_cur_resident_vertex = cur_label->resident_vertex;
Chris@16:       std::list<Splabel>& list_labels_cur_vertex = 
Chris@101:         get(vec_vertex_labels, i_cur_resident_vertex);
Chris@16:       if( list_labels_cur_vertex.size() >= 2 
Chris@101:           && vec_last_valid_index_for_dominance[i_cur_resident_vertex] 
Chris@16:                < list_labels_cur_vertex.size() )
Chris@16:       {
Chris@16:         typename std::list<Splabel>::iterator outer_iter = 
Chris@16:           list_labels_cur_vertex.begin();
Chris@16:         bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = false;
Chris@16:         while( outer_iter != list_labels_cur_vertex.end() )
Chris@16:         {
Chris@16:           Splabel cur_outer_splabel = *outer_iter;
Chris@101:           assert (cur_outer_splabel->b_is_valid);
Chris@16:           typename std::list<Splabel>::iterator inner_iter = outer_iter;
Chris@16:           if( !b_outer_iter_at_or_beyond_last_valid_pos_for_dominance 
Chris@16:               && outer_iter == 
Chris@101:                    get(vec_last_valid_positions_for_dominance,
Chris@101:                        i_cur_resident_vertex) )
Chris@16:             b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true;
Chris@101:           if( !get(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex)
Chris@16:               || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance )
Chris@16:           {
Chris@16:             ++inner_iter;
Chris@16:           }
Chris@16:           else
Chris@16:           {
Chris@16:             inner_iter = 
Chris@101:               get(vec_last_valid_positions_for_dominance,
Chris@101:                   i_cur_resident_vertex);
Chris@16:             ++inner_iter;
Chris@16:           }
Chris@16:           bool b_outer_iter_erased = false;
Chris@16:           while( inner_iter != list_labels_cur_vertex.end() )
Chris@16:           {
Chris@16:             Splabel cur_inner_splabel = *inner_iter;
Chris@101:             assert (cur_inner_splabel->b_is_valid);
Chris@16:             if( dominance( cur_outer_splabel->
Chris@16:                              cumulated_resource_consumption, 
Chris@16:                            cur_inner_splabel->
Chris@16:                              cumulated_resource_consumption ) )
Chris@16:             {
Chris@16:               typename std::list<Splabel>::iterator buf = inner_iter;
Chris@16:               ++inner_iter;
Chris@16:               list_labels_cur_vertex.erase( buf );
Chris@16:               if( cur_inner_splabel->b_is_processed )
Chris@16:               {
Chris@101:                 cur_inner_splabel->b_is_valid = false;
Chris@16:                 l_alloc.destroy( cur_inner_splabel.get() );
Chris@16:                 l_alloc.deallocate( cur_inner_splabel.get(), 1 );
Chris@16:               }
Chris@16:               else
Chris@16:                 cur_inner_splabel->b_is_dominated = true;
Chris@16:               continue;
Chris@16:             }
Chris@16:             else
Chris@16:               ++inner_iter;
Chris@16:             if( dominance( cur_inner_splabel->
Chris@16:                              cumulated_resource_consumption, 
Chris@16:                            cur_outer_splabel->
Chris@16:                              cumulated_resource_consumption ) )
Chris@16:             {
Chris@16:               typename std::list<Splabel>::iterator buf = outer_iter;
Chris@16:               ++outer_iter;
Chris@16:               list_labels_cur_vertex.erase( buf );
Chris@16:               b_outer_iter_erased = true;
Chris@101:               assert (cur_outer_splabel->b_is_valid);
Chris@16:               if( cur_outer_splabel->b_is_processed )
Chris@16:               {
Chris@101:                 cur_outer_splabel->b_is_valid = false;
Chris@16:                 l_alloc.destroy( cur_outer_splabel.get() );
Chris@16:                 l_alloc.deallocate( cur_outer_splabel.get(), 1 );
Chris@16:               }
Chris@16:               else
Chris@16:                 cur_outer_splabel->b_is_dominated = true;
Chris@16:               break;
Chris@16:             }
Chris@16:           }
Chris@16:           if( !b_outer_iter_erased )
Chris@16:             ++outer_iter;
Chris@16:         }
Chris@16:         if( list_labels_cur_vertex.size() > 1 )
Chris@101:           put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
Chris@101:             (--(list_labels_cur_vertex.end())));
Chris@16:         else
Chris@101:           put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
Chris@101:             list_labels_cur_vertex.begin());
Chris@101:         put(b_vec_vertex_already_checked_for_dominance,
Chris@101:             i_cur_resident_vertex, true);
Chris@101:         put(vec_last_valid_index_for_dominance, i_cur_resident_vertex,
Chris@101:           list_labels_cur_vertex.size() - 1);
Chris@16:       }
Chris@16:     }
Chris@101:     assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid);
Chris@16:     if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t )
Chris@16:     {
Chris@16:       // the devil don't sleep
Chris@16:       if( cur_label->b_is_dominated )
Chris@16:       {
Chris@101:         cur_label->b_is_valid = false;
Chris@16:         l_alloc.destroy( cur_label.get() );
Chris@16:         l_alloc.deallocate( cur_label.get(), 1 );
Chris@16:       }
Chris@16:       while( unprocessed_labels.size() )
Chris@16:       {
Chris@16:         Splabel l = unprocessed_labels.top();
Chris@101:         assert (l->b_is_valid);
Chris@16:         unprocessed_labels.pop();
Chris@16:         // delete only dominated labels, because nondominated labels are 
Chris@16:         // deleted at the end of the function
Chris@16:         if( l->b_is_dominated )
Chris@16:         {
Chris@101:           l->b_is_valid = false;
Chris@16:           l_alloc.destroy( l.get() );
Chris@16:           l_alloc.deallocate( l.get(), 1 );
Chris@16:         }
Chris@16:       }
Chris@16:       break;
Chris@16:     }
Chris@16:     if( !cur_label->b_is_dominated )
Chris@16:     {
Chris@16:       cur_label->b_is_processed = true;
Chris@16:       vis.on_label_not_dominated( *cur_label, g );
Chris@16:       typename graph_traits<Graph>::vertex_descriptor cur_vertex = 
Chris@16:         cur_label->resident_vertex;
Chris@16:       typename graph_traits<Graph>::out_edge_iterator oei, oei_end;
Chris@16:       for( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g ); 
Chris@16:            oei != oei_end; 
Chris@16:            ++oei )
Chris@16:       {
Chris@16:         b_feasible = true;
Chris@16:         r_c_shortest_paths_label<Graph, Resource_Container>* new_label = 
Chris@16:           l_alloc.allocate( 1 );
Chris@16:         l_alloc.construct( new_label, 
Chris@16:                            r_c_shortest_paths_label
Chris@16:                              <Graph, Resource_Container>
Chris@16:                                ( i_label_num++, 
Chris@16:                                  cur_label->cumulated_resource_consumption, 
Chris@16:                                  cur_label.get(), 
Chris@16:                                  *oei, 
Chris@16:                                  target( *oei, g ) ) );
Chris@16:         b_feasible = 
Chris@16:           ref( g, 
Chris@16:                new_label->cumulated_resource_consumption, 
Chris@16:                new_label->p_pred_label->cumulated_resource_consumption, 
Chris@16:                new_label->pred_edge );
Chris@16: 
Chris@16:         if( !b_feasible )
Chris@16:         {
Chris@16:           vis.on_label_not_feasible( *new_label, g );
Chris@101:           new_label->b_is_valid = false;
Chris@16:           l_alloc.destroy( new_label );
Chris@16:           l_alloc.deallocate( new_label, 1 );
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:           const r_c_shortest_paths_label<Graph, Resource_Container>& 
Chris@16:             ref_new_label = *new_label;
Chris@16:           vis.on_label_feasible( ref_new_label, g );
Chris@16:           Splabel new_sp_label( new_label );
Chris@101:           vec_vertex_labels[new_sp_label->resident_vertex].
Chris@16:             push_back( new_sp_label );
Chris@16:           unprocessed_labels.push( new_sp_label );
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16:     else
Chris@16:     {
Chris@101:       assert (cur_label->b_is_valid);
Chris@16:       vis.on_label_dominated( *cur_label, g );
Chris@101:       cur_label->b_is_valid = false;
Chris@16:       l_alloc.destroy( cur_label.get() );
Chris@16:       l_alloc.deallocate( cur_label.get(), 1 );
Chris@16:     }
Chris@16:   }
Chris@101:   std::list<Splabel> dsplabels = get(vec_vertex_labels, t);
Chris@16:   typename std::list<Splabel>::const_iterator csi = dsplabels.begin();
Chris@16:   typename std::list<Splabel>::const_iterator csi_end = dsplabels.end();
Chris@16:   // if d could be reached from o
Chris@16:   if( !dsplabels.empty() )
Chris@16:   {
Chris@16:     for( ; csi != csi_end; ++csi )
Chris@16:     {
Chris@16:       std::vector<typename graph_traits<Graph>::edge_descriptor> 
Chris@16:         cur_pareto_optimal_path;
Chris@16:       const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label = 
Chris@16:         (*csi).get();
Chris@101:       assert (p_cur_label->b_is_valid);
Chris@16:       pareto_optimal_resource_containers.
Chris@16:         push_back( p_cur_label->cumulated_resource_consumption );
Chris@16:       while( p_cur_label->num != 0 )
Chris@16:       {
Chris@16:         cur_pareto_optimal_path.push_back( p_cur_label->pred_edge );
Chris@16:         p_cur_label = p_cur_label->p_pred_label;
Chris@101:         assert (p_cur_label->b_is_valid);
Chris@16:       }
Chris@16:       pareto_optimal_solutions.push_back( cur_pareto_optimal_path );
Chris@16:       if( !b_all_pareto_optimal_solutions )
Chris@16:         break;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@101:   BGL_FORALL_VERTICES_T(i, g, Graph) {
Chris@16:     const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
Chris@16:     csi_end = list_labels_cur_vertex.end();
Chris@16:     for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi )
Chris@16:     {
Chris@101:       assert ((*csi)->b_is_valid);
Chris@101:       (*csi)->b_is_valid = false;
Chris@16:       l_alloc.destroy( (*csi).get() );
Chris@16:       l_alloc.deallocate( (*csi).get(), 1 );
Chris@16:     }
Chris@16:   }
Chris@16: } // r_c_shortest_paths_dispatch
Chris@16: 
Chris@16: } // detail
Chris@16: 
Chris@16: // default_r_c_shortest_paths_visitor struct
Chris@16: struct default_r_c_shortest_paths_visitor
Chris@16: {
Chris@16:   template<class Label, class Graph>
Chris@16:   void on_label_popped( const Label&, const Graph& ) {}
Chris@16:   template<class Label, class Graph>
Chris@16:   void on_label_feasible( const Label&, const Graph& ) {}
Chris@16:   template<class Label, class Graph>
Chris@16:   void on_label_not_feasible( const Label&, const Graph& ) {}
Chris@16:   template<class Label, class Graph>
Chris@16:   void on_label_dominated( const Label&, const Graph& ) {}
Chris@16:   template<class Label, class Graph>
Chris@16:   void on_label_not_dominated( const Label&, const Graph& ) {}
Chris@16:   template<class Queue, class Graph>             
Chris@16:   bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;}
Chris@16: }; // default_r_c_shortest_paths_visitor
Chris@16: 
Chris@16: 
Chris@16: // default_r_c_shortest_paths_allocator
Chris@16: typedef 
Chris@16:   std::allocator<int> default_r_c_shortest_paths_allocator;
Chris@16: // default_r_c_shortest_paths_allocator
Chris@16: 
Chris@16: 
Chris@16: // r_c_shortest_paths functions (handle/interface)
Chris@16: // first overload:
Chris@16: // - return all pareto-optimal solutions
Chris@16: // - specify Label_Allocator and Visitor arguments
Chris@16: template<class Graph, 
Chris@16:          class VertexIndexMap, 
Chris@16:          class EdgeIndexMap, 
Chris@16:          class Resource_Container, 
Chris@16:          class Resource_Extension_Function, 
Chris@16:          class Dominance_Function, 
Chris@16:          class Label_Allocator, 
Chris@16:          class Visitor>
Chris@16: void r_c_shortest_paths
Chris@16: ( const Graph& g, 
Chris@16:   const VertexIndexMap& vertex_index_map, 
Chris@16:   const EdgeIndexMap& edge_index_map, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor s, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:   // each inner vector corresponds to a pareto-optimal path
Chris@16:   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& 
Chris@16:     pareto_optimal_solutions, 
Chris@16:   std::vector<Resource_Container>& pareto_optimal_resource_containers, 
Chris@16:   // to initialize the first label/resource container 
Chris@16:   // and to carry the type information
Chris@16:   const Resource_Container& rc, 
Chris@16:   const Resource_Extension_Function& ref, 
Chris@16:   const Dominance_Function& dominance, 
Chris@16:   // to specify the memory management strategy for the labels
Chris@16:   Label_Allocator la, 
Chris@16:   Visitor vis )
Chris@16: {
Chris@16:   r_c_shortest_paths_dispatch( g, 
Chris@16:                                vertex_index_map, 
Chris@16:                                edge_index_map, 
Chris@16:                                s, 
Chris@16:                                t, 
Chris@16:                                pareto_optimal_solutions, 
Chris@16:                                pareto_optimal_resource_containers, 
Chris@16:                                true, 
Chris@16:                                rc, 
Chris@16:                                ref, 
Chris@16:                                dominance, 
Chris@16:                                la, 
Chris@16:                                vis );
Chris@16: }
Chris@16: 
Chris@16: // second overload:
Chris@16: // - return only one pareto-optimal solution
Chris@16: // - specify Label_Allocator and Visitor arguments
Chris@16: template<class Graph, 
Chris@16:          class VertexIndexMap, 
Chris@16:          class EdgeIndexMap, 
Chris@16:          class Resource_Container, 
Chris@16:          class Resource_Extension_Function, 
Chris@16:          class Dominance_Function, 
Chris@16:          class Label_Allocator, 
Chris@16:          class Visitor>
Chris@16: void r_c_shortest_paths
Chris@16: ( const Graph& g, 
Chris@16:   const VertexIndexMap& vertex_index_map, 
Chris@16:   const EdgeIndexMap& edge_index_map, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor s, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:   std::vector<typename graph_traits<Graph>::edge_descriptor>& 
Chris@16:     pareto_optimal_solution, 
Chris@16:   Resource_Container& pareto_optimal_resource_container, 
Chris@16:   // to initialize the first label/resource container 
Chris@16:   // and to carry the type information
Chris@16:   const Resource_Container& rc, 
Chris@16:   const Resource_Extension_Function& ref, 
Chris@16:   const Dominance_Function& dominance, 
Chris@16:   // to specify the memory management strategy for the labels
Chris@16:   Label_Allocator la, 
Chris@16:   Visitor vis )
Chris@16: {
Chris@16:   // each inner vector corresponds to a pareto-optimal path
Chris@16:   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > 
Chris@16:     pareto_optimal_solutions;
Chris@16:   std::vector<Resource_Container> pareto_optimal_resource_containers;
Chris@16:   r_c_shortest_paths_dispatch( g, 
Chris@16:                                vertex_index_map, 
Chris@16:                                edge_index_map, 
Chris@16:                                s, 
Chris@16:                                t, 
Chris@16:                                pareto_optimal_solutions, 
Chris@16:                                pareto_optimal_resource_containers, 
Chris@16:                                false, 
Chris@16:                                rc, 
Chris@16:                                ref, 
Chris@16:                                dominance, 
Chris@16:                                la, 
Chris@16:                                vis );
Chris@16:   if (!pareto_optimal_solutions.empty()) {
Chris@16:     pareto_optimal_solution = pareto_optimal_solutions[0];
Chris@16:     pareto_optimal_resource_container = pareto_optimal_resource_containers[0];
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: // third overload:
Chris@16: // - return all pareto-optimal solutions
Chris@16: // - use default Label_Allocator and Visitor
Chris@16: template<class Graph, 
Chris@16:          class VertexIndexMap, 
Chris@16:          class EdgeIndexMap, 
Chris@16:          class Resource_Container, 
Chris@16:          class Resource_Extension_Function, 
Chris@16:          class Dominance_Function>
Chris@16: void r_c_shortest_paths
Chris@16: ( const Graph& g, 
Chris@16:   const VertexIndexMap& vertex_index_map, 
Chris@16:   const EdgeIndexMap& edge_index_map, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor s, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:   // each inner vector corresponds to a pareto-optimal path
Chris@16:   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& 
Chris@16:     pareto_optimal_solutions, 
Chris@16:   std::vector<Resource_Container>& pareto_optimal_resource_containers, 
Chris@16:   // to initialize the first label/resource container 
Chris@16:   // and to carry the type information
Chris@16:   const Resource_Container& rc, 
Chris@16:   const Resource_Extension_Function& ref, 
Chris@16:   const Dominance_Function& dominance )
Chris@16: {
Chris@16:   r_c_shortest_paths_dispatch( g, 
Chris@16:                                vertex_index_map, 
Chris@16:                                edge_index_map, 
Chris@16:                                s, 
Chris@16:                                t, 
Chris@16:                                pareto_optimal_solutions, 
Chris@16:                                pareto_optimal_resource_containers, 
Chris@16:                                true, 
Chris@16:                                rc, 
Chris@16:                                ref, 
Chris@16:                                dominance, 
Chris@16:                                default_r_c_shortest_paths_allocator(), 
Chris@16:                                default_r_c_shortest_paths_visitor() );
Chris@16: }
Chris@16: 
Chris@16: // fourth overload:
Chris@16: // - return only one pareto-optimal solution
Chris@16: // - use default Label_Allocator and Visitor
Chris@16: template<class Graph, 
Chris@16:          class VertexIndexMap, 
Chris@16:          class EdgeIndexMap, 
Chris@16:          class Resource_Container, 
Chris@16:          class Resource_Extension_Function, 
Chris@16:          class Dominance_Function>
Chris@16: void r_c_shortest_paths
Chris@16: ( const Graph& g, 
Chris@16:   const VertexIndexMap& vertex_index_map, 
Chris@16:   const EdgeIndexMap& edge_index_map, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor s, 
Chris@16:   typename graph_traits<Graph>::vertex_descriptor t, 
Chris@16:   std::vector<typename graph_traits<Graph>::edge_descriptor>& 
Chris@16:     pareto_optimal_solution, 
Chris@16:   Resource_Container& pareto_optimal_resource_container, 
Chris@16:   // to initialize the first label/resource container 
Chris@16:   // and to carry the type information
Chris@16:   const Resource_Container& rc, 
Chris@16:   const Resource_Extension_Function& ref, 
Chris@16:   const Dominance_Function& dominance )
Chris@16: {
Chris@16:   // each inner vector corresponds to a pareto-optimal path
Chris@16:   std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > 
Chris@16:     pareto_optimal_solutions;
Chris@16:   std::vector<Resource_Container> pareto_optimal_resource_containers;
Chris@16:   r_c_shortest_paths_dispatch( g, 
Chris@16:                                vertex_index_map, 
Chris@16:                                edge_index_map, 
Chris@16:                                s, 
Chris@16:                                t, 
Chris@16:                                pareto_optimal_solutions, 
Chris@16:                                pareto_optimal_resource_containers, 
Chris@16:                                false, 
Chris@16:                                rc, 
Chris@16:                                ref, 
Chris@16:                                dominance, 
Chris@16:                                default_r_c_shortest_paths_allocator(), 
Chris@16:                                default_r_c_shortest_paths_visitor() );
Chris@16:   if (!pareto_optimal_solutions.empty()) {
Chris@16:     pareto_optimal_solution = pareto_optimal_solutions[0];
Chris@16:     pareto_optimal_resource_container = pareto_optimal_resource_containers[0];
Chris@16:   }
Chris@16: }
Chris@16: // r_c_shortest_paths
Chris@16: 
Chris@16: 
Chris@16: // check_r_c_path function
Chris@16: template<class Graph, 
Chris@16:          class Resource_Container, 
Chris@16:          class Resource_Extension_Function>
Chris@16: void check_r_c_path( const Graph& g, 
Chris@16:                      const std::vector
Chris@16:                        <typename graph_traits
Chris@16:                          <Graph>::edge_descriptor>& ed_vec_path, 
Chris@16:                      const Resource_Container& initial_resource_levels, 
Chris@16:                      // if true, computed accumulated final resource levels must 
Chris@16:                      // be equal to desired_final_resource_levels
Chris@16:                      // if false, computed accumulated final resource levels must 
Chris@16:                      // be less than or equal to desired_final_resource_levels
Chris@16:                      bool b_result_must_be_equal_to_desired_final_resource_levels, 
Chris@16:                      const Resource_Container& desired_final_resource_levels, 
Chris@16:                      Resource_Container& actual_final_resource_levels, 
Chris@16:                      const Resource_Extension_Function& ref, 
Chris@16:                      bool& b_is_a_path_at_all, 
Chris@16:                      bool& b_feasible, 
Chris@16:                      bool& b_correctly_extended, 
Chris@16:                      typename graph_traits<Graph>::edge_descriptor& 
Chris@16:                        ed_last_extended_arc )
Chris@16: {
Chris@16:   size_t i_size_ed_vec_path = ed_vec_path.size();
Chris@16:   std::vector<typename graph_traits<Graph>::edge_descriptor> buf_path;
Chris@16:   if( i_size_ed_vec_path == 0 )
Chris@16:     b_feasible = true;
Chris@16:   else
Chris@16:   {
Chris@16:     if( i_size_ed_vec_path == 1 
Chris@16:         || target( ed_vec_path[0], g ) == source( ed_vec_path[1], g ) )
Chris@16:       buf_path = ed_vec_path;
Chris@16:     else
Chris@16:       for( size_t i = i_size_ed_vec_path ; i > 0; --i )
Chris@16:         buf_path.push_back( ed_vec_path[i - 1] );
Chris@16:     for( size_t i = 0; i < i_size_ed_vec_path - 1; ++i )
Chris@16:     {
Chris@16:       if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) )
Chris@16:       {
Chris@16:         b_is_a_path_at_all = false;
Chris@16:         b_feasible = false;
Chris@16:         b_correctly_extended = false;
Chris@16:         return;
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16:   b_is_a_path_at_all = true;
Chris@16:   b_feasible = true;
Chris@16:   b_correctly_extended = false;
Chris@16:   Resource_Container current_resource_levels = initial_resource_levels;
Chris@16:   actual_final_resource_levels = current_resource_levels;
Chris@16:   for( size_t i = 0; i < i_size_ed_vec_path; ++i )
Chris@16:   {
Chris@16:     ed_last_extended_arc = buf_path[i];
Chris@16:     b_feasible = ref( g, 
Chris@16:                       actual_final_resource_levels, 
Chris@16:                       current_resource_levels, 
Chris@16:                       buf_path[i] );
Chris@16:     current_resource_levels = actual_final_resource_levels;
Chris@16:     if( !b_feasible )
Chris@16:       return;
Chris@16:   }
Chris@16:   if( b_result_must_be_equal_to_desired_final_resource_levels )
Chris@16:     b_correctly_extended = 
Chris@16:      actual_final_resource_levels == desired_final_resource_levels ? 
Chris@16:        true : false;
Chris@16:   else
Chris@16:   {
Chris@16:     if( actual_final_resource_levels < desired_final_resource_levels 
Chris@16:         || actual_final_resource_levels == desired_final_resource_levels )
Chris@16:       b_correctly_extended = true;
Chris@16:   }
Chris@16: } // check_path
Chris@16: 
Chris@16: } // namespace
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP