Subject: [Boost-commit] svn:boost r64024 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2010-07-14 18:15:50
Author: jewillco
Date: 2010-07-14 18:15:48 EDT (Wed, 14 Jul 2010)
New Revision: 64024
URL: http://svn.boost.org/trac/boost/changeset/64024
Log:
Changed to new-style named parameters for A* code; added named parameters for astar_search_no_init()
Text files modified:
trunk/boost/graph/astar_search.hpp | 123 +++++++++++++++++++--------------------
trunk/boost/graph/named_function_params.hpp | 38 ++++++++---
trunk/libs/graph/doc/astar_search.html | 36 +++++++----
3 files changed, 108 insertions(+), 89 deletions(-)
Modified: trunk/boost/graph/astar_search.hpp
==============================================================================
--- trunk/boost/graph/astar_search.hpp (original)
+++ trunk/boost/graph/astar_search.hpp 2010-07-14 18:15:48 EDT (Wed, 14 Jul 2010)
@@ -300,63 +300,7 @@
}
-
-
- namespace detail {
- template <class VertexListGraph, class AStarHeuristic,
- class CostMap, class DistanceMap, class WeightMap,
- class IndexMap, class ColorMap, class Params>
- inline void
- astar_dispatch2
- (const VertexListGraph& g,
- typename graph_traits<VertexListGraph>::vertex_descriptor s,
- AStarHeuristic h, CostMap cost, DistanceMap distance,
- WeightMap weight, IndexMap index_map, ColorMap color,
- const Params& params)
- {
- dummy_property_map p_map;
- typedef typename property_traits<CostMap>::value_type C;
- astar_search
- (g, s, h,
- choose_param(get_param(params, graph_visitor),
- make_astar_visitor(null_visitor())),
- choose_param(get_param(params, vertex_predecessor), p_map),
- cost, distance, weight, index_map, color,
- choose_param(get_param(params, distance_compare_t()),
- std::less<C>()),
- choose_param(get_param(params, distance_combine_t()),
- closed_plus<C>()),
- choose_param(get_param(params, distance_inf_t()),
- std::numeric_limits<C>::max BOOST_PREVENT_MACRO_SUBSTITUTION ()),
- choose_param(get_param(params, distance_zero_t()),
- C()));
- }
-
- template <class VertexListGraph, class AStarHeuristic,
- class CostMap, class DistanceMap, class WeightMap,
- class IndexMap, class ColorMap, class Params>
- inline void
- astar_dispatch1
- (const VertexListGraph& g,
- typename graph_traits<VertexListGraph>::vertex_descriptor s,
- AStarHeuristic h, CostMap cost, DistanceMap distance,
- WeightMap weight, IndexMap index_map, ColorMap color,
- const Params& params)
- {
- typedef typename property_traits<WeightMap>::value_type D;
-
- detail::astar_dispatch2
- (g, s, h,
- choose_param(cost, vector_property_map<D, IndexMap>(index_map)),
- choose_param(distance, vector_property_map<D, IndexMap>(index_map)),
- weight, index_map,
- choose_param(color, vector_property_map<default_color_type, IndexMap>(index_map)),
- params);
- }
- } // namespace detail
-
-
- // Named parameter interface
+ // Named parameter interfaces
template <typename VertexListGraph,
typename AStarHeuristic,
typename P, typename T, typename R>
@@ -366,16 +310,67 @@
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;
- detail::astar_dispatch1
+ astar_search
(g, s, h,
- get_param(params, vertex_rank),
- get_param(params, vertex_distance),
- choose_const_pmap(get_param(params, edge_weight), g, edge_weight),
- choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
- get_param(params, vertex_color),
- params);
+ 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),
+ override_const_property(arg_pack, _weight_map, g, edge_weight),
+ 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),
+ override_const_property(arg_pack, _weight_map, g, edge_weight),
+ 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
Modified: trunk/boost/graph/named_function_params.hpp
==============================================================================
--- trunk/boost/graph/named_function_params.hpp (original)
+++ trunk/boost/graph/named_function_params.hpp 2010-07-14 18:15:48 EDT (Wed, 14 Jul 2010)
@@ -393,12 +393,19 @@
};
template <typename ArgPack, typename Tag, typename Prop, typename Graph>
- typename override_const_property_t<
- typename boost::parameter::value_type<ArgPack, Tag, int>::type,
- Prop,
- Graph,
- boost::detail::parameter_exists<ArgPack, Tag>::value
- >::result_type
+ struct override_const_property_result {
+ typedef
+ typename override_const_property_t<
+ typename boost::parameter::value_type<ArgPack, Tag, int>::type,
+ Prop,
+ Graph,
+ boost::detail::parameter_exists<ArgPack, Tag>::value
+ >::result_type
+ type;
+ };
+
+ template <typename ArgPack, typename Tag, typename Prop, typename Graph>
+ typename override_const_property_result<ArgPack, Tag, Prop, Graph>::type
override_const_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop) {
return override_const_property_t<
typename boost::parameter::value_type<ArgPack, Tag, int>::type,
@@ -421,12 +428,19 @@
};
template <typename ArgPack, typename Tag, typename Prop, typename Graph>
- typename override_property_t<
- typename boost::parameter::value_type<ArgPack, Tag, int>::type,
- Prop,
- Graph,
- boost::detail::parameter_exists<ArgPack, Tag>::value
- >::result_type
+ struct override_property_result {
+ typedef
+ typename override_property_t<
+ typename boost::parameter::value_type<ArgPack, Tag, int>::type,
+ Prop,
+ Graph,
+ boost::detail::parameter_exists<ArgPack, Tag>::value
+ >::result_type
+ type;
+ };
+
+ template <typename ArgPack, typename Tag, typename Prop, typename Graph>
+ typename override_property_result<ArgPack, Tag, Prop, Graph>::type
override_property(const ArgPack& ap, const boost::parameter::keyword<Tag>& t, const Graph& g, Prop prop) {
return override_property_t<
typename boost::parameter::value_type<ArgPack, Tag, int>::type,
Modified: trunk/libs/graph/doc/astar_search.html
==============================================================================
--- trunk/libs/graph/doc/astar_search.html (original)
+++ trunk/libs/graph/doc/astar_search.html 2010-07-14 18:15:48 EDT (Wed, 14 Jul 2010)
@@ -22,7 +22,7 @@
<P>
<PRE>
-<i>// Named parameter interface</i>
+<i>// Named parameter interfaces</i>
template <typename VertexListGraph,
typename AStarHeuristic,
typename P, typename T, typename R>
@@ -32,6 +32,15 @@
typename graph_traits<VertexListGraph>::vertex_descriptor s,
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
+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);
+
<i>// Non-named parameter interface</i>
template <typename VertexListGraph, typename AStarHeuristic,
typename AStarVisitor, typename PredecessorMap,
@@ -71,7 +80,8 @@
CostInf inf, CostZero zero);
<b>Note that the index_map and color parameters are swapped in
-astar_search_no_init relative to astar_search.</b>
+astar_search_no_init() relative to astar_search(); the named parameter
+interfaces are not affected.</b>
</PRE>
<P>
@@ -110,7 +120,7 @@
Implicit graphs are graphs that are not completely known at the
beginning of the search. Upon visiting a vertex, its neighbors are
"generated" and added to the search. Implicit graphs are particularly
-useful for searching large state spaces -- in gameplaying scenarios
+useful for searching large state spaces -- in game-playing scenarios
(e.g. chess), for example -- in which it may not be possible to store
the entire graph. Implicit searches can be performed with this
implementation of A* by creating special visitors that generate
@@ -293,7 +303,7 @@
<b>Default:</b> <tt>get(vertex_index, g)</tt>.
Note: if you use this default, make sure your graph has
an internal <tt>vertex_index</tt> property. For example,
- <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
+ <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
not have an internal <tt>vertex_index</tt> property.
</blockquote>
@@ -330,8 +340,8 @@
href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
provided by the <tt>compare</tt> function object.<br>
- <b>Default:</b> <tt>iterator_property_map</tt> created from a
- <tt>std::vector</tt> with the same value type as the
+ <b>Default:</b> <tt>shared_array_property_map</tt>
+ with the same value type as the
<tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
the <tt>i_map</tt> for the index map.
</blockquote>
@@ -356,9 +366,9 @@
for this map must be the same as the value type for the distance
map.<br>
- <b>Default:</b> <tt>iterator_property_map</tt> created from a
- <tt>std::vector</tt> with the same value type as the
- <tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
+ <b>Default:</b> <tt>shared_array_property_map</tt>
+ with the same value type as the
+ <tt>DistanceMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
the <tt>i_map</tt> for the index map.
</blockquote>
@@ -378,10 +388,10 @@
key type of the map, and the value type of the map must be a model
of Color Value.<br>
- <b>Default:</b> <tt>iterator_property_map</tt> created from a
- <tt>std::vector</tt> of value type <tt>default_color_type</tt>, with
- size <tt>num_vertices(g)</tt>, and using the <tt>i_map</tt> for the
- index map.
+ <b>Default:</b> <tt>shared_array_property_map</tt>
+ of value type <tt>default_color_type</tt>, with size
+ <tt>num_vertices(g)</tt>, and using
+ the <tt>i_map</tt> for the index map.
</blockquote>
IN: <tt>distance_compare(CompareFunction cmp)</tt>