1 // r_c_shortest_paths.hpp header file
3 // Copyright Michael Drexl 2005, 2006.
4 // Distributed under the Boost Software License, Version 1.0.
5 // (See accompanying file LICENSE_1_0.txt or copy at
6 // http://boost.org/LICENSE_1_0.txt)
8 #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
9 #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/graph/iteration_macros.hpp>
18 #include <boost/property_map/property_map.hpp>
22 // r_c_shortest_paths_label struct
23 template<class Graph, class Resource_Container>
24 struct r_c_shortest_paths_label
26 r_c_shortest_paths_label
27 ( const unsigned long n,
28 const Resource_Container& rc = Resource_Container(),
29 const r_c_shortest_paths_label* const pl = 0,
30 const typename graph_traits<Graph>::edge_descriptor& ed =
31 graph_traits<Graph>::edge_descriptor(),
32 const typename graph_traits<Graph>::vertex_descriptor& vd =
33 graph_traits<Graph>::vertex_descriptor() )
35 cumulated_resource_consumption( rc ),
38 resident_vertex( vd ),
39 b_is_dominated( false ),
40 b_is_processed( false ),
43 r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other )
47 this->~r_c_shortest_paths_label();
48 new( this ) r_c_shortest_paths_label( other );
51 const unsigned long num;
52 Resource_Container cumulated_resource_consumption;
53 const r_c_shortest_paths_label* const p_pred_label;
54 const typename graph_traits<Graph>::edge_descriptor pred_edge;
55 const typename graph_traits<Graph>::vertex_descriptor resident_vertex;
59 }; // r_c_shortest_paths_label
61 template<class Graph, class Resource_Container>
62 inline bool operator==
63 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
64 const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
66 assert (l1.b_is_valid && l2.b_is_valid);
68 l1.cumulated_resource_consumption == l2.cumulated_resource_consumption;
71 template<class Graph, class Resource_Container>
72 inline bool operator!=
73 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
74 const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
76 assert (l1.b_is_valid && l2.b_is_valid);
81 template<class Graph, class Resource_Container>
83 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
84 const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
86 assert (l1.b_is_valid && l2.b_is_valid);
88 l1.cumulated_resource_consumption < l2.cumulated_resource_consumption;
91 template<class Graph, class Resource_Container>
93 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
94 const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
96 assert (l1.b_is_valid && l2.b_is_valid);
98 l2.cumulated_resource_consumption < l1.cumulated_resource_consumption;
101 template<class Graph, class Resource_Container>
102 inline bool operator<=
103 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
104 const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
106 assert (l1.b_is_valid && l2.b_is_valid);
111 template<class Graph, class Resource_Container>
112 inline bool operator>=
113 ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1,
114 const r_c_shortest_paths_label<Graph, Resource_Container>& l2 )
116 assert (l1.b_is_valid && l2.b_is_valid);
117 return l2 < l1 || l1 == l2;
122 // ks_smart_pointer class
124 // Kuhlins, S.; Schader, M. (1999):
125 // Die C++-Standardbibliothek
129 class ks_smart_pointer
132 ks_smart_pointer( T* ptt = 0 ) : pt( ptt ) {}
133 ks_smart_pointer( const ks_smart_pointer& other ) : pt( other.pt ) {}
134 ks_smart_pointer& operator=( const ks_smart_pointer& other )
135 { pt = other.pt; return *this; }
136 ~ks_smart_pointer() {}
137 T& operator*() const { return *pt; }
138 T* operator->() const { return pt; }
139 T* get() const { return pt; }
140 operator T*() const { return pt; }
141 friend bool operator==( const ks_smart_pointer& t,
142 const ks_smart_pointer& u )
143 { return *t.pt == *u.pt; }
144 friend bool operator!=( const ks_smart_pointer& t,
145 const ks_smart_pointer& u )
146 { return *t.pt != *u.pt; }
147 friend bool operator<( const ks_smart_pointer& t,
148 const ks_smart_pointer& u )
149 { return *t.pt < *u.pt; }
150 friend bool operator>( const ks_smart_pointer& t,
151 const ks_smart_pointer& u )
152 { return *t.pt > *u.pt; }
153 friend bool operator<=( const ks_smart_pointer& t,
154 const ks_smart_pointer& u )
155 { return *t.pt <= *u.pt; }
156 friend bool operator>=( const ks_smart_pointer& t,
157 const ks_smart_pointer& u )
158 { return *t.pt >= *u.pt; }
161 }; // ks_smart_pointer
164 // r_c_shortest_paths_dispatch function (body/implementation)
165 template<class Graph,
166 class VertexIndexMap,
168 class Resource_Container,
169 class Resource_Extension_Function,
170 class Dominance_Function,
171 class Label_Allocator,
173 void r_c_shortest_paths_dispatch
175 const VertexIndexMap& vertex_index_map,
176 const EdgeIndexMap& /*edge_index_map*/,
177 typename graph_traits<Graph>::vertex_descriptor s,
178 typename graph_traits<Graph>::vertex_descriptor t,
179 // each inner vector corresponds to a pareto-optimal path
182 <typename graph_traits
183 <Graph>::edge_descriptor> >& pareto_optimal_solutions,
185 <Resource_Container>& pareto_optimal_resource_containers,
186 bool b_all_pareto_optimal_solutions,
187 // to initialize the first label/resource container
188 // and to carry the type information
189 const Resource_Container& rc,
190 Resource_Extension_Function& ref,
191 Dominance_Function& dominance,
192 // to specify the memory management strategy for the labels
193 Label_Allocator /*la*/,
196 pareto_optimal_resource_containers.clear();
197 pareto_optimal_solutions.clear();
199 size_t i_label_num = 0;
202 Label_Allocator::template rebind
203 <r_c_shortest_paths_label
204 <Graph, Resource_Container> >::other LAlloc;
208 <r_c_shortest_paths_label<Graph, Resource_Container> > Splabel;
209 std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> >
212 bool b_feasible = true;
213 r_c_shortest_paths_label<Graph, Resource_Container>* first_label =
214 l_alloc.allocate( 1 );
217 r_c_shortest_paths_label
218 <Graph, Resource_Container>( i_label_num++,
221 typename graph_traits<Graph>::
225 Splabel splabel_first_label = Splabel( first_label );
226 unprocessed_labels.push( splabel_first_label );
227 std::vector<std::list<Splabel> > vec_vertex_labels_data( num_vertices( g ) );
228 iterator_property_map<typename std::vector<std::list<Splabel> >::iterator,
230 vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map);
231 vec_vertex_labels[s].push_back( splabel_first_label );
233 std::vector<typename std::list<Splabel>::iterator>
234 vec_last_valid_positions_for_dominance_data_type;
235 vec_last_valid_positions_for_dominance_data_type
236 vec_last_valid_positions_for_dominance_data( num_vertices( g ) );
237 iterator_property_map<
238 typename vec_last_valid_positions_for_dominance_data_type::iterator,
240 vec_last_valid_positions_for_dominance
241 (vec_last_valid_positions_for_dominance_data.begin(),
243 BGL_FORALL_VERTICES_T(v, g, Graph) {
244 put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin());
246 std::vector<size_t> vec_last_valid_index_for_dominance_data( num_vertices( g ), 0 );
247 iterator_property_map<std::vector<size_t>::iterator, VertexIndexMap>
248 vec_last_valid_index_for_dominance
249 (vec_last_valid_index_for_dominance_data.begin(), vertex_index_map);
251 b_vec_vertex_already_checked_for_dominance_data( num_vertices( g ), false );
252 iterator_property_map<std::vector<bool>::iterator, VertexIndexMap>
253 b_vec_vertex_already_checked_for_dominance
254 (b_vec_vertex_already_checked_for_dominance_data.begin(),
257 while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) )
259 Splabel cur_label = unprocessed_labels.top();
260 assert (cur_label->b_is_valid);
261 unprocessed_labels.pop();
262 vis.on_label_popped( *cur_label, g );
263 // an Splabel object in unprocessed_labels and the respective Splabel
264 // object in the respective list<Splabel> of vec_vertex_labels share their
265 // embedded r_c_shortest_paths_label object
266 // to avoid memory leaks, dominated
267 // r_c_shortest_paths_label objects are marked and deleted when popped
268 // from unprocessed_labels, as they can no longer be deleted at the end of
269 // the function; only the Splabel object in unprocessed_labels still
270 // references the r_c_shortest_paths_label object
271 // this is also for efficiency, because the else branch is executed only
272 // if there is a chance that extending the
273 // label leads to new undominated labels, which in turn is possible only
274 // if the label to be extended is undominated
275 assert (cur_label->b_is_valid);
276 if( !cur_label->b_is_dominated )
278 typename boost::graph_traits<Graph>::vertex_descriptor
279 i_cur_resident_vertex = cur_label->resident_vertex;
280 std::list<Splabel>& list_labels_cur_vertex =
281 get(vec_vertex_labels, i_cur_resident_vertex);
282 if( list_labels_cur_vertex.size() >= 2
283 && vec_last_valid_index_for_dominance[i_cur_resident_vertex]
284 < list_labels_cur_vertex.size() )
286 typename std::list<Splabel>::iterator outer_iter =
287 list_labels_cur_vertex.begin();
288 bool b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = false;
289 while( outer_iter != list_labels_cur_vertex.end() )
291 Splabel cur_outer_splabel = *outer_iter;
292 assert (cur_outer_splabel->b_is_valid);
293 typename std::list<Splabel>::iterator inner_iter = outer_iter;
294 if( !b_outer_iter_at_or_beyond_last_valid_pos_for_dominance
296 get(vec_last_valid_positions_for_dominance,
297 i_cur_resident_vertex) )
298 b_outer_iter_at_or_beyond_last_valid_pos_for_dominance = true;
299 if( !get(b_vec_vertex_already_checked_for_dominance, i_cur_resident_vertex)
300 || b_outer_iter_at_or_beyond_last_valid_pos_for_dominance )
307 get(vec_last_valid_positions_for_dominance,
308 i_cur_resident_vertex);
311 bool b_outer_iter_erased = false;
312 while( inner_iter != list_labels_cur_vertex.end() )
314 Splabel cur_inner_splabel = *inner_iter;
315 assert (cur_inner_splabel->b_is_valid);
316 if( dominance( cur_outer_splabel->
317 cumulated_resource_consumption,
319 cumulated_resource_consumption ) )
321 typename std::list<Splabel>::iterator buf = inner_iter;
323 list_labels_cur_vertex.erase( buf );
324 if( cur_inner_splabel->b_is_processed )
326 cur_inner_splabel->b_is_valid = false;
327 l_alloc.destroy( cur_inner_splabel.get() );
328 l_alloc.deallocate( cur_inner_splabel.get(), 1 );
331 cur_inner_splabel->b_is_dominated = true;
336 if( dominance( cur_inner_splabel->
337 cumulated_resource_consumption,
339 cumulated_resource_consumption ) )
341 typename std::list<Splabel>::iterator buf = outer_iter;
343 list_labels_cur_vertex.erase( buf );
344 b_outer_iter_erased = true;
345 assert (cur_outer_splabel->b_is_valid);
346 if( cur_outer_splabel->b_is_processed )
348 cur_outer_splabel->b_is_valid = false;
349 l_alloc.destroy( cur_outer_splabel.get() );
350 l_alloc.deallocate( cur_outer_splabel.get(), 1 );
353 cur_outer_splabel->b_is_dominated = true;
357 if( !b_outer_iter_erased )
360 if( list_labels_cur_vertex.size() > 1 )
361 put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
362 (--(list_labels_cur_vertex.end())));
364 put(vec_last_valid_positions_for_dominance, i_cur_resident_vertex,
365 list_labels_cur_vertex.begin());
366 put(b_vec_vertex_already_checked_for_dominance,
367 i_cur_resident_vertex, true);
368 put(vec_last_valid_index_for_dominance, i_cur_resident_vertex,
369 list_labels_cur_vertex.size() - 1);
372 assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid);
373 if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t )
375 // the devil don't sleep
376 if( cur_label->b_is_dominated )
378 cur_label->b_is_valid = false;
379 l_alloc.destroy( cur_label.get() );
380 l_alloc.deallocate( cur_label.get(), 1 );
382 while( unprocessed_labels.size() )
384 Splabel l = unprocessed_labels.top();
385 assert (l->b_is_valid);
386 unprocessed_labels.pop();
387 // delete only dominated labels, because nondominated labels are
388 // deleted at the end of the function
389 if( l->b_is_dominated )
391 l->b_is_valid = false;
392 l_alloc.destroy( l.get() );
393 l_alloc.deallocate( l.get(), 1 );
398 if( !cur_label->b_is_dominated )
400 cur_label->b_is_processed = true;
401 vis.on_label_not_dominated( *cur_label, g );
402 typename graph_traits<Graph>::vertex_descriptor cur_vertex =
403 cur_label->resident_vertex;
404 typename graph_traits<Graph>::out_edge_iterator oei, oei_end;
405 for( boost::tie( oei, oei_end ) = out_edges( cur_vertex, g );
410 r_c_shortest_paths_label<Graph, Resource_Container>* new_label =
411 l_alloc.allocate( 1 );
412 l_alloc.construct( new_label,
413 r_c_shortest_paths_label
414 <Graph, Resource_Container>
416 cur_label->cumulated_resource_consumption,
419 target( *oei, g ) ) );
422 new_label->cumulated_resource_consumption,
423 new_label->p_pred_label->cumulated_resource_consumption,
424 new_label->pred_edge );
428 vis.on_label_not_feasible( *new_label, g );
429 new_label->b_is_valid = false;
430 l_alloc.destroy( new_label );
431 l_alloc.deallocate( new_label, 1 );
435 const r_c_shortest_paths_label<Graph, Resource_Container>&
436 ref_new_label = *new_label;
437 vis.on_label_feasible( ref_new_label, g );
438 Splabel new_sp_label( new_label );
439 vec_vertex_labels[new_sp_label->resident_vertex].
440 push_back( new_sp_label );
441 unprocessed_labels.push( new_sp_label );
447 assert (cur_label->b_is_valid);
448 vis.on_label_dominated( *cur_label, g );
449 cur_label->b_is_valid = false;
450 l_alloc.destroy( cur_label.get() );
451 l_alloc.deallocate( cur_label.get(), 1 );
454 std::list<Splabel> dsplabels = get(vec_vertex_labels, t);
455 typename std::list<Splabel>::const_iterator csi = dsplabels.begin();
456 typename std::list<Splabel>::const_iterator csi_end = dsplabels.end();
457 // if d could be reached from o
458 if( !dsplabels.empty() )
460 for( ; csi != csi_end; ++csi )
462 std::vector<typename graph_traits<Graph>::edge_descriptor>
463 cur_pareto_optimal_path;
464 const r_c_shortest_paths_label<Graph, Resource_Container>* p_cur_label =
466 assert (p_cur_label->b_is_valid);
467 pareto_optimal_resource_containers.
468 push_back( p_cur_label->cumulated_resource_consumption );
469 while( p_cur_label->num != 0 )
471 cur_pareto_optimal_path.push_back( p_cur_label->pred_edge );
472 p_cur_label = p_cur_label->p_pred_label;
473 assert (p_cur_label->b_is_valid);
475 pareto_optimal_solutions.push_back( cur_pareto_optimal_path );
476 if( !b_all_pareto_optimal_solutions )
481 BGL_FORALL_VERTICES_T(i, g, Graph) {
482 const std::list<Splabel>& list_labels_cur_vertex = vec_vertex_labels[i];
483 csi_end = list_labels_cur_vertex.end();
484 for( csi = list_labels_cur_vertex.begin(); csi != csi_end; ++csi )
486 assert ((*csi)->b_is_valid);
487 (*csi)->b_is_valid = false;
488 l_alloc.destroy( (*csi).get() );
489 l_alloc.deallocate( (*csi).get(), 1 );
492 } // r_c_shortest_paths_dispatch
496 // default_r_c_shortest_paths_visitor struct
497 struct default_r_c_shortest_paths_visitor
499 template<class Label, class Graph>
500 void on_label_popped( const Label&, const Graph& ) {}
501 template<class Label, class Graph>
502 void on_label_feasible( const Label&, const Graph& ) {}
503 template<class Label, class Graph>
504 void on_label_not_feasible( const Label&, const Graph& ) {}
505 template<class Label, class Graph>
506 void on_label_dominated( const Label&, const Graph& ) {}
507 template<class Label, class Graph>
508 void on_label_not_dominated( const Label&, const Graph& ) {}
509 template<class Queue, class Graph>
510 bool on_enter_loop(const Queue& queue, const Graph& graph) {return true;}
511 }; // default_r_c_shortest_paths_visitor
514 // default_r_c_shortest_paths_allocator
516 std::allocator<int> default_r_c_shortest_paths_allocator;
517 // default_r_c_shortest_paths_allocator
520 // r_c_shortest_paths functions (handle/interface)
522 // - return all pareto-optimal solutions
523 // - specify Label_Allocator and Visitor arguments
524 template<class Graph,
525 class VertexIndexMap,
527 class Resource_Container,
528 class Resource_Extension_Function,
529 class Dominance_Function,
530 class Label_Allocator,
532 void r_c_shortest_paths
534 const VertexIndexMap& vertex_index_map,
535 const EdgeIndexMap& edge_index_map,
536 typename graph_traits<Graph>::vertex_descriptor s,
537 typename graph_traits<Graph>::vertex_descriptor t,
538 // each inner vector corresponds to a pareto-optimal path
539 std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >&
540 pareto_optimal_solutions,
541 std::vector<Resource_Container>& pareto_optimal_resource_containers,
542 // to initialize the first label/resource container
543 // and to carry the type information
544 const Resource_Container& rc,
545 const Resource_Extension_Function& ref,
546 const Dominance_Function& dominance,
547 // to specify the memory management strategy for the labels
551 r_c_shortest_paths_dispatch( g,
556 pareto_optimal_solutions,
557 pareto_optimal_resource_containers,
567 // - return only one pareto-optimal solution
568 // - specify Label_Allocator and Visitor arguments
569 template<class Graph,
570 class VertexIndexMap,
572 class Resource_Container,
573 class Resource_Extension_Function,
574 class Dominance_Function,
575 class Label_Allocator,
577 void r_c_shortest_paths
579 const VertexIndexMap& vertex_index_map,
580 const EdgeIndexMap& edge_index_map,
581 typename graph_traits<Graph>::vertex_descriptor s,
582 typename graph_traits<Graph>::vertex_descriptor t,
583 std::vector<typename graph_traits<Graph>::edge_descriptor>&
584 pareto_optimal_solution,
585 Resource_Container& pareto_optimal_resource_container,
586 // to initialize the first label/resource container
587 // and to carry the type information
588 const Resource_Container& rc,
589 const Resource_Extension_Function& ref,
590 const Dominance_Function& dominance,
591 // to specify the memory management strategy for the labels
595 // each inner vector corresponds to a pareto-optimal path
596 std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >
597 pareto_optimal_solutions;
598 std::vector<Resource_Container> pareto_optimal_resource_containers;
599 r_c_shortest_paths_dispatch( g,
604 pareto_optimal_solutions,
605 pareto_optimal_resource_containers,
612 if (!pareto_optimal_solutions.empty()) {
613 pareto_optimal_solution = pareto_optimal_solutions[0];
614 pareto_optimal_resource_container = pareto_optimal_resource_containers[0];
619 // - return all pareto-optimal solutions
620 // - use default Label_Allocator and Visitor
621 template<class Graph,
622 class VertexIndexMap,
624 class Resource_Container,
625 class Resource_Extension_Function,
626 class Dominance_Function>
627 void r_c_shortest_paths
629 const VertexIndexMap& vertex_index_map,
630 const EdgeIndexMap& edge_index_map,
631 typename graph_traits<Graph>::vertex_descriptor s,
632 typename graph_traits<Graph>::vertex_descriptor t,
633 // each inner vector corresponds to a pareto-optimal path
634 std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >&
635 pareto_optimal_solutions,
636 std::vector<Resource_Container>& pareto_optimal_resource_containers,
637 // to initialize the first label/resource container
638 // and to carry the type information
639 const Resource_Container& rc,
640 const Resource_Extension_Function& ref,
641 const Dominance_Function& dominance )
643 r_c_shortest_paths_dispatch( g,
648 pareto_optimal_solutions,
649 pareto_optimal_resource_containers,
654 default_r_c_shortest_paths_allocator(),
655 default_r_c_shortest_paths_visitor() );
659 // - return only one pareto-optimal solution
660 // - use default Label_Allocator and Visitor
661 template<class Graph,
662 class VertexIndexMap,
664 class Resource_Container,
665 class Resource_Extension_Function,
666 class Dominance_Function>
667 void r_c_shortest_paths
669 const VertexIndexMap& vertex_index_map,
670 const EdgeIndexMap& edge_index_map,
671 typename graph_traits<Graph>::vertex_descriptor s,
672 typename graph_traits<Graph>::vertex_descriptor t,
673 std::vector<typename graph_traits<Graph>::edge_descriptor>&
674 pareto_optimal_solution,
675 Resource_Container& pareto_optimal_resource_container,
676 // to initialize the first label/resource container
677 // and to carry the type information
678 const Resource_Container& rc,
679 const Resource_Extension_Function& ref,
680 const Dominance_Function& dominance )
682 // each inner vector corresponds to a pareto-optimal path
683 std::vector<std::vector<typename graph_traits<Graph>::edge_descriptor> >
684 pareto_optimal_solutions;
685 std::vector<Resource_Container> pareto_optimal_resource_containers;
686 r_c_shortest_paths_dispatch( g,
691 pareto_optimal_solutions,
692 pareto_optimal_resource_containers,
697 default_r_c_shortest_paths_allocator(),
698 default_r_c_shortest_paths_visitor() );
699 if (!pareto_optimal_solutions.empty()) {
700 pareto_optimal_solution = pareto_optimal_solutions[0];
701 pareto_optimal_resource_container = pareto_optimal_resource_containers[0];
704 // r_c_shortest_paths
707 // check_r_c_path function
708 template<class Graph,
709 class Resource_Container,
710 class Resource_Extension_Function>
711 void check_r_c_path( const Graph& g,
713 <typename graph_traits
714 <Graph>::edge_descriptor>& ed_vec_path,
715 const Resource_Container& initial_resource_levels,
716 // if true, computed accumulated final resource levels must
717 // be equal to desired_final_resource_levels
718 // if false, computed accumulated final resource levels must
719 // be less than or equal to desired_final_resource_levels
720 bool b_result_must_be_equal_to_desired_final_resource_levels,
721 const Resource_Container& desired_final_resource_levels,
722 Resource_Container& actual_final_resource_levels,
723 const Resource_Extension_Function& ref,
724 bool& b_is_a_path_at_all,
726 bool& b_correctly_extended,
727 typename graph_traits<Graph>::edge_descriptor&
728 ed_last_extended_arc )
730 size_t i_size_ed_vec_path = ed_vec_path.size();
731 std::vector<typename graph_traits<Graph>::edge_descriptor> buf_path;
732 if( i_size_ed_vec_path == 0 )
736 if( i_size_ed_vec_path == 1
737 || target( ed_vec_path[0], g ) == source( ed_vec_path[1], g ) )
738 buf_path = ed_vec_path;
740 for( size_t i = i_size_ed_vec_path ; i > 0; --i )
741 buf_path.push_back( ed_vec_path[i - 1] );
742 for( size_t i = 0; i < i_size_ed_vec_path - 1; ++i )
744 if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) )
746 b_is_a_path_at_all = false;
748 b_correctly_extended = false;
753 b_is_a_path_at_all = true;
755 b_correctly_extended = false;
756 Resource_Container current_resource_levels = initial_resource_levels;
757 actual_final_resource_levels = current_resource_levels;
758 for( size_t i = 0; i < i_size_ed_vec_path; ++i )
760 ed_last_extended_arc = buf_path[i];
762 actual_final_resource_levels,
763 current_resource_levels,
765 current_resource_levels = actual_final_resource_levels;
769 if( b_result_must_be_equal_to_desired_final_resource_levels )
770 b_correctly_extended =
771 actual_final_resource_levels == desired_final_resource_levels ?
775 if( actual_final_resource_levels < desired_final_resource_levels
776 || actual_final_resource_levels == desired_final_resource_levels )
777 b_correctly_extended = true;
783 #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP