diff options
Diffstat (limited to 'boost/graph/r_c_shortest_paths.hpp')
| -rw-r--r-- | boost/graph/r_c_shortest_paths.hpp | 133 |
1 files changed, 91 insertions, 42 deletions
diff --git a/boost/graph/r_c_shortest_paths.hpp b/boost/graph/r_c_shortest_paths.hpp index 9d395799ea..afa50cf084 100644 --- a/boost/graph/r_c_shortest_paths.hpp +++ b/boost/graph/r_c_shortest_paths.hpp @@ -13,6 +13,8 @@ #include <vector> #include <boost/graph/graph_traits.hpp> +#include <boost/graph/iteration_macros.hpp> +#include <boost/property_map/property_map.hpp> namespace boost { @@ -34,7 +36,8 @@ struct r_c_shortest_paths_label pred_edge( ed ), resident_vertex( vd ), b_is_dominated( false ), - b_is_processed( false ) + b_is_processed( false ), + b_is_valid( true ) {} r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other ) { @@ -51,6 +54,7 @@ struct r_c_shortest_paths_label const typename graph_traits<Graph>::vertex_descriptor resident_vertex; bool b_is_dominated; bool b_is_processed; + bool b_is_valid; }; // r_c_shortest_paths_label template<class Graph, class Resource_Container> @@ -58,6 +62,7 @@ inline bool operator== ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { + assert (l1.b_is_valid && l2.b_is_valid); return l1.cumulated_resource_consumption == l2.cumulated_resource_consumption; } @@ -67,6 +72,7 @@ inline bool operator!= ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { + assert (l1.b_is_valid && l2.b_is_valid); return !( l1 == l2 ); } @@ -76,6 +82,7 @@ inline bool operator< ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { + assert (l1.b_is_valid && l2.b_is_valid); return l1.cumulated_resource_consumption < l2.cumulated_resource_consumption; } @@ -85,6 +92,7 @@ inline bool operator> ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { + assert (l1.b_is_valid && l2.b_is_valid); return l2.cumulated_resource_consumption < l1.cumulated_resource_consumption; } @@ -94,6 +102,7 @@ inline bool operator<= ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { + assert (l1.b_is_valid && l2.b_is_valid); return l1 < l2 || l1 == l2; } @@ -103,6 +112,7 @@ inline bool operator>= ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) { + assert (l1.b_is_valid && l2.b_is_valid); return l2 < l1 || l1 == l2; } @@ -185,7 +195,7 @@ void r_c_shortest_paths_dispatch pareto_optimal_resource_containers.clear(); pareto_optimal_solutions.clear(); - unsigned long i_label_num = 0; + size_t i_label_num = 0; typedef typename Label_Allocator::template rebind @@ -213,18 +223,40 @@ void r_c_shortest_paths_dispatch 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<std::list<Splabel> > vec_vertex_labels_data( num_vertices( g ) ); + iterator_property_map<typename std::vector<std::list<Splabel> >::iterator, + VertexIndexMap> + vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map); + vec_vertex_labels[s].push_back( splabel_first_label ); + typedef + std::vector<typename std::list<Splabel>::iterator> + vec_last_valid_positions_for_dominance_data_type; + vec_last_valid_positions_for_dominance_data_type + vec_last_valid_positions_for_dominance_data( num_vertices( g ) ); + iterator_property_map< + typename vec_last_valid_positions_for_dominance_data_type::iterator, + VertexIndexMap> + vec_last_valid_positions_for_dominance + (vec_last_valid_positions_for_dominance_data.begin(), + vertex_index_map); + BGL_FORALL_VERTICES_T(v, g, Graph) { + put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin()); + } + std::vector<size_t> vec_last_valid_index_for_dominance_data( num_vertices( g ), 0 ); + iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap> + vec_last_valid_index_for_dominance + (vec_last_valid_index_for_dominance_data.begin(), vertex_index_map); std::vector<bool> - b_vec_vertex_already_checked_for_dominance( num_vertices( g ), false ); - while( unprocessed_labels.size() ) + b_vec_vertex_already_checked_for_dominance_data( num_vertices( g ), false ); + iterator_property_map<std::vector<bool>::iterator, VertexIndexMap> + b_vec_vertex_already_checked_for_dominance + (b_vec_vertex_already_checked_for_dominance_data.begin(), + vertex_index_map); + + while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) ) { Splabel cur_label = unprocessed_labels.top(); + assert (cur_label->b_is_valid); unprocessed_labels.pop(); vis.on_label_popped( *cur_label, g ); // an Splabel object in unprocessed_labels and the respective Splabel @@ -239,14 +271,16 @@ void r_c_shortest_paths_dispatch // 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 + assert (cur_label->b_is_valid); if( !cur_label->b_is_dominated ) { - int i_cur_resident_vertex_num = cur_label->resident_vertex; + typename boost::graph_traits<Graph>::vertex_descriptor + i_cur_resident_vertex = 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() ) ) + get(vec_vertex_labels, i_cur_resident_vertex); + if( list_labels_cur_vertex.size() >= 2 + && vec_last_valid_index_for_dominance[i_cur_resident_vertex] + < list_labels_cur_vertex.size() ) { typename std::list<Splabel>::iterator outer_iter = list_labels_cur_vertex.begin(); @@ -254,14 +288,14 @@ void r_c_shortest_paths_dispatch while( outer_iter != list_labels_cur_vertex.end() ) { Splabel cur_outer_splabel = *outer_iter; + assert (cur_outer_splabel->b_is_valid); 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] ) + get(vec_last_valid_positions_for_dominance, + i_cur_resident_vertex) ) 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] + if( !get(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex) || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance ) { ++inner_iter; @@ -269,14 +303,15 @@ void r_c_shortest_paths_dispatch else { inner_iter = - vec_last_valid_positions_for_dominance - [i_cur_resident_vertex_num]; + get(vec_last_valid_positions_for_dominance, + i_cur_resident_vertex); ++inner_iter; } bool b_outer_iter_erased = false; while( inner_iter != list_labels_cur_vertex.end() ) { Splabel cur_inner_splabel = *inner_iter; + assert (cur_inner_splabel->b_is_valid); if( dominance( cur_outer_splabel-> cumulated_resource_consumption, cur_inner_splabel-> @@ -287,6 +322,7 @@ void r_c_shortest_paths_dispatch list_labels_cur_vertex.erase( buf ); if( cur_inner_splabel->b_is_processed ) { + cur_inner_splabel->b_is_valid = false; l_alloc.destroy( cur_inner_splabel.get() ); l_alloc.deallocate( cur_inner_splabel.get(), 1 ); } @@ -305,8 +341,10 @@ void r_c_shortest_paths_dispatch ++outer_iter; list_labels_cur_vertex.erase( buf ); b_outer_iter_erased = true; + assert (cur_outer_splabel->b_is_valid); if( cur_outer_splabel->b_is_processed ) { + cur_outer_splabel->b_is_valid = false; l_alloc.destroy( cur_outer_splabel.get() ); l_alloc.deallocate( cur_outer_splabel.get(), 1 ); } @@ -318,34 +356,38 @@ void r_c_shortest_paths_dispatch 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())); + if( list_labels_cur_vertex.size() > 1 ) + put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex, + (--(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; + put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex, + list_labels_cur_vertex.begin()); + put(b_vec_vertex_already_checked_for_dominance, + i_cur_resident_vertex, true); + put(vec_last_valid_index_for_dominance, i_cur_resident_vertex, + list_labels_cur_vertex.size() - 1); } } + assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid); if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t ) { // the devil don't sleep if( cur_label->b_is_dominated ) { + cur_label->b_is_valid = false; l_alloc.destroy( cur_label.get() ); l_alloc.deallocate( cur_label.get(), 1 ); } while( unprocessed_labels.size() ) { Splabel l = unprocessed_labels.top(); + assert (l->b_is_valid); unprocessed_labels.pop(); // delete only dominated labels, because nondominated labels are // deleted at the end of the function if( l->b_is_dominated ) { + l->b_is_valid = false; l_alloc.destroy( l.get() ); l_alloc.deallocate( l.get(), 1 ); } @@ -383,6 +425,7 @@ void r_c_shortest_paths_dispatch if( !b_feasible ) { vis.on_label_not_feasible( *new_label, g ); + new_label->b_is_valid = false; l_alloc.destroy( new_label ); l_alloc.deallocate( new_label, 1 ); } @@ -392,7 +435,7 @@ void r_c_shortest_paths_dispatch 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]]. + vec_vertex_labels[new_sp_label->resident_vertex]. push_back( new_sp_label ); unprocessed_labels.push( new_sp_label ); } @@ -400,16 +443,18 @@ void r_c_shortest_paths_dispatch } else { + assert (cur_label->b_is_valid); vis.on_label_dominated( *cur_label, g ); + cur_label->b_is_valid = false; l_alloc.destroy( cur_label.get() ); l_alloc.deallocate( cur_label.get(), 1 ); } } - std::list<Splabel> dsplabels = vec_vertex_labels[vertex_index_map[t]]; + std::list<Splabel> dsplabels = get(vec_vertex_labels, 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() ) + if( !dsplabels.empty() ) { for( ; csi != csi_end; ++csi ) { @@ -417,12 +462,14 @@ void r_c_shortest_paths_dispatch cur_pareto_optimal_path; const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label = (*csi).get(); + assert (p_cur_label->b_is_valid); 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; + assert (p_cur_label->b_is_valid); } pareto_optimal_solutions.push_back( cur_pareto_optimal_path ); if( !b_all_pareto_optimal_solutions ) @@ -430,13 +477,13 @@ void r_c_shortest_paths_dispatch } } - int i_size = static_cast<int>( vec_vertex_labels.size() ); - for( int i = 0; i < i_size; ++i ) - { + BGL_FORALL_VERTICES_T(i, g, Graph) { 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 ) { + assert ((*csi)->b_is_valid); + (*csi)->b_is_valid = false; l_alloc.destroy( (*csi).get() ); l_alloc.deallocate( (*csi).get(), 1 ); } @@ -458,6 +505,8 @@ struct default_r_c_shortest_paths_visitor void on_label_dominated( const Label&, const Graph& ) {} template<class Label, class Graph> void on_label_not_dominated( const Label&, const Graph& ) {} + template<class Queue, class Graph> + bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;} }; // default_r_c_shortest_paths_visitor @@ -677,7 +726,7 @@ void check_r_c_path( const Graph& g, typename graph_traits<Graph>::edge_descriptor& ed_last_extended_arc ) { - int i_size_ed_vec_path = static_cast<int>( ed_vec_path.size() ); + size_t i_size_ed_vec_path = ed_vec_path.size(); std::vector<typename graph_traits<Graph>::edge_descriptor> buf_path; if( i_size_ed_vec_path == 0 ) b_feasible = true; @@ -687,9 +736,9 @@ void check_r_c_path( const Graph& g, || 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 ) + for( size_t i = i_size_ed_vec_path ; i > 0; --i ) + buf_path.push_back( ed_vec_path[i - 1] ); + for( size_t i = 0; i < i_size_ed_vec_path - 1; ++i ) { if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) ) { @@ -705,7 +754,7 @@ void check_r_c_path( const Graph& g, 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 ) + for( size_t i = 0; i < i_size_ed_vec_path; ++i ) { ed_last_extended_arc = buf_path[i]; b_feasible = ref( g, |