[Boost-commit] svn:boost r81600 - in trunk: boost/graph libs/graph/doc libs/graph/example

Subject: [Boost-commit] svn:boost r81600 - in trunk: boost/graph libs/graph/doc libs/graph/example
From: jewillco_at_[hidden]
Date: 2012-11-27 17:13:48

Author: jewillco
Date: 2012-11-27 17:13:46 EST (Tue, 27 Nov 2012)
New Revision: 81600
URL: http://svn.boost.org/trac/boost/changeset/81600

Log:
Added tree version of astar_search functions
Text files modified: 
   trunk/boost/graph/astar_search.hpp        |   297 +++++++++++++++++++++++++++++++++++++++ 
   trunk/libs/graph/doc/astar_search.html    |    85 ++++++++++-                             
   trunk/libs/graph/example/astar-cities.cpp |     2                                         
   3 files changed, 366 insertions(+), 18 deletions(-)

Modified: trunk/boost/graph/astar_search.hpp
==============================================================================
--- trunk/boost/graph/astar_search.hpp	(original)
+++ trunk/boost/graph/astar_search.hpp	2012-11-27 17:13:46 EST (Tue, 27 Nov 2012)
@@ -22,9 +22,12 @@
 #include <boost/graph/relax.hpp>
 #include <boost/graph/exception.hpp>
 #include <boost/graph/breadth_first_search.hpp>
+#include <boost/graph/iteration_macros.hpp>
 #include <boost/graph/detail/d_ary_heap.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
 #include <boost/property_map/property_map.hpp>
 #include <boost/property_map/vector_property_map.hpp>
+#include <boost/property_map/function_property_map.hpp>
 #include <boost/concept/assert.hpp>
 
 namespace boost {
@@ -159,8 +162,9 @@
       template <class Edge, class Graph>
       void tree_edge(Edge e, const Graph& g) {
         using boost::get;
-        m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
-                            m_combine, m_compare);
+        bool m_decreased =
+          relax(e, g, m_weight, m_predecessor, m_distance,
+                m_combine, m_compare);
 
         if(m_decreased) {
           m_vis.edge_relaxed(e, g);
@@ -175,8 +179,9 @@
       template <class Edge, class Graph>
       void gray_target(Edge e, const Graph& g) {
         using boost::get;
-        m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
-                            m_combine, m_compare);
+        bool m_decreased =
+          relax(e, g, m_weight, m_predecessor, m_distance,
+                m_combine, m_compare);
 
         if(m_decreased) {
           put(m_cost, target(e, g),
@@ -192,8 +197,9 @@
       template <class Edge, class Graph>
       void black_target(Edge e, const Graph& g) {
         using boost::get;
-        m_decreased = relax(e, g, m_weight, m_predecessor, m_distance,
-                            m_combine, m_compare);
+        bool m_decreased =
+          relax(e, g, m_weight, m_predecessor, m_distance,
+                m_combine, m_compare);
 
         if(m_decreased) {
           m_vis.edge_relaxed(e, g);
@@ -219,11 +225,112 @@
       ColorMap m_color;
       BinaryFunction m_combine;
       BinaryPredicate m_compare;
-      bool m_decreased;
       C m_zero;
 
     };
 
+    template <class AStarHeuristic, class UniformCostVisitor,
+              class UpdatableQueue, class PredecessorMap,
+              class CostMap, class DistanceMap, class WeightMap,
+              class BinaryFunction,
+              class BinaryPredicate>
+    struct astar_tree_bfs_visitor
+    {
+
+      typedef typename property_traits<CostMap>::value_type C;
+      typedef typename property_traits<DistanceMap>::value_type distance_type;
+
+      astar_tree_bfs_visitor(AStarHeuristic h, UniformCostVisitor vis,
+                             UpdatableQueue& Q, PredecessorMap p,
+                             CostMap c, DistanceMap d, WeightMap w,
+                             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_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) {
+        using boost::get;
+        bool 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) {
+        abort(); // Should not get here in tree case
+      }
+
+
+      template <class Edge, class Graph>
+      void black_target(Edge e, const Graph& g) {
+        abort(); // Should not get here in tree case
+      }
+
+
+
+      AStarHeuristic m_h;
+      UniformCostVisitor m_vis;
+      UpdatableQueue& m_Q;
+      PredecessorMap m_predecessor;
+      CostMap m_cost;
+      DistanceMap m_distance;
+      WeightMap m_weight;
+      BinaryFunction m_combine;
+      BinaryPredicate m_compare;
+      C m_zero;
+
+    };
+
+    template <typename UnderlyingQ, typename CostMap>
+    struct astar_search_tree_queue_wrapper: public UnderlyingQ {
+      astar_search_tree_queue_wrapper(const UnderlyingQ& uq, CostMap cost): UnderlyingQ(uq), m_cost(cost) {}
+
+      typedef typename boost::property_traits<CostMap>::key_type key_type;
+      void push(const key_type& k) {UnderlyingQ::push(std::make_pair(k, get(m_cost, k)));}
+      key_type top() const {return UnderlyingQ::top().first;}
+
+      private:
+      CostMap m_cost;
+    };
+
   } // namespace detail
 
 
@@ -263,6 +370,77 @@
     breadth_first_visit(g, s, Q, bfs_vis, color);
   }
 
+  namespace graph_detail {
+    template <typename A, typename B>
+    struct select1st {
+      typedef std::pair<A, B> argument_type;
+      typedef A result_type;
+      A operator()(const std::pair<A, B>& p) const {return p.first;}
+    };
+  }
+
+  template <typename VertexListGraph, typename AStarHeuristic,
+            typename AStarVisitor, typename PredecessorMap,
+            typename CostMap, typename DistanceMap,
+            typename WeightMap,
+            typename CompareFunction, typename CombineFunction,
+            typename CostInf, typename CostZero>
+  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 /*inf*/, CostZero zero)
+  {
+    typedef typename graph_traits<VertexListGraph>::vertex_descriptor
+      Vertex;
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    typedef d_ary_heap_indirect<
+              std::pair<Distance, Vertex>,
+              4,
+              null_property_map<std::pair<Distance, Vertex>, std::size_t>,
+              function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
+              CompareFunction>
+      MutableQueue;
+    MutableQueue Q(
+      make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()),
+      null_property_map<std::pair<Distance, Vertex>, std::size_t>(),
+      compare);
+
+    vis.discover_vertex(s, g);
+    Q.push(std::make_pair(get(cost, s), s));
+    while (!Q.empty()) {
+      Vertex v;
+      Distance v_rank;
+      boost::tie(v_rank, v) = Q.top();
+      Q.pop();
+      vis.examine_vertex(v, g);
+      BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) {
+        Vertex w = target(e, g);
+        vis.examine_edge(e, g);
+        Distance e_weight = get(weight, e);
+        if (compare(e_weight, zero))
+          BOOST_THROW_EXCEPTION(negative_edge());
+        bool decreased =
+          relax(e, g, weight, predecessor, distance,
+                combine, compare);
+        Distance w_d = combine(get(distance, v), e_weight);
+        if (decreased) {
+          vis.edge_relaxed(e, g);
+          Distance w_rank = combine(get(distance, w), h(w));
+          put(cost, w, w_rank);
+          vis.discover_vertex(w, g);
+          Q.push(std::make_pair(w_rank, w));
+        } else {
+          vis.edge_not_relaxed(e, g);
+        }
+      }
+      vis.finish_vertex(v, g);
+    }
+  }
 
   // Non-named parameter interface
   template <typename VertexListGraph, typename AStarHeuristic,
@@ -303,6 +481,40 @@
 
   }
 
+  // Non-named parameter interface
+  template <typename VertexListGraph, typename AStarHeuristic,
+            typename AStarVisitor, typename PredecessorMap,
+            typename CostMap, typename DistanceMap,
+            typename WeightMap,
+            typename CompareFunction, typename CombineFunction,
+            typename CostInf, typename CostZero>
+  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)
+  {
+
+    typename graph_traits<VertexListGraph>::vertex_iterator ui, ui_end;
+    for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
+      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_tree
+      (g, s, h, vis, predecessor, cost, distance, weight,
+       compare, combine, inf, zero);
+
+  }
+
   // Named parameter interfaces
   template <typename VertexListGraph,
             typename AStarHeuristic,
@@ -345,6 +557,46 @@
        arg_pack[_distance_zero | D()]);
   }
 
+  // Named parameter interfaces
+  template <typename VertexListGraph,
+            typename AStarHeuristic,
+            typename P, typename T, typename R>
+  void
+  astar_search_tree
+    (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;
+    const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+
+    astar_search_tree
+      (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),
+       arg_pack[_distance_compare | std::less<D>()],
+       arg_pack[_distance_combine | closed_plus<D>(inf)],
+       inf,
+       arg_pack[_distance_zero | D()]);
+  }
+
   template <typename VertexListGraph,
             typename AStarHeuristic,
             typename P, typename T, typename R>
