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

Subject: [Boost-commit] svn:boost r53327 - in trunk: boost/graph libs/graph/doc libs/graph/example libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-05-27 16:54:26

Author: jewillco
Date: 2009-05-27 16:54:24 EDT (Wed, 27 May 2009)
New Revision: 53327
URL: http://svn.boost.org/trac/boost/changeset/53327

Log:
Added more updates, docs, and tests from Michael Hansen
Added:
   trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html   (contents, props changed)
   trunk/libs/graph/example/dijkstra-no-color-map-example.cpp   (contents, props changed)
   trunk/libs/graph/test/dijkstra_no_color_map_compare.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/dijkstra_shortest_paths_no_color_map.hpp |   329 ++++++++++++++++++++++++++------------- 
   trunk/libs/graph/doc/dijkstra_shortest_paths.html          |     1                                         
   trunk/libs/graph/doc/table_of_contents.html                |     1                                         
   trunk/libs/graph/test/Jamfile.v2                           |     1                                         
   4 files changed, 219 insertions(+), 113 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-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -20,127 +20,230 @@
 
 namespace boost {
 
-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 vertex_index_map,
-   DistanceCompare distance_compare,
-   DistanceWeightCombine distance_weight_combine,
-   DistanceInfinity distance_infinity,
-   DistanceZero distance_zero,
-   DijkstraVisitor visitor)
-{
-  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
-  typedef typename property_traits<DistanceMap>::value_type Distance;
-  typedef typename property_traits<WeightMap>::value_type Weight;
-  
-  typedef indirect_cmp<DistanceMap, DistanceCompare> DistanceIndirectCompare;
-  DistanceIndirectCompare
-    distance_indirect_compare(distance_map, distance_compare);
-
-  // Choose vertex queue type
-#if BOOST_GRAPH_DIJKSTRA_USE_RELAXED_HEAP
-  typedef relaxed_heap<Vertex, DistanceIndirectCompare, VertexIndexMap>
-    VertexQueue;
-  VertexQueue vertex_queue(num_vertices(graph),
-                           distance_indirect_compare,
-                           vertex_index_map);
-#else
-  // Default - use d-ary heap (d = 4)
-  typedef
-    detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t>
-    IndexInHeapMapHelper;
-  typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
-  typedef
-    d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, DistanceCompare>
-    VertexQueue;
-
-  boost::scoped_array<std::size_t> index_in_heap_map_holder;
-  IndexInHeapMap index_in_heap =
-    IndexInHeapMapHelper::build(graph, vertex_index_map,
-                                index_in_heap_map_holder);  
-  VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare);
-#endif
-
-  // 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);
+  // 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);
   }
 
