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

Subject: [Boost-commit] svn:boost r53349 - in trunk: boost/graph libs/graph/doc
From: jewillco_at_[hidden]
Date: 2009-05-28 13:17:50

Author: jewillco
Date: 2009-05-28 13:17:49 EDT (Thu, 28 May 2009)
New Revision: 53349
URL: http://svn.boost.org/trac/boost/changeset/53349

Log:
Added more changes from Michael Hansen
Text files modified: 
   trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp     |    90 ++++++++++++++++++++--------------------
   trunk/libs/graph/doc/dijkstra_shortest_paths.html              |     4                                         
   trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html |    21 ++++----                                
   3 files changed, 58 insertions(+), 57 deletions(-)

Modified: trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp
==============================================================================
--- trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp	(original)
+++ trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp	2009-05-28 13:17:49 EDT (Thu, 28 May 2009)
@@ -20,46 +20,6 @@
 
 namespace boost {
 
-  // Full init version
-  template <typename Graph, typename DijkstraVisitor,
-            typename PredecessorMap, typename DistanceMap,
-            typename WeightMap, typename VertexIndexMap,
-            typename DistanceCompare, typename DistanceWeightCombine,
-            typename DistanceInfinity, typename DistanceZero>
-  void dijkstra_shortest_paths_no_color_map
-    (const Graph& graph,
-     typename graph_traits<Graph>::vertex_descriptor start_vertex,
-     PredecessorMap predecessor_map,
-     DistanceMap distance_map,
-     WeightMap weight_map,
-     VertexIndexMap index_map,
-     DistanceCompare distance_compare,
-     DistanceWeightCombine distance_weight_combine,
-     DistanceInfinity distance_infinity,
-     DistanceZero distance_zero,
-     DijkstraVisitor visitor)
-  {
-    // Initialize vertices
-    BGL_FORALL_VERTICES_T(current_vertex, graph, Graph) {
-      visitor.initialize_vertex(current_vertex, graph);
-      
-      // Default all distances to infinity
-      put(distance_map, current_vertex, distance_infinity);
-  
-      // Default all vertex predecessors to the vertex itself
-      put(predecessor_map, current_vertex, current_vertex);
-    }
-  
-    // Set distance for start_vertex to zero
-    put(distance_map, start_vertex, distance_zero);
-  
-    // Pass everything on to the no_init version
-    dijkstra_shortest_paths_no_color_map_no_init(graph,
-      start_vertex, predecessor_map, distance_map, weight_map,
-      index_map, distance_compare, distance_weight_combine,
-      distance_infinity, distance_zero, visitor);
-  }
-
   // No init version
   template <typename Graph, typename DijkstraVisitor,
             typename PredecessorMap, typename DistanceMap,
@@ -88,13 +48,13 @@
       distance_indirect_compare(distance_map, distance_compare);
   
     // Choose vertex queue type
-  #if BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
+#if BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
     typedef relaxed_heap<Vertex, DistanceIndirectCompare, VertexIndexMap>
       VertexQueue;
     VertexQueue vertex_queue(num_vertices(graph),
                              distance_indirect_compare,
                              index_map);
-  #else
+#else
     // Default - use d-ary heap (d = 4)
     typedef
       detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t>
@@ -109,7 +69,7 @@
       IndexInHeapMapHelper::build(graph, index_map,
                                   index_in_heap_map_holder);  
     VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare);
-  #endif
+#endif
   
     // Add vertex to the queue
     vertex_queue.push(start_vertex);
@@ -147,7 +107,7 @@
         Distance neighbor_vertex_distance = get(distance_map, neighbor_vertex);
         bool is_neighbor_undiscovered = 
           !distance_compare(neighbor_vertex_distance, distance_infinity);
-  
+
         // Attempt to relax the edge
         bool was_edge_relaxed = relax(current_edge, graph, weight_map,
           predecessor_map, distance_map,
@@ -170,6 +130,46 @@
     } // end while queue not empty
   }
 