@@ -378,6 +630,37 @@
        arg_pack[_distance_zero | D()]);
   }
 
+  template <typename VertexListGraph,
+            typename AStarHeuristic,
+            typename P, typename T, typename R>
+  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)
+  {
+    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;
+    const D inf = arg_pack[_distance_inf | (std::numeric_limits<D>::max)()];
+    astar_search_no_init_tree
+      (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),
+       arg_pack[_distance_compare | std::less<D>()],
+       arg_pack[_distance_combine | closed_plus<D>(inf)],
+       inf,
+       arg_pack[_distance_zero | D()]);
+  }
+
 } // namespace boost
 
 #endif // BOOST_GRAPH_ASTAR_SEARCH_HPP

Modified: trunk/libs/graph/doc/astar_search.html
==============================================================================
--- trunk/libs/graph/doc/astar_search.html	(original)
+++ trunk/libs/graph/doc/astar_search.html	2012-11-27 17:13:46 EST (Tue, 27 Nov 2012)
@@ -41,6 +41,24 @@
    typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
    <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
 
+template &lt;typename VertexListGraph,
+          typename AStarHeuristic,
+          typename P, typename T, typename R&gt;
+void
+astar_search_tree
+  (const VertexListGraph &amp;g,
+   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
+   AStarHeuristic h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
+
+template &lt;typename VertexListGraph,
+          typename AStarHeuristic,
+          typename P, typename T, typename R&gt;
+void
+astar_search_no_init_tree
+  (const VertexListGraph &amp;g,
+   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
+   AStarHeuristic h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
+
 <i>// Non-named parameter interface</i>
 template &lt;typename VertexListGraph, typename AStarHeuristic,
           typename AStarVisitor, typename PredecessorMap,
@@ -60,7 +78,23 @@
    CompareFunction compare, CombineFunction combine,
    CostInf inf, CostZero zero);
 
-<i>// Version that does not initialize property maps (used for implicit graphs)</i>
+template &lt;typename VertexListGraph, typename AStarHeuristic,
+          typename AStarVisitor, typename PredecessorMap,
+          typename CostMap, typename DistanceMap,
+          typename WeightMap,
+          typename CompareFunction, typename CombineFunction,
+          typename CostInf, typename CostZero&gt;
+inline void
+astar_search_tree
+  (const VertexListGraph &amp;g,
+   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
+   AStarHeuristic h, AStarVisitor vis,
+   PredecessorMap predecessor, CostMap cost,
+   DistanceMap distance, WeightMap weight,
+   CompareFunction compare, CombineFunction combine,
+   CostInf inf, CostZero zero);
+
+<i>// Versions that do not initialize property maps (used for implicit graphs)</i>
 template &lt;typename IncidenceGraph, typename AStarHeuristic,
           typename AStarVisitor, typename PredecessorMap,
           typename CostMap, typename DistanceMap,
@@ -82,6 +116,22 @@
 <b>Note that the index_map and color parameters are swapped in
 astar_search_no_init() relative to astar_search(); the named parameter
 interfaces are not affected.</b>
+
+template &lt;typename IncidenceGraph, typename AStarHeuristic,
+          typename AStarVisitor, typename PredecessorMap,
+          typename CostMap, typename DistanceMap,
+          typename WeightMap,
+          typename CompareFunction, typename CombineFunction,
+          typename CostInf, typename CostZero&gt;
+inline void
+astar_search_no_init_tree
+  (const IncidenceGraph &amp;g,
+   typename graph_traits&lt;IncidenceGraph&gt;::vertex_descriptor s,
+   AStarHeuristic h, AStarVisitor vis,
+   PredecessorMap predecessor, CostMap cost,
+   DistanceMap distance, WeightMap weight,
+   CompareFunction compare, CombineFunction combine,
+   CostInf inf, CostZero zero);
 </PRE>
 
 <P>
@@ -125,7 +175,8 @@
 the entire graph.  Implicit searches can be performed with this
 implementation of A* by creating special visitors that generate
 neighbors of newly-expanded vertices.  Please note that
-<tt>astar_search_no_init()</tt> must be used for implicit graphs; the basic
+<tt>astar_search_no_init()</tt> or <tt>astar_search_no_init_tree()</tt> must be
+used for implicit graphs; the basic
 <tt>astar_search()</tt> function requires a graph that models
 the Vertex List Graph concept.  Both
 versions
@@ -134,8 +185,9 @@
 </P>
 
 <P>
-This implementation of A* is based on an OPEN/CLOSED list formulation
-of the algorithm.  Vertices on the OPEN list have been ``discovered''
+For the non-tree versions of the algorithm,
+this implementation of A* is based on an OPEN/CLOSED list formulation.
+Vertices on the OPEN list have been ``discovered''
 by the algorithm, but not ``expanded'' (we have not discovered their
 adjacent vertices).  Vertices on the CLOSED list have been completely
 examined by our search (we have expanded them and added their children
@@ -146,7 +198,11 @@
 trapped by loops in the graph.  The OPEN/CLOSED lists are implemented
 using BGL's vertex coloring mechanisms.  Vertices in OPEN are colored
 gray, vertices in CLOSED are colored black, and undiscovered vertices
-are colored white.
+are colored white.  For the versions of the algorithm whose names end in
+<tt>_tree</tt>, all vertices are assumed to always be white, leading to
+checking for repeated vertices being done using the distance map.  If a dummy
+value is used for the distance map and the graph contains cycles, the algorithm
+will probably enter an infinite loop.
 </P>
 
 <P>
@@ -292,7 +348,8 @@
 IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
 <blockquote>
   This maps each vertex to an integer in the range <tt>[0,
-  num_vertices(g))</tt>.  This is necessary for efficient updates of
+  num_vertices(g))</tt>.  This is necessary in non-tree versions of the
+  algorithm for efficient updates of
   the heap data structure when an edge is relaxed.  The type
   <tt>VertexIndexMap</tt> must be a model of <a
   href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable
@@ -338,7 +395,10 @@
   <tt>combine</tt> function object and the zero object for the
   identity element.  Also the distance value type must have a <a
   href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
-  provided by the <tt>compare</tt> function object.<br>
+  provided by the <tt>compare</tt> function object.  A
+  <tt>constant_writable_property_map</tt> returning the infinity value can be
+  used for this parameter in tree versions of the algorithm when the graph does
+  not contain a directed cycle.<br>
 
   <b>Default:</b> <tt>shared_array_property_map</tt>
   with the same value type as the
@@ -355,7 +415,10 @@
   <tt>h</tt>) from the vertex to a goal.  The type <tt>CostMap</tt>
   must be a model of <a
   href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