-  // Set distance for start_vertex to zero
-  put(distance_map, start_vertex, distance_zero);
-
-  // Add vertex to the queue
-  vertex_queue.push(start_vertex);
-
-  // Starting vertex will always be the first discovered vertex
-  visitor.discover_vertex(start_vertex, graph);
-
-  while (!vertex_queue.empty()) {
-    Vertex min_vertex = vertex_queue.top();
-    vertex_queue.pop();
-    
-    visitor.examine_vertex(min_vertex, graph);
-
-    // Check if any other vertices can be reached
-    Distance min_vertex_distance = get(distance_map, min_vertex);
+  // No 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_no_init
+    (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)
+  {
+    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef typename property_traits<DistanceMap>::value_type Distance;
+    typedef typename property_traits<WeightMap>::value_type Weight;
     
-    if (!distance_compare(min_vertex_distance, distance_infinity)) {
-      // This is the minimum vertex, so all other vertices are unreachable
-      return;
-    }
-
-    // Examine neighbors of min_vertex
-    typedef typename graph_traits<Graph>::edge_descriptor Edge;
-    typename graph_traits<Graph>::out_edge_iterator edge_iter, edge_iter_end;
-    BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) {
-      visitor.examine_edge(current_edge, graph);
+    typedef indirect_cmp<DistanceMap, DistanceCompare> DistanceIndirectCompare;
+    DistanceIndirectCompare
+      distance_indirect_compare(distance_map, distance_compare);
+  
+    // Choose vertex queue type
+  #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
+    // Default - use d-ary heap (d = 4)
+    typedef
+      detail::vertex_property_map_generator<Graph, VertexIndexMap, std::size_t>
+      IndexInHeapMapHelper;
+    typedef typename IndexInHeapMapHelper::type IndexInHeapMap;
+    typedef
+      d_ary_heap_indirect<Vertex, 4, IndexInHeapMap, DistanceMap, DistanceCompare>
+      VertexQueue;
+  
+    boost::scoped_array<std::size_t> index_in_heap_map_holder;
+    IndexInHeapMap index_in_heap =
+      IndexInHeapMapHelper::build(graph, index_map,
+                                  index_in_heap_map_holder);  
+    VertexQueue vertex_queue(distance_map, index_in_heap, distance_compare);
+  #endif
+  
+    // Add vertex to the queue
+    vertex_queue.push(start_vertex);
+  
+    // Starting vertex will always be the first discovered vertex
+    visitor.discover_vertex(start_vertex, graph);
+  
+    while (!vertex_queue.empty()) {
+      Vertex min_vertex = vertex_queue.top();
+      vertex_queue.pop();
       
-      // Check if the edge has a negative weight
-      if (distance_compare(get(weight_map, current_edge), distance_zero)) {
-        boost::throw_exception(negative_edge());
-      }
+      visitor.examine_vertex(min_vertex, graph);
+  
+      // Check if any other vertices can be reached
+      Distance min_vertex_distance = get(distance_map, min_vertex);
       
-      Vertex neighbor_vertex = target(current_edge, graph);
-      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,
-        distance_weight_combine, distance_compare);
-
-      if (was_edge_relaxed) {
-        vertex_queue.update(neighbor_vertex);
-        visitor.edge_relaxed(current_edge, graph);
-      } else {
-        visitor.edge_not_relaxed(current_edge, graph);
+      if (!distance_compare(min_vertex_distance, distance_infinity)) {
+        // This is the minimum vertex, so all other vertices are unreachable
+        return;
       }
+  
+      // Examine neighbors of min_vertex
+      typedef typename graph_traits<Graph>::edge_descriptor Edge;
+      typename graph_traits<Graph>::out_edge_iterator edge_iter, edge_iter_end;
+      BGL_FORALL_OUTEDGES_T(min_vertex, current_edge, graph, Graph) {
+        visitor.examine_edge(current_edge, graph);
+        
+        // Check if the edge has a negative weight
+        if (distance_compare(get(weight_map, current_edge), distance_zero)) {
+          boost::throw_exception(negative_edge());
+        }
+  
+        // Extract the neighboring vertex and get its distance
+        Vertex neighbor_vertex = target(current_edge, graph);
+        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,
+          distance_weight_combine, distance_compare);
+  
+        if (was_edge_relaxed) {
+          vertex_queue.update(neighbor_vertex);
+          visitor.edge_relaxed(current_edge, graph);
+        } else {
+          visitor.edge_not_relaxed(current_edge, graph);
+        }
+  
+        if (is_neighbor_undiscovered) {
+          visitor.discover_vertex(neighbor_vertex, graph);
+          vertex_queue.push(neighbor_vertex);
+        }
+      } // end out edge iteration
+  
+      visitor.finish_vertex(min_vertex, graph);
+    } // end while queue not empty
+  }
 
-      if (is_neighbor_undiscovered) {
-        visitor.discover_vertex(neighbor_vertex, graph);
-        vertex_queue.push(neighbor_vertex);
-      }
-    } // end out edge iteration
+  namespace detail {
+
+    // Handle defaults for PredecessorMap, DistanceCompare,
+    // DistanceWeightCombine, DistanceInfinity and DistanceZero
+    template <typename Graph, typename DistanceMap, typename WeightMap,
+              typename VertexIndexMap, typename Params>
+    inline void
+    dijkstra_no_color_map_dispatch2
+      (const Graph& graph,
+       typename graph_traits<Graph>::vertex_descriptor start_vertex,
+       DistanceMap distance_map, WeightMap weight_map,
+       VertexIndexMap index_map, const Params& params)
+    {
+      // Default for predecessor map
+      dummy_property_map predecessor_map;
+
+      typedef typename property_traits<DistanceMap>::value_type DistanceType;
+      dijkstra_shortest_paths_no_color_map
+        (graph, start_vertex,
+         choose_param(get_param(params, vertex_predecessor), predecessor_map),
+         distance_map, weight_map, index_map,
+         choose_param(get_param(params, distance_compare_t()),
+                      std::less<DistanceType>()),
+         choose_param(get_param(params, distance_combine_t()),
+                      closed_plus<DistanceType>()),
+         choose_param(get_param(params, distance_inf_t()),
+                      (std::numeric_limits<DistanceType>::max)()),
+         choose_param(get_param(params, distance_zero_t()),
+                      DistanceType()),
+         choose_param(get_param(params, graph_visitor),
+                      make_dijkstra_visitor(null_visitor())));
+    }
+
+    template <typename Graph, typename DistanceMap, typename WeightMap,
+              typename IndexMap, typename Params>
+    inline void
+    dijkstra_no_color_map_dispatch1
+      (const Graph& graph,
+       typename graph_traits<Graph>::vertex_descriptor start_vertex,
+       DistanceMap distance_map, WeightMap weight_map,
+       IndexMap index_map, const Params& params)
+    {
+      // Default for distance map
+      typedef typename property_traits<WeightMap>::value_type DistanceType;
+      typename std::vector<DistanceType>::size_type
+        vertex_count = is_default_param(distance_map) ? num_vertices(graph) : 1;
+        
+      std::vector<DistanceType> default_distance_map(vertex_count);
+
+      detail::dijkstra_no_color_map_dispatch2
+        (graph, start_vertex, choose_param(distance_map,
+         make_iterator_property_map(default_distance_map.begin(), index_map,
+                                    default_distance_map[0])),
+         weight_map, index_map, params);
+    }
+  } // namespace detail
 
