[Boost-commit] svn:boost r50812 - in trunk: boost/graph libs/graph/test

Subject: [Boost-commit] svn:boost r50812 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-01-27 14:59:40

Author: jewillco
Date: 2009-01-27 14:59:40 EST (Tue, 27 Jan 2009)
New Revision: 50812
URL: http://svn.boost.org/trac/boost/changeset/50812

Log:
Changed Dijkstra shortest path algorithm to use d-ary heap by default, and to use a vector_property_map when the graph does not model VertexListGraph (only supported for dijkstra_shortest_paths_no_init); fixes #708
Text files modified: 
   trunk/boost/graph/dijkstra_shortest_paths.hpp       |    76 ++++++++++++++++++++++++++++++++------- 
   trunk/libs/graph/test/dijkstra_heap_performance.cpp |     9 ++--                                    
   2 files changed, 66 insertions(+), 19 deletions(-)

Modified: trunk/boost/graph/dijkstra_shortest_paths.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths.hpp	(original)
+++ trunk/boost/graph/dijkstra_shortest_paths.hpp	2009-01-27 14:59:40 EST (Tue, 27 Jan 2009)
@@ -19,6 +19,9 @@
 #include <boost/pending/relaxed_heap.hpp>
 #include <boost/smart_ptr.hpp>
 #include <boost/graph/detail/d_ary_heap.hpp>
+#include <boost/property_map.hpp>
+#include <boost/vector_property_map.hpp>
+#include <boost/type_traits.hpp>
 
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
 #  include <boost/pending/mutable_queue.hpp>
@@ -27,6 +30,8 @@
 namespace boost {
 
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
+  // This is a misnomer now: it now just refers to the "default heap", which is
+  // currently d-ary (d=4) but can be changed by a #define.
   static bool dijkstra_relaxed_heap = true;
 #endif
 
@@ -141,6 +146,42 @@
 
   } // namespace detail
 
+  namespace detail {
+    template <class Graph, class IndexMap, class Value, bool KnownNumVertices>
+    struct vertex_property_map_generator_helper {};
+
+    template <class Graph, class IndexMap, class Value>
+    struct vertex_property_map_generator_helper<Graph, IndexMap, Value, true> {
+      typedef boost::iterator_property_map<Value*, IndexMap> type;
+      static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
+        array_holder.reset(new Value[num_vertices(g)]);
+        std::fill(array_holder.get(), array_holder.get() + num_vertices(g), Value());
+        return make_iterator_property_map(array_holder.get(), index);
+      }
+    };
+
+    template <class Graph, class IndexMap, class Value>
+    struct vertex_property_map_generator_helper<Graph, IndexMap, Value, false> {
+      typedef boost::vector_property_map<Value, IndexMap> type;
+      static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
+        return make_vector_property_map(index);
+      }
+    };
+
+    template <class Graph, class IndexMap, class Value>
+    struct vertex_property_map_generator {
+      typedef boost::is_base_and_derived<
+                boost::vertex_list_graph_tag,
+                typename boost::graph_traits<Graph>::traversal_category>
+              known_num_vertices;
+      typedef vertex_property_map_generator_helper<Graph, IndexMap, Value, known_num_vertices::value> helper;
+      typedef typename helper::type type;
+      static type build(const Graph& g, const IndexMap& index, boost::scoped_array<Value>& array_holder) {
+        return helper::build(g, index, array_holder);
+      }
+    };
+  }
+
   // Call breadth first search with default color map.
   template <class VertexListGraph, class DijkstraVisitor,
             class PredecessorMap, class DistanceMap,
@@ -155,11 +196,16 @@
      Compare compare, Combine combine, DistZero zero,
      DijkstraVisitor vis)
   {
-    std::vector<default_color_type> color(num_vertices(g));
-    default_color_type c = white_color;
+    boost::scoped_array<default_color_type> color_map_holder;
+    typedef
+      detail::vertex_property_map_generator<VertexListGraph, IndexMap, default_color_type>
+      ColorMapHelper;
+    typedef typename ColorMapHelper::type ColorMap;
+    ColorMap color =
+      ColorMapHelper::build(g, index_map, white_color, color_map_holder);
     dijkstra_shortest_paths_no_init( g, s, predecessor, distance, weight,
       index_map, compare, combine, zero, vis,
-        make_iterator_property_map(&color[0], index_map, c));
+        color);
   }
 
   // Call breadth first search
@@ -183,20 +229,10 @@
 
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING
     if (!dijkstra_relaxed_heap) {
-#ifdef BOOST_GRAPH_TEST_D_ARY_HEAP
-      boost::scoped_array<std::size_t> index_in_heap_map(new std::size_t[num_vertices(g)]);
-      typedef boost::iterator_property_map<std::size_t*, IndexMap> IndexInHeapMap;
-      IndexInHeapMap index_in_heap(&index_in_heap_map[0], index_map);
-      typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
-        MutableQueue;
-      MutableQueue Q(distance, index_in_heap, compare);
-#else
       typedef mutable_queue<Vertex, std::vector<Vertex>, IndirectCmp, IndexMap>
         MutableQueue;
 
       MutableQueue Q(num_vertices(g), icmp, index_map);
-#endif
-
       detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
         PredecessorMap, DistanceMap, Combine, Compare>
       bfs_vis(vis, Q, weight, predecessor, distance, combine, compare, zero);
@@ -206,9 +242,21 @@
     }
 #endif // BOOST_GRAPH_DIJKSTRA_TESTING
 
+#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
     typedef relaxed_heap<Vertex, IndirectCmp, IndexMap> MutableQueue;
-
     MutableQueue Q(num_vertices(g), icmp, index_map);
+#else // Now the default: use a d-ary heap
+      boost::scoped_array<std::size_t> index_in_heap_map_holder;
+      typedef
+        detail::vertex_property_map_generator<VertexListGraph, IndexMap, std::size_t>
+        IndexInHeapMapHelper;
+      typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
+      IndexInHeapMap index_in_heap =
+        IndexInHeapMapHelper::build(g, index_map, index_in_heap_map_holder);
+      typedef d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, Compare>
+        MutableQueue;
+      MutableQueue Q(distance, index_in_heap, compare);
+#endif
 
     detail::dijkstra_bfs_visitor<DijkstraVisitor, MutableQueue, WeightMap,
       PredecessorMap, DistanceMap, Combine, Compare>

Modified: trunk/libs/graph/test/dijkstra_heap_performance.cpp
==============================================================================
--- trunk/libs/graph/test/dijkstra_heap_performance.cpp	(original)
+++ trunk/libs/graph/test/dijkstra_heap_performance.cpp	2009-01-27 14:59:40 EST (Tue, 27 Jan 2009)
@@ -8,7 +8,6 @@
 //           Andrew Lumsdaine
 #ifndef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
 #  define BOOST_GRAPH_DIJKSTRA_TESTING
-#  define BOOST_GRAPH_TEST_D_ARY_HEAP
 #endif
 
 #include <boost/graph/dijkstra_shortest_paths.hpp>
@@ -107,11 +106,7 @@
   std::vector<double> relaxed_heap_distances(n);
 
   // Run binary or d-ary heap version
-#ifdef BOOST_GRAPH_TEST_D_ARY_HEAP
-  std::cout << "Running Dijkstra's with d-ary heap...";
-#else
   std::cout << "Running Dijkstra's with binary heap...";
-#endif
   std::cout.flush();
   timer t;
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR
@@ -125,7 +120,11 @@
   std::cout << binary_heap_time << " seconds.\n";
 
   // Run relaxed heap version
+#ifdef BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
   std::cout << "Running Dijkstra's with relaxed heap...";
+#else
+  std::cout << "Running Dijkstra's with d-ary heap (d=4)...";
+#endif
   std::cout.flush();
   t.restart();
 #ifdef BOOST_GRAPH_DIJKSTRA_TESTING_DIETMAR