+  // Full init version
+  template <typename Graph, typename DijkstraVisitor,
+            typename PredecessorMap, typename DistanceMap,
+            typename WeightMap, typename VertexIndexMap,
+            typename DistanceCompare, typename DistanceWeightCombine,
+            typename DistanceInfinity, typename DistanceZero>
+  void dijkstra_shortest_paths_no_color_map
+    (const Graph& graph,
+     typename graph_traits<Graph>::vertex_descriptor start_vertex,
+     PredecessorMap predecessor_map,
+     DistanceMap distance_map,
+     WeightMap weight_map,
+     VertexIndexMap index_map,
+     DistanceCompare distance_compare,
+     DistanceWeightCombine distance_weight_combine,
+     DistanceInfinity distance_infinity,
+     DistanceZero distance_zero,
+     DijkstraVisitor visitor)
+  {
+    // Initialize vertices
+    BGL_FORALL_VERTICES_T(current_vertex, graph, Graph) {
+      visitor.initialize_vertex(current_vertex, graph);
+      
+      // Default all distances to infinity
+      put(distance_map, current_vertex, distance_infinity);
+  
+      // Default all vertex predecessors to the vertex itself
+      put(predecessor_map, current_vertex, current_vertex);
+    }
+  
+    // Set distance for start_vertex to zero
+    put(distance_map, start_vertex, distance_zero);
+  
+    // Pass everything on to the no_init version
+    dijkstra_shortest_paths_no_color_map_no_init(graph,
+      start_vertex, predecessor_map, distance_map, weight_map,
+      index_map, distance_compare, distance_weight_combine,
+      distance_infinity, distance_zero, visitor);
+  }
+
   namespace detail {
 
     // Handle defaults for PredecessorMap, DistanceCompare,
@@ -233,7 +233,7 @@
   dijkstra_shortest_paths_no_color_map
     (const Graph& graph,
      typename graph_traits<Graph>::vertex_descriptor start_vertex,
-     const bgl_named_params<Param,Tag,Rest>& params)
+     const bgl_named_params<Param, Tag, Rest>& params)
   {
     // Default for edge weight and vertex index map is to ask for them
     // from the graph. Default for the visitor is null_visitor.

Modified: trunk/libs/graph/doc/dijkstra_shortest_paths.html
==============================================================================
--- trunk/libs/graph/doc/dijkstra_shortest_paths.html	(original)
+++ trunk/libs/graph/doc/dijkstra_shortest_paths.html	2009-05-28 13:17:49 EDT (Thu, 28 May 2009)
@@ -19,8 +19,6 @@
 <TT>dijkstra_shortest_paths</TT>
 </H1>
 
-<p>See also dijkstra_shortest_paths_no_color_map
-
 <P>
 <PRE>
 <i>// named parameter version</i>
@@ -431,6 +429,8 @@
 <TT>example/dijkstra-example.cpp</TT></a> for an example of using Dijkstra's
 algorithm.
 
+<H3>See also</H3> dijkstra_shortest_paths_no_color_map for a version of dijkstra's shortest path that does not use a color map.
+
 <H3>Notes</H3>
 
 <a name="1">[1]</a>

Modified: trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
==============================================================================
--- trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html	(original)
+++ trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html	2009-05-28 13:17:49 EDT (Thu, 28 May 2009)
@@ -19,8 +19,6 @@
 <TT>dijkstra_shortest_paths_no_color_map</TT>
 </H1>
 
-<p>See also dijkstra_shortest_paths
-
 <P>
 <PRE>
 <i>// named parameter version</i>
@@ -71,6 +69,10 @@
 </P>
 
 <P>
+	<tt>dijkstra_shortest_paths_no_color_map</tt> differs from the original <tt>dijkstra_shortest_paths</tt> algorithm by not using a color map to identify vertices as discovered or undiscovered.  Instead, this is done with the distance map: a vertex <i>u</i> such that <i>distance_compare(distance_map[u], distance_infinity) == false</i> is considered to be undiscovered.
+</P>
+
+<P>
 There are two main options for obtaining output from the
 <tt>dijkstra_shortest_paths_no_color_map()</tt> function. If you provide a
 distance property map through the <tt>distance_map()</tt> parameter
@@ -82,7 +84,7 @@
 either the source or a vertex unreachable from the source).  In
 addition to these two options, the user can provide their own
 custom-made visitor that takes actions during any of the
-algorithm's event points.</P>
+algorithm's event points [4].</P>
 
 <P>
 Dijkstra's algorithm finds all the shortest paths from the source
@@ -100,12 +102,6 @@
 the top of the priority queue. The algorithm finishes when the
 priority queue is empty.
 </P>
-<P>
-The algorithm uses the distance map to keep
-track of which set each vertex is in. Vertices with a non-infinite distance are in
-<i>S</i>. Vertices with an infinite distance are in <i>V-S</i> and have
-not yet been discovered.
-</P>
 <p>
 The following is the pseudo-code for Dijkstra's single-source shortest
 paths algorithm. <i>w</i> is the edge weight, <i>d</i> is the distance label,
@@ -193,7 +189,7 @@
 IN: <tt>weight_map(WeightMap weight_map)</tt>   
 <blockquote>
   The weight or ``length'' of each edge in the graph. The weights
-  must all be non-negative and non-infinite. The algorithm will throw a
+  must all be non-negative and non-infinite [3]. The algorithm will throw a
   <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> 
   exception is one of the edges is negative.
   The type <tt>WeightMap</tt> must be a model of
@@ -366,6 +362,8 @@
 See <a href="../example/dijkstra-no-color-map-example.cpp">
 <TT>example/dijkstra-no-color-map-example.cpp</TT></a> for an example of using Dijkstra's algorithm.
 
+<H3>See also</H3> dijkstra_shortest_paths for a version of dijkstra's shortest path that uses a color map.
+
 <H3>Notes</H3>
 
 <p>Based on the documentation for dijkstra_shortest_paths.
@@ -385,6 +383,9 @@
   
 <p><a name="3">[3]</a> 
   The algorithm will not work correctly if any of the edge weights are equal to infinity since the infinite distance value is used to determine if a vertex has been discovered.
+  
+<p><a name="4">[4]</a> 
+  Calls to the visitor events occur in the same order as <tt>dijkstra_shortest_paths</tt> (i.e. <i>discover_vertex(u)</i> will always be called after <i>examine_vertex(u)</i> for an undiscovered vertex <i>u</i>).  However, the vertices of the graph given to <i>dijkstra_shortest_paths_no_color_map</i> will <b>not</b> necessarily be visited in the same order as <i>dijkstra_shortest_paths</i>.
 
 <br>
 <HR>