-    visitor.finish_vertex(min_vertex, graph);
-  } // end while queue not empty
-}
+  // Named parameter version
+  template <typename Graph, typename Param, typename Tag, typename Rest>
+  inline void
+  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)
+  {
+    // Default for edge weight and vertex index map is to ask for them
+    // from the graph. Default for the visitor is null_visitor.
+    detail::dijkstra_no_color_map_dispatch1
+      (graph, start_vertex,
+       get_param(params, vertex_distance),
+       choose_const_pmap(get_param(params, edge_weight), graph, edge_weight),
+       choose_const_pmap(get_param(params, vertex_index), graph, vertex_index),
+       params);
+  }
 
 } // namespace boost
 

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-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -19,6 +19,7 @@
 <TT>dijkstra_shortest_paths</TT>
 </H1>
 
+<p>See also dijkstra_shortest_paths_no_color_map
 
 <P>
 <PRE>

Added: trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html	2009-05-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -0,0 +1,397 @@
+<HTML>
+<!--
+     Copyright (c) Michael Hansen 2009
+    
+     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)
+  -->
+<Head>
+<Title>Boost Graph Library: Dijkstra's Shortest Paths (No Color Map)</Title>
+<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
+        ALINK="#ff0000"> 
+<IMG SRC="../../../boost.png" 
+     ALT="C++ Boost" width="277" height="86"> 
+
+<BR Clear>
+
+<H1><A NAME="sec:dijkstra"></A>
+<TT>dijkstra_shortest_paths_no_color_map</TT>
+</H1>
+
+<p>See also dijkstra_shortest_paths
+
+<P>
+<PRE>
+<i>// named parameter version</i>
+template &lt;typename Graph, typename Param, typename Tag, typename Rest&gt;
+void dijkstra_shortest_paths_no_color_map
+  (const Graph&amp; graph,
+   typename graph_traits&lt;Graph&gt;::vertex_descriptor start_vertex,
+   const bgl_named_params<Param,Tag,Rest>& params);
+   
+<i>// non-named parameter version</i>
+template &lt;typename Graph, typename DijkstraVisitor, 
+	  typename PredecessorMap, typename DistanceMap,
+	  typename WeightMap, typename VertexIndexMap, typename DistanceCompare, typename DistanceWeightCombine, 
+	  typename DistanceInfinity, typename DistanceZero&gt;
+void dijkstra_shortest_paths_no_color_map
+  (const Graph&amp; graph,
+   typename graph_traits&lt;Graph&gt;::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);
+
+<i>// version that does not initialize the property maps</i>
+template &lt;typename Graph, typename DijkstraVisitor, 
+	  typename PredecessorMap, typename DistanceMap,
+	  typename WeightMap, typename VertexIndexMap, typename DistanceCompare, typename DistanceWeightCombine, 
+	  typename DistanceInfinity, typename DistanceZero&gt;
+void dijkstra_shortest_paths_no_color_map_no_init
+  (const Graph&amp; graph,
+   typename graph_traits&lt;Graph&gt;::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);
+</PRE>
+
+<P>
+This algorithm&nbsp;[10,<A
+HREF="bibliography.html#clr90">8</A>] solves the single-source
+shortest-paths problem on a weighted, directed or undirected graph for
+the case where all edge weights are nonnegative.  Use the Bellman-Ford
+algorithm for the case when some edge weights are negative.  Use
+breadth-first search instead of Dijkstra's algorithm when all edge
+weights are equal to one.  For the definition of the shortest-path
+problem see Section <A
+HREF="graph_theory_review.html#sec:shortest-paths-algorithms">Shortest-Paths
+Algorithms</A> for some background to the shortest-path problem.
+</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
+then the shortest distance from the start vertex to every other
+vertex in the graph will be recorded in the distance map. Also you can
+record the shortest paths tree in a predecessor map: for each vertex
+<i>u in V</i>, <i>p[u]</i> will be the predecessor of <i>u</i> in
+the shortest paths tree (unless <i>p[u] = u</i>, in which case <i>u</i> is
+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>
+
+<P>
+Dijkstra's algorithm finds all the shortest paths from the source
+vertex to every other vertex by iteratively &quot;growing&quot; the set of
+vertices <i>S</i> to which it knows the shortest path. At each step of
+the algorithm, the next vertex added to <i>S</i> is determined by a
+priority queue.  The queue contains the vertices in <i>V - S</i><a
+href="#1">[1]</a> prioritized by their distance label, which is the
+length of the shortest path seen so far for each vertex. The vertex
+<i>u</i> at the top of the priority queue is then added to <i>S</i>,
+and each of its out-edges is relaxed: if the distance to <i>u</i> plus
+the weight of the out-edge <i>(u,v)</i> is less than the distance
+label for <i>v</i> then the estimated distance for vertex <i>v</i> is
+reduced.  The algorithm then loops back, processing the next vertex at
+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,
+and <i>p</i> is the predecessor of each vertex which is used to encode
+the shortest paths tree. <i>Q</i> is a priority queue that supports the
+DECREASE-KEY operation.  The visitor event points for the algorithm are
+indicated by the labels on the right.
+</p>
+
+<table>
+<tr>
+<td valign="top">
+<pre>
+DIJKSTRA(<i>G</i>, <i>s</i>, <i>w</i>)
+  <b>for</b> each vertex <i>u in V</i> <b>(This loop is not run in dijkstra_shortest_paths_no_color_map_no_init)</b>
+    <i>d[u] := infinity</i> 
+    <i>p[u] := u</i> 
+  <b>end for</b>
+  <i>d[s] := 0</i> 
+  INSERT(<i>Q</i>, <i>s</i>)
+  <b>while</b> (<i>Q != &Oslash;</i>)
+    <i>u :=</i> EXTRACT-MIN(<i>Q</i>)
+    <b>for</b> each vertex <i>v in Adj[u]</i>
+      <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
+        <i>d[v] := w(u,v) + d[u]</i>
+        <i>p[v] := u</i> 
+        DECREASE-KEY(<i>Q</i>, <i>v</i>)
+      <b>else</b>
+      	...
+      <b>if</b> (<i>d[v]</i> was originally infinity) 
+        INSERT(<i>Q</i>, <i>v</i>)   
+    <b>end for</b>
+  <b>end while</b>
+  return (<i>d</i>, <i>p</i>)
+</pre>
+</td>
+<td valign="top">
+<pre>
+
+initialize vertex <i>u</i>
+
+
+
+
+discover vertex <i>s</i>
+
+examine vertex <i>u</i>
+examine edge <i>(u,v)</i>
+
+edge <i>(u,v)</i> relaxed
+
+
+
+edge <i>(u,v)</i> not relaxed
+
+discover vertex <i>v</i>
+finish vertex <i>u</i>
+</pre>
+</td>
+</tr>
+</table>
+
+<h3>Where Defined</h3>
+
+boost/graph/dijkstra_shortest_paths_no_color_map.hpp
+
+<h3>Parameters</h3>
+
+IN: <tt>const Graph&amp; graph</tt> 
+<blockquote>
+  The graph object on which the algorithm will be applied.
+  The type <tt>Graph</tt> must be a model of 
+  Vertex List Graph
+  and Incidence Graph.<br>
+</blockquote>
+
+IN: <tt>vertex_descriptor start_vertex</tt> 
+<blockquote>
+  The source vertex. All distance will be calculated from this vertex,
+  and the shortest paths tree will be rooted at this vertex.<br>
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+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
+  negative_edge 
+  exception is one of the edges is negative.
+  The type <tt>WeightMap</tt> must be a model of
+  Readable Property Map. The edge descriptor type of
+  the graph needs to be usable as the key type for the weight
+  map. The value type for this map must be
+  the same as the value type of the distance map.<br>
+  <b>Default:</b>  <tt>get(edge_weight, graph)</tt><br>
+</blockquote>
+
+IN: <tt>index_map(VertexIndexMap index_map)</tt> 
+<blockquote>
+  This maps each vertex to an integer in the range <tt>[0,
+    num_vertices(graph))</tt>. This is necessary for efficient updates of the
+  heap data structure&nbsp;[<A
+  HREF="bibliography.html#driscoll88">61</A>] when an edge is relaxed.
+  The type 
+  <tt>VertexIndexMap</tt> must be a model of
+  Readable Property Map. The value type of the map must be an
+  integer type. The vertex descriptor type of the graph needs to be
+  usable as the key type of the map.<br>
+  <b>Default:</b> <tt>get(vertex_index, graph)</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
+    not have an internal <tt>vertex_index</tt> property.
+   <br>
+</blockquote>
+
+OUT: <tt>predecessor_map(PredecessorMap predecessor_map)</tt> 
+<blockquote>
+  The predecessor map records the edges in the minimum spanning
+  tree. Upon completion of the algorithm, the edges <i>(p[u],u)</i>
+  for all <i>u in V</i> are in the minimum spanning tree. If <i>p[u] =
+  u</i> then <i>u</i> is either the source vertex or a vertex that is
+  not reachable from the source.  The <tt>PredecessorMap</tt> type
+  must be a <a
+  href="../../property_map/ReadWritePropertyMap.html">Read/Write
+  Property Map</a> whose key and value types are the same as the vertex
+  descriptor type of the graph.<br>
+  <b>Default:</b> <tt>dummy_property_map</tt><br>
+
+  <b>Python</b>: Must be a <tt>vertex_vertex_map</tt> for the graph.<br>
+</blockquote>
+
+UTIL/OUT: <tt>distance_map(DistanceMap distance_map)</tt> 
+<blockquote>
+  The shortest path weight from the source vertex <tt>start_vertex</tt> to each
+  vertex in the graph <tt>graph</tt> is recorded in this property map. The
+  shortest path weight is the sum of the edge weights along the
+  shortest path.  The type <tt>DistanceMap</tt> must be a model of <a
+  href="../../property_map/ReadWritePropertyMap.html">Read/Write
+  Property Map</a>. 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">Monoid</a> formed with the <tt>distance_weight_combine</tt>
+  function object and the <tt>distance_zero</tt> object for the identity
+  element. Also the distance value type must have a <a
+  href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">
+  StrictWeakOrdering</a> provided by the <tt>distance_compare</tt> function
+  object.<br>
+  <b>Default:</b> <a
+  href="../../property_map/iterator_property_map.html">
+  <tt>iterator_property_map</tt></a> created from a
+  <tt>std::vector</tt> of the <tt>WeightMap</tt>'s value type of size
+  <tt>num_vertices(graph)</tt> and using the <tt>index_map</tt> for the index
+  map.<br>
+</blockquote>
+
+IN: <tt>distance_compare(CompareFunction distance_compare)</tt> 
+<blockquote>
+  This function is use to compare distances to determine which vertex
+  is closer to the source vertex.  The <tt>DistanceCompareFunction</tt> type
+  must be a model of <a
+  href="http://www.sgi.com/tech/stl/BinaryPredicate.html">Binary
+  Predicate</a> and have argument types that match the value type of
+  the <tt>DistanceMap</tt> property map.<br>
+
+  <b>Default:</b>
+  <tt>std::less&lt;D&gt;</tt> with <tt>D=typename
+  property_traits&lt;DistanceMap&gt;::value_type</tt><br>
+</blockquote>
+
+IN: <tt>distance_combine(CombineFunction distance_weight_combine)</tt> 
+<blockquote>
+  This function is used to combine distances to compute the distance
+  of a path. The <tt>DistanceWeightCombineFunction</tt> type must be a model of <a
+  href="http://www.sgi.com/tech/stl/BinaryFunction.html">Binary
+  Function</a>. The first argument type of the binary function must
+  match the value type of the <tt>DistanceMap</tt> property map and
+  the second argument type must match the value type of the
+  <tt>WeightMap</tt> property map.  The result type must be the same
+  type as the distance value type.<br>
+
+  <b>Default:</b> <tt>boost::closed_plus&lt;D&gt;</tt> with
+   <tt>D=typename property_traits&lt;DistanceMap&gt;::value_type</tt><br>
+</blockquote>
+
+IN: <tt>distance_inf(D distance_infinity)</tt> 
+<blockquote>
+  The <tt>distance_infinity</tt> object must be the greatest value of any <tt>D</tt> object.
+  That is, <tt>distance_compare(d, distance_infinity) == true</tt> for any <tt>d != distance_infinity</tt>.
+  The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+  <b>Default:</b> <tt>std::numeric_limits&lt;D&gt;::max()</tt><br>
+</blockquote>
+
+IN: <tt>distance_zero(D distance_zero)</tt> 
+<blockquote>
+  The <tt>distance_zero</tt> value must be the identity element for the
+  Monoid formed by the distance values
+  and the <tt>distance_weight_combine</tt> function object.
+  The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+  <b>Default:</b> <tt>D()</tt>with
+   <tt>D=typename property_traits&lt;DistanceMap&gt;::value_type</tt><br>
+</blockquote>
+  
+OUT: <tt>visitor(DijkstraVisitor v)</tt>  
+<blockquote>
+  Use this to specify actions that you would like to happen
+  during certain event points within the algorithm.
+  The type <tt>DijkstraVisitor</tt> must be a model of the
+  Dijkstra Visitor concept. 
+ The visitor object is passed by value <a
+  href="#2">[2]</a>.<br>
+  <b>Default:</b> <tt>dijkstra_visitor&lt;null_visitor&gt;</tt><br>
+</blockquote>
+
+
+<H3>Complexity</H3>
+
+<P>
+The time complexity is <i>O(V log V)</i>.
+
+
+<h3>Visitor Event Points</h3>
+
+<ul>
+<li><b><tt>vis.initialize_vertex(u, g)</tt></b>
+  is invoked on each vertex in the graph before the start of the
+  algorithm.
+<li><b><tt>vis.examine_vertex(u, g)</tt></b>
+  is invoked on a vertex as it is removed from the priority queue
+  and added to set <i>S</i>. At this point we know that <i>(p[u],u)</i>
+  is a shortest-paths tree edge so 
+  <i>d[u] = delta(s,u) = d[p[u]] + w(p[u],u)</i>. Also, the distances 
+  of the examined vertices is monotonically increasing
+  <i>d[u<sub>1</sub>] <= d[u<sub>2</sub>] <= d[u<sub>n</sub>]</i>. 
+<li><b><tt>vis.examine_edge(e, g)</tt></b>
+  is invoked on each out-edge of a vertex immediately after it has
+  been added to set <i>S</i>. 
+<li><b><tt>vis.edge_relaxed(e, g)</tt></b>
+  is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>.
+  The edge <i>(u,v)</i> that participated in the last
+  relaxation for vertex <i>v</i> is an edge in the shortest paths tree. 
+<li><b><tt>vis.discover_vertex(v, g)</tt></b>
+  is invoked on vertex <i>v</i> when the edge 
+  <i>(u,v)</i> is examined and <i>v</i> has not yet been discovered (i.e. its distance was infinity before relaxation was attempted on the edge).  This
+  is also when the vertex is inserted into the priority queue.
+<li><b><tt>vis.edge_not_relaxed(e, g)</tt></b>
+  is invoked if the edge is not relaxed (see above).
+<li><b><tt>vis.finish_vertex(u, g)</tt></b>
+   is invoked on a vertex after all of its out edges have
+  been examined.
+</ul>
+
+<H3>Example</H3>
+
+<P>
+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>Notes</H3>
+
+<p>Based on the documentation for dijkstra_shortest_paths.
+
+<p><a name="1">[1]</a>
+The algorithm used here saves a little space by not putting all <i>V -
+S</i> vertices in the priority queue at once, but instead only those
+vertices in <i>V - S</i> that are discovered and therefore have a
+distance less than infinity.
+
+<p><a name="2">[2]</a> 
+  Since the visitor parameter is passed by value, if your visitor
+  contains state then any changes to the state during the algorithm
+  will be made to a copy of the visitor object, not the visitor object
+  passed in. Therefore you may want the visitor to hold this state by
+  pointer or reference.
+  
+<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.
+
+<br>
+<HR>
+<TABLE>
+<TR valign=top>
+<TD nowrap>Copyright &copy 2009</TD><TD>
+Trustees of Indiana University</TD></TR></TABLE>
+
+</BODY>
+</HTML> 

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html	(original)
+++ trunk/libs/graph/doc/table_of_contents.html	2009-05-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -141,6 +141,7 @@
                 <LI>Shortest Paths Algorithms
                   <OL>
                     <LI>dijkstra_shortest_paths
+                    <LI>dijkstra_shortest_paths_no_color_map
                     <LI>bellman_ford_shortest_paths
                     <LI>dag_shortest_paths
                     <LI><A

Added: trunk/libs/graph/example/dijkstra-no-color-map-example.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/example/dijkstra-no-color-map-example.cpp	2009-05-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -0,0 +1,99 @@
+//=======================================================================
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee
+// Copyright 2009 Trustees of Indiana University.
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
+//
+// 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)
+//
+// NOTE: Based off of dijkstra-example.cpp
+//=======================================================================
+#include <boost/config.hpp>
+#include <iostream>
+#include <fstream>
+
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
+
+using namespace boost;
+
+int
+main(int, char *[])
+{
+  typedef adjacency_list < listS, vecS, directedS,
+    no_property, property < edge_weight_t, int > > graph_t;
+  typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
+  typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
+  typedef std::pair<int, int> Edge;
+
+  const int num_nodes = 5;
+  enum nodes { A, B, C, D, E };
+  char name[] = "ABCDE";
+  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
+    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
+  };
+  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
+  int num_arcs = sizeof(edge_array) / sizeof(Edge);
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+  graph_t g(num_nodes);
+  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
+  for (std::size_t j = 0; j < num_arcs; ++j) {
+    edge_descriptor e; bool inserted;
+    tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
+    weightmap[e] = weights[j];
+  }
+#else
+  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
+  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);
+#endif
+  std::vector<vertex_descriptor> p(num_vertices(g));
+  std::vector<int> d(num_vertices(g));
+  vertex_descriptor s = vertex(A, g);
+
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+  // VC++ has trouble with the named parameters mechanism
+  property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index, g);
+  dijkstra_shortest_paths_no_color_map(g, s, &p[0], &d[0], weightmap,
+                                       indexmap, std::less<int>(),
+                                       closed_plus<int>(),
+                                       (std::numeric_limits<int>::max)(), 0,
+                                       default_dijkstra_visitor());
+#else
+  dijkstra_shortest_paths_no_color_map(g, s, predecessor_map(&p[0]).distance_map(&d[0]));
+#endif
+
+  std::cout << "distances and parents:" << std::endl;
+  graph_traits < graph_t >::vertex_iterator vi, vend;
+  for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {
+    std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
+    std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::
+      endl;
+  }
+  std::cout << std::endl;
+
+  std::ofstream dot_file("figs/dijkstra-no-color-map-eg.dot");
+
+  dot_file << "digraph D {\n"
+    << "  rankdir=LR\n"
+    << "  size=\"4,3\"\n"
+    << "  ratio=\"fill\"\n"
+    << "  edge[style=\"bold\"]\n" << "  node[shape=\"circle\"]\n";
+
+  graph_traits < graph_t >::edge_iterator ei, ei_end;
+  for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
+    graph_traits < graph_t >::edge_descriptor e = *ei;
+    graph_traits < graph_t >::vertex_descriptor
+      u = source(e, g), v = target(e, g);
+    dot_file << name[u] << " -> " << name[v]
+      << "[label=\"" << get(weightmap, e) << "\"";
+    if (p[v] == u)
+      dot_file << ", color=\"black\"";
+    else
+      dot_file << ", color=\"grey\"";
+    dot_file << "]";
+  }
+  dot_file << "}";
+  return EXIT_SUCCESS;
+}

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2009-05-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -49,6 +49,7 @@
     [ compile dfs_cc.cpp ]
     [ compile dijkstra_cc.cpp ]
     [ run dijkstra_heap_performance.cpp : 10000 ]
+    [ run dijkstra_no_color_map_compare.cpp : 10000 ]
     [ run dominator_tree_test.cpp ]
     [ run relaxed_heap_test.cpp : 5000 15000 ]
     [ compile edge_list_cc.cpp ]

Added: trunk/libs/graph/test/dijkstra_no_color_map_compare.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/dijkstra_no_color_map_compare.cpp	2009-05-27 16:54:24 EDT (Wed, 27 May 2009)
@@ -0,0 +1,124 @@
+//=======================================================================
+// Copyright 2009 Trustees of Indiana University.
+// Authors: Michael Hansen
+//
+// 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)
+//=======================================================================
+
+#include <iostream>
+#include <map>
+#include <vector>
+
+#include <boost/lexical_cast.hpp>
+#include <boost/random.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/dijkstra_shortest_paths_no_color_map.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/properties.hpp>
+#include <boost/graph/random.hpp>
+#include <boost/test/minimal.hpp>
+
+#define INITIALIZE_VERTEX 0
+#define DISCOVER_VERTEX 1
+#define EXAMINE_VERTEX 2
+#define EXAMINE_EDGE 3
+#define EDGE_RELAXED 4
+#define EDGE_NOT_RELAXED 5
+#define FINISH_VERTEX 6
+
+template <typename Graph>
+void run_dijkstra_test(const Graph& graph)
+{
+  using namespace boost;
+  
+  // Set up property maps
+  typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
+  
+  typedef typename std::map<vertex_t, vertex_t> vertex_map_t;
+  typedef associative_property_map<vertex_map_t> predecessor_map_t;
+  vertex_map_t default_vertex_map, no_color_map_vertex_map;
+  predecessor_map_t default_predecessor_map(default_vertex_map),
+                    no_color_map_predecessor_map(no_color_map_vertex_map);
+
+  typedef typename std::map<vertex_t, double> vertex_double_map_t;
+  typedef associative_property_map<vertex_double_map_t> distance_map_t;
+  vertex_double_map_t default_vertex_double_map, no_color_map_vertex_double_map;
+  distance_map_t default_distance_map(default_vertex_double_map),
+                 no_color_map_distance_map(no_color_map_vertex_double_map);
+
+  // Run dijkstra algoirthms
+  dijkstra_shortest_paths(graph, vertex(0, graph),
+                          predecessor_map(default_predecessor_map)
+                          .distance_map(default_distance_map));
+                                       
+  dijkstra_shortest_paths_no_color_map(graph, vertex(0, graph),
+                                       predecessor_map(no_color_map_predecessor_map)
+                                       .distance_map(no_color_map_distance_map));
+
+  // Verify that predecessor maps are equal
+  BOOST_CHECK(std::equal(default_vertex_map.begin(), default_vertex_map.end(),
+              no_color_map_vertex_map.begin()));
+
+  // Verify that distance maps are equal
+  BOOST_CHECK(std::equal(default_vertex_double_map.begin(), default_vertex_double_map.end(),
+              no_color_map_vertex_double_map.begin()));
+}
+
+int test_main(int argc, char* argv[])
+{
+  using namespace boost;
+
+  int vertices_to_create = 10; 
+  int edges_to_create = 500;
+  std::size_t random_seed = time(0);
+  
+  if (argc > 1) {
+    vertices_to_create = lexical_cast<int>(argv[1]);
+  }
+  
+  if (argc > 2) {
+    edges_to_create = lexical_cast<int>(argv[2]);
+  }
+  
+  if (argc > 3) {
+    random_seed = lexical_cast<std::size_t>(argv[3]);
+  }
+
+  minstd_rand generator(random_seed);
+
+  // Set up graph
+  typedef adjacency_list<listS, listS, directedS,
+    property<vertex_index_t, int >,
+    property<edge_weight_t, double> > graph_t;
+
+  typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
+  typedef graph_traits<graph_t>::edge_descriptor edge_t;
+
+  graph_t graph;  
+  generate_random_graph(graph, vertices_to_create, edges_to_create, generator);
+
+  // Set up property maps
+  typedef property_map<graph_t, vertex_index_t>::type index_map_t;
+  index_map_t index_map = get(vertex_index, graph);
+  int vertex_index = 0;
+
+  BGL_FORALL_VERTICES(current_vertex, graph, graph_t) {
+    put(index_map, current_vertex, vertex_index++);
+  }
+
+  typedef property_map<graph_t, edge_weight_t>::type weight_map_t;
+  weight_map_t weight_map = get(edge_weight, graph);
+  randomize_property<edge_weight_t>(graph, generator);
+
+  // Run comparison test with original dijkstra_shortest_paths
+  std::cout << "Running dijkstra shortest paths test with " << num_vertices(graph) <<
+    " vertices and " << num_edges(graph) << " edges " << std::endl;
+    
+  run_dijkstra_test(graph);
+
+  return 0;
+}
+