1 2 3 // 4 //======================================================================= 5 // Copyright (c) 2004 Kristopher Beevers 6 // 7 // Distributed under the Boost Software License, Version 1.0. (See 8 // accompanying file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 //======================================================================= 11 // 12 13 #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP 14 #define BOOST_GRAPH_ASTAR_SEARCH_HPP 15 16 17 #include <functional> 18 #include <vector> 19 #include <boost/limits.hpp> 20 #include <boost/throw_exception.hpp> 21 #include <boost/graph/named_function_params.hpp> 22 #include <boost/graph/relax.hpp> 23 #include <boost/graph/exception.hpp> 24 #include <boost/graph/breadth_first_search.hpp> 25 #include <boost/graph/iteration_macros.hpp> 26 #include <boost/graph/detail/d_ary_heap.hpp> 27 #include <boost/graph/property_maps/constant_property_map.hpp> 28 #include <boost/property_map/property_map.hpp> 29 #include <boost/property_map/vector_property_map.hpp> 30 #include <boost/property_map/function_property_map.hpp> 31 #include <boost/concept/assert.hpp> 32 33 namespace boost { 34 35 36 template <class Heuristic, class Graph> 37 struct AStarHeuristicConcept { constraintsboost::AStarHeuristicConcept38 void constraints() 39 { 40 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> )); 41 h(u); 42 } 43 Heuristic h; 44 typename graph_traits<Graph>::vertex_descriptor u; 45 }; 46 47 48 template <class Graph, class CostType> 49 class astar_heuristic 50 { 51 public: 52 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 53 typedef Vertex argument_type; 54 typedef CostType result_type; astar_heuristic()55 astar_heuristic() {} operator ()(Vertex u)56 CostType operator()(Vertex u) { return static_cast<CostType>(0); } 57 }; 58 59 60 61 template <class Visitor, class Graph> 62 struct AStarVisitorConcept { constraintsboost::AStarVisitorConcept63 void constraints() 64 { 65 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> )); 66 vis.initialize_vertex(u, g); 67 vis.discover_vertex(u, g); 68 vis.examine_vertex(u, g); 69 vis.examine_edge(e, g); 70 vis.edge_relaxed(e, g); 71 vis.edge_not_relaxed(e, g); 72 vis.black_target(e, g); 73 vis.finish_vertex(u, g); 74 } 75 Visitor vis; 76 Graph g; 77 typename graph_traits<Graph>::vertex_descriptor u; 78 typename graph_traits<Graph>::edge_descriptor e; 79 }; 80 81 82 template <class Visitors = null_visitor> 83 class astar_visitor : public bfs_visitor<Visitors> { 84 public: astar_visitor()85 astar_visitor() {} astar_visitor(Visitors vis)86 astar_visitor(Visitors vis) 87 : bfs_visitor<Visitors>(vis) {} 88 89 template <class Edge, class Graph> edge_relaxed(Edge e,const Graph & g)90 void edge_relaxed(Edge e, const Graph& g) { 91 invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); 92 } 93 template <class Edge, class Graph> edge_not_relaxed(Edge e,const Graph & g)94 void edge_not_relaxed(Edge e, const Graph& g) { 95 invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); 96 } 97 private: 98 template <class Edge, class Graph> tree_edge(Edge e,const Graph & g)99 void tree_edge(Edge e, const Graph& g) {} 100 template <class Edge, class Graph> non_tree_edge(Edge e,const Graph & g)101 void non_tree_edge(Edge e, const Graph& g) {} 102 }; 103 template <class Visitors> 104 astar_visitor<Visitors> make_astar_visitor(Visitors vis)105 make_astar_visitor(Visitors vis) { 106 return astar_visitor<Visitors>(vis); 107 } 108 typedef astar_visitor<> default_astar_visitor; 109 110 111 namespace detail { 112 113 template <class AStarHeuristic, class UniformCostVisitor, 114 class UpdatableQueue, class PredecessorMap, 115 class CostMap, class DistanceMap, class WeightMap, 116 class ColorMap, class BinaryFunction, 117 class BinaryPredicate> 118 struct astar_bfs_visitor 119 { 120 121 typedef typename property_traits<CostMap>::value_type C; 122 typedef typename property_traits<ColorMap>::value_type ColorValue; 123 typedef color_traits<ColorValue> Color; 124 typedef typename property_traits<DistanceMap>::value_type distance_type; 125 astar_bfs_visitorboost::detail::astar_bfs_visitor126 astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis, 127 UpdatableQueue& Q, PredecessorMap p, 128 CostMap c, DistanceMap d, WeightMap w, 129 ColorMap col, BinaryFunction combine, 130 BinaryPredicate compare, C zero) 131 : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), 132 m_distance(d), m_weight(w), m_color(col), 133 m_combine(combine), m_compare(compare), m_zero(zero) {} 134 135 136 template <class Vertex, class Graph> initialize_vertexboost::detail::astar_bfs_visitor137 void initialize_vertex(Vertex u, const Graph& g) { 138 m_vis.initialize_vertex(u, g); 139 } 140 template <class Vertex, class Graph> discover_vertexboost::detail::astar_bfs_visitor141 void discover_vertex(Vertex u, const Graph& g) { 142 m_vis.discover_vertex(u, g); 143 } 144 template <class Vertex, class Graph> examine_vertexboost::detail::astar_bfs_visitor145 void examine_vertex(Vertex u, const Graph& g) { 146 m_vis.examine_vertex(u, g); 147 } 148 template <class Vertex, class Graph> finish_vertexboost::detail::astar_bfs_visitor149 void finish_vertex(Vertex u, const Graph& g) { 150 m_vis.finish_vertex(u, g); 151 } 152 template <class Edge, class Graph> examine_edgeboost::detail::astar_bfs_visitor153 void examine_edge(Edge e, const Graph& g) { 154 if (m_compare(get(m_weight, e), m_zero)) 155 BOOST_THROW_EXCEPTION(negative_edge()); 156 m_vis.examine_edge(e, g); 157 } 158 template <class Edge, class Graph> non_tree_edgeboost::detail::astar_bfs_visitor159 void non_tree_edge(Edge, const Graph&) {} 160 161 162 163 template <class Edge, class Graph> tree_edgeboost::detail::astar_bfs_visitor164 void tree_edge(Edge e, const Graph& g) { 165 using boost::get; 166 bool m_decreased = 167 relax(e, g, m_weight, m_predecessor, m_distance, 168 m_combine, m_compare); 169 170 if(m_decreased) { 171 m_vis.edge_relaxed(e, g); 172 put(m_cost, target(e, g), 173 m_combine(get(m_distance, target(e, g)), 174 m_h(target(e, g)))); 175 } else 176 m_vis.edge_not_relaxed(e, g); 177 } 178 179 180 template <class Edge, class Graph> gray_targetboost::detail::astar_bfs_visitor181 void gray_target(Edge e, const Graph& g) { 182 using boost::get; 183 bool m_decreased = 184 relax(e, g, m_weight, m_predecessor, m_distance, 185 m_combine, m_compare); 186 187 if(m_decreased) { 188 put(m_cost, target(e, g), 189 m_combine(get(m_distance, target(e, g)), 190 m_h(target(e, g)))); 191 m_Q.update(target(e, g)); 192 m_vis.edge_relaxed(e, g); 193 } else 194 m_vis.edge_not_relaxed(e, g); 195 } 196 197 198 template <class Edge, class Graph> black_targetboost::detail::astar_bfs_visitor199 void black_target(Edge e, const Graph& g) { 200 using boost::get; 201 bool m_decreased = 202 relax(e, g, m_weight, m_predecessor, m_distance, 203 m_combine, m_compare); 204 205 if(m_decreased) { 206 m_vis.edge_relaxed(e, g); 207 put(m_cost, target(e, g), 208 m_combine(get(m_distance, target(e, g)), 209 m_h(target(e, g)))); 210 m_Q.push(target(e, g)); 211 put(m_color, target(e, g), Color::gray()); 212 m_vis.black_target(e, g); 213 } else 214 m_vis.edge_not_relaxed(e, g); 215 } 216 217 218 219 AStarHeuristic m_h; 220 UniformCostVisitor m_vis; 221 UpdatableQueue& m_Q; 222 PredecessorMap m_predecessor; 223 CostMap m_cost; 224 DistanceMap m_distance; 225 WeightMap m_weight; 226 ColorMap m_color; 227 BinaryFunction m_combine; 228 BinaryPredicate m_compare; 229 C m_zero; 230 231 }; 232 233 } // namespace detail 234 235 236 237 template <typename VertexListGraph, typename AStarHeuristic, 238 typename AStarVisitor, typename PredecessorMap, 239 typename CostMap, typename DistanceMap, 240 typename WeightMap, typename ColorMap, 241 typename VertexIndexMap, 242 typename CompareFunction, typename CombineFunction, 243 typename CostInf, typename CostZero> 244 inline void astar_search_no_init(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,AStarVisitor vis,PredecessorMap predecessor,CostMap cost,DistanceMap distance,WeightMap weight,ColorMap color,VertexIndexMap index_map,CompareFunction compare,CombineFunction combine,CostInf,CostZero zero)245 astar_search_no_init 246 (const VertexListGraph &g, 247 typename graph_traits<VertexListGraph>::vertex_descriptor s, 248 AStarHeuristic h, AStarVisitor vis, 249 PredecessorMap predecessor, CostMap cost, 250 DistanceMap distance, WeightMap weight, 251 ColorMap color, VertexIndexMap index_map, 252 CompareFunction compare, CombineFunction combine, 253 CostInf /*inf*/, CostZero zero) 254 { 255 typedef typename graph_traits<VertexListGraph>::vertex_descriptor 256 Vertex; 257 typedef boost::vector_property_map<std::size_t, VertexIndexMap> IndexInHeapMap; 258 IndexInHeapMap index_in_heap(index_map); 259 typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction> 260 MutableQueue; 261 MutableQueue Q(cost, index_in_heap, compare); 262 263 detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor, 264 MutableQueue, PredecessorMap, CostMap, DistanceMap, 265 WeightMap, ColorMap, CombineFunction, CompareFunction> 266 bfs_vis(h, vis, Q, predecessor, cost, distance, weight, 267 color, combine, compare, zero); 268 269 breadth_first_visit(g, s, Q, bfs_vis, color); 270 } 271 272 namespace graph_detail { 273 template <typename A, typename B> 274 struct select1st { 275 typedef std::pair<A, B> argument_type; 276 typedef A result_type; operator ()boost::graph_detail::select1st277 A operator()(const std::pair<A, B>& p) const {return p.first;} 278 }; 279 } 280 281 template <typename VertexListGraph, typename AStarHeuristic, 282 typename AStarVisitor, typename PredecessorMap, 283 typename CostMap, typename DistanceMap, 284 typename WeightMap, 285 typename CompareFunction, typename CombineFunction, 286 typename CostInf, typename CostZero> 287 inline void astar_search_no_init_tree(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,AStarVisitor vis,PredecessorMap predecessor,CostMap cost,DistanceMap distance,WeightMap weight,CompareFunction compare,CombineFunction combine,CostInf,CostZero zero)288 astar_search_no_init_tree 289 (const VertexListGraph &g, 290 typename graph_traits<VertexListGraph>::vertex_descriptor s, 291 AStarHeuristic h, AStarVisitor vis, 292 PredecessorMap predecessor, CostMap cost, 293 DistanceMap distance, WeightMap weight, 294 CompareFunction compare, CombineFunction combine, 295 CostInf /*inf*/, CostZero zero) 296 { 297 typedef typename graph_traits<VertexListGraph>::vertex_descriptor 298 Vertex; 299 typedef typename property_traits<DistanceMap>::value_type Distance; 300 typedef d_ary_heap_indirect< 301 std::pair<Distance, Vertex>, 302 4, 303 null_property_map<std::pair<Distance, Vertex>, std::size_t>, 304 function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >, 305 CompareFunction> 306 MutableQueue; 307 MutableQueue Q( 308 make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()), 309 null_property_map<std::pair<Distance, Vertex>, std::size_t>(), 310 compare); 311 312 vis.discover_vertex(s, g); 313 Q.push(std::make_pair(get(cost, s), s)); 314 while (!Q.empty()) { 315 Vertex v; 316 Distance v_rank; 317 boost::tie(v_rank, v) = Q.top(); 318 Q.pop(); 319 vis.examine_vertex(v, g); 320 BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) { 321 Vertex w = target(e, g); 322 vis.examine_edge(e, g); 323 Distance e_weight = get(weight, e); 324 if (compare(e_weight, zero)) 325 BOOST_THROW_EXCEPTION(negative_edge()); 326 bool decreased = 327 relax(e, g, weight, predecessor, distance, 328 combine, compare); 329 combine(get(distance, v), e_weight); 330 if (decreased) { 331 vis.edge_relaxed(e, g); 332 Distance w_rank = combine(get(distance, w), h(w)); 333 put(cost, w, w_rank); 334 vis.discover_vertex(w, g); 335 Q.push(std::make_pair(w_rank, w)); 336 } else { 337 vis.edge_not_relaxed(e, g); 338 } 339 } 340 vis.finish_vertex(v, g); 341 } 342 } 343 344 // Non-named parameter interface 345 template <typename VertexListGraph, typename AStarHeuristic, 346 typename AStarVisitor, typename PredecessorMap, 347 typename CostMap, typename DistanceMap, 348 typename WeightMap, typename VertexIndexMap, 349 typename ColorMap, 350 typename CompareFunction, typename CombineFunction, 351 typename CostInf, typename CostZero> 352 inline void astar_search(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,AStarVisitor vis,PredecessorMap predecessor,CostMap cost,DistanceMap distance,WeightMap weight,VertexIndexMap index_map,ColorMap color,CompareFunction compare,CombineFunction combine,CostInf inf,CostZero zero)353 astar_search 354 (const VertexListGraph &g, 355 typename graph_traits<VertexListGraph>::vertex_descriptor s, 356 AStarHeuristic h, AStarVisitor vis, 357 PredecessorMap predecessor, CostMap cost, 358 DistanceMap distance, WeightMap weight, 359 VertexIndexMap index_map, ColorMap color, 360 CompareFunction compare, CombineFunction combine, 361 CostInf inf, CostZero zero) 362 { 363 364 typedef typename property_traits<ColorMap>::value_type ColorValue; 365 typedef color_traits<ColorValue> Color; 366 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; 367 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { 368 put(color, *ui, Color::white()); 369 put(distance, *ui, inf); 370 put(cost, *ui, inf); 371 put(predecessor, *ui, *ui); 372 vis.initialize_vertex(*ui, g); 373 } 374 put(distance, s, zero); 375 put(cost, s, h(s)); 376 377 astar_search_no_init 378 (g, s, h, vis, predecessor, cost, distance, weight, 379 color, index_map, compare, combine, inf, zero); 380 381 } 382 383 // Non-named parameter interface 384 template <typename VertexListGraph, typename AStarHeuristic, 385 typename AStarVisitor, typename PredecessorMap, 386 typename CostMap, typename DistanceMap, 387 typename WeightMap, 388 typename CompareFunction, typename CombineFunction, 389 typename CostInf, typename CostZero> 390 inline void astar_search_tree(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,AStarVisitor vis,PredecessorMap predecessor,CostMap cost,DistanceMap distance,WeightMap weight,CompareFunction compare,CombineFunction combine,CostInf inf,CostZero zero)391 astar_search_tree 392 (const VertexListGraph &g, 393 typename graph_traits<VertexListGraph>::vertex_descriptor s, 394 AStarHeuristic h, AStarVisitor vis, 395 PredecessorMap predecessor, CostMap cost, 396 DistanceMap distance, WeightMap weight, 397 CompareFunction compare, CombineFunction combine, 398 CostInf inf, CostZero zero) 399 { 400 401 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; 402 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { 403 put(distance, *ui, inf); 404 put(cost, *ui, inf); 405 put(predecessor, *ui, *ui); 406 vis.initialize_vertex(*ui, g); 407 } 408 put(distance, s, zero); 409 put(cost, s, h(s)); 410 411 astar_search_no_init_tree 412 (g, s, h, vis, predecessor, cost, distance, weight, 413 compare, combine, inf, zero); 414 415 } 416 417 // Named parameter interfaces 418 template <typename VertexListGraph, 419 typename AStarHeuristic, 420 typename P, typename T, typename R> 421 void astar_search(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)422 astar_search 423 (const VertexListGraph &g, 424 typename graph_traits<VertexListGraph>::vertex_descriptor s, 425 AStarHeuristic h, const bgl_named_params<P, T, R>& params) 426 { 427 using namespace boost::graph::keywords; 428 typedef bgl_named_params<P, T, R> params_type; 429 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) 430 431 // Distance type is the value type of the distance map if there is one, 432 // otherwise the value type of the weight map. 433 typedef typename boost::detail::override_const_property_result< 434 arg_pack_type, 435 boost::graph::keywords::tag::weight_map, 436 edge_weight_t, 437 VertexListGraph 438 >::type weight_map_type; 439 typedef typename boost::property_traits<weight_map_type>::value_type D; 440 const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; 441 const D zero_actual = D(); 442 const D zero_d = arg_pack[_distance_zero | zero_actual]; 443 null_visitor null_vis; 444 astar_visitor<null_visitor> default_visitor(null_vis); 445 typename boost::parameter::binding< 446 arg_pack_type, 447 boost::graph::keywords::tag::visitor, 448 dummy_property_map& 449 >::type vis = arg_pack[_visitor | default_visitor]; 450 dummy_property_map dummy_prop; 451 typename boost::parameter::binding< 452 arg_pack_type, 453 boost::graph::keywords::tag::predecessor_map, 454 dummy_property_map& 455 >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; 456 boost::detail::make_property_map_from_arg_pack_gen< 457 boost::graph::keywords::tag::rank_map, 458 D 459 > rank_map_gen(zero_actual); 460 typename boost::detail::map_maker< 461 VertexListGraph, 462 arg_pack_type, 463 boost::graph::keywords::tag::rank_map, 464 D 465 >::map_type r_map = rank_map_gen(g, arg_pack); 466 boost::detail::make_property_map_from_arg_pack_gen< 467 boost::graph::keywords::tag::distance_map, 468 D 469 > dist_map_gen(zero_actual); 470 typename boost::detail::map_maker< 471 VertexListGraph, 472 arg_pack_type, 473 boost::graph::keywords::tag::distance_map, 474 D 475 >::map_type dist_map = dist_map_gen(g, arg_pack); 476 weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); 477 typename boost::detail::override_const_property_result< 478 arg_pack_type, 479 boost::graph::keywords::tag::vertex_index_map, 480 vertex_index_t, 481 VertexListGraph 482 >::type v_i_map = detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index); 483 typename boost::detail::map_maker< 484 VertexListGraph, 485 arg_pack_type, 486 boost::graph::keywords::tag::color_map, 487 boost::default_color_type 488 >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); 489 std::less<D> default_compare; 490 typename boost::parameter::binding< 491 arg_pack_type, 492 boost::graph::keywords::tag::distance_compare, 493 std::less<D>& 494 >::type dist_comp = arg_pack[_distance_compare | default_compare]; 495 closed_plus<D> default_combine(inf); 496 typename boost::parameter::binding< 497 arg_pack_type, 498 boost::graph::keywords::tag::distance_combine, 499 closed_plus<D>& 500 >::type dist_comb = arg_pack[_distance_combine | default_combine]; 501 astar_search 502 (g, s, h, 503 vis, 504 pred_map, 505 r_map, 506 dist_map, 507 w_map, 508 v_i_map, 509 c_map, 510 dist_comp, 511 dist_comb, 512 inf, 513 zero_d); 514 } 515 516 template <typename VertexListGraph, 517 typename AStarHeuristic, 518 typename P, typename T, typename R> 519 void astar_search_tree(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)520 astar_search_tree 521 (const VertexListGraph &g, 522 typename graph_traits<VertexListGraph>::vertex_descriptor s, 523 AStarHeuristic h, const bgl_named_params<P, T, R>& params) 524 { 525 using namespace boost::graph::keywords; 526 typedef bgl_named_params<P, T, R> params_type; 527 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) 528 529 // Distance type is the value type of the distance map if there is one, 530 // otherwise the value type of the weight map. 531 typedef typename boost::detail::override_const_property_result< 532 arg_pack_type, 533 boost::graph::keywords::tag::weight_map, 534 edge_weight_t, 535 VertexListGraph 536 >::type weight_map_type; 537 typedef typename boost::property_traits<weight_map_type>::value_type D; 538 const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; 539 const D zero_actual = D(); 540 const D zero_d = arg_pack[_distance_zero | zero_actual]; 541 null_visitor null_vis; 542 astar_visitor<null_visitor> default_visitor(null_vis); 543 typename boost::parameter::binding< 544 arg_pack_type, 545 boost::graph::keywords::tag::visitor, 546 dummy_property_map& 547 >::type vis = arg_pack[_visitor | default_visitor]; 548 dummy_property_map dummy_prop; 549 typename boost::parameter::binding< 550 arg_pack_type, 551 boost::graph::keywords::tag::predecessor_map, 552 dummy_property_map& 553 >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; 554 boost::detail::make_property_map_from_arg_pack_gen< 555 boost::graph::keywords::tag::rank_map, 556 D 557 > rank_map_gen(zero_actual); 558 typename boost::detail::map_maker< 559 VertexListGraph, 560 arg_pack_type, 561 boost::graph::keywords::tag::rank_map, 562 D 563 >::map_type r_map = rank_map_gen(g, arg_pack); 564 boost::detail::make_property_map_from_arg_pack_gen< 565 boost::graph::keywords::tag::distance_map, 566 D 567 > dist_map_gen(zero_actual); 568 typename boost::detail::map_maker< 569 VertexListGraph, 570 arg_pack_type, 571 boost::graph::keywords::tag::distance_map, 572 D 573 >::map_type dist_map = dist_map_gen(g, arg_pack); 574 weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); 575 std::less<D> default_compare; 576 typename boost::parameter::binding< 577 arg_pack_type, 578 boost::graph::keywords::tag::distance_compare, 579 std::less<D>& 580 >::type dist_comp = arg_pack[_distance_compare | default_compare]; 581 closed_plus<D> default_combine(inf); 582 typename boost::parameter::binding< 583 arg_pack_type, 584 boost::graph::keywords::tag::distance_combine, 585 closed_plus<D>& 586 >::type dist_comb = arg_pack[_distance_combine | default_combine]; 587 astar_search_tree 588 (g, s, h, 589 vis, 590 pred_map, 591 r_map, 592 dist_map, 593 w_map, 594 dist_comp, 595 dist_comb, 596 inf, 597 zero_d); 598 } 599 600 template <typename VertexListGraph, 601 typename AStarHeuristic, 602 typename P, typename T, typename R> 603 void astar_search_no_init(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)604 astar_search_no_init 605 (const VertexListGraph &g, 606 typename graph_traits<VertexListGraph>::vertex_descriptor s, 607 AStarHeuristic h, const bgl_named_params<P, T, R>& params) 608 { 609 using namespace boost::graph::keywords; 610 typedef bgl_named_params<P, T, R> params_type; 611 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) 612 typedef typename boost::detail::override_const_property_result< 613 arg_pack_type, 614 boost::graph::keywords::tag::weight_map, 615 edge_weight_t, 616 VertexListGraph 617 >::type weight_map_type; 618 typedef typename boost::property_traits<weight_map_type>::value_type D; 619 const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; 620 const D zero_actual = D(); 621 const D zero_d = arg_pack[_distance_zero | zero_actual]; 622 null_visitor null_vis; 623 astar_visitor<null_visitor> default_visitor(null_vis); 624 typename boost::parameter::binding< 625 arg_pack_type, 626 boost::graph::keywords::tag::visitor, 627 dummy_property_map& 628 >::type vis = arg_pack[_visitor | default_visitor]; 629 dummy_property_map dummy_prop; 630 typename boost::parameter::binding< 631 arg_pack_type, 632 boost::graph::keywords::tag::predecessor_map, 633 dummy_property_map& 634 >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; 635 boost::detail::make_property_map_from_arg_pack_gen< 636 boost::graph::keywords::tag::rank_map, 637 D 638 > rank_map_gen(zero_actual); 639 typename boost::detail::map_maker< 640 VertexListGraph, 641 arg_pack_type, 642 boost::graph::keywords::tag::rank_map, 643 D 644 >::map_type r_map = rank_map_gen(g, arg_pack); 645 boost::detail::make_property_map_from_arg_pack_gen< 646 boost::graph::keywords::tag::distance_map, 647 D 648 > dist_map_gen(zero_actual); 649 typename boost::detail::map_maker< 650 VertexListGraph, 651 arg_pack_type, 652 boost::graph::keywords::tag::distance_map, 653 D 654 >::map_type dist_map = dist_map_gen(g, arg_pack); 655 weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); 656 typename boost::detail::map_maker< 657 VertexListGraph, 658 arg_pack_type, 659 boost::graph::keywords::tag::color_map, 660 boost::default_color_type 661 >::map_type c_map = boost::detail::make_color_map_from_arg_pack(g, arg_pack); 662 typename boost::detail::override_const_property_result< 663 arg_pack_type, 664 boost::graph::keywords::tag::vertex_index_map, 665 vertex_index_t, 666 VertexListGraph 667 >::type v_i_map = detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index); 668 std::less<D> default_compare; 669 typename boost::parameter::binding< 670 arg_pack_type, 671 boost::graph::keywords::tag::distance_compare, 672 std::less<D>& 673 >::type dist_comp = arg_pack[_distance_compare | default_compare]; 674 closed_plus<D> default_combine(inf); 675 typename boost::parameter::binding< 676 arg_pack_type, 677 boost::graph::keywords::tag::distance_combine, 678 closed_plus<D>& 679 >::type dist_comb = arg_pack[_distance_combine | default_combine]; 680 astar_search_no_init 681 (g, s, h, 682 vis, 683 pred_map, 684 r_map, 685 dist_map, 686 w_map, 687 c_map, 688 v_i_map, 689 dist_comp, 690 dist_comb, 691 inf, 692 zero_d); 693 } 694 695 template <typename VertexListGraph, 696 typename AStarHeuristic, 697 typename P, typename T, typename R> 698 void astar_search_no_init_tree(const VertexListGraph & g,typename graph_traits<VertexListGraph>::vertex_descriptor s,AStarHeuristic h,const bgl_named_params<P,T,R> & params)699 astar_search_no_init_tree 700 (const VertexListGraph &g, 701 typename graph_traits<VertexListGraph>::vertex_descriptor s, 702 AStarHeuristic h, const bgl_named_params<P, T, R>& params) 703 { 704 using namespace boost::graph::keywords; 705 typedef bgl_named_params<P, T, R> params_type; 706 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) 707 typedef typename boost::detail::override_const_property_result< 708 arg_pack_type, 709 boost::graph::keywords::tag::weight_map, 710 edge_weight_t, 711 VertexListGraph 712 >::type weight_map_type; 713 typedef typename boost::property_traits<weight_map_type>::value_type D; 714 const D inf = arg_pack[_distance_inf || detail::get_max<D>()]; 715 const D zero_actual = D(); 716 const D zero_d = arg_pack[_distance_zero | zero_actual]; 717 null_visitor null_vis; 718 astar_visitor<null_visitor> default_visitor(null_vis); 719 typename boost::parameter::binding< 720 arg_pack_type, 721 boost::graph::keywords::tag::visitor, 722 dummy_property_map& 723 >::type vis = arg_pack[_visitor | default_visitor]; 724 dummy_property_map dummy_prop; 725 typename boost::parameter::binding< 726 arg_pack_type, 727 boost::graph::keywords::tag::predecessor_map, 728 dummy_property_map& 729 >::type pred_map = arg_pack[_predecessor_map | dummy_prop]; 730 boost::detail::make_property_map_from_arg_pack_gen< 731 boost::graph::keywords::tag::rank_map, 732 D 733 > rank_map_gen(zero_actual); 734 typename boost::detail::map_maker< 735 VertexListGraph, 736 arg_pack_type, 737 boost::graph::keywords::tag::rank_map, 738 D 739 >::map_type r_map = rank_map_gen(g, arg_pack); 740 boost::detail::make_property_map_from_arg_pack_gen< 741 boost::graph::keywords::tag::distance_map, 742 D 743 > dist_map_gen(zero_actual); 744 typename boost::detail::map_maker< 745 VertexListGraph, 746 arg_pack_type, 747 boost::graph::keywords::tag::distance_map, 748 D 749 >::map_type dist_map = dist_map_gen(g, arg_pack); 750 weight_map_type w_map = detail::override_const_property(arg_pack, _weight_map, g, edge_weight); 751 std::less<D> default_compare; 752 typename boost::parameter::binding< 753 arg_pack_type, 754 boost::graph::keywords::tag::distance_compare, 755 std::less<D>& 756 >::type dist_comp = arg_pack[_distance_compare | default_compare]; 757 closed_plus<D> default_combine(inf); 758 typename boost::parameter::binding< 759 arg_pack_type, 760 boost::graph::keywords::tag::distance_combine, 761 closed_plus<D>& 762 >::type dist_comb = arg_pack[_distance_combine | default_combine]; 763 astar_search_no_init_tree 764 (g, s, h, 765 vis, 766 pred_map, 767 r_map, 768 dist_map, 769 w_map, 770 dist_comp, 771 dist_comb, 772 inf, 773 zero_d); 774 } 775 776 } // namespace boost 777 778 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP 779