]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // r_c_shortest_paths.hpp header file |
2 | ||
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) | |
7 | ||
8 | #ifndef BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP | |
9 | #define BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP | |
10 | ||
11 | #include <map> | |
12 | #include <queue> | |
13 | #include <vector> | |
14 | #include <list> | |
15 | ||
16 | #include <boost/graph/graph_traits.hpp> | |
17 | #include <boost/graph/iteration_macros.hpp> | |
18 | #include <boost/property_map/property_map.hpp> | |
19 | ||
20 | namespace boost { | |
21 | ||
22 | // r_c_shortest_paths_label struct | |
23 | template<class Graph, class Resource_Container> | |
24 | struct r_c_shortest_paths_label | |
25 | { | |
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() ) | |
34 | : num( n ), | |
35 | cumulated_resource_consumption( rc ), | |
36 | p_pred_label( pl ), | |
37 | pred_edge( ed ), | |
38 | resident_vertex( vd ), | |
39 | b_is_dominated( false ), | |
40 | b_is_processed( false ), | |
41 | b_is_valid( true ) | |
42 | {} | |
43 | r_c_shortest_paths_label& operator=( const r_c_shortest_paths_label& other ) | |
44 | { | |
45 | if( this == &other ) | |
46 | return *this; | |
47 | this->~r_c_shortest_paths_label(); | |
48 | new( this ) r_c_shortest_paths_label( other ); | |
49 | return *this; | |
50 | } | |
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; | |
56 | bool b_is_dominated; | |
57 | bool b_is_processed; | |
58 | bool b_is_valid; | |
59 | }; // r_c_shortest_paths_label | |
60 | ||
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 ) | |
65 | { | |
66 | assert (l1.b_is_valid && l2.b_is_valid); | |
67 | return | |
68 | l1.cumulated_resource_consumption == l2.cumulated_resource_consumption; | |
69 | } | |
70 | ||
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 ) | |
75 | { | |
76 | assert (l1.b_is_valid && l2.b_is_valid); | |
77 | return | |
78 | !( l1 == l2 ); | |
79 | } | |
80 | ||
81 | template<class Graph, class Resource_Container> | |
82 | inline bool operator< | |
83 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, | |
84 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) | |
85 | { | |
86 | assert (l1.b_is_valid && l2.b_is_valid); | |
87 | return | |
88 | l1.cumulated_resource_consumption < l2.cumulated_resource_consumption; | |
89 | } | |
90 | ||
91 | template<class Graph, class Resource_Container> | |
92 | inline bool operator> | |
93 | ( const r_c_shortest_paths_label<Graph, Resource_Container>& l1, | |
94 | const r_c_shortest_paths_label<Graph, Resource_Container>& l2 ) | |
95 | { | |
96 | assert (l1.b_is_valid && l2.b_is_valid); | |
97 | return | |
98 | l2.cumulated_resource_consumption < l1.cumulated_resource_consumption; | |
99 | } | |
100 | ||
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 ) | |
105 | { | |
106 | assert (l1.b_is_valid && l2.b_is_valid); | |
107 | return | |
108 | l1 < l2 || l1 == l2; | |
109 | } | |
110 | ||
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 ) | |
115 | { | |
116 | assert (l1.b_is_valid && l2.b_is_valid); | |
117 | return l2 < l1 || l1 == l2; | |
118 | } | |
119 | ||
120 | namespace detail { | |
121 | ||
122 | // ks_smart_pointer class | |
123 | // from: | |
124 | // Kuhlins, S.; Schader, M. (1999): | |
125 | // Die C++-Standardbibliothek | |
126 | // Springer, Berlin | |
127 | // p. 333 f. | |
128 | template<class T> | |
129 | class ks_smart_pointer | |
130 | { | |
131 | public: | |
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; } | |
159 | private: | |
160 | T* pt; | |
161 | }; // ks_smart_pointer | |
162 | ||
163 | ||
164 | // r_c_shortest_paths_dispatch function (body/implementation) | |
165 | template<class Graph, | |
166 | class VertexIndexMap, | |
167 | class EdgeIndexMap, | |
168 | class Resource_Container, | |
169 | class Resource_Extension_Function, | |
170 | class Dominance_Function, | |
171 | class Label_Allocator, | |
172 | class Visitor> | |
173 | void r_c_shortest_paths_dispatch | |
174 | ( const Graph& g, | |
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 | |
180 | std::vector | |
181 | <std::vector | |
182 | <typename graph_traits | |
183 | <Graph>::edge_descriptor> >& pareto_optimal_solutions, | |
184 | std::vector | |
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*/, | |
194 | Visitor vis ) | |
195 | { | |
196 | pareto_optimal_resource_containers.clear(); | |
197 | pareto_optimal_solutions.clear(); | |
198 | ||
199 | size_t i_label_num = 0; | |
200 | typedef | |
201 | typename | |
202 | Label_Allocator::template rebind | |
203 | <r_c_shortest_paths_label | |
204 | <Graph, Resource_Container> >::other LAlloc; | |
205 | LAlloc l_alloc; | |
206 | typedef | |
207 | ks_smart_pointer | |
208 | <r_c_shortest_paths_label<Graph, Resource_Container> > Splabel; | |
209 | std::priority_queue<Splabel, std::vector<Splabel>, std::greater<Splabel> > | |
210 | unprocessed_labels; | |
211 | ||
212 | bool b_feasible = true; | |
213 | r_c_shortest_paths_label<Graph, Resource_Container>* first_label = | |
214 | l_alloc.allocate( 1 ); | |
215 | l_alloc.construct | |
216 | ( first_label, | |
217 | r_c_shortest_paths_label | |
218 | <Graph, Resource_Container>( i_label_num++, | |
219 | rc, | |
220 | 0, | |
221 | typename graph_traits<Graph>:: | |
222 | edge_descriptor(), | |
223 | s ) ); | |
224 | ||
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, | |
229 | VertexIndexMap> | |
230 | vec_vertex_labels(vec_vertex_labels_data.begin(), vertex_index_map); | |
231 | vec_vertex_labels[s].push_back( splabel_first_label ); | |
232 | typedef | |
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, | |
239 | VertexIndexMap> | |
240 | vec_last_valid_positions_for_dominance | |
241 | (vec_last_valid_positions_for_dominance_data.begin(), | |
242 | vertex_index_map); | |
243 | BGL_FORALL_VERTICES_T(v, g, Graph) { | |
244 | put(vec_last_valid_positions_for_dominance, v, vec_vertex_labels[v].begin()); | |
245 | } | |
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); | |
250 | std::vector<bool> | |
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(), | |
255 | vertex_index_map); | |
256 | ||
257 | while( !unprocessed_labels.empty() && vis.on_enter_loop(unprocessed_labels, g) ) | |
258 | { | |
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 ) | |
277 | { | |
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() ) | |
285 | { | |
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() ) | |
290 | { | |
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 | |
295 | && outer_iter == | |
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 ) | |
301 | { | |
302 | ++inner_iter; | |
303 | } | |
304 | else | |
305 | { | |
306 | inner_iter = | |
307 | get(vec_last_valid_positions_for_dominance, | |
308 | i_cur_resident_vertex); | |
309 | ++inner_iter; | |
310 | } | |
311 | bool b_outer_iter_erased = false; | |
312 | while( inner_iter != list_labels_cur_vertex.end() ) | |
313 | { | |
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, | |
318 | cur_inner_splabel-> | |
319 | cumulated_resource_consumption ) ) | |
320 | { | |
321 | typename std::list<Splabel>::iterator buf = inner_iter; | |
322 | ++inner_iter; | |
323 | list_labels_cur_vertex.erase( buf ); | |
324 | if( cur_inner_splabel->b_is_processed ) | |
325 | { | |
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 ); | |
329 | } | |
330 | else | |
331 | cur_inner_splabel->b_is_dominated = true; | |
332 | continue; | |
333 | } | |
334 | else | |
335 | ++inner_iter; | |
336 | if( dominance( cur_inner_splabel-> | |
337 | cumulated_resource_consumption, | |
338 | cur_outer_splabel-> | |
339 | cumulated_resource_consumption ) ) | |
340 | { | |
341 | typename std::list<Splabel>::iterator buf = outer_iter; | |
342 | ++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 ) | |
347 | { | |
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 ); | |
351 | } | |
352 | else | |
353 | cur_outer_splabel->b_is_dominated = true; | |
354 | break; | |
355 | } | |
356 | } | |
357 | if( !b_outer_iter_erased ) | |
358 | ++outer_iter; | |
359 | } | |
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()))); | |
363 | else | |
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); | |
370 | } | |
371 | } | |
372 | assert (b_all_pareto_optimal_solutions || cur_label->b_is_valid); | |
373 | if( !b_all_pareto_optimal_solutions && cur_label->resident_vertex == t ) | |
374 | { | |
375 | // the devil don't sleep | |
376 | if( cur_label->b_is_dominated ) | |
377 | { | |
378 | cur_label->b_is_valid = false; | |
379 | l_alloc.destroy( cur_label.get() ); | |
380 | l_alloc.deallocate( cur_label.get(), 1 ); | |
381 | } | |
382 | while( unprocessed_labels.size() ) | |
383 | { | |
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 ) | |
390 | { | |
391 | l->b_is_valid = false; | |
392 | l_alloc.destroy( l.get() ); | |
393 | l_alloc.deallocate( l.get(), 1 ); | |
394 | } | |
395 | } | |
396 | break; | |
397 | } | |
398 | if( !cur_label->b_is_dominated ) | |
399 | { | |
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 ); | |
406 | oei != oei_end; | |
407 | ++oei ) | |
408 | { | |
409 | b_feasible = true; | |
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> | |
415 | ( i_label_num++, | |
416 | cur_label->cumulated_resource_consumption, | |
417 | cur_label.get(), | |
418 | *oei, | |
419 | target( *oei, g ) ) ); | |
420 | b_feasible = | |
421 | ref( g, | |
422 | new_label->cumulated_resource_consumption, | |
423 | new_label->p_pred_label->cumulated_resource_consumption, | |
424 | new_label->pred_edge ); | |
425 | ||
426 | if( !b_feasible ) | |
427 | { | |
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 ); | |
432 | } | |
433 | else | |
434 | { | |
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 ); | |
442 | } | |
443 | } | |
444 | } | |
445 | else | |
446 | { | |
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 ); | |
452 | } | |
453 | } | |
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() ) | |
459 | { | |
460 | for( ; csi != csi_end; ++csi ) | |
461 | { | |
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 = | |
465 | (*csi).get(); | |
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 ) | |
470 | { | |
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); | |
474 | } | |
475 | pareto_optimal_solutions.push_back( cur_pareto_optimal_path ); | |
476 | if( !b_all_pareto_optimal_solutions ) | |
477 | break; | |
478 | } | |
479 | } | |
480 | ||
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 ) | |
485 | { | |
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 ); | |
490 | } | |
491 | } | |
492 | } // r_c_shortest_paths_dispatch | |
493 | ||
494 | } // detail | |
495 | ||
496 | // default_r_c_shortest_paths_visitor struct | |
497 | struct default_r_c_shortest_paths_visitor | |
498 | { | |
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 | |
512 | ||
513 | ||
514 | // default_r_c_shortest_paths_allocator | |
515 | typedef | |
516 | std::allocator<int> default_r_c_shortest_paths_allocator; | |
517 | // default_r_c_shortest_paths_allocator | |
518 | ||
519 | ||
520 | // r_c_shortest_paths functions (handle/interface) | |
521 | // first overload: | |
522 | // - return all pareto-optimal solutions | |
523 | // - specify Label_Allocator and Visitor arguments | |
524 | template<class Graph, | |
525 | class VertexIndexMap, | |
526 | class EdgeIndexMap, | |
527 | class Resource_Container, | |
528 | class Resource_Extension_Function, | |
529 | class Dominance_Function, | |
530 | class Label_Allocator, | |
531 | class Visitor> | |
532 | void r_c_shortest_paths | |
533 | ( const Graph& g, | |
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 | |
548 | Label_Allocator la, | |
549 | Visitor vis ) | |
550 | { | |
551 | r_c_shortest_paths_dispatch( g, | |
552 | vertex_index_map, | |
553 | edge_index_map, | |
554 | s, | |
555 | t, | |
556 | pareto_optimal_solutions, | |
557 | pareto_optimal_resource_containers, | |
558 | true, | |
559 | rc, | |
560 | ref, | |
561 | dominance, | |
562 | la, | |
563 | vis ); | |
564 | } | |
565 | ||
566 | // second overload: | |
567 | // - return only one pareto-optimal solution | |
568 | // - specify Label_Allocator and Visitor arguments | |
569 | template<class Graph, | |
570 | class VertexIndexMap, | |
571 | class EdgeIndexMap, | |
572 | class Resource_Container, | |
573 | class Resource_Extension_Function, | |
574 | class Dominance_Function, | |
575 | class Label_Allocator, | |
576 | class Visitor> | |
577 | void r_c_shortest_paths | |
578 | ( const Graph& g, | |
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 | |
592 | Label_Allocator la, | |
593 | Visitor vis ) | |
594 | { | |
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, | |
600 | vertex_index_map, | |
601 | edge_index_map, | |
602 | s, | |
603 | t, | |
604 | pareto_optimal_solutions, | |
605 | pareto_optimal_resource_containers, | |
606 | false, | |
607 | rc, | |
608 | ref, | |
609 | dominance, | |
610 | la, | |
611 | vis ); | |
612 | if (!pareto_optimal_solutions.empty()) { | |
613 | pareto_optimal_solution = pareto_optimal_solutions[0]; | |
614 | pareto_optimal_resource_container = pareto_optimal_resource_containers[0]; | |
615 | } | |
616 | } | |
617 | ||
618 | // third overload: | |
619 | // - return all pareto-optimal solutions | |
620 | // - use default Label_Allocator and Visitor | |
621 | template<class Graph, | |
622 | class VertexIndexMap, | |
623 | class EdgeIndexMap, | |
624 | class Resource_Container, | |
625 | class Resource_Extension_Function, | |
626 | class Dominance_Function> | |
627 | void r_c_shortest_paths | |
628 | ( const Graph& g, | |
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 ) | |
642 | { | |
643 | r_c_shortest_paths_dispatch( g, | |
644 | vertex_index_map, | |
645 | edge_index_map, | |
646 | s, | |
647 | t, | |
648 | pareto_optimal_solutions, | |
649 | pareto_optimal_resource_containers, | |
650 | true, | |
651 | rc, | |
652 | ref, | |
653 | dominance, | |
654 | default_r_c_shortest_paths_allocator(), | |
655 | default_r_c_shortest_paths_visitor() ); | |
656 | } | |
657 | ||
658 | // fourth overload: | |
659 | // - return only one pareto-optimal solution | |
660 | // - use default Label_Allocator and Visitor | |
661 | template<class Graph, | |
662 | class VertexIndexMap, | |
663 | class EdgeIndexMap, | |
664 | class Resource_Container, | |
665 | class Resource_Extension_Function, | |
666 | class Dominance_Function> | |
667 | void r_c_shortest_paths | |
668 | ( const Graph& g, | |
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 ) | |
681 | { | |
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, | |
687 | vertex_index_map, | |
688 | edge_index_map, | |
689 | s, | |
690 | t, | |
691 | pareto_optimal_solutions, | |
692 | pareto_optimal_resource_containers, | |
693 | false, | |
694 | rc, | |
695 | ref, | |
696 | dominance, | |
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]; | |
702 | } | |
703 | } | |
704 | // r_c_shortest_paths | |
705 | ||
706 | ||
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, | |
712 | const std::vector | |
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, | |
725 | bool& b_feasible, | |
726 | bool& b_correctly_extended, | |
727 | typename graph_traits<Graph>::edge_descriptor& | |
728 | ed_last_extended_arc ) | |
729 | { | |
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 ) | |
733 | b_feasible = true; | |
734 | else | |
735 | { | |
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; | |
739 | else | |
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 ) | |
743 | { | |
744 | if( target( buf_path[i], g ) != source( buf_path[i + 1], g ) ) | |
745 | { | |
746 | b_is_a_path_at_all = false; | |
747 | b_feasible = false; | |
748 | b_correctly_extended = false; | |
749 | return; | |
750 | } | |
751 | } | |
752 | } | |
753 | b_is_a_path_at_all = true; | |
754 | b_feasible = 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 ) | |
759 | { | |
760 | ed_last_extended_arc = buf_path[i]; | |
761 | b_feasible = ref( g, | |
762 | actual_final_resource_levels, | |
763 | current_resource_levels, | |
764 | buf_path[i] ); | |
765 | current_resource_levels = actual_final_resource_levels; | |
766 | if( !b_feasible ) | |
767 | return; | |
768 | } | |
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 ? | |
772 | true : false; | |
773 | else | |
774 | { | |
775 | if( actual_final_resource_levels < desired_final_resource_levels | |
776 | || actual_final_resource_levels == desired_final_resource_levels ) | |
777 | b_correctly_extended = true; | |
778 | } | |
779 | } // check_path | |
780 | ||
781 | } // namespace | |
782 | ||
783 | #endif // BOOST_GRAPH_R_C_SHORTEST_PATHS_HPP |