| |
| |
| // |
| //======================================================================= |
| // Copyright (c) 2004 Kristopher Beevers |
| // |
| // Distributed under the Boost Software License, Version 1.0. (See |
| // accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| //======================================================================= |
| // |
| |
| #ifndef BOOST_GRAPH_ASTAR_SEARCH_HPP |
| #define BOOST_GRAPH_ASTAR_SEARCH_HPP |
| |
| |
| #include <functional> |
| #include <vector> |
| #include <boost/limits.hpp> |
| #include <boost/throw_exception.hpp> |
| #include <boost/graph/named_function_params.hpp> |
| #include <boost/graph/relax.hpp> |
| #include <boost/graph/exception.hpp> |
| #include <boost/graph/breadth_first_search.hpp> |
| #include <boost/graph/detail/d_ary_heap.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <boost/property_map/vector_property_map.hpp> |
| |
| |
| namespace boost { |
| |
| |
| template <class Heuristic, class Graph> |
| struct AStarHeuristicConcept { |
| void constraints() |
| { |
| function_requires< CopyConstructibleConcept<Heuristic> >(); |
| h(u); |
| } |
| Heuristic h; |
| typename graph_traits<Graph>::vertex_descriptor u; |
| }; |
| |
| |
| template <class Graph, class CostType> |
| class astar_heuristic : public std::unary_function< |
| typename graph_traits<Graph>::vertex_descriptor, CostType> |
| { |
| public: |
| typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |
| astar_heuristic() {} |
| CostType operator()(Vertex u) { return static_cast<CostType>(0); } |
| }; |
| |
| |
| |
| template <class Visitor, class Graph> |
| struct AStarVisitorConcept { |
| void constraints() |
| { |
| function_requires< CopyConstructibleConcept<Visitor> >(); |
| vis.initialize_vertex(u, g); |
| vis.discover_vertex(u, g); |
| vis.examine_vertex(u, g); |
| vis.examine_edge(e, g); |
| vis.edge_relaxed(e, g); |
| vis.edge_not_relaxed(e, g); |
| vis.black_target(e, g); |
| vis.finish_vertex(u, g); |
| } |
| Visitor vis; |
| Graph g; |
| typename graph_traits<Graph>::vertex_descriptor u; |
| typename graph_traits<Graph>::edge_descriptor e; |
| }; |
| |
| |
| template <class Visitors = null_visitor> |
| class astar_visitor : public bfs_visitor<Visitors> { |
| public: |
| astar_visitor() {} |
| astar_visitor(Visitors vis) |
| : bfs_visitor<Visitors>(vis) {} |
| |
| template <class Edge, class Graph> |
| void edge_relaxed(Edge e, const Graph& g) { |
| invoke_visitors(this->m_vis, e, g, on_edge_relaxed()); |
| } |
| template <class Edge, class Graph> |
| void edge_not_relaxed(Edge e, const Graph& g) { |
| invoke_visitors(this->m_vis, e, g, on_edge_not_relaxed()); |
| } |
| private: |
| template <class Edge, class Graph> |
| void tree_edge(Edge e, const Graph& g) {} |
| template <class Edge, class Graph> |
| void non_tree_edge(Edge e, const Graph& g) {} |
| }; |
| template <class Visitors> |
| astar_visitor<Visitors> |
| make_astar_visitor(Visitors vis) { |
| return astar_visitor<Visitors>(vis); |
| } |
| typedef astar_visitor<> default_astar_visitor; |
| |
| |
| namespace detail { |
| |
| template <class AStarHeuristic, class UniformCostVisitor, |
| class UpdatableQueue, class PredecessorMap, |
| class CostMap, class DistanceMap, class WeightMap, |
| class ColorMap, class BinaryFunction, |
| class BinaryPredicate> |
| struct astar_bfs_visitor |
| { |
| |
| typedef typename property_traits<CostMap>::value_type C; |
| typedef typename property_traits<ColorMap>::value_type ColorValue; |
| typedef color_traits<ColorValue> Color; |
| typedef typename property_traits<DistanceMap>::value_type distance_type; |
| |
| astar_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis, |
| UpdatableQueue& Q, PredecessorMap p, |
| CostMap c, DistanceMap d, WeightMap w, |
| ColorMap col, BinaryFunction combine, |
| BinaryPredicate compare, C zero) |
| : m_h(h), m_vis(vis), m_Q(Q), m_predecessor(p), m_cost(c), |
| m_distance(d), m_weight(w), m_color(col), |
| m_combine(combine), m_compare(compare), m_zero(zero) {} |
| |
| |
| template <class Vertex, class Graph> |
| void initialize_vertex(Vertex u, const Graph& g) { |
| m_vis.initialize_vertex(u, g); |
| } |
| template <class Vertex, class Graph> |
| void discover_vertex(Vertex u, const Graph& g) { |
| m_vis.discover_vertex(u, g); |
| } |
| template <class Vertex, class Graph> |
| void examine_vertex(Vertex u, const Graph& g) { |
| m_vis.examine_vertex(u, g); |
| } |
| template <class Vertex, class Graph> |
| void finish_vertex(Vertex u, const Graph& g) { |
| m_vis.finish_vertex(u, g); |
| } |
| template <class Edge, class Graph> |
| void examine_edge(Edge e, const Graph& g) { |
| if (m_compare(get(m_weight, e), m_zero)) |
| BOOST_THROW_EXCEPTION(negative_edge()); |
| m_vis.examine_edge(e, g); |
| } |
| template <class Edge, class Graph> |
| void non_tree_edge(Edge, const Graph&) {} |
| |
| |
| |
| template <class Edge, class Graph> |
| void tree_edge(Edge e, const Graph& g) { |
| m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, |
| m_combine, m_compare); |
| |
| if(m_decreased) { |
| m_vis.edge_relaxed(e, g); |
| put(m_cost, target(e, g), |
| m_combine(get(m_distance, target(e, g)), |
| m_h(target(e, g)))); |
| } else |
| m_vis.edge_not_relaxed(e, g); |
| } |
| |
| |
| template <class Edge, class Graph> |
| void gray_target(Edge e, const Graph& g) { |
| m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, |
| m_combine, m_compare); |
| |
| if(m_decreased) { |
| put(m_cost, target(e, g), |
| m_combine(get(m_distance, target(e, g)), |
| m_h(target(e, g)))); |
| m_Q.update(target(e, g)); |
| m_vis.edge_relaxed(e, g); |
| } else |
| m_vis.edge_not_relaxed(e, g); |
| } |
| |
| |
| template <class Edge, class Graph> |
| void black_target(Edge e, const Graph& g) { |
| m_decreased = relax(e, g, m_weight, m_predecessor, m_distance, |
| m_combine, m_compare); |
| |
| if(m_decreased) { |
| m_vis.edge_relaxed(e, g); |
| put(m_cost, target(e, g), |
| m_combine(get(m_distance, target(e, g)), |
| m_h(target(e, g)))); |
| m_Q.push(target(e, g)); |
| put(m_color, target(e, g), Color::gray()); |
| m_vis.black_target(e, g); |
| } else |
| m_vis.edge_not_relaxed(e, g); |
| } |
| |
| |
| |
| AStarHeuristic m_h; |
| UniformCostVisitor m_vis; |
| UpdatableQueue& m_Q; |
| PredecessorMap m_predecessor; |
| CostMap m_cost; |
| DistanceMap m_distance; |
| WeightMap m_weight; |
| ColorMap m_color; |
| BinaryFunction m_combine; |
| BinaryPredicate m_compare; |
| bool m_decreased; |
| C m_zero; |
| |
| }; |
| |
| } // namespace detail |
| |
| |
| |
| template <typename VertexListGraph, typename AStarHeuristic, |
| typename AStarVisitor, typename PredecessorMap, |
| typename CostMap, typename DistanceMap, |
| typename WeightMap, typename ColorMap, |
| typename VertexIndexMap, |
| typename CompareFunction, typename CombineFunction, |
| typename CostInf, typename CostZero> |
| 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 /*inf*/, CostZero zero) |
| { |
| typedef typename graph_traits<VertexListGraph>::vertex_descriptor |
| Vertex; |
| typedef boost::vector_property_map<std::size_t, VertexIndexMap> IndexInHeapMap; |
| IndexInHeapMap index_in_heap(index_map); |
| typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, CostMap, CompareFunction> |
| MutableQueue; |
| MutableQueue Q(cost, index_in_heap, compare); |
| |
| detail::astar_bfs_visitor<AStarHeuristic, AStarVisitor, |
| MutableQueue, PredecessorMap, CostMap, DistanceMap, |
| WeightMap, ColorMap, CombineFunction, CompareFunction> |
| bfs_vis(h, vis, Q, predecessor, cost, distance, weight, |
| color, combine, compare, zero); |
| |
| breadth_first_visit(g, s, Q, bfs_vis, color); |
| } |
| |
| |
| // Non-named parameter interface |
| template <typename VertexListGraph, typename AStarHeuristic, |
| typename AStarVisitor, typename PredecessorMap, |
| typename CostMap, typename DistanceMap, |
| typename WeightMap, typename VertexIndexMap, |
| typename ColorMap, |
| typename CompareFunction, typename CombineFunction, |
| typename CostInf, typename CostZero> |
| 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) |
| { |
| |
| typedef typename property_traits<ColorMap>::value_type ColorValue; |
| typedef color_traits<ColorValue> Color; |
| typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end; |
| for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) { |
| put(color, *ui, Color::white()); |
| put(distance, *ui, inf); |
| put(cost, *ui, inf); |
| put(predecessor, *ui, *ui); |
| vis.initialize_vertex(*ui, g); |
| } |
| put(distance, s, zero); |
| put(cost, s, h(s)); |
| |
| astar_search_no_init |
| (g, s, h, vis, predecessor, cost, distance, weight, |
| color, index_map, compare, combine, inf, zero); |
| |
| } |
| |
| // Named parameter interfaces |
| template <typename VertexListGraph, |
| typename AStarHeuristic, |
| typename P, typename T, typename R> |
| void |
| astar_search |
| (const VertexListGraph &g, |
| typename graph_traits<VertexListGraph>::vertex_descriptor s, |
| AStarHeuristic h, const bgl_named_params<P, T, R>& params) |
| { |
| using namespace boost::graph::keywords; |
| typedef bgl_named_params<P, T, R> params_type; |
| BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
| |
| // Distance type is the value type of the distance map if there is one, |
| // otherwise the value type of the weight map. |
| typedef |
| typename detail::override_const_property_result< |
| arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type |
| weight_map_type; |
| typedef typename boost::property_traits<weight_map_type>::value_type W; |
| typedef |
| typename detail::map_maker<VertexListGraph, arg_pack_type, tag::distance_map, W>::map_type |
| distance_map_type; |
| typedef typename boost::property_traits<distance_map_type>::value_type D; |
| |
| astar_search |
| (g, s, h, |
| arg_pack[_visitor | make_astar_visitor(null_visitor())], |
| arg_pack[_predecessor_map | dummy_property_map()], |
| detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), |
| detail::make_property_map_from_arg_pack_gen<tag::distance_map, W>(W())(g, arg_pack), |
| detail::override_const_property(arg_pack, _weight_map, g, edge_weight), |
| detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index), |
| detail::make_color_map_from_arg_pack(g, arg_pack), |
| arg_pack[_distance_compare | std::less<D>()], |
| arg_pack[_distance_combine | closed_plus<D>()], |
| arg_pack[_distance_inf | (std::numeric_limits<D>::max)()], |
| arg_pack[_distance_zero | D()]); |
| } |
| |
| template <typename VertexListGraph, |
| typename AStarHeuristic, |
| typename P, typename T, typename R> |
| 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) |
| { |
| using namespace boost::graph::keywords; |
| typedef bgl_named_params<P, T, R> params_type; |
| BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params) |
| typedef |
| typename detail::override_const_property_result< |
| arg_pack_type, tag::weight_map, edge_weight_t, VertexListGraph>::type |
| weight_map_type; |
| typedef typename boost::property_traits<weight_map_type>::value_type D; |
| astar_search_no_init |
| (g, s, h, |
| arg_pack[_visitor | make_astar_visitor(null_visitor())], |
| arg_pack[_predecessor_map | dummy_property_map()], |
| detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack), |
| detail::make_property_map_from_arg_pack_gen<tag::distance_map, D>(D())(g, arg_pack), |
| detail::override_const_property(arg_pack, _weight_map, g, edge_weight), |
| detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index), |
| detail::make_color_map_from_arg_pack(g, arg_pack), |
| arg_pack[_distance_compare | std::less<D>()], |
| arg_pack[_distance_combine | closed_plus<D>()], |
| arg_pack[_distance_inf | (std::numeric_limits<D>::max)()], |
| arg_pack[_distance_zero | D()]); |
| } |
| |
| } // namespace boost |
| |
| #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP |