Mercurial > hg > vamp-build-and-test

annotate DEPENDENCIES/generic/include/boost/graph/astar_search.hpp @ 125:34e428693f5d vext

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Vext -> Repoint
author Chris Cannam
date Thu, 14 Jun 2018 11:15:39 +0100
parents 2665513ce2d3
children
rev   line source
Chris@16 1
Chris@16 2
Chris@16 3 //
Chris@16 4 //=======================================================================
Chris@16 5 // Copyright (c) 2004 Kristopher Beevers
Chris@16 6 //
Chris@16 7 // Distributed under the Boost Software License, Version 1.0. (See
Chris@16 8 // accompanying file LICENSE_1_0.txt or copy at
Chris@16 9 // http://www.boost.org/LICENSE_1_0.txt)
Chris@16 10 //=======================================================================
Chris@16 11 //
Chris@16 12
Chris@16 13 #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP
Chris@16 14 #define BOOST_GRAPH_ASTAR_SEARCH_HPP
Chris@16 15
Chris@16 16
Chris@16 17 #include <functional>
Chris@16 18 #include <vector>
Chris@16 19 #include <boost/limits.hpp>
Chris@16 20 #include <boost/throw_exception.hpp>
Chris@16 21 #include <boost/graph/named_function_params.hpp>
Chris@16 22 #include <boost/graph/relax.hpp>
Chris@16 23 #include <boost/graph/exception.hpp>
Chris@16 24 #include <boost/graph/breadth_first_search.hpp>
Chris@16 25 #include <boost/graph/iteration_macros.hpp>
Chris@16 26 #include <boost/graph/detail/d_ary_heap.hpp>
Chris@16 27 #include <boost/graph/property_maps/constant_property_map.hpp>
Chris@16 28 #include <boost/property_map/property_map.hpp>
Chris@16 29 #include <boost/property_map/vector_property_map.hpp>
Chris@16 30 #include <boost/property_map/function_property_map.hpp>
Chris@16 31 #include <boost/concept/assert.hpp>
Chris@16 32
Chris@16 33 namespace boost {
Chris@16 34
Chris@16 35
Chris@16 36 template <class Heuristic, class Graph>
Chris@16 37 struct AStarHeuristicConcept {
Chris@16 38 void constraints()
Chris@16 39 {
Chris@16 40 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> ));
Chris@16 41 h(u);
Chris@16 42 }
Chris@16 43 Heuristic h;
Chris@16 44 typename graph_traits<Graph>::vertex_descriptor u;
Chris@16 45 };
Chris@16 46
Chris@16 47
Chris@16 48 template <class Graph, class CostType>
Chris@16 49 class astar_heuristic : public std::unary_function<
Chris@16 50 typename graph_traits<Graph>::vertex_descriptor, CostType>
Chris@16 51 {
Chris@16 52 public:
Chris@16 53 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16 54 astar_heuristic() {}
Chris@16 55 CostType operator()(Vertex u) { return static_cast<CostType>(0); }
Chris@16 56 };
Chris@16 57
Chris@16 58
Chris@16 59
Chris@16 60 template <class Visitor, class Graph>
Chris@16 61 struct AStarVisitorConcept {
Chris@16 62 void constraints()
Chris@16 63 {
Chris@16 64 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Visitor> ));
Chris@16 65 vis.initialize_vertex(u, g);
Chris@16 66 vis.discover_vertex(u, g);
Chris@16 67 vis.examine_vertex(u, g);
Chris@16 68 vis.examine_edge(e, g);
Chris@16 69 vis.edge_relaxed(e, g);
Chris@16 70 vis.edge_not_relaxed(e, g);
Chris@16 71 vis.black_target(e, g);
Chris@16 72 vis.finish_vertex(u, g);
Chris@16 73 }
Chris@16 74 Visitor vis;
Chris@16 75 Graph g;
Chris@16 76 typename graph_traits<Graph>::vertex_descriptor u;
Chris@16 77 typename graph_traits<Graph>::edge_descriptor e;
Chris@16 78 };
Chris@16 79
Chris@16 80
Chris@16 81 template <class Visitors = null_visitor>
Chris@16 82 class astar_visitor : public bfs_visitor<Visitors> {
Chris@16 83 public:
Chris@16 84 astar_visitor() {}
Chris@16 85 astar_visitor(Visitors vis)
Chris@16 86 : bfs_visitor<Visitors>(vis) {}
Chris@16 87
Chris@16 88 template <class Edge, class Graph>
Chris@16 89 void edge_relaxed(Edge e, const Graph& g) {
Chris@16 90 invoke_visitors(this->m_vis, e, g, on_edge_relaxed());
Chris@16 91 }
Chris@16 92 template <class Edge, class Graph>
Chris@16 93 void edge_not_relaxed(Edge e, const Graph& g) {
Chris@16 94 invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed());
Chris@16 95 }
Chris@16 96 private:
Chris@16 97 template <class Edge, class Graph>
Chris@16 98 void tree_edge(Edge e, const Graph& g) {}
Chris@16 99 template <class Edge, class Graph>
Chris@16 100 void non_tree_edge(Edge e, const Graph& g) {}
Chris@16 101 };
Chris@16 102 template <class Visitors>
Chris@16 103 astar_visitor<Visitors>
Chris@16 104 make_astar_visitor(Visitors vis) {
Chris@16 105 return astar_visitor<Visitors>(vis);
Chris@16 106 }
Chris@16 107 typedef astar_visitor<> default_astar_visitor;
Chris@16 108
Chris@16 109
Chris@16 110 namespace detail {
Chris@16 111
Chris@16 112 template <class AStarHeuristic, class UniformCostVisitor,
Chris@16 113 class UpdatableQueue, class PredecessorMap,
Chris@16 114 class CostMap, class DistanceMap, class WeightMap,
Chris@16 115 class ColorMap, class BinaryFunction,
Chris@16 116 class BinaryPredicate>
Chris@16 117 struct astar_bfs_visitor
Chris@16 118 {
Chris@16 119
Chris@16 120 typedef typename property_traits<CostMap>::value_type C;
Chris@16 121 typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16 122 typedef color_traits<ColorValue> Color;
Chris@16 123 typedef typename property_traits<DistanceMap>::value_type distance_type;
Chris@16 124
Chris@16 125 astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
Chris@16 126 UpdatableQueue& Q, PredecessorMap p,
Chris@16 127 CostMap c, DistanceMap d, WeightMap w,
Chris@16 128 ColorMap col, BinaryFunction combine,
Chris@16 129 BinaryPredicate compare, C zero)
Chris@16 130 : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c),
Chris@16 131 m_distance(d), m_weight(w), m_color(col),
Chris@16 132 m_combine(combine), m_compare(compare), m_zero(zero) {}
Chris@16 133
Chris@16 134
Chris@16 135 template <class Vertex, class Graph>
Chris@16 136 void initialize_vertex(Vertex u, const Graph& g) {
Chris@16 137 m_vis.initialize_vertex(u, g);
Chris@16 138 }
Chris@16 139 template <class Vertex, class Graph>
Chris@16 140 void discover_vertex(Vertex u, const Graph& g) {
Chris@16 141 m_vis.discover_vertex(u, g);
Chris@16 142 }
Chris@16 143 template <class Vertex, class Graph>
Chris@16 144 void examine_vertex(Vertex u, const Graph& g) {
Chris@16 145 m_vis.examine_vertex(u, g);
Chris@16 146 }
Chris@16 147 template <class Vertex, class Graph>
Chris@16 148 void finish_vertex(Vertex u, const Graph& g) {
Chris@16 149 m_vis.finish_vertex(u, g);
Chris@16 150 }
Chris@16 151 template <class Edge, class Graph>
Chris@16 152 void examine_edge(Edge e, const Graph& g) {
Chris@16 153 if (m_compare(get(m_weight, e), m_zero))
Chris@16 154 BOOST_THROW_EXCEPTION(negative_edge());
Chris@16 155 m_vis.examine_edge(e, g);
Chris@16 156 }
Chris@16 157 template <class Edge, class Graph>
Chris@16 158 void non_tree_edge(Edge, const Graph&) {}
Chris@16 159
Chris@16 160
Chris@16 161
Chris@16 162 template <class Edge, class Graph>
Chris@16 163 void tree_edge(Edge e, const Graph& g) {
Chris@16 164 using boost::get;
Chris@16 165 bool m_decreased =
Chris@16 166 relax(e, g, m_weight, m_predecessor, m_distance,
Chris@16 167 m_combine, m_compare);
Chris@16 168
Chris@16 169 if(m_decreased) {
Chris@16 170 m_vis.edge_relaxed(e, g);
Chris@16 171 put(m_cost, target(e, g),
Chris@16 172 m_combine(get(m_distance, target(e, g)),
Chris@16 173 m_h(target(e, g))));
Chris@16 174 } else
Chris@16 175 m_vis.edge_not_relaxed(e, g);
Chris@16 176 }
Chris@16 177
Chris@16 178
Chris@16 179 template <class Edge, class Graph>
Chris@16 180 void gray_target(Edge e, const Graph& g) {
Chris@16 181 using boost::get;
Chris@16 182 bool m_decreased =
Chris@16 183 relax(e, g, m_weight, m_predecessor, m_distance,
Chris@16 184 m_combine, m_compare);
Chris@16 185
Chris@16 186 if(m_decreased) {
Chris@16 187 put(m_cost, target(e, g),
Chris@16 188 m_combine(get(m_distance, target(e, g)),
Chris@16 189 m_h(target(e, g))));
Chris@16 190 m_Q.update(target(e, g));
Chris@16 191 m_vis.edge_relaxed(e, g);
Chris@16 192 } else
Chris@16 193 m_vis.edge_not_relaxed(e, g);
Chris@16 194 }
Chris@16 195
Chris@16 196
Chris@16 197 template <class Edge, class Graph>
Chris@16 198 void black_target(Edge e, const Graph& g) {
Chris@16 199 using boost::get;
Chris@16 200 bool m_decreased =
Chris@16 201 relax(e, g, m_weight, m_predecessor, m_distance,
Chris@16 202 m_combine, m_compare);
Chris@16 203
Chris@16 204 if(m_decreased) {
Chris@16 205 m_vis.edge_relaxed(e, g);
Chris@16 206 put(m_cost, target(e, g),
Chris@16 207 m_combine(get(m_distance, target(e, g)),
Chris@16 208 m_h(target(e, g))));
Chris@16 209 m_Q.push(target(e, g));
Chris@16 210 put(m_color, target(e, g), Color::gray());
Chris@16 211 m_vis.black_target(e, g);
Chris@16 212 } else
Chris@16 213 m_vis.edge_not_relaxed(e, g);
Chris@16 214 }
Chris@16 215
Chris@16 216
Chris@16 217
Chris@16 218 AStarHeuristic m_h;
Chris@16 219 UniformCostVisitor m_vis;
Chris@16 220 UpdatableQueue& m_Q;
Chris@16 221 PredecessorMap m_predecessor;
Chris@16 222 CostMap m_cost;
Chris@16 223 DistanceMap m_distance;
Chris@16 224 WeightMap m_weight;
Chris@16 225 ColorMap m_color;
Chris@16 226 BinaryFunction m_combine;
Chris@16 227 BinaryPredicate m_compare;
Chris@16 228 C m_zero;
Chris@16 229
Chris@16 230 };
Chris@16 231
Chris@16 232 } // namespace detail
Chris@16 233
Chris@16 234
Chris@16 235
Chris@16 236 template <typename VertexListGraph, typename AStarHeuristic,
Chris@16 237 typename AStarVisitor, typename PredecessorMap,
Chris@16 238 typename CostMap, typename DistanceMap,
Chris@16 239 typename WeightMap, typename ColorMap,
Chris@16 240 typename VertexIndexMap,
Chris@16 241 typename CompareFunction, typename CombineFunction,
Chris@16 242 typename CostInf, typename CostZero>
Chris@16 243 inline void
Chris@16 244 astar_search_no_init
Chris@16 245 (const VertexListGraph &g,
Chris@16 246 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 247 AStarHeuristic h, AStarVisitor vis,
Chris@16 248 PredecessorMap predecessor, CostMap cost,
Chris@16 249 DistanceMap distance, WeightMap weight,
Chris@16 250 ColorMap color, VertexIndexMap index_map,
Chris@16 251 CompareFunction compare, CombineFunction combine,
Chris@16 252 CostInf /*inf*/, CostZero zero)
Chris@16 253 {
Chris@16 254 typedef typename graph_traits<VertexListGraph>::vertex_descriptor
Chris@16 255 Vertex;
Chris@16 256 typedef boost::vector_property_map<std::size_t, VertexIndexMap> IndexInHeapMap;
Chris@16 257 IndexInHeapMap index_in_heap(index_map);
Chris@16 258 typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction>
Chris@16 259 MutableQueue;
Chris@16 260 MutableQueue Q(cost, index_in_heap, compare);
Chris@16 261
Chris@16 262 detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor,
Chris@16 263 MutableQueue, PredecessorMap, CostMap, DistanceMap,
Chris@16 264 WeightMap, ColorMap, CombineFunction, CompareFunction>
Chris@16 265 bfs_vis(h, vis, Q, predecessor, cost, distance, weight,
Chris@16 266 color, combine, compare, zero);
Chris@16 267
Chris@16 268 breadth_first_visit(g, s, Q, bfs_vis, color);
Chris@16 269 }
Chris@16 270
Chris@16 271 namespace graph_detail {
Chris@16 272 template <typename A, typename B>
Chris@16 273 struct select1st {
Chris@16 274 typedef std::pair<A, B> argument_type;
Chris@16 275 typedef A result_type;
Chris@16 276 A operator()(const std::pair<A, B>& p) const {return p.first;}
Chris@16 277 };
Chris@16 278 }
Chris@16 279
Chris@16 280 template <typename VertexListGraph, typename AStarHeuristic,
Chris@16 281 typename AStarVisitor, typename PredecessorMap,
Chris@16 282 typename CostMap, typename DistanceMap,
Chris@16 283 typename WeightMap,
Chris@16 284 typename CompareFunction, typename CombineFunction,
Chris@16 285 typename CostInf, typename CostZero>
Chris@16 286 inline void
Chris@16 287 astar_search_no_init_tree
Chris@16 288 (const VertexListGraph &g,
Chris@16 289 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 290 AStarHeuristic h, AStarVisitor vis,
Chris@16 291 PredecessorMap predecessor, CostMap cost,
Chris@16 292 DistanceMap distance, WeightMap weight,
Chris@16 293 CompareFunction compare, CombineFunction combine,
Chris@16 294 CostInf /*inf*/, CostZero zero)
Chris@16 295 {
Chris@16 296 typedef typename graph_traits<VertexListGraph>::vertex_descriptor
Chris@16 297 Vertex;
Chris@16 298 typedef typename property_traits<DistanceMap>::value_type Distance;
Chris@16 299 typedef d_ary_heap_indirect<
Chris@16 300 std::pair<Distance, Vertex>,
Chris@16 301 4,
Chris@16 302 null_property_map<std::pair<Distance, Vertex>, std::size_t>,
Chris@16 303 function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
Chris@16 304 CompareFunction>
Chris@16 305 MutableQueue;
Chris@16 306 MutableQueue Q(
Chris@16 307 make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()),
Chris@16 308 null_property_map<std::pair<Distance, Vertex>, std::size_t>(),
Chris@16 309 compare);
Chris@16 310
Chris@16 311 vis.discover_vertex(s, g);
Chris@16 312 Q.push(std::make_pair(get(cost, s), s));
Chris@16 313 while (!Q.empty()) {
Chris@16 314 Vertex v;
Chris@16 315 Distance v_rank;
Chris@16 316 boost::tie(v_rank, v) = Q.top();
Chris@16 317 Q.pop();
Chris@16 318 vis.examine_vertex(v, g);
Chris@16 319 BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) {
Chris@16 320 Vertex w = target(e, g);
Chris@16 321 vis.examine_edge(e, g);
Chris@16 322 Distance e_weight = get(weight, e);
Chris@16 323 if (compare(e_weight, zero))
Chris@16 324 BOOST_THROW_EXCEPTION(negative_edge());
Chris@16 325 bool decreased =
Chris@16 326 relax(e, g, weight, predecessor, distance,
Chris@16 327 combine, compare);
Chris@16 328 Distance w_d = combine(get(distance, v), e_weight);
Chris@16 329 if (decreased) {
Chris@16 330 vis.edge_relaxed(e, g);
Chris@16 331 Distance w_rank = combine(get(distance, w), h(w));
Chris@16 332 put(cost, w, w_rank);
Chris@16 333 vis.discover_vertex(w, g);
Chris@16 334 Q.push(std::make_pair(w_rank, w));
Chris@16 335 } else {
Chris@16 336 vis.edge_not_relaxed(e, g);
Chris@16 337 }
Chris@16 338 }
Chris@16 339 vis.finish_vertex(v, g);
Chris@16 340 }
Chris@16 341 }
Chris@16 342
Chris@16 343 // Non-named parameter interface
Chris@16 344 template <typename VertexListGraph, typename AStarHeuristic,
Chris@16 345 typename AStarVisitor, typename PredecessorMap,
Chris@16 346 typename CostMap, typename DistanceMap,
Chris@16 347 typename WeightMap, typename VertexIndexMap,
Chris@16 348 typename ColorMap,
Chris@16 349 typename CompareFunction, typename CombineFunction,
Chris@16 350 typename CostInf, typename CostZero>
Chris@16 351 inline void
Chris@16 352 astar_search
Chris@16 353 (const VertexListGraph &g,
Chris@16 354 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 355 AStarHeuristic h, AStarVisitor vis,
Chris@16 356 PredecessorMap predecessor, CostMap cost,
Chris@16 357 DistanceMap distance, WeightMap weight,
Chris@16 358 VertexIndexMap index_map, ColorMap color,
Chris@16 359 CompareFunction compare, CombineFunction combine,
Chris@16 360 CostInf inf, CostZero zero)
Chris@16 361 {
Chris@16 362
Chris@16 363 typedef typename property_traits<ColorMap>::value_type ColorValue;
Chris@16 364 typedef color_traits<ColorValue> Color;
Chris@16 365 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
Chris@16 366 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
Chris@16 367 put(color, *ui, Color::white());
Chris@16 368 put(distance, *ui, inf);
Chris@16 369 put(cost, *ui, inf);
Chris@16 370 put(predecessor, *ui, *ui);
Chris@16 371 vis.initialize_vertex(*ui, g);
Chris@16 372 }
Chris@16 373 put(distance, s, zero);
Chris@16 374 put(cost, s, h(s));
Chris@16 375
Chris@16 376 astar_search_no_init
Chris@16 377 (g, s, h, vis, predecessor, cost, distance, weight,
Chris@16 378 color, index_map, compare, combine, inf, zero);
Chris@16 379
Chris@16 380 }
Chris@16 381
Chris@16 382 // Non-named parameter interface
Chris@16 383 template <typename VertexListGraph, typename AStarHeuristic,
Chris@16 384 typename AStarVisitor, typename PredecessorMap,
Chris@16 385 typename CostMap, typename DistanceMap,
Chris@16 386 typename WeightMap,
Chris@16 387 typename CompareFunction, typename CombineFunction,
Chris@16 388 typename CostInf, typename CostZero>
Chris@16 389 inline void
Chris@16 390 astar_search_tree
Chris@16 391 (const VertexListGraph &g,
Chris@16 392 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 393 AStarHeuristic h, AStarVisitor vis,
Chris@16 394 PredecessorMap predecessor, CostMap cost,
Chris@16 395 DistanceMap distance, WeightMap weight,
Chris@16 396 CompareFunction compare, CombineFunction combine,
Chris@16 397 CostInf inf, CostZero zero)
Chris@16 398 {
Chris@16 399
Chris@16 400 typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
Chris@16 401 for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
Chris@16 402 put(distance, *ui, inf);
Chris@16 403 put(cost, *ui, inf);
Chris@16 404 put(predecessor, *ui, *ui);
Chris@16 405 vis.initialize_vertex(*ui, g);
Chris@16 406 }
Chris@16 407 put(distance, s, zero);
Chris@16 408 put(cost, s, h(s));
Chris@16 409
Chris@16 410 astar_search_no_init_tree
Chris@16 411 (g, s, h, vis, predecessor, cost, distance, weight,
Chris@16 412 compare, combine, inf, zero);
Chris@16 413
Chris@16 414 }
Chris@16 415
Chris@16 416 // Named parameter interfaces
Chris@16 417 template <typename VertexListGraph,
Chris@16 418 typename AStarHeuristic,
Chris@16 419 typename P, typename T, typename R>
Chris@16 420 void
Chris@16 421 astar_search
Chris@16 422 (const VertexListGraph &g,
Chris@16 423 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 424 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16 425 {
Chris@16 426 using namespace boost::graph::keywords;
Chris@16 427 typedef bgl_named_params<P, T, R> params_type;
Chris@16 428 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16 429
Chris@16 430 // Distance type is the value type of the distance map if there is one,
Chris@16 431 // otherwise the value type of the weight map.
Chris@16 432 typedef
Chris@16 433 typename detail::override_const_property_result<
Chris@16 434 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16 435 weight_map_type;
Chris@16 436 typedef typename boost::property_traits<weight_map_type>::value_type W;
Chris@16 437 typedef
Chris@16 438 typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
Chris@16 439 distance_map_type;
Chris@16 440 typedef typename boost::property_traits<distance_map_type>::value_type D;
Chris@16 441 const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16 442
Chris@16 443 astar_search
Chris@16 444 (g, s, h,
Chris@16 445 arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16 446 arg_pack[_predecessor_map | dummy_property_map()],
Chris@16 447 detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16 448 detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack),
Chris@16 449 detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16 450 detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
Chris@16 451 detail::make_color_map_from_arg_pack(g, arg_pack),
Chris@16 452 arg_pack[_distance_compare | std::less<D>()],
Chris@16 453 arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16 454 inf,
Chris@16 455 arg_pack[_distance_zero | D()]);
Chris@16 456 }
Chris@16 457
Chris@16 458 // Named parameter interfaces
Chris@16 459 template <typename VertexListGraph,
Chris@16 460 typename AStarHeuristic,
Chris@16 461 typename P, typename T, typename R>
Chris@16 462 void
Chris@16 463 astar_search_tree
Chris@16 464 (const VertexListGraph &g,
Chris@16 465 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 466 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16 467 {
Chris@16 468 using namespace boost::graph::keywords;
Chris@16 469 typedef bgl_named_params<P, T, R> params_type;
Chris@16 470 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16 471
Chris@16 472 // Distance type is the value type of the distance map if there is one,
Chris@16 473 // otherwise the value type of the weight map.
Chris@16 474 typedef
Chris@16 475 typename detail::override_const_property_result<
Chris@16 476 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16 477 weight_map_type;
Chris@16 478 typedef typename boost::property_traits<weight_map_type>::value_type W;
Chris@16 479 typedef
Chris@16 480 typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type
Chris@16 481 distance_map_type;
Chris@16 482 typedef typename boost::property_traits<distance_map_type>::value_type D;
Chris@16 483 const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16 484
Chris@16 485 astar_search_tree
Chris@16 486 (g, s, h,
Chris@16 487 arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16 488 arg_pack[_predecessor_map | dummy_property_map()],
Chris@16 489 detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16 490 detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack),
Chris@16 491 detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16 492 arg_pack[_distance_compare | std::less<D>()],
Chris@16 493 arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16 494 inf,
Chris@16 495 arg_pack[_distance_zero | D()]);
Chris@16 496 }
Chris@16 497
Chris@16 498 template <typename VertexListGraph,
Chris@16 499 typename AStarHeuristic,
Chris@16 500 typename P, typename T, typename R>
Chris@16 501 void
Chris@16 502 astar_search_no_init
Chris@16 503 (const VertexListGraph &g,
Chris@16 504 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 505 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16 506 {
Chris@16 507 using namespace boost::graph::keywords;
Chris@16 508 typedef bgl_named_params<P, T, R> params_type;
Chris@16 509 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16 510 typedef
Chris@16 511 typename detail::override_const_property_result<
Chris@16 512 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16 513 weight_map_type;
Chris@16 514 typedef typename boost::property_traits<weight_map_type>::value_type D;
Chris@16 515 const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16 516 astar_search_no_init
Chris@16 517 (g, s, h,
Chris@16 518 arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16 519 arg_pack[_predecessor_map | dummy_property_map()],
Chris@16 520 detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16 521 detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack),
Chris@16 522 detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16 523 detail::make_color_map_from_arg_pack(g, arg_pack),
Chris@16 524 detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index),
Chris@16 525 arg_pack[_distance_compare | std::less<D>()],
Chris@16 526 arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16 527 inf,
Chris@16 528 arg_pack[_distance_zero | D()]);
Chris@16 529 }
Chris@16 530
Chris@16 531 template <typename VertexListGraph,
Chris@16 532 typename AStarHeuristic,
Chris@16 533 typename P, typename T, typename R>
Chris@16 534 void
Chris@16 535 astar_search_no_init_tree
Chris@16 536 (const VertexListGraph &g,
Chris@16 537 typename graph_traits<VertexListGraph>::vertex_descriptor s,
Chris@16 538 AStarHeuristic h, const bgl_named_params<P, T, R>& params)
Chris@16 539 {
Chris@16 540 using namespace boost::graph::keywords;
Chris@16 541 typedef bgl_named_params<P, T, R> params_type;
Chris@16 542 BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
Chris@16 543 typedef
Chris@16 544 typename detail::override_const_property_result<
Chris@16 545 arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type
Chris@16 546 weight_map_type;
Chris@16 547 typedef typename boost::property_traits<weight_map_type>::value_type D;
Chris@16 548 const D inf = arg_pack[_distance_inf || detail::get_max<D>()];
Chris@16 549 astar_search_no_init_tree
Chris@16 550 (g, s, h,
Chris@16 551 arg_pack[_visitor | make_astar_visitor(null_visitor())],
Chris@16 552 arg_pack[_predecessor_map | dummy_property_map()],
Chris@16 553 detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack),
Chris@16 554 detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack),
Chris@16 555 detail::override_const_property(arg_pack, _weight_map, g, edge_weight),
Chris@16 556 arg_pack[_distance_compare | std::less<D>()],
Chris@16 557 arg_pack[_distance_combine | closed_plus<D>(inf)],
Chris@16 558 inf,
Chris@16 559 arg_pack[_distance_zero | D()]);
Chris@16 560 }
Chris@16 561
Chris@16 562 } // namespace boost
Chris@16 563
Chris@16 564 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP