| // 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( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g ); | |
| oei != oei_end; | |
| ++oei ) | |
| { | |
| b_feasible = true; | |
| r_c_shortest_paths_label<Graph, Resource_Container>* new_label = | |
| l_alloc.allocate( 1 ); | |
| l_alloc.construct( new_label, | |
| r_c_shortest_paths_label | |
| <Graph, Resource_Container> | |
| ( i_label_num++, | |
| cur_label->cumulated_resource_consumption, | |
| cur_label.get(), | |
| *oei, | |
| target( *oei, g ) ) ); | |
| b_feasible = | |
| ref( g, | |
| new_label->cumulated_resource_consumption, | |
| new_label->p_pred_label->cumulated_resource_consumption, | |
| new_label->pred_edge ); | |
| if( !b_feasible ) | |
| { | |
| vis.on_label_not_feasible( *new_label, g ); | |
| 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&, const Graph& ) {} | |
| template<class Label, class Graph> | |
| void on_label_feasible( const Label&, const Graph& ) {} | |
| template<class Label, class Graph> | |
| void on_label_not_feasible( const Label&, const Graph& ) {} | |
| template<class Label, class Graph> | |
| void on_label_dominated( const Label&, const Graph& ) {} | |
| template<class Label, class Graph> | |
| void on_label_not_dominated( const Label&, const Graph& ) {} | |
| }; // default_r_c_shortest_paths_visitor | |
| // default_r_c_shortest_paths_allocator | |
| typedef | |
| std::allocator<int> default_r_c_shortest_paths_allocator; | |
| // default_r_c_shortest_paths_allocator | |
| // r_c_shortest_paths functions (handle/interface) | |
| // first overload: | |
| // - return all pareto-optimal solutions | |
| // - specify Label_Allocator and Visitor arguments | |
| template<class Graph, | |
| class VertexIndexMap, | |
| class EdgeIndexMap, | |
| class Resource_Container, | |
| class Resource_Extension_Function, | |
| class Dominance_Function, | |
| class Label_Allocator, | |
| class Visitor> | |
| void r_c_shortest_paths | |
| ( const Graph& g, | |
| const VertexIndexMap& vertex_index_map, | |
| const EdgeIndexMap& edge_index_map, | |
| typename graph_traits<Graph>::vertex_descriptor s, | |
| typename graph_traits<Graph>::vertex_descriptor t, | |
| // each inner vector corresponds to a pareto-optimal path | |
| std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& | |
| pareto_optimal_solutions, | |
| std::vector<Resource_Container>& pareto_optimal_resource_containers, | |
| // to initialize the first label/resource container | |
| // and to carry the type information | |
| const Resource_Container& rc, | |
| const Resource_Extension_Function& ref, | |
| const Dominance_Function& dominance, | |
| // to specify the memory management strategy for the labels | |
| Label_Allocator la, | |
| Visitor vis ) | |
| { | |
| r_c_shortest_paths_dispatch( g, | |
| vertex_index_map, | |
| edge_index_map, | |
| s, | |
| t, | |
| pareto_optimal_solutions, | |
| pareto_optimal_resource_containers, | |
| true, | |
| rc, | |
| ref, | |
| dominance, | |
| la, | |
| vis ); | |
| } | |
| // second overload: | |
| // - return only one pareto-optimal solution | |
| // - specify Label_Allocator and Visitor arguments | |
| template<class Graph, | |
| class VertexIndexMap, | |
| class EdgeIndexMap, | |
| class Resource_Container, | |
| class Resource_Extension_Function, | |
| class Dominance_Function, | |
| class Label_Allocator, | |
| class Visitor> | |
| void r_c_shortest_paths | |
| ( const Graph& g, | |
| const VertexIndexMap& vertex_index_map, | |
| const EdgeIndexMap& edge_index_map, | |
| typename graph_traits<Graph>::vertex_descriptor s, | |
| typename graph_traits<Graph>::vertex_descriptor t, | |
| std::vector<typename graph_traits<Graph>::edge_descriptor>& | |
| pareto_optimal_solution, | |
| Resource_Container& pareto_optimal_resource_container, | |
| // to initialize the first label/resource container | |
| // and to carry the type information | |
| const Resource_Container& rc, | |
| const Resource_Extension_Function& ref, | |
| const Dominance_Function& dominance, | |
| // to specify the memory management strategy for the labels | |
| Label_Allocator la, | |
| Visitor vis ) | |
| { | |
| // each inner vector corresponds to a pareto-optimal path | |
| std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > | |
| pareto_optimal_solutions; | |
| std::vector<Resource_Container> pareto_optimal_resource_containers; | |
| r_c_shortest_paths_dispatch( g, | |
| vertex_index_map, | |
| edge_index_map, | |
| s, | |
| t, | |
| pareto_optimal_solutions, | |
| pareto_optimal_resource_containers, | |
| false, | |
| rc, | |
| ref, | |
| dominance, | |
| la, | |
| vis ); | |
| if (!pareto_optimal_solutions.empty()) { | |
| pareto_optimal_solution = pareto_optimal_solutions[0]; | |
| pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; | |
| } | |
| } | |
| // third overload: | |
| // - return all pareto-optimal solutions | |
| // - use default Label_Allocator and Visitor | |
| template<class Graph, | |
| class VertexIndexMap, | |
| class EdgeIndexMap, | |
| class Resource_Container, | |
| class Resource_Extension_Function, | |
| class Dominance_Function> | |
| void r_c_shortest_paths | |
| ( const Graph& g, | |
| const VertexIndexMap& vertex_index_map, | |
| const EdgeIndexMap& edge_index_map, | |
| typename graph_traits<Graph>::vertex_descriptor s, | |
| typename graph_traits<Graph>::vertex_descriptor t, | |
| // each inner vector corresponds to a pareto-optimal path | |
| std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >& | |
| pareto_optimal_solutions, | |
| std::vector<Resource_Container>& pareto_optimal_resource_containers, | |
| // to initialize the first label/resource container | |
| // and to carry the type information | |
| const Resource_Container& rc, | |
| const Resource_Extension_Function& ref, | |
| const Dominance_Function& dominance ) | |
| { | |
| r_c_shortest_paths_dispatch( g, | |
| vertex_index_map, | |
| edge_index_map, | |
| s, | |
| t, | |
| pareto_optimal_solutions, | |
| pareto_optimal_resource_containers, | |
| true, | |
| rc, | |
| ref, | |
| dominance, | |
| default_r_c_shortest_paths_allocator(), | |
| default_r_c_shortest_paths_visitor() ); | |
| } | |
| // fourth overload: | |
| // - return only one pareto-optimal solution | |
| // - use default Label_Allocator and Visitor | |
| template<class Graph, | |
| class VertexIndexMap, | |
| class EdgeIndexMap, | |
| class Resource_Container, | |
| class Resource_Extension_Function, | |
| class Dominance_Function> | |
| void r_c_shortest_paths | |
| ( const Graph& g, | |
| const VertexIndexMap& vertex_index_map, | |
| const EdgeIndexMap& edge_index_map, | |
| typename graph_traits<Graph>::vertex_descriptor s, | |
| typename graph_traits<Graph>::vertex_descriptor t, | |
| std::vector<typename graph_traits<Graph>::edge_descriptor>& | |
| pareto_optimal_solution, | |
| Resource_Container& pareto_optimal_resource_container, | |
| // to initialize the first label/resource container | |
| // and to carry the type information | |
| const Resource_Container& rc, | |
| const Resource_Extension_Function& ref, | |
| const Dominance_Function& dominance ) | |
| { | |
| // each inner vector corresponds to a pareto-optimal path | |
| std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> > | |
| pareto_optimal_solutions; | |
| std::vector<Resource_Container> pareto_optimal_resource_containers; | |
| r_c_shortest_paths_dispatch( g, | |
| vertex_index_map, | |
| edge_index_map, | |
| s, | |
| t, | |
| pareto_optimal_solutions, | |
| pareto_optimal_resource_containers, | |
| false, | |
| rc, | |
| ref, | |
| dominance, | |
| default_r_c_shortest_paths_allocator(), | |
| default_r_c_shortest_paths_visitor() ); | |
| if (!pareto_optimal_solutions.empty()) { | |
| pareto_optimal_solution = pareto_optimal_solutions[0]; | |
| pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; | |
| } | |
| } | |
| // r_c_shortest_paths | |
| // check_r_c_path function | |
| template<class Graph, | |
| class Resource_Container, | |
| class Resource_Extension_Function> | |
| void check_r_c_path( const Graph& g, | |
| const std::vector | |
| <typename graph_traits | |
| <Graph>::edge_descriptor>& ed_vec_path, | |
| const Resource_Container& initial_resource_levels, | |
| // if true, computed accumulated final resource levels must | |
| // be equal to desired_final_resource_levels | |
| // if false, computed accumulated final resource levels must | |
| // be less than or equal to desired_final_resource_levels | |
| bool b_result_must_be_equal_to_desired_final_resource_levels, | |
| const Resource_Container& desired_final_resource_levels, | |
| Resource_Container& actual_final_resource_levels, | |
| const Resource_Extension_Function& ref, | |
| bool& b_is_a_path_at_all, | |
| bool& b_feasible, | |
| bool& b_correctly_extended, | |
| typename graph_traits<Graph>::edge_descriptor& | |
| ed_last_extended_arc ) | |
| { | |
| 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 |