-  Property Map</tt></a>.  The vertex descriptor type of the graph
+  Property Map</tt></a> in non-tree versions of the algorithm, and <a
+  href="../../property_map/doc/WritablePropertyMap.html"><tt>Writable Property
+  Map</tt></a> in tree versions of the algorithm.  The vertex descriptor type
+  of the graph
   needs to be usable as the key type of the distance map.  The value
   type of the distance map is the element type of a <a
   href="./Monoid.html"><tt>Monoid</tt></a> formed with the
@@ -364,7 +427,8 @@
   href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
   provided by the <tt>compare</tt> function object.  The value type
   for this map must be the same as the value type for the distance
-  map.<br>
+  map.  In tree versions of the algorithm, <tt>null_property_map</tt> can be
+  used for this parameter.<br>
 
   <b>Default:</b> <tt>shared_array_property_map</tt>
   with the same value type as the
@@ -375,7 +439,8 @@
 UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
 <blockquote>
 
-  This is used during the execution of the algorithm to mark the
+  This is used during the execution of non-tree versions of the algorithm to
+  mark the
   vertices, indicating whether they are on the OPEN or CLOSED lists.
   The vertices start out white and become gray when they are inserted
   into the OPEN list.  They then turn black when they are examined and

Modified: trunk/libs/graph/example/astar-cities.cpp
==============================================================================
--- trunk/libs/graph/example/astar-cities.cpp	(original)
+++ trunk/libs/graph/example/astar-cities.cpp	2012-11-27 17:13:46 EST (Tue, 27 Nov 2012)
@@ -192,7 +192,7 @@
   vector<cost> d(num_vertices(g));
   try {
     // call astar named parameter interface
-    astar_search
+    astar_search_tree
       (g, start,
        distance_heuristic<mygraph_t, cost, location*>
         (locations, goal),