1 | // |
---|
2 | //======================================================================= |
---|
3 | // Copyright (c) 2004 Kristopher Beevers |
---|
4 | // 2007 Anton A. Patrushev, Orkney Inc. |
---|
5 | // |
---|
6 | // Distributed under the Boost Software License, Version 1.0. (See |
---|
7 | // accompanying file LICENSE_1_0.txt or copy at |
---|
8 | // http://www.boost.org/LICENSE_1_0.txt) |
---|
9 | //======================================================================= |
---|
10 | // |
---|
11 | |
---|
12 | #ifndef BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP |
---|
13 | #define BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP |
---|
14 | |
---|
15 | #define MAX_RULE_LENGTH 5 |
---|
16 | |
---|
17 | #include <functional> |
---|
18 | #include <boost/limits.hpp> |
---|
19 | #include <boost/graph/named_function_params.hpp> |
---|
20 | #include <boost/pending/mutable_queue.hpp> |
---|
21 | #include <boost/pending/relaxed_heap.hpp> |
---|
22 | #include <shooting_star_relax.hpp> |
---|
23 | #include <boost/pending/indirect_cmp.hpp> |
---|
24 | #include <boost/graph/exception.hpp> |
---|
25 | #include <boost/graph/breadth_first_search.hpp> |
---|
26 | |
---|
27 | #include <queue> |
---|
28 | #include "edge_visitors.hpp" |
---|
29 | |
---|
30 | #include <iostream> |
---|
31 | #include <fstream> |
---|
32 | |
---|
33 | template <class Edge> |
---|
34 | struct EdgeRankCompare { |
---|
35 | bool operator()(const Edge& LHS, const Edge& RHS) { |
---|
36 | return (LHS.rank < RHS.rank); |
---|
37 | } |
---|
38 | |
---|
39 | }; |
---|
40 | |
---|
41 | template <class Edge, class Container, class Cmp> |
---|
42 | class edge_queue : public std::priority_queue<Edge, Container, Cmp> |
---|
43 | { |
---|
44 | protected: |
---|
45 | using std::priority_queue< Edge, Container, Cmp >::c; |
---|
46 | using std::priority_queue< Edge, Container, Cmp >::comp; |
---|
47 | |
---|
48 | public: |
---|
49 | void sort() |
---|
50 | { |
---|
51 | sort_heap(c.begin(), c.end(), comp); |
---|
52 | } |
---|
53 | }; |
---|
54 | |
---|
55 | namespace boost { |
---|
56 | |
---|
57 | |
---|
58 | template <class Heuristic, class Graph> |
---|
59 | struct AStarHeuristicConcept { |
---|
60 | void constraints() |
---|
61 | { |
---|
62 | function_requires< CopyConstructibleConcept<Heuristic> >(); |
---|
63 | h(u); |
---|
64 | } |
---|
65 | Heuristic h; |
---|
66 | typename graph_traits<Graph>::vertex_descriptor u; |
---|
67 | }; |
---|
68 | |
---|
69 | |
---|
70 | |
---|
71 | template <class Graph, class CostType> |
---|
72 | class astar_heuristic : public std::unary_function< |
---|
73 | typename graph_traits<Graph>::vertex_descriptor, CostType> |
---|
74 | { |
---|
75 | public: |
---|
76 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
---|
77 | astar_heuristic() {} |
---|
78 | CostType operator()(Vertex u) { return static_cast<CostType>(0); } |
---|
79 | }; |
---|
80 | |
---|
81 | |
---|
82 | |
---|
83 | template <class Visitor, class Graph> |
---|
84 | struct ShootingStarVisitorConcept { |
---|
85 | void constraints() |
---|
86 | { |
---|
87 | function_requires< CopyConstructibleConcept<Visitor> >(); |
---|
88 | vis.initialize_vertex(u, g); |
---|
89 | vis.discover_vertex(u, g); |
---|
90 | vis.examine_vertex(u, g); |
---|
91 | vis.examine_edge(e, g); |
---|
92 | vis.black_target(e, pe, g, e_max_id); |
---|
93 | vis.gray_target(e, pe, g, e_max_id); |
---|
94 | vis.finish_vertex(u, g); |
---|
95 | |
---|
96 | vis.tree_edge(e, pe, g, e_max_id); |
---|
97 | |
---|
98 | vis.initialize_edge(e, g); |
---|
99 | vis.discover_edge(e, g); |
---|
100 | vis.finish_edge(e, g); |
---|
101 | |
---|
102 | } |
---|
103 | Visitor vis; |
---|
104 | Graph g; |
---|
105 | typename graph_traits<Graph>::vertex_descriptor u; |
---|
106 | typename graph_traits<Graph>::edge_descriptor e, pe; |
---|
107 | int e_max_id; |
---|
108 | }; |
---|
109 | |
---|
110 | |
---|
111 | template <class IncidenceGraph, class Buffer, class BFSVisitor, |
---|
112 | class ColorMap, class EdgeColorMap, class HistoryMap> |
---|
113 | void shooting_star_edges_visit (const IncidenceGraph& g, |
---|
114 | typename graph_traits<IncidenceGraph>::edge_descriptor s, |
---|
115 | Buffer& Q, BFSVisitor vis, ColorMap color, EdgeColorMap edge_color, |
---|
116 | HistoryMap history, int e_max_id) |
---|
117 | { |
---|
118 | function_requires< IncidenceGraphConcept<IncidenceGraph> >(); |
---|
119 | typedef graph_traits<IncidenceGraph> GTraits; |
---|
120 | typedef typename GTraits::vertex_descriptor Vertex; |
---|
121 | typedef typename GTraits::edge_descriptor Edge; |
---|
122 | function_requires< ShootingStarVisitorConcept<BFSVisitor, IncidenceGraph> >(); |
---|
123 | function_requires< ReadWritePropertyMapConcept<ColorMap, Vertex> >(); |
---|
124 | function_requires< ReadWritePropertyMapConcept<EdgeColorMap, Edge> >(); |
---|
125 | |
---|
126 | typedef typename property_traits<ColorMap>::value_type ColorValue; |
---|
127 | typedef color_traits<ColorValue> Color; |
---|
128 | |
---|
129 | typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue; |
---|
130 | typedef color_traits<EdgeColorValue> EdgeColor; |
---|
131 | |
---|
132 | typename GTraits::out_edge_iterator ei, ei_end; |
---|
133 | |
---|
134 | put(edge_color, s, EdgeColor::gray()); vis.discover_edge(s, g); |
---|
135 | Q.push(s); |
---|
136 | |
---|
137 | while (! Q.empty()) { |
---|
138 | Edge e = Q.top(); Q.pop(); vis.examine_edge(e, g); |
---|
139 | |
---|
140 | for (tie(ei, ei_end) = out_edges(target(e, g), g); ei != ei_end; ++ei) { |
---|
141 | |
---|
142 | EdgeColorValue e_color = get(edge_color, *ei); |
---|
143 | |
---|
144 | if (e_color == EdgeColor::white()) { vis.tree_edge(*ei, e, g, e_max_id); |
---|
145 | put(edge_color, *ei, EdgeColor::gray()); vis.discover_edge(*ei, g); |
---|
146 | Q.push(*ei); |
---|
147 | |
---|
148 | } else { vis.non_tree_edge(*ei, g); |
---|
149 | if (e_color == EdgeColor::gray()){ vis.gray_target(*ei, e, g, e_max_id); |
---|
150 | } |
---|
151 | else{ vis.black_target(*ei, e, g, e_max_id); |
---|
152 | } |
---|
153 | } |
---|
154 | |
---|
155 | } // end for |
---|
156 | |
---|
157 | put(edge_color, e, EdgeColor::black()); vis.finish_edge(e, g); |
---|
158 | |
---|
159 | } // end while |
---|
160 | |
---|
161 | } |
---|
162 | |
---|
163 | |
---|
164 | template <class Visitors = null_visitor> |
---|
165 | class shooting_star_visitor : public bfs_visitor<Visitors> { |
---|
166 | public: |
---|
167 | shooting_star_visitor() {} |
---|
168 | shooting_star_visitor(Visitors vis) |
---|
169 | : bfs_visitor<Visitors>(vis) {} |
---|
170 | |
---|
171 | template <class Edge, class Graph> |
---|
172 | void edge_relaxed(Edge e, Graph& g) { |
---|
173 | invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); |
---|
174 | } |
---|
175 | template <class Edge, class Graph> |
---|
176 | void edge_not_relaxed(Edge e, Graph& g) { |
---|
177 | invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); |
---|
178 | } |
---|
179 | template <class Edge, class Graph> |
---|
180 | void initialize_edge(Edge e, Graph& g) { |
---|
181 | invoke_visitors(this->m_vis, e, g, on_initialize_edge()); |
---|
182 | } |
---|
183 | |
---|
184 | private: |
---|
185 | template <class Edge, class Graph> |
---|
186 | void tree_edge(Edge e, Edge pe, Graph& g) {} |
---|
187 | template <class Edge, class Graph> |
---|
188 | void non_tree_edge(Edge e, Graph& g) {} |
---|
189 | }; |
---|
190 | template <class Visitors> |
---|
191 | shooting_star_visitor<Visitors> |
---|
192 | make_shooting_star_visitor(Visitors vis) { |
---|
193 | return shooting_star_visitor<Visitors>(vis); |
---|
194 | } |
---|
195 | typedef shooting_star_visitor<> default_shooting_star_visitor; |
---|
196 | |
---|
197 | |
---|
198 | namespace detail { |
---|
199 | |
---|
200 | template <class AStarHeuristic, class UniformCostVisitor, |
---|
201 | class UpdatableQueue, class PredecessorMap, |
---|
202 | class CostMap, class DistanceMap, class WeightMap, |
---|
203 | class EdgeMap, |
---|
204 | class ColorMap, class EdgeColorMap, class HistoryMap, |
---|
205 | class BinaryFunction, |
---|
206 | class BinaryPredicate> |
---|
207 | struct shooting_star_bfs_visitor |
---|
208 | { |
---|
209 | |
---|
210 | typedef typename property_traits<CostMap>::value_type C; |
---|
211 | typedef typename property_traits<ColorMap>::value_type ColorValue; |
---|
212 | typedef color_traits<ColorValue> Color; |
---|
213 | |
---|
214 | typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue; |
---|
215 | typedef color_traits<ColorValue> EdgeColor; |
---|
216 | |
---|
217 | typedef typename property_traits<DistanceMap>::value_type distance_type; |
---|
218 | |
---|
219 | shooting_star_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis, |
---|
220 | UpdatableQueue& Q, PredecessorMap& p, |
---|
221 | CostMap c, DistanceMap d, WeightMap w, EdgeMap em, |
---|
222 | ColorMap col, EdgeColorMap ecol, HistoryMap his, |
---|
223 | BinaryFunction combine, |
---|
224 | BinaryPredicate compare, C zero) |
---|
225 | : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), |
---|
226 | m_distance(d), m_weight(w), m_edge(em), m_color(col), |
---|
227 | m_ecolor(ecol), m_history(his), |
---|
228 | m_combine(combine), m_compare(compare), m_zero(zero) {} |
---|
229 | |
---|
230 | |
---|
231 | template <class Vertex, class Graph> |
---|
232 | void initialize_vertex(Vertex u, Graph& g) { |
---|
233 | m_vis.initialize_vertex(u, g); |
---|
234 | } |
---|
235 | template <class Edge, class Graph> |
---|
236 | void initialize_edge(Edge e, Graph& g) { |
---|
237 | m_vis.initialize_edge(e, g); |
---|
238 | } |
---|
239 | template <class Vertex, class Graph> |
---|
240 | void discover_vertex(Vertex u, Graph& g) { |
---|
241 | m_vis.discover_vertex(u, g); |
---|
242 | } |
---|
243 | template <class Edge, class Graph> |
---|
244 | void discover_edge(Edge e, Graph& g) { |
---|
245 | m_vis.discover_vertex(e, g); |
---|
246 | } |
---|
247 | template <class Vertex, class Graph> |
---|
248 | void examine_vertex(Vertex u, Graph& g) { |
---|
249 | m_vis.examine_vertex(u, g); |
---|
250 | } |
---|
251 | template <class Vertex, class Graph> |
---|
252 | void finish_vertex(Vertex u, Graph& g) { |
---|
253 | m_vis.finish_vertex(u, g); |
---|
254 | } |
---|
255 | template <class Edge, class Graph> |
---|
256 | void examine_edge(Edge e, Graph& g) { |
---|
257 | if (m_compare(get(m_weight, e), m_zero)) |
---|
258 | throw negative_edge(); |
---|
259 | m_vis.examine_edge(e, g); |
---|
260 | } |
---|
261 | template <class Edge, class Graph> |
---|
262 | void non_tree_edge(Edge, Graph&) {} |
---|
263 | |
---|
264 | template <class Edge, class Graph> |
---|
265 | void finish_edge(Edge e, Graph& g) { |
---|
266 | m_vis.finish_edge(e, g); |
---|
267 | } |
---|
268 | |
---|
269 | |
---|
270 | template <class Edge, class Graph> |
---|
271 | void tree_edge(Edge e, Edge pe, Graph& g, int e_max_id) { |
---|
272 | |
---|
273 | m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance, |
---|
274 | m_cost, m_history, m_combine, m_compare, e_max_id); |
---|
275 | |
---|
276 | if(m_decreased) { |
---|
277 | m_vis.edge_relaxed(e, g); |
---|
278 | |
---|
279 | put(m_cost, e, |
---|
280 | m_combine(get(m_distance, e), |
---|
281 | m_h(e))); |
---|
282 | |
---|
283 | } else |
---|
284 | m_vis.edge_not_relaxed(e, g); |
---|
285 | } |
---|
286 | |
---|
287 | |
---|
288 | template <class Edge, class Graph> |
---|
289 | void gray_target(Edge e, Edge pe, Graph& g, int e_max_id) { |
---|
290 | |
---|
291 | m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance, |
---|
292 | m_cost, m_history, m_combine, m_compare, e_max_id); |
---|
293 | |
---|
294 | if(m_decreased) { |
---|
295 | put(m_cost, e, |
---|
296 | m_combine(get(m_distance, e), |
---|
297 | m_h(e))); |
---|
298 | |
---|
299 | m_Q.update(e); |
---|
300 | |
---|
301 | m_vis.edge_relaxed(e, g); |
---|
302 | } else |
---|
303 | m_vis.edge_not_relaxed(e, g); |
---|
304 | } |
---|
305 | |
---|
306 | |
---|
307 | template <class Edge, class Graph> |
---|
308 | void black_target(Edge e, Edge pe, Graph& g, int e_max_id) { |
---|
309 | |
---|
310 | m_decreased = relax(e, pe, g, m_weight, m_edge, m_predecessor, m_distance, |
---|
311 | m_cost, m_history, m_combine, m_compare, e_max_id); |
---|
312 | |
---|
313 | if(m_decreased) { |
---|
314 | m_vis.edge_relaxed(e, g); |
---|
315 | put(m_cost, e, |
---|
316 | m_combine(get(m_distance, e), |
---|
317 | m_h(e))); |
---|
318 | |
---|
319 | m_Q.push(e); |
---|
320 | put(m_ecolor, e, EdgeColor::gray()); |
---|
321 | m_vis.black_target(e, g); |
---|
322 | } else |
---|
323 | m_vis.edge_not_relaxed(e, g); |
---|
324 | } |
---|
325 | |
---|
326 | AStarHeuristic m_h; |
---|
327 | UniformCostVisitor m_vis; |
---|
328 | UpdatableQueue& m_Q; |
---|
329 | PredecessorMap& m_predecessor; |
---|
330 | CostMap m_cost; |
---|
331 | EdgeMap m_edge; |
---|
332 | DistanceMap m_distance; |
---|
333 | WeightMap m_weight; |
---|
334 | ColorMap m_color; |
---|
335 | EdgeColorMap m_ecolor; |
---|
336 | HistoryMap m_history; |
---|
337 | BinaryFunction m_combine; |
---|
338 | BinaryPredicate m_compare; |
---|
339 | bool m_decreased; |
---|
340 | C m_zero; |
---|
341 | |
---|
342 | }; |
---|
343 | |
---|
344 | } // namespace detail |
---|
345 | |
---|
346 | template <typename VertexAndEdgeListGraph, typename AStarHeuristic, |
---|
347 | typename ShootingStarVisitor, typename PredecessorMap, |
---|
348 | typename CostMap, typename DistanceMap, |
---|
349 | typename WeightMap, |
---|
350 | typename EdgeMap, |
---|
351 | typename ColorMap, typename EdgeColorMap, |
---|
352 | typename HistoryMap, |
---|
353 | typename IndexMap, |
---|
354 | typename CompareFunction, typename CombineFunction, |
---|
355 | typename CostInf, typename CostZero> |
---|
356 | inline void |
---|
357 | shooting_star_search_no_init |
---|
358 | (VertexAndEdgeListGraph &g, |
---|
359 | typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s, |
---|
360 | AStarHeuristic h, ShootingStarVisitor vis, |
---|
361 | PredecessorMap &predecessor, CostMap cost, |
---|
362 | DistanceMap distance, WeightMap weight, EdgeMap edge_map, |
---|
363 | ColorMap color, EdgeColorMap edge_color, HistoryMap history, |
---|
364 | IndexMap index_map, CompareFunction compare, CombineFunction combine, |
---|
365 | CostInf inf, CostZero zero, int e_max_id) |
---|
366 | { |
---|
367 | typedef indirect_cmp<CostMap, CompareFunction> IndirectCmp; |
---|
368 | IndirectCmp icmp(cost, compare); |
---|
369 | |
---|
370 | typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor |
---|
371 | Edge; |
---|
372 | |
---|
373 | typedef mutable_queue<Edge, std::vector<Edge>, IndirectCmp, IndexMap> |
---|
374 | MutableQueue; |
---|
375 | MutableQueue Q(num_edges(g), icmp, index_map); |
---|
376 | |
---|
377 | detail::shooting_star_bfs_visitor<AStarHeuristic, ShootingStarVisitor, |
---|
378 | MutableQueue, PredecessorMap, CostMap, DistanceMap, |
---|
379 | WeightMap, EdgeMap, ColorMap, EdgeColorMap, HistoryMap, CombineFunction, CompareFunction> |
---|
380 | bfs_vis(h, vis, Q, predecessor, cost, distance, weight, |
---|
381 | edge_map, color, edge_color, history, combine, compare, zero); |
---|
382 | |
---|
383 | shooting_star_edges_visit(g, s, Q, bfs_vis, color, edge_color, history, e_max_id); |
---|
384 | } |
---|
385 | |
---|
386 | // Non-named parameter interface |
---|
387 | template <typename VertexAndEdgeListGraph, typename AStarHeuristic, |
---|
388 | typename ShootingStarVisitor, typename PredecessorMap, |
---|
389 | typename CostMap, typename DistanceMap, |
---|
390 | typename WeightMap, typename EdgeMap, |
---|
391 | typename IndexMap, |
---|
392 | typename ColorMap, typename EdgeColorMap, |
---|
393 | typename HistoryMap, |
---|
394 | typename CompareFunction, typename CombineFunction, |
---|
395 | typename CostInf, typename CostZero> |
---|
396 | inline void |
---|
397 | shooting_star_search |
---|
398 | (VertexAndEdgeListGraph &g, |
---|
399 | typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s, |
---|
400 | AStarHeuristic h, ShootingStarVisitor vis, |
---|
401 | PredecessorMap &predecessor, CostMap cost, |
---|
402 | DistanceMap distance, WeightMap weight, |
---|
403 | EdgeMap edge_map, IndexMap index_map, ColorMap color, EdgeColorMap edge_color, |
---|
404 | HistoryMap history, CompareFunction compare, CombineFunction combine, |
---|
405 | CostInf inf, CostZero zero, int e_max_id) |
---|
406 | { |
---|
407 | |
---|
408 | typedef typename property_traits<ColorMap>::value_type ColorValue; |
---|
409 | typedef color_traits<ColorValue> Color; |
---|
410 | |
---|
411 | typedef typename property_traits<EdgeColorMap>::value_type EdgeColorValue; |
---|
412 | typedef color_traits<EdgeColorValue> EdgeColor; |
---|
413 | |
---|
414 | typename graph_traits<VertexAndEdgeListGraph>::vertex_iterator ui, ui_end; |
---|
415 | typename graph_traits<VertexAndEdgeListGraph>::edge_iterator ei, ei_end; |
---|
416 | |
---|
417 | for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { |
---|
418 | vis.initialize_vertex(*ui, g); |
---|
419 | } |
---|
420 | |
---|
421 | for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) { |
---|
422 | put(distance, *ei, inf); |
---|
423 | put(edge_color, *ei, EdgeColor::white()); |
---|
424 | predecessor[g[*ei].id] = *ei; |
---|
425 | put(cost, *ei, inf); |
---|
426 | } |
---|
427 | |
---|
428 | put(distance, s, zero); |
---|
429 | |
---|
430 | put(cost, s, h(s)); |
---|
431 | |
---|
432 | shooting_star_search_no_init |
---|
433 | (g, s, h, vis, predecessor, cost, distance, weight, edge_map, |
---|
434 | color, edge_color, history, index_map, compare, combine, inf, zero, e_max_id); |
---|
435 | |
---|
436 | } |
---|
437 | |
---|
438 | namespace detail { |
---|
439 | template <class VertexAndEdgeListGraph, class AStarHeuristic, |
---|
440 | class CostMap, class DistanceMap, class WeightMap, class EdgeMap, |
---|
441 | class IndexMap, |
---|
442 | class PredecessorMap, |
---|
443 | class ColorMap, class EdgeColorMap, |
---|
444 | class HistoryMap, class Params> |
---|
445 | inline void |
---|
446 | shooting_star_dispatch2 |
---|
447 | (VertexAndEdgeListGraph& g, |
---|
448 | typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s, |
---|
449 | AStarHeuristic h, CostMap cost, DistanceMap distance, |
---|
450 | WeightMap weight, EdgeMap edge_map, IndexMap index_map, |
---|
451 | PredecessorMap& predecessor, ColorMap color, |
---|
452 | EdgeColorMap edge_color, HistoryMap history, const Params& params, |
---|
453 | int e_max_id) |
---|
454 | { |
---|
455 | dummy_property_map p_map; |
---|
456 | typedef typename property_traits<CostMap>::value_type C; |
---|
457 | shooting_star_search |
---|
458 | (g, s, h, |
---|
459 | choose_param(get_param(params, graph_visitor), |
---|
460 | make_shooting_star_visitor(null_visitor())), |
---|
461 | predecessor, |
---|
462 | cost, distance, weight, edge_map, index_map, color, edge_color, history, |
---|
463 | choose_param(get_param(params, distance_compare_t()), |
---|
464 | std::less<C>()), |
---|
465 | choose_param(get_param(params, distance_combine_t()), |
---|
466 | closed_plus<C>()), |
---|
467 | choose_param(get_param(params, distance_inf_t()), |
---|
468 | std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()), |
---|
469 | choose_param(get_param(params, distance_zero_t()), |
---|
470 | C()), |
---|
471 | e_max_id |
---|
472 | ); |
---|
473 | } |
---|
474 | |
---|
475 | template <class VertexAndEdgeListGraph, class AStarHeuristic, |
---|
476 | class CostMap, class DistanceMap, class WeightMap, |
---|
477 | class EdgeMap, class IndexMap, |
---|
478 | class PredecessorMap, |
---|
479 | class ColorMap, class EdgeColorMap, |
---|
480 | class HistoryMap, class Params> |
---|
481 | inline void |
---|
482 | shooting_star_dispatch1 |
---|
483 | (VertexAndEdgeListGraph& g, |
---|
484 | typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s, |
---|
485 | AStarHeuristic h, CostMap cost, DistanceMap distance, |
---|
486 | WeightMap weight, EdgeMap edge_map, IndexMap index_map, PredecessorMap& predecessor, |
---|
487 | ColorMap color, EdgeColorMap edge_color, HistoryMap history, const Params& params, |
---|
488 | int e_max_id) |
---|
489 | { |
---|
490 | typedef typename property_traits<WeightMap>::value_type D; |
---|
491 | typename std::vector<D>::size_type |
---|
492 | n = is_default_param(distance) ? num_vertices(g) : 1; |
---|
493 | std::vector<D> distance_map(n); |
---|
494 | n = is_default_param(cost) ? num_vertices(g) : 1; |
---|
495 | std::vector<D> cost_map(n); |
---|
496 | |
---|
497 | std::vector<default_color_type> color_map(num_vertices(g)); |
---|
498 | std::vector<default_color_type> edge_color_map(num_edges(g)); |
---|
499 | default_color_type c = white_color; |
---|
500 | |
---|
501 | detail::shooting_star_dispatch2 |
---|
502 | (g, s, h, |
---|
503 | choose_param(cost, make_iterator_property_map |
---|
504 | (cost_map.begin(), index_map, |
---|
505 | cost_map[0])), |
---|
506 | choose_param(distance, make_iterator_property_map |
---|
507 | (distance_map.begin(), index_map, |
---|
508 | distance_map[0])), |
---|
509 | weight, edge_map, index_map, |
---|
510 | predecessor, |
---|
511 | choose_param(color, make_iterator_property_map |
---|
512 | (color_map.begin(), index_map, c)), |
---|
513 | edge_color, |
---|
514 | history, |
---|
515 | params, |
---|
516 | e_max_id); |
---|
517 | } |
---|
518 | } // namespace detail |
---|
519 | |
---|
520 | // Named parameter interface |
---|
521 | template <typename VertexAndEdgeListGraph, |
---|
522 | typename AStarHeuristic, |
---|
523 | typename P, typename T, typename R, |
---|
524 | typename IndexMap, |
---|
525 | typename DistanceMap, |
---|
526 | typename CostMap, |
---|
527 | typename HistoryMap, |
---|
528 | typename PredecessorMap> |
---|
529 | void |
---|
530 | shooting_star_search |
---|
531 | (VertexAndEdgeListGraph &g, |
---|
532 | typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor s, |
---|
533 | AStarHeuristic h, const bgl_named_params<P, T, R>& params, |
---|
534 | IndexMap edge_index, |
---|
535 | DistanceMap distance, |
---|
536 | CostMap cost, |
---|
537 | HistoryMap history, |
---|
538 | PredecessorMap &pre_map, |
---|
539 | int e_max_id) |
---|
540 | { |
---|
541 | typedef typename graph_traits<VertexAndEdgeListGraph>::edge_descriptor tEdge; |
---|
542 | |
---|
543 | detail::shooting_star_dispatch1 |
---|
544 | (g, s, h, |
---|
545 | cost, |
---|
546 | distance, |
---|
547 | choose_const_pmap(get_param(params, edge_weight), g, edge_weight), //weight |
---|
548 | choose_const_pmap(get_param(params, edge_weight2), g, edge_weight2), //adjacent edges cost |
---|
549 | edge_index, |
---|
550 | pre_map, //predecessors |
---|
551 | get_param(params, vertex_color), //vertex color (deprecated) |
---|
552 | get_param(params, edge_color), //edge color |
---|
553 | history, |
---|
554 | params, |
---|
555 | e_max_id |
---|
556 | ); |
---|
557 | } |
---|
558 | |
---|
559 | } // namespace boost |
---|
560 | |
---|
561 | #endif // BOOST_GRAPH_SHOOTING_STAR_SEARCH_HPP |
---|