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

Subject: [Boost-commit] svn:boost r80637 - trunk/libs/graph/doc
From: jewillco_at_[hidden]
Date: 2012-09-22 15:21:40

Author: jewillco
Date: 2012-09-22 15:21:39 EDT (Sat, 22 Sep 2012)
New Revision: 80637
URL: http://svn.boost.org/trac/boost/changeset/80637

Log:
Added wording that infinite-weight edges are not guaranteed to work correctly; fixes #7398
Text files modified: 
   trunk/libs/graph/doc/dijkstra_shortest_paths.html              |     4 +++-                                    
   trunk/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html |    14 ++++----------                          
   2 files changed, 7 insertions(+), 11 deletions(-)

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	2012-09-22 15:21:39 EDT (Sat, 22 Sep 2012)
@@ -330,7 +330,9 @@
 <blockquote>
   The <tt>inf</tt> object must be the greatest value of any <tt>D</tt> object.
   That is, <tt>compare(d, inf) == true</tt> for any <tt>d != inf</tt>.
-  The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
+  The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.  Edges
+  are assumed to have a weight less than (using <tt>distance_compare</tt> for
+  comparison) this value.<br>
   <b>Default:</b> <tt>std::numeric_limits&lt;D&gt;::max()</tt><br>
 
   <b>Python</b>: Unsupported parameter.

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	2012-09-22 15:21:39 EDT (Sat, 22 Sep 2012)
@@ -69,7 +69,7 @@
 </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.
+	<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.  Note that this means that edges with infinite weight will not work correctly in this algorithm.
 </P>
 
 <P>
@@ -116,10 +116,6 @@
 <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>)
@@ -141,10 +137,6 @@
 <td valign="top">
 <pre>
 
-initialize vertex <i>u</i>
-
-
-
 
 discover vertex <i>s</i>
 
@@ -293,7 +285,9 @@
 <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>
+  The type <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.  All edges
+  are assumed to have weight less than (by <tt>distance_compare</tt>) this
+  value.<br>
   <b>Default:</b> <tt>std::numeric_limits&lt;D&gt;::max()</tt><br>
 </blockquote>