123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751 |
- // 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 <list>
- #include <boost/make_shared.hpp>
- #include <boost/enable_shared_from_this.hpp>
- #include <boost/graph/graph_traits.hpp>
- #include <boost/graph/iteration_macros.hpp>
- #include <boost/property_map/property_map.hpp>
- namespace boost {
- // r_c_shortest_paths_label struct
- template<class Graph, class Resource_Container>
- struct r_c_shortest_paths_label : public boost::enable_shared_from_this<r_c_shortest_paths_label<Graph, Resource_Container> >
- {
- r_c_shortest_paths_label
- ( const unsigned long n,
- const Resource_Container& rc = Resource_Container(),
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > pl = boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> >(),
- 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 boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > 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;
- }
- template<typename Graph, typename Resource_Container>
- inline bool operator<
- ( const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t,
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u) {
- return *t < *u;
- }
- template<typename Graph, typename Resource_Container>
- inline bool operator<=( const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t,
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u ) {
- return *t <= *u;
- }
- template<typename Graph, typename Resource_Container>
- inline bool operator>
- (
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t,
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u ) {
- return *t > *u;
- }
- template<typename Graph, typename Resource_Container>
- inline bool operator>=
- (
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &t,
- const boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > &u) {
- return *t >= *u;
- }
- namespace detail {
- // 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();
- size_t i_label_num = 0;
- #if defined(BOOST_NO_CXX11_ALLOCATOR)
- typedef
- typename
- Label_Allocator::template rebind
- <r_c_shortest_paths_label
- <Graph, Resource_Container> >::other LAlloc;
- #else
- typedef
- typename
- std::allocator_traits<Label_Allocator>::template rebind_alloc
- <r_c_shortest_paths_label
- <Graph, Resource_Container> > LAlloc;
- typedef std::allocator_traits<LAlloc> LTraits;
- #endif
- LAlloc l_alloc;
- typedef
- boost::shared_ptr<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;
- Splabel splabel_first_label = boost::allocate_shared<r_c_shortest_paths_label<Graph, Resource_Container> >(
- l_alloc,
- i_label_num++,
- rc,
- boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> >(),
- typename graph_traits<Graph>::edge_descriptor(),
- s );
- unprocessed_labels.push( splabel_first_label );
- 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_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();
- 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 )
- {
- typename boost::graph_traits<Graph>::vertex_descriptor
- i_cur_resident_vertex = cur_label->resident_vertex;
- std::list<Splabel>& list_labels_cur_vertex =
- 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();
- 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 ==
- get(vec_last_valid_positions_for_dominance,
- i_cur_resident_vertex) )
- b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true;
- 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;
- }
- else
- {
- inner_iter =
- 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;
- 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 )
- {
- cur_inner_splabel.reset();
- }
- 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 )
- {
- cur_outer_splabel.reset();
- }
- else
- cur_outer_splabel->b_is_dominated = true;
- break;
- }
- }
- if( !b_outer_iter_erased )
- ++outer_iter;
- }
- if( list_labels_cur_vertex.size() > 1 )
- put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
- (--(list_labels_cur_vertex.end())));
- else
- 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);
- }
- }
- if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t )
- {
- // the devil don't sleep
- if( cur_label->b_is_dominated )
- {
- cur_label.reset();
- }
- 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.reset();
- }
- }
- 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;
- Splabel new_label = boost::allocate_shared<r_c_shortest_paths_label<Graph, Resource_Container> >(
- l_alloc,
- i_label_num++,
- cur_label->cumulated_resource_consumption,
- cur_label,
- *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 );
- new_label.reset();
- }
- else
- {
- vis.on_label_feasible( *new_label, g );
- vec_vertex_labels[new_label->resident_vertex].
- push_back( new_label );
- unprocessed_labels.push( new_label );
- }
- }
- }
- else
- {
- vis.on_label_dominated( *cur_label, g );
- cur_label.reset();
- }
- }
- 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.empty() )
- {
- for( ; csi != csi_end; ++csi )
- {
- std::vector<typename graph_traits<Graph>::edge_descriptor>
- cur_pareto_optimal_path;
- boost::shared_ptr<r_c_shortest_paths_label<Graph, Resource_Container> > p_cur_label = *csi;
- 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;
- // assertion b_is_valid beyond this point is not correct if the domination function
- // requires resource levels to be strictly greater than existing values
- //
- // Example
- // Customers
- // id min_arrival max_departure
- // 2 0 974
- // 3 0 972
- // 4 0 964
- // 5 678 801
- //
- // Path A: 2-3-4-5 (times: 0-16-49-84-678)
- // Path B: 3-2-4-5 (times: 0-18-51-62-678)
- // The partial path 3-2-4 dominates the other partial path 2-3-4,
- // though the path 3-2-4-5 does not strictly dominate the path 2-3-4-5
- }
- pareto_optimal_solutions.push_back( cur_pareto_optimal_path );
- if( !b_all_pareto_optimal_solutions )
- break;
- }
- }
- BGL_FORALL_VERTICES_T(i, g, Graph) {
- std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
- typename std::list<Splabel>::iterator si = list_labels_cur_vertex.begin();
- const typename std::list<Splabel>::iterator si_end = list_labels_cur_vertex.end();
- for(; si != si_end; ++si )
- {
- (*si).reset();
- }
- }
- } // 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& ) {}
- template<class Queue, class Graph>
- bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;}
- }; // 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 )
- {
- 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;
- 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( 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 ) )
- {
- 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( size_t 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
|