[Boost-commit] svn:boost r52509 - in trunk/libs/graph: example examples quickbook quickbook/reference

Subject: [Boost-commit] svn:boost r52509 - in trunk/libs/graph: example examples quickbook quickbook/reference
From: asutton_at_[hidden]
Date: 2009-04-20 10:35:01

Author: asutton
Date: 2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
New Revision: 52509
URL: http://svn.boost.org/trac/boost/changeset/52509

Log:
Migrating all examples into example directory
Added:
   trunk/libs/graph/example/Jamfile.v2   (props changed)
      - copied unchanged from r52508, /trunk/libs/graph/examples/Jamfile.v2
   trunk/libs/graph/example/bron_kerbosch_clique_number.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/bron_kerbosch_clique_number.cpp
   trunk/libs/graph/example/bron_kerbosch_print_cliques.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/bron_kerbosch_print_cliques.cpp
   trunk/libs/graph/example/closeness_centrality.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/closeness_centrality.cpp
   trunk/libs/graph/example/clustering_coefficient.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/clustering_coefficient.cpp
   trunk/libs/graph/example/comm_network.graph   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/comm_network.graph
   trunk/libs/graph/example/degree_centrality.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/degree_centrality.cpp
   trunk/libs/graph/example/eccentricity.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/eccentricity.cpp
   trunk/libs/graph/example/helper.hpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/helper.hpp
   trunk/libs/graph/example/inclusive_mean_geodesic.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/inclusive_mean_geodesic.cpp
   trunk/libs/graph/example/influence_prestige.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/influence_prestige.cpp
   trunk/libs/graph/example/info_network.graph   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/info_network.graph
   trunk/libs/graph/example/mean_geodesic.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/mean_geodesic.cpp
   trunk/libs/graph/example/prism_3_2.graph   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/prism_3_2.graph
   trunk/libs/graph/example/prob_network.graph   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/prob_network.graph
   trunk/libs/graph/example/scaled_closeness_centrality.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/scaled_closeness_centrality.cpp
   trunk/libs/graph/example/social_network.graph   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/social_network.graph
   trunk/libs/graph/example/tiernan_girth_circumference.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/tiernan_girth_circumference.cpp
   trunk/libs/graph/example/tiernan_print_cycles.cpp   (props changed)
      - copied unchanged from r52505, /trunk/libs/graph/examples/tiernan_print_cycles.cpp
Removed:
   trunk/libs/graph/examples/
Text files modified: 
   trunk/libs/graph/example/quick-tour.cpp                            |     4                                         
   trunk/libs/graph/example/quick_tour.cpp                            |    33 ++--                                    
   trunk/libs/graph/quickbook/Jamfile.v2                              |     7                                         
   trunk/libs/graph/quickbook/boost_reference.qbk                     |    78 ++++++----                              
   trunk/libs/graph/quickbook/graph.qbk                               |     2                                         
   trunk/libs/graph/quickbook/history.qbk                             |    28 ++-                                     
   trunk/libs/graph/quickbook/introduction.qbk                        |   280 ++++++++++++++++++++++------------------
   trunk/libs/graph/quickbook/reference/betweenness_centrality.qbk    |     4                                         
   trunk/libs/graph/quickbook/reference/bron_kerbosch_all_cliques.qbk |     4                                         
   trunk/libs/graph/quickbook/reference/closeness_centrality.qbk      |     4                                         
   trunk/libs/graph/quickbook/reference/clustering_coefficient.qbk    |     4                                         
   trunk/libs/graph/quickbook/reference/eccentricity.qbk              |     2                                         
   trunk/libs/graph/quickbook/reference/mean_geodesic.qbk             |     2                                         
   trunk/libs/graph/quickbook/reference/tiernan_all_cycles.qbk        |     4                                         
   trunk/libs/graph/quickbook/tour.qbk                                |   162 ++++++++++++----------                  
   15 files changed, 343 insertions(+), 275 deletions(-)

Modified: trunk/libs/graph/example/quick-tour.cpp
==============================================================================
--- trunk/libs/graph/example/quick-tour.cpp	(original)
+++ trunk/libs/graph/example/quick-tour.cpp	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -1,14 +1,16 @@
 //=======================================================================
-// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, 
+// 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)
 //=======================================================================
+
 #include <boost/config.hpp>
 #include <iostream>
 #include <fstream>
 #include <boost/graph/adjacency_list.hpp>
+
 using namespace boost;
 
 template < typename VertexDescriptor, typename VertexNameMap > void

Modified: trunk/libs/graph/example/quick_tour.cpp
==============================================================================
--- trunk/libs/graph/example/quick_tour.cpp	(original)
+++ trunk/libs/graph/example/quick_tour.cpp	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -8,11 +8,10 @@
 //=======================================================================
 
 #include <boost/config.hpp>
-#include <iostream>                      // for std::cout
-#include <utility>                       // for std::pair
-#include <algorithm>                     // for std::for_each
-#include <boost/utility.hpp>             // for boost::tie
-#include <boost/graph/graph_traits.hpp>  // for boost::graph_traits
+#include <iostream>                         // for std::cout
+#include <utility>                          // for std::pair
+#include <algorithm>                        // for std::for_each
+#include <boost/utility.hpp>                // for boost::tie
 #include <boost/graph/adjacency_list.hpp>
 #include <boost/graph/graphviz.hpp>
 
@@ -24,7 +23,7 @@
   void operator()(const Vertex& v) const
   {
     using namespace boost;
-    typename property_map<Graph, vertex_index_t>::type 
+    typename property_map<Graph, vertex_index_t>::type
       vertex_id = get(vertex_index, g);
     std::cout << "vertex: " << get(vertex_id, v) << std::endl;
 
@@ -32,7 +31,7 @@
     std::cout << "\tout-edges: ";
     typename graph_traits<Graph>::out_edge_iterator out_i, out_end;
     typename graph_traits<Graph>::edge_descriptor e;
-    for (tie(out_i, out_end) = out_edges(v, g); 
+    for (tie(out_i, out_end) = out_edges(v, g);
          out_i != out_end; ++out_i)
     {
       e = *out_i;
@@ -42,7 +41,7 @@
     }
     std::cout << std::endl;
 
-    // Write out the incoming edges    
+    // Write out the incoming edges
     std::cout << "\tin-edges: ";
     typename graph_traits<Graph>::in_edge_iterator in_i, in_end;
     for (tie(in_i, in_end) = in_edges(v, g); in_i != in_end; ++in_i)
@@ -54,7 +53,7 @@
     }
     std::cout << std::endl;
 
-    // Write out all adjacent vertices    
+    // Write out all adjacent vertices
     std::cout << "\tadjacent vertices: ";
     typename graph_traits<Graph>::adjacency_iterator ai, ai_end;
     for (tie(ai,ai_end) = adjacent_vertices(v, g);  ai != ai_end; ++ai)
@@ -78,7 +77,7 @@
 
   // writing out the edges in the graph
   typedef std::pair<int,int> Edge;
-  Edge edge_array[] = 
+  Edge edge_array[] =
   { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
     Edge(C,E), Edge(B,D), Edge(D,E), };
   const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
@@ -101,7 +100,7 @@
           transmission_delay, num_vertices);
 #endif
 
-  boost::property_map<Graph, vertex_index_t>::type 
+  boost::property_map<Graph, vertex_index_t>::type
     vertex_id = get(vertex_index, g);
   boost::property_map<Graph, edge_weight_t>::type
     trans_delay = get(edge_weight, g);
@@ -112,29 +111,29 @@
   for (vp = vertices(g); vp.first != vp.second; ++vp.first)
     std::cout << name[get(vertex_id, *vp.first)] <<  " ";
   std::cout << std::endl;
-  
+
   std::cout << "edges(g) = ";
   graph_traits<Graph>::edge_iterator ei, ei_end;
   for (tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
     std::cout << "(" << name[get(vertex_id, source(*ei, g))]
               << "," << name[get(vertex_id, target(*ei, g))] << ") ";
   std::cout << std::endl;
-  
+
   std::for_each(vertices(g).first, vertices(g).second,
                 exercise_vertex<Graph>(g));
-  
+
   std::map<std::string,std::string> graph_attr, vertex_attr, edge_attr;
   graph_attr["size"] = "3,3";
   graph_attr["rankdir"] = "LR";
   graph_attr["ratio"] = "fill";
   vertex_attr["shape"] = "circle";
 
-  boost::write_graphviz(std::cout, g, 
+  boost::write_graphviz(std::cout, g,
                         make_label_writer(name),
                         make_label_writer(trans_delay),
-                        make_graph_attributes_writer(graph_attr, vertex_attr, 
+                        make_graph_attributes_writer(graph_attr, vertex_attr,
                                                      edge_attr));
-  
+
   return 0;
 }
 

Modified: trunk/libs/graph/quickbook/Jamfile.v2
==============================================================================
--- trunk/libs/graph/quickbook/Jamfile.v2	(original)
+++ trunk/libs/graph/quickbook/Jamfile.v2	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -1,9 +1,8 @@
-
-# Copyright John Maddock 2005. Use, modification, and distribution are
-# subject to the Boost Software License, Version 1.0. (See accompanying
+# Copyright (C) 2007-2009 Andrew Sutton
+#
+# 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)
 
-
 xml graph : graph.qbk ;
 
 boostbook standalone

Modified: trunk/libs/graph/quickbook/boost_reference.qbk
==============================================================================
--- trunk/libs/graph/quickbook/boost_reference.qbk	(original)
+++ trunk/libs/graph/quickbook/boost_reference.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -25,32 +25,42 @@
 [template time_stamper[] [link boost_graph.reference.event_visitors.time_stamper [^time_stamper]]]
 [template property_writer[] [link boost_graph.reference.event_visitors.property_writer [^property_writer]]]
 
+[/ Attribute BGL interface function back to concept definitions /]
+[template add_vertex[] [link
+    boost_graph.concepts.graph_concepts.mutable_graph [^add_vertex]]]
+[template remove_vertex[] [link
+    boost_graph.concepts.graph_concepts.mutable_graph [^remove_vertex]]]
+[template add_edge[] [link
+    boost_graph.concepts.graph_concepts.mutable_graph [^add_edge]]]
+[template remove_edge[] [link
+    boost_graph.concepts.graph_concepts.mutable_graph [^remove_edge]]]
+
 [/ Fundamental /]
 [template breadth_first_search[] [link
     boost_graph.reference.algorithms.fundamental.breadth_first_search
-    [^breadth_first_search()]]]
+    [^breadth_first_search]]]
 [template depth_first_search[] [link
     boost_graph.reference.algorithms.fundamental.depth_first_search
-    [^depth_first_search()]]]
+    [^depth_first_search]]]
 
 [/ Shortest Path /]
 [template dijkstra_shortest_paths[] [link
     boost_graph.reference.algorithms.shortest_paths.dijkstra_shortest_paths
-    [^dijkstra_shortest_paths()]]]
+    [^dijkstra_shortest_paths]]]
 [template bellman_ford_shortest_paths[] [link
     boost_graph.reference.algorithms.shortest_paths.bellman_ford_shortest_paths
-    [^bellman_ford_shortest_paths()]]]
+    [^bellman_ford_shortest_paths]]]
 [template floyd_warshall_all_pairs_shortest_paths[] [link
     boost_graph.reference.algorithms.shortest_paths.floyd_warshall_all_pairs_shortest_paths
-    [^floyd_warshall_all_pairs_shortest_paths()]]]
+    [^floyd_warshall_all_pairs_shortest_paths]]]
 [template johnson_all_pairs_shortest_paths[] [link
     boost_graph.reference.algorithms.shortest_paths.johnson_all_pairs_shortest_paths
-    [^johnson_all_pairs_shortest_paths()]]]
+    [^johnson_all_pairs_shortest_paths]]]
 
 [/ Connectivity /]
 [template connected_components[] [link
     boost_graph.reference.algorithms.connectivity.connected_components
-    [^connected_components()]]]
+    [^connected_components]]]
 [template strong_connected_components[] [link
     boost_graph.reference.algorithms.connectivity.strongly_connected_components
     [^strongly_connected_components]]]
@@ -58,80 +68,86 @@
 [/ Subgraph/ ]
 [template bron_kerbosch_visit_cliques[] [link
     boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques
-    [^bron_kerbosch_all_cliques()]]]
+    [^bron_kerbosch_all_cliques]]]
 
 [template tiernan_all_cycles[] [link
     boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_all_cycles___
-    [^tiernan_all_cycles()]]]
+    [^tiernan_all_cycles]]]
 [template tiernan_girth[] [link
     boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_girth___
-    [^tiernan_girth()]]]
+    [^tiernan_girth]]]
 [template tiernan_circumference[] [link
     boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_circumference___
-    [^tiernan_circumference()]]]
+    [^tiernan_circumference]]]
 [template tiernan_girth_and_circumference[] [link
     boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_girth_and_circumference___
-    [^tiernan_girth_and_circumference()]]]
+    [^tiernan_girth_and_circumference]]]
 
 [template bron_kerbosch_all_cliques[] [link
     boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.__bron_kerbosch_all_cliques___
-    [^bron_kerbosch_all_cliques()]]]
+    [^bron_kerbosch_all_cliques]]]
 [template bron_kerbosch_clique_number[] [link
     boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.__bron_kerbosch_clique_number___
-    [^bron_kerbosch_clique_number()]]]
+    [^bron_kerbosch_clique_number]]]
 
 
 [/ Measures /]
 [template degree_centrality[] [link
     boost_graph.reference.algorithms.measures.degree_centrality.__degree_centrality___
-    [^degree_centrality()]]]
+    [^degree_centrality]]]
 [template all_degree_centralities[] [link
     boost_graph.reference.algorithms.measures.degree_centrality.__all_degree_centralities___
-    [^all_degree_centralities()]]]
+    [^all_degree_centralities]]]
 [template closeness_centrality[] [link
     boost_graph.reference.algorithms.measures.closeness_centrality.__closeness_centrality___
-    [^closeness_centrality()]]]
+    [^closeness_centrality]]]
 [template all_closeness_centralities[] [link
     boost_graph.reference.algorithms.measures.closeness_centrality.__all_closeness_centralities___
-    [^all_closeness_centralities()]]]
+    [^all_closeness_centralities]]]
 [template mean_geodesic[] [link
     boost_graph.reference.algorithms.measures.mean_geodesic.__mean_geodesic___
-    [^mean_geodesic()]]]
+    [^mean_geodesic]]]
 [template all_mean_geodesics[] [link
     boost_graph.reference.algorithms.measures.mean_geodesic.__all_mean_geodesics___
-    [^all_mean_geodesics()]]]
+    [^all_mean_geodesics]]]
 [template small_world_distance[] [link
     boost_graph.reference.algorithms.measures.mean_geodesic.__small_world_distance___
-    [^small_world_distance()]]]
+    [^small_world_distance]]]
 [template eccentricity[] [link
     boost_graph.reference.algorithms.measures.eccentricity.__eccentricity___
-    [^eccentricity()]]]
+    [^eccentricity]]]
 [template eccentricities[] [link
     boost_graph.reference.algorithms.measures.eccentricity.__eccentricities___
-    [^eccentricities()]]]
+    [^eccentricities]]]
 [template radius[] [link
     boost_graph.reference.algorithms.measures.eccentricity.__radius___
-    [^radius()]]]
+    [^radius]]]
 [template diameter[] [link
     boost_graph.reference.algorithms.measures.eccentricity.__diameter___
-    [^diameter()]]]
+    [^diameter]]]
 [template radius_and_diameter[] [link
     boost_graph.reference.algorithms.measures.eccentricity.__radius_and_diameter___
-    [^radius_and_diameter()]]]
+    [^radius_and_diameter]]]
 [template clustering_coefficient[] [link
     boost_graph.reference.algorithms.measures.clustering_coefficient.__clustering_coefficient___
-    [^clustering_coefficient()]]]
+    [^clustering_coefficient]]]
 [template all_clustering_coefficients[] [link
     boost_graph.reference.algorithms.measures.clustering_coefficient.__all_clustering_coefficients___
-    [^all_clustering_coefficients()]]]
+    [^all_clustering_coefficients]]]
 [template num_paths_through_vertex[] [link
     boost_graph.reference.algorithms.measures.clustering_coefficient.__num_paths_through_vertex___
-    [^num_paths_through_vertex()]]]
+    [^num_paths_through_vertex]]]
 [template num_triangles_on_vertex[] [link
     boost_graph.reference.algorithms.measures.clustering_coefficient.__num_triangles_on_vertex___
-    [^num_triangles_on_vertex()]]]
+    [^num_triangles_on_vertex]]]
+
 
+[/ Tours /]
+[template metric_tsp_approxp[] [link
+    boost.graph.reference.algorithms.tours.metrc_tsp_approx.__metric_tsp_approx__
+    [^metric_tsp_approx]]]
 
+[/ Misc /]
 [template exterior_vertex_property[] [link
     graph
     [^exterior_vertex_property]]]
@@ -139,7 +155,7 @@
     graph
     [^exterior_edge_property]]]
 
-[/ Import lots of examples to build code templates]
+[/ Import a number of examples to build code templates /]
 [import ../examples/degree_centrality.cpp]
 [import ../examples/influence_prestige.cpp]
 [import ../examples/closeness_centrality.cpp]

Modified: trunk/libs/graph/quickbook/graph.qbk
==============================================================================
--- trunk/libs/graph/quickbook/graph.qbk	(original)
+++ trunk/libs/graph/quickbook/graph.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -23,7 +23,7 @@
 ]
 
 [/ Templates /]
-[template super[x]'''<superscript>'''[x]'''</superscript>''']
+[template sup[x]'''<superscript>'''[x]'''</superscript>''']
 [template sub[x]'''<subscript>'''[x]'''</subscript>''']
 
 [template delta[]'''&#x3B4;'''] [/ d Greek small letter delta]

Modified: trunk/libs/graph/quickbook/history.qbk
==============================================================================
--- trunk/libs/graph/quickbook/history.qbk	(original)
+++ trunk/libs/graph/quickbook/history.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -10,7 +10,7 @@
 The Boost Graph Library began its life as the Generic Graph Component Library (GGCL), a software
 project at the Lab for Scientific Computing (LSC) at the University of Notre Dame, under the
 direction of Professor Andrew Lumsdaine. The Lab's research directions include numerical linear
-algebra, parallel computing, and software engineering (including generic programming). 
+algebra, parallel computing, and software engineering (including generic programming).
 
 Soon after the Standard Template Library was released, work began at the LSC to apply generic
 programming to scientific computing. The Matrix Template Library (Jeremy Siek's masters thesis)
@@ -23,11 +23,11 @@
 and high-performance requirements of the LSC. Others were also expressing interest in a generic C++
 graph library. During a meeting with Bjarne Stroustrup we were introduced to several people at AT&T
 who needed such a library. There had also been earlier work in the area of generic graph algorithms,
-including some codes written by Alexander Stepanov, and Dietmar Kuhl's masters thesis. 
+including some codes written by Alexander Stepanov, and Dietmar Kuhl's masters thesis.
 
 With this in mind, and motivated by homework assignments in his algorithms class, Jeremy began
 prototyping an interface and some graph classes in the spring on 1998. Lie-Quan Lee then developed
-the first version of GGCL, which became his masters thesis project. 
+the first version of GGCL, which became his masters thesis project.
 
 The following year, Jeremy went to work for SGI with Alexander Stepanov and Matt Austern. During
 this time Alex's disjoint-sets based connected components algorithm was added to GGCL, and Jeremy
@@ -37,15 +37,25 @@
 in creating high-quality C++ libraries. At Boost there were several people interested in generic
 graph algorithms, most notably Dietmar Kuhl. Some discussions about generic interfaces for graph
 structures resulted in the a revision of GGCL which closely resembles the current Boost Graph Library
-interface. 
+interface.
 
 On September 4, 2000 GGCL passed the Boost formal review and became the Boost Graph Library (BGL).
 The first release of BGL was September 27, 2000.
 
 [h2 Changes by Revision]
 
+* Version 1.38.0
+ * New algorithms
+   * Travelling Salesman Problem approximation by Matyas Egyhazy ([metric_tsp_approx]).
+   * Support for named vertices in `adjacency_list`.
+ * Bug Fixes
+   * Fixed spelling of `edmonds_karp` algorithm name.
+   * Correctly remove loop edges from undirected [adjacency_list].
+   * Correctly handle infinite edge weights in [floyd_warshall_all_pairs_shortest_paths].
+   * Edge counts are no longer modified if [remove_edge] fails.
+
 * Version 1.35.0
-  * New algorithms and components 
+  * New algorithms and components
     * kolmogorov_max_flow, from Stephan Diederich as part of the 2006 Google Summer of Code.
     * read_dimacs_max_flow and write_dimacs_max_flow for max-flow problems, from Stephan Diederich.
     * read_graphml and write_graphml for GraphML input/output, from Tiago de Paula Peixoto.
@@ -53,7 +63,7 @@
     * LEDA Adaptor improvements, from Jens Muller.
 
 * Version 1.34.0
-  * New algorithms and components 
+  * New algorithms and components
     * edmonds_maximum_cardinality_matching, from Aaron Windsor.
     * lengauer_tarjan_dominator_tree, from JongSoo Park.
     * compressed_sparse_row_graph, from Jeremiah Willcock and Douglas Gregor of Indiana University.
@@ -69,15 +79,15 @@
     * Bundled properties now work with adjacency list I/O.
     * floyd_warshall_all_pairs_shortest_paths now properly uses its compare, inf, and zero parameters.
     * johnson_all_pairs_shortest_paths now supports compare, combine, inf, and zero.
-    * Fixed a bug in smallest_last_vertex_ordering.hpp which could cause a vertex to be moved to the  wrong bucket during an BucketSorter update. 
+    * Fixed a bug in smallest_last_vertex_ordering.hpp which could cause a vertex to be moved to the  wrong bucket during an BucketSorter update.
 
 * Version 1.33.1
-  * Bug Fixes 
+  * Bug Fixes
     * fruchterman_reingold_force_directed_layout: Fixed enumeration of grid-force pairs, which caused some odd graph formations along grid lines.
     * king_ordering and cuthill_mckee_ordering: Fixed bug that caused failures with the multi-component version of these algorithms.
 
 * Version 1.33.0
-  * New algorithms and components 
+  * New algorithms and components
     * Experimental Python bindings, from Doug Gregor and Indiana University.
     * floyd_warshall_all_pairs_shortest_paths, from Lauren Foutz and Scott Hill.
     * astar_search, from Kristopher Beevers and Jufeng Peng.

Modified: trunk/libs/graph/quickbook/introduction.qbk
==============================================================================
--- trunk/libs/graph/quickbook/introduction.qbk	(original)
+++ trunk/libs/graph/quickbook/introduction.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -1,129 +1,148 @@
 [/
- / Copyright (c) 2007 Andrew Sutton
+ / Copyright (c) 2007-2009 Andrew Sutton
  /
  / 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)
  /]
 
 [section Introduction]
+Graphs are mathematical abstractions that are useful for solving many types of
+problems in computer science. Consequently, these abstractions must also be
+represented in computer programs. A standardized generic interface for
+traversing graphs is of utmost importance to encourage reuse of graph algorithms
+and data structures. Part of the Boost Graph Library is a generic interface that
+allows access to a graph's structure, but hides the details of the implementation.
+This is an "open" interface in the sense that any graph library that implements
+this interface will be interoperable with the BGL generic algorithms and with
+other algorithms that also use this interface. The BGL provides some general
+purpose graph classes that conform to this interface, but they are not meant to
+be the /only/ graph classes; there certainly will be other graph classes that
+are better for certain situations. We believe that the main contribution of the
+The BGL is the formulation of this interface.
+
+The BGL graph interface and graph components are generic, in the same sense as
+the the Standard Template Library (STL). In the following sections, we review
+the role that generic programming plays in the STL and compare that to how we
+applied generic programming in the context of graphs.
 
-Graphs are mathematical abstractions that are useful for solving many types of problems in
-computer science. Consequently, these abstractions must also be represented in computer
-programs. A standardized generic interface for traversing graphs is of utmost importance to
-encourage reuse of graph algorithms and data structures. Part of the Boost Graph Library is
-a generic interface that allows access to a graph's structure, but hides the details of the
-implementation. This is an "open" interface in the sense that any graph library that implements
-this interface will be interoperable with the BGL generic algorithms and with other algorithms
-that also use this interface. The BGL provides some general purpose graph classes that conform
-to this interface, but they are not meant to be the ``only'' graph classes; there certainly will
-be other graph classes that are better for certain situations. We believe that the main
-contribution of the The BGL is the formulation of this interface. 
-
-The BGL graph interface and graph components are generic, in the same sense as the the Standard
-Template Library (STL). In the following sections, we review the role that generic programming
-plays in the STL and compare that to how we applied generic programming in the context of graphs. 
+Of course, if you are already are familiar with generic programming, please dive
+right in! Here's the Table of Contents.
 
-Of course, if you are already are familiar with generic programming, please dive right in! Here's
-the Table of Contents. 
-
-The source for the BGL is available as part of the Boost distribution, which you can  download
-from here.
+The source for the BGL is available as part of the Boost distribution, which you
+can  download from here.
 
 [h2 How to Build Boost.Graph]
-[*DON'T!] The Boost Graph Library is a header-only library and does not need to be built to be used.
-The only exception is the GraphViz input parser.
+[*DON'T!] The Boost Graph Library is a header-only library and does not need to
+be built to be used. The only exception is the GraphViz input parser.
 
-When compiling programs that use the BGL, be sure to compile with optimization. For instance,
-select "Release" mode with Microsoft Visual C++ or supply the flag -O2 or -O3 to GCC. 
+When compiling programs that use the BGL, be sure to compile with optimization.
+For instance, select "Release" mode with Microsoft Visual C++ or supply the flag
+`-O2` or `-O3` to GCC. Compiling in "Debug" mode can sometimes result in
+algorithms that execute slower by an order magnitude!
 
 [h2 Genericity in the STL]
 There are three ways in which the STL is generic.
 
 [h3 Algorithm/Data Structure Interoperability in the STL]
-First, each algorithm is written in a data-structure neutral way, allowing a single template
-function to operate on many different classes of containers. The concept of an iterator is the
-key ingredient in this decoupling of algorithms and data-structures. The impact of this technique
-is a reduction in the STL's code size from O(M*N) to O(M+N), where M is the number of algorithms
-and N is the number of containers. Considering a situation of 20 algorithms and 5 data-structures,
-this would be the difference between writing 100 functions versus only 25 functions! And the
-differences continues to grow faster and faster as the number of algorithms and data-structures
-increase.
+First, each algorithm is written in a data-structure neutral way, allowing a
+single template function to operate on many different classes of containers. The
+concept of an iterator is the key ingredient in this decoupling of algorithms
+and data-structures. The impact of this technique is a reduction in the STL's
+code size from O(M*N) to O(M+N), where M is the number of algorithms and N is
+the number of containers. Considering a situation of 20 algorithms and 5
+data-structures, this would be the difference between writing 100 functions
+versus only 25 functions! And the differences continues to grow faster and
+faster as the number of algorithms and data-structures increase.
 
 [h3 Extension Through Function Objects]
-The second way that STL is generic is that its algorithms and containers are extensible. The user
-can adapt and customize the STL through the use of function objects. This flexibility is what makes
-STL such a great tool for solving real-world problems. Each programming problem brings its own set
-of entities and interactions that must be modeled. Function objects provide a mechanism for extending
-the STL to handle the specifics of each problem domain
+The second way that STL is generic is that its algorithms and containers are
+extensible. The user can adapt and customize the STL through the use of function
+objects. This flexibility is what makes STL such a great tool for solving
+real-world problems. Each programming problem brings its own set of entities and
+interactions that must be modeled. Function objects provide a mechanism for
+extending the STL to handle the specifics of each problem domain
 
 [h3 Element Type Parameterization]
-The third way that STL is generic is that its containers are parameterized on the element type. Though
-hugely important, this is perhaps the least "interesting" way in which STL is generic. Generic
-programming is often summarized by a brief description of parameterized lists such as `std::list<T>`.
-This hardly scratches the surface!
+The third way that STL is generic is that its containers are parameterized on
+the element type. Though hugely important, this is perhaps the least "interesting"
+way in which STL is generic. Generic programming is often summarized by a brief
+description of parameterized lists such as `std::list<T>`. This hardly scratches
+the surface!
 
 [h2 Genericity in Boost.Graph]
 Like the STL, there are three ways in which the BGL is generic.
 
 [h3 Algorithm/Data Structure Interoperability in Boost.Graph]
-First, the graph algorithms of the BGL are written to an interface that abstracts away the details
-of the particular graph data-structure. Like the STL, the BGL uses iterators to define the interface
-for data-structure traversal. There are three distinct graph traversal patterns: traversal of all
-vertices in the graph, through all of the edges, and along the adjacency structure of the graph
-(from a vertex to each of its neighbors). There are separate iterators for each pattern of traversal. 
-
-This generic interface allows template functions such as breadth_first_search() to work on a large
-variety of graph data-structures, from graphs implemented with pointer-linked nodes to graphs
-encoded in arrays. This flexibility is especially important in the domain of graphs. Graph data
-structures are often custom-made for a particular application. Traditionally, if programmers want
-to reuse an algorithm implementation they must convert/copy their graph data into the graph library's
-prescribed graph structure. This is the case with libraries such as LEDA, GTL, Stanford GraphBase;
-it is especially true of graph algorithms written in Fortran. This severely limits the reuse of their
-graph algorithms. 
-
-In contrast, custom-made (or even legacy) graph structures can be used as-is with the generic graph
-algorithms of the BGL, using external adaptation (see Section How to Convert Existing Graphs to the
-BGL). External adaptation wraps a new interface around a data-structure without copying and without
-placing the data inside adaptor objects. The BGL interface was carefully designed to make this
-adaptation easy. To demonstrate this, we have built interfacing code for using a variety of graph
-dstructures (LEDA graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in BGL graph
-algorithms.
+First, the graph algorithms of the BGL are written to an interface that abstracts
+away the details of the particular graph data-structure. Like the STL, the BGL
+uses iterators to define the interface for data-structure traversal. There are
+three distinct graph traversal patterns: traversal of all vertices in the graph,
+through all of the edges, and along the adjacency structure of the graph (from a
+vertex to each of its neighbors). There are separate iterators for each pattern
+of traversal.
+
+This generic interface allows template functions such as breadth_first_search()
+to work on a large variety of graph data-structures, from graphs implemented
+with pointer-linked nodes to graphs encoded in arrays. This flexibility is
+especially important in the domain of graphs. Graph data structures are often
+custom-made for a particular application. Traditionally, if programmers want to
+reuse an algorithm implementation they must convert/copy their graph data into
+the graph library's prescribed graph structure. This is the case with libraries
+such as LEDA, GTL, Stanford GraphBase; it is especially true of graph algorithms
+written in Fortran. This severely limits the reuse of their graph algorithms.
+
+In contrast, custom-made (or even legacy) graph structures can be used as-is
+with the generic graph algorithms of the BGL, using external adaptation (see
+Section How to Convert Existing Graphs to the BGL). External adaptation wraps a
+new interface around a data-structure without copying and without placing the
+data inside adaptor objects. The BGL interface was carefully designed to make
+this adaptation easy. To demonstrate this, we have built interfacing code for
+using a variety of graph dstructures (LEDA graphs, Stanford GraphBase graphs,
+and even Fortran-style arrays) in BGL graph algorithms.
 
 [h3 Extension through Visitors]
-Second, the graph algorithms of the BGL are extensible. The BGL introduces the notion of a visitor,
-which is just a function object with multiple methods. In graph algorithms, there are often several
-key /event points/ at which it is useful to insert user-defined operations. The visitor object has
-a different method that is invoked at each event point. The particular event points and corresponding
-visitor methods depend on the particular algorithm. They often include methods like `start_vertex()`,
-`discover_vertex()`, `examine_edge()`, `tree_edge()`, and `finish_vertex()`.
+Second, the graph algorithms of the BGL are extensible. The BGL introduces the
+notion of a visitor, which is just a function object with multiple methods. In
+graph algorithms, there are often several key /event points/ at which it is
+useful to insert user-defined operations. The visitor object has a different
+method that is invoked at each event point. The particular event points and
+corresponding visitor methods depend on the particular algorithm. They often
+include methods like `start_vertex`, `discover_vertex`, `examine_edge`,
+`tree_edge`, and `finish_vertex`.
 
 [h3 Vertex and Edge Property Multi-Parameterization]
-The third way that the BGL is generic is analogous to the parameterization of the element-type
-in STL containers, though again the story is a bit more complicated for graphs. We need to
-associate values (called "properties") with both the vertices and the edges of the graph. In
-addition, it will often be necessary to associate multiple properties with each vertex and edge;
-this is what we mean by multi-parameterization. The STL `std::list<T>` class has a parameter `T`
-for its element type. Similarly, BGL graph classes have template parameters for vertex and edge
-"properties". A property specifies the parameterized type of the property and also assigns an
-identifying tag to the property. This tag is used to distinguish between the multiple properties
-which an edge or vertex may have. A property value that is attached to a particular vertex or edge
-can be obtained via a property map. There is a separate property map for each property. 
-
-Traditional graph libraries and graph structures fall down when it comes to the parameterization
-of graph properties. This is one of the primary reasons that graph data-structures must be
-custom-built for applications. The parameterization of properties in the BGL graph classes makes
-them well suited for re-use.
+The third way that the BGL is generic is analogous to the parameterization of
+the element-type in STL containers, though again the story is a bit more
+complicated for graphs. We need to associate values (called "properties") with
+both the vertices and the edges of the graph. In addition, it will often be
+necessary to associate multiple properties with each vertex and edge; this is
+what we mean by multi-parameterization. The STL `std::list<T>` class has a
+parameter `T` for its element type. Similarly, BGL graph classes have template
+parameters for vertex and edge "properties". A property specifies the
+parameterized type of the property and also assigns an identifying tag to the
+property. This tag is used to distinguish between the multiple properties which
+an edge or vertex may have. A property value that is attached to a particular
+vertex or edge can be obtained via a property map. There is a separate property
+map for each property.
+
+Traditional graph libraries and graph structures frequently fall down when it
+comes to the parameterization of graph properties. This is one of the primary
+reasons that graph data-structures must be custom-built for applications. The
+parameterization of properties in the BGL graph classes makes them well suited
+for reuse.
 
 [h2 Algorithms]
-Boost.Graph algorithms consist of a core set of algorithm patterns (implemented as generic algorithms)
-and a larger set of graph algorithms. The core algorithm patterns are:
-* Breadth First Search 
-* Depth First Search 
+Boost.Graph algorithms consist of a core set of algorithm patterns (implemented
+as generic algorithms) and a larger set of graph algorithms. The core algorithm
+patterns are:
+
+* Breadth First Search
+* Depth First Search
 * Uniform Cost Search
 
-By themselves, the algorithm patterns do not compute any meaningful quantities over graphs; they are
-merely building blocks for constructing graph algorithms. The graph algorithms in the BGL currently
-include:
+By themselves, the algorithm patterns do not compute any meaningful quantities
+over graphs; they are merely building blocks for constructing graph algorithms.
+The graph algorithms in the BGL currently include:
 
 * Dijkstra's Shortest Paths
 * Bellman-Ford Shortest Paths
@@ -146,21 +165,23 @@
 * adjacency_matrix
 * edge_list
 
-The adjacency_list class is the general purpose "swiss army knife" of graph classes. It is highly
-parameterized so that it can be optimized for different situations: the graph is directed or
-undirected, allow or disallow parallel edges, efficient access to just the out-edges or also to
-the in-edges, fast vertex insertion and removal at the cost of extra space overhead, etc. 
-
-The adjacency_matrix class stores edges in a |V| x |V| matrix (where |V| is the number of vertices).
-The elements of this matrix represent edges in the graph. Adjacency matrix representations are
-especially suitable for very dense graphs, i.e., those where the number of edges approaches |V|2.
+The adjacency_list class is the general purpose "swiss army knife" of graph
+classes. It is highly parameterized so that it can be optimized for different
+situations: the graph is directed or undirected, allow or disallow parallel
+edges, efficient access to just the out-edges or also to the in-edges, fast
+vertex insertion and removal at the cost of extra space overhead, etc.
+
+The adjacency_matrix class stores edges in a |V| x |V| matrix (where |V| is the
+number of vertices). The elements of this matrix represent edges in the graph.
+Adjacency matrix representations are especially suitable for very dense
+graphs, i.e., those where the number of edges approaches |V|[sup 2].
 
-The `edge_list` class is an adaptor that takes any kind of edge iterator and implements an
-Edge List Graph.
+The `edge_list` class is an adaptor that takes any kind of edge iterator and
+implements an Edge List Graph.
 
 [h2 Projects Using This Library]
-This section should probably be merged into the global "Who's using me now page". But, for completeness
-here's the list (with links, too):
+Here is an abbreviated list of projects that use the BGL or are based on the
+graph concepts in the BGL.
 
 * [@http://www.cs.rpi.edu/~musser/gsd/ Generic Software Design Course at RPI]
 * [@http://alps.comp-phys.org/ The ALPS quantum mechanics project]
@@ -177,6 +198,8 @@
 * [@http://hyperworx.org Hyperworx Platform Project]
 
 [h2 Publications about this Library]
+Here is a short list of publications about the BGL.
+
 * Dr. Dobb's Sept. 2000 Article
 * OOPSLA'99 GGCL Paper
 * Lie-Quan Lee's Master's Thesis about GGCL(ps) (pdf)
@@ -185,30 +208,35 @@
 * C++ Template Workshop 2000, Concept Checking
 
 [h2 Acknowledgements]
-We owe many debts of thanks to a number of individuals who both inspired and encouraged us in
-developing the Boost Graph Library. 
+We owe many debts of thanks to a number of individuals who both inspired and
+encouraged us in developing the Boost Graph Library.
 
-A most profound thanks goes to Alexander Stepanov for his pioneering work in generic programming,
-for his encouragement, and for his algorithm contributions to the BGL. We thank Matthew Austern for
-his work on documenting the concepts of STL which provided a foundation for creating the concepts in
-the BGL. We thank Dietmar Kuhl for his work on generic graph algorithms and design patterns;
+A most profound thanks goes to Alexander Stepanov for his pioneering work in
+generic programming, for his encouragement, and for his algorithm contributions
+to the BGL. We thank Matthew Austern for his work on documenting the concepts
+of STL which provided a foundation for creating the concepts in the BGL. We
+thank Dietmar Kuhl for his work on generic graph algorithms and design patterns;
 especially for the property map abstraction.
 
-Dave Abrahams, Jens Maurer, Beman Dawes, Gary Powell, Greg Colvin, Valentin Bonnard, and the rest
-of the group at Boost provided valuable input to the BGL interface, numerous suggestions for improvement,
-proof reads of the documentation, and help with polishing the code. A special thanks to Dave Abrahams
-for managing the formal review. 
-
-We also thank the following BGL users whose questions helped to improve the BGL: Gordon Woodhull,
-Dave Longhorn, Joel Phillips, and Edward Luke.
-
-A special thanks to Jeffrey Squyres for editing and proof reading of the documentation. 
-
-Our original work on the Boost Graph Library was supported in part by NSF grant ACI-9982205 and by
-the Director, Office of Science, Division of Mathematical, Information, and Computational Sciences of
-the U.S. Department of Energy under contract number DE-AC03-76SF00098. 
-
-In our work we also used resources of the National Energy Research Scientific Computing Center, which
-is supported by the Office of Science of the U.S. Department of Energy. 
+Dave Abrahams, Jens Maurer, Beman Dawes, Gary Powell, Greg Colvin, Valentin
+Bonnard, and the rest of the group at Boost provided valuable input to the BGL
+interface, numerous suggestions for improvement, proof reads of the
+documentation, and help with polishing the code. A special thanks to Dave
+Abrahams for managing the formal review.
+
+We also thank the following BGL users whose questions helped to improve the
+BGL: Gordon Woodhull, Dave Longhorn, Joel Phillips, and Edward Luke.
+
+A special thanks to Jeffrey Squyres for editing and proof reading of the
+documentation.
+
+Our original work on the Boost Graph Library was supported in part by NSF grant
+ACI-9982205 and by the Director, Office of Science, Division of Mathematical,
+Information, and Computational Sciences of the U.S. Department of Energy under
+contract number DE-AC03-76SF00098.
+
+In our work we also used resources of the National Energy Research Scientific
+Computing Center, which is supported by the Office of Science of the U.S.
+Department of Energy.
 
 [endsect]
\ No newline at end of file

Modified: trunk/libs/graph/quickbook/reference/betweenness_centrality.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/betweenness_centrality.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/betweenness_centrality.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -141,9 +141,9 @@
 If the source vertex is disconnected from any vertices in the graph, this value is 0.
 
 [heading Complexity]
-The `closenesss_centrality()` function returns in ['O(n[super 2]*O(M))] where /n/
+The `closenesss_centrality()` function returns in ['O(n[sup 2]*O(M))] where /n/
 is the number of vertices in the graph and /M/ is the complexity of the given distance
-measure. This is ['O(n[super 2])] by default
+measure. This is ['O(n[sup 2])] by default
 
 The `vertex_closeness_centrality()` function returns in ['O(n*O(M))]. This is
 linear by default.

Modified: trunk/libs/graph/quickbook/reference/bron_kerbosch_all_cliques.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/bron_kerbosch_all_cliques.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/bron_kerbosch_all_cliques.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -97,10 +97,10 @@
 ]
 
 [heading Complexity]
-This problem has a loose upper bound of ['O(2[super n])] if one considers all possible
+This problem has a loose upper bound of ['O(2[sup n])] if one considers all possible
 combinations of subsets of vertices as cliques (i.e., the powerset of vertices).
 The original publication, however, approximates the runtime of the algorithm as
-being proportional to ['O(3.14[super n])].
+being proportional to ['O(3.14[sup n])].
 
 Graphs that do not meet the constant-time requirements of the [AdjacencyMatrix]
 concept will incur additional runtime costs during execution (usually by a linear

Modified: trunk/libs/graph/quickbook/reference/closeness_centrality.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/closeness_centrality.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/closeness_centrality.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -228,9 +228,9 @@
 ]
 
 [heading Complexity]
-The `all_closenesss_centralities()` function returns in ['O(n[super 2]*O(M))] where /n/
+The `all_closenesss_centralities()` function returns in ['O(n[sup 2]*O(M))] where /n/
 is the number of vertices in the graph and /O(M)/ is the complexity of the distance
-measure. If no distance measure is given, this functions returns in ['O(n[super 2])]
+measure. If no distance measure is given, this functions returns in ['O(n[sup 2])]
 time.
 [endsect]
 

Modified: trunk/libs/graph/quickbook/reference/clustering_coefficient.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/clustering_coefficient.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/clustering_coefficient.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -117,7 +117,7 @@
 vertex. The return type is either `float` or the type specified by the user.
 
 [heading Complexity]
-The `clustering_coefficient()` function returns in ['O(d(v)[super 2]] where
+The `clustering_coefficient()` function returns in ['O(d(v)[sup 2]] where
 /d(v)/ is the degree of /v/.
 [endsect]
 
@@ -159,7 +159,7 @@
 ]
 
 [heading Complexity]
-The `all_clustering_coefficients()` function returns in ['O(nd[super 2])] where
+The `all_clustering_coefficients()` function returns in ['O(nd[sup 2])] where
 /d/ is the mean (average) degree of vertices in the graph.
 [endsect]
 

Modified: trunk/libs/graph/quickbook/reference/eccentricity.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/eccentricity.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/eccentricity.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -145,7 +145,7 @@
 as the `first` and `second` elements respectively.
 
 [heading Complexity]
-The `eccentricities()` function returns in ['O(n[super 2])] where /n/ is the number
+The `eccentricities()` function returns in ['O(n[sup 2])] where /n/ is the number
 of vertices in the graph.
 [endsect]
 

Modified: trunk/libs/graph/quickbook/reference/mean_geodesic.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/mean_geodesic.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/mean_geodesic.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -223,7 +223,7 @@
 will also be infinite.
 
 [heading Complexity]
-The `all_mean_geodesics()` function returns in ['O(n[super 2]*O(M))] where /n/ is the
+The `all_mean_geodesics()` function returns in ['O(n[sup 2]*O(M))] where /n/ is the
 number of vertices in the graph, and /O(M)/ is the complexity of the given measure.
 If no measure is given, this function returns in quadratic time.
 [endsect]

Modified: trunk/libs/graph/quickbook/reference/tiernan_all_cycles.qbk
==============================================================================
--- trunk/libs/graph/quickbook/reference/tiernan_all_cycles.qbk	(original)
+++ trunk/libs/graph/quickbook/reference/tiernan_all_cycles.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -134,7 +134,7 @@
 ]
 
 [heading Complexity]
-This function has a (loose) upper bound of ['O(2[super n])] where /n/ is the
+This function has a (loose) upper bound of ['O(2[sup n])] where /n/ is the
 number of vertices a graph. This bound is derived from the powerset of vertices
 in /g/ and does not account for the vertex of origin or directionality of edges
 connecting vertices in a path. If one considers the paths in a triangle {1, 2, 3}
@@ -142,7 +142,7 @@
 be much greater. From a practical standpoint, it is unlikely that real graphs will
 ever approach a number of paths remotely close to this number.
 
-This function requires ['O(n[super 2])] space where /n/ is the number of vertices
+This function requires ['O(n[sup 2])] space where /n/ is the number of vertices
 in a graph.
 [endsect]
 

Modified: trunk/libs/graph/quickbook/tour.qbk
==============================================================================
--- trunk/libs/graph/quickbook/tour.qbk	(original)
+++ trunk/libs/graph/quickbook/tour.qbk	2009-04-20 10:34:59 EDT (Mon, 20 Apr 2009)
@@ -6,43 +6,55 @@
  /]
 
 [section A Quick tour of Boost.Graph]
-The domain of graph data structures and algorithms is in some respects more complicated than
-that of containers. The abstract iterator interface used by STL is not sufficiently rich to
-encompass the numerous ways that graph algorithms may traverse a graph. Instead, we formulate an
-abstract interface that serves the same purpose for graphs that iterators do for basic containers
-(though iterators still play a large role). Figure 1 depicts the analogy between the STL and
+The domain of graph data structures and algorithms is in some respects more
+complicated than that of containers. The abstract iterator interface used by
+STL is not sufficiently rich to encompass the numerous ways that graph
+algorithms may traverse a graph. Instead, we formulate an abstract interface
+that serves the same purpose for graphs that iterators do for basic containers
+(though iterators still play a large role). Figure 1 depicts the analogy between
+the STL and
 Boost.Graph.
 
 [$../images/tour_analogy.gif]
 
-The graph abstraction consists of a set of vertices (or nodes), and a set of edges (or arcs) that
-connect the vertices. Figure 2 depicts a directed graph with five vertices (labeled 0 through 4)
-and 11 edges. The edges leaving a vertex are called the out-edges of the vertex. The edges
-{(0,1),(0,2),(0,3),(0,4)} are all out-edges of vertex 0. The edges entering a vertex are called
-the in-edges of the vertex. The edges {(0,4),(2,4),(3,4)} are all in-edges of vertex 4.
+The graph abstraction consists of a set of vertices (or nodes), and a set of
+edges (or arcs) that connect the vertices. Figure 2 depicts a directed graph
+with five vertices (labeled 0 through 4) and 11 edges. The edges leaving a
+vertex are called the out-edges of the vertex. The edges {(0,1),(0,2),(0,3),(0,4)}
+are all out-edges of vertex 0. The edges entering a vertex are called the in-edges
+of the vertex. The edges {(0,4),(2,4),(3,4)} are all in-edges of vertex 4.
 
 [$../images/tour_graph.png]
 
-In the following sections we will use Boost.Graph to construct this example graph and manipulate it in
-various ways. The complete source code for this example can be found in examples/quick_tour.cpp. Each
-of the following sections discusses a "slice" of this example file. Excerpts from the output of the
-example program will also be listed.
+In the following sections we will use Boost.Graph to construct this example
+graph and manipulate it in various ways. The complete source code for this
+example can be found in `examples/quick_tour.cpp`. Each of the following
+sections discusses a "slice" of this example file. Excerpts from the output of
+the example program will also be listed.
 
 [h2 Constructing the Graph]
-In this example we will use the `adjacency_list<>` class to demonstrate the main ideas in the
-Boost.Graph interface. The `adjacency_list<>` class provides a generalized version of the classic
-"adjacency list" data structure. The `adjacency_list<>` is a template class with six template parameters,
-though here we only fill in the first three parameters and use the defaults for the remainder.
-The first two template arguments (`vecS`, `vecS`) determine the data structure used to represent the
-out-edges for each vertex in the graph and the data structure used to represent the graph's vertex set
-(see section Choosing the Edgelist and VertexList for information about the tradeoffs of the different
-data structures). The third argument, `bidirectionalS`, selects a directed graph that provides access to
-both out and in-edges. The other options for the third argument are `directedS` which selects a directed
-graph with only out-edges, and `undirectedS` which selects an undirected graph.
-
-Once we have the graph type selected, we can create the graph in Figure 2 by declaring a graph object
-and filling in edges using the add_edge() function of the MutableGraph interface (which `adjacency_list<>`
-implements). We use the array of pairs edge_array merely as a convenient way to explicitly create the
+
+In this example
+
+[h2 Constructing the Graph]
+In this example we will use the [adjacency_list] class to demonstrate the main
+ideas in the Boost.Graph interface. The [adjacency_list] class provides a
+generalized version of the classic /adjacency list/ data structure. The
+[adjacency_list] class is a template class with six template parameters, though
+here we only fill in the first three parameters and use the defaults for the
+remainder. The first two template arguments (`vecS`, `vecS`) determine the data
+structure used to represent the out-edges for each vertex in the graph and the
+data structure used to represent the graph's vertex set (see section Choosing
+the Edgelist and VertexList for information about the tradeoffs of the different
+data structures). The third argument, `bidirectionalS`, selects a directed graph
+that provides access to both out and in-edges. The other options for the third
+argument are `directedS` which selects a directed graph with only out-edges, and
+`undirectedS` which selects an undirected graph.
+
+Once we have the graph type selected, we can create the graph in Figure 2 by
+declaring a graph object and filling in edges using the add_edge() function of
+the MutableGraph interface (which `adjacency_list<>` implements). We use the
+array of pairs edge_array merely as a convenient way to explicitly create the
 edges for this example.
 
  #include <iostream>          // for std::cout
@@ -83,16 +95,17 @@
    return 0;
  }
 
-Instead of calling the `add_edge()` function for each edge, we could use the edge iterator constructor
-of the graph. This is typically more efficient than using `add_edge()`. Pointers to the `edge_array` can
-be viewed as iterators, so we can call the iterator constructor by passing pointers to the beginning
-and end of the array.
+Instead of calling the `add_edge()` function for each edge, we could use the
+edge iterator constructor of the graph. This is typically more efficient than
+using `add_edge()`. Pointers to the `edge_array` can be viewed as iterators, so
+we can call the iterator constructor by passing pointers to the beginning and
+end of the array.
 
  Graph g(edges, edges + sizeof(edge_array) / sizeof(edge_array[0]), num_vertices);
 
-Instead of creating a graph with a certain number of vertices to begin with, it is also possible to
-add and remove vertices with the `add_vertex()` and `remove_vertex()` functions, also of the /MutableGraph/
-interface.
+Instead of creating a graph with a certain number of vertices to begin with, it
+is also possible to add and remove vertices with the [add_vertex] and
+[remove_vertex] functions, also of the [MutableGraph] interface.
 
 [h2 Accessing the Vertex Set]
 Now that we have created a graph, we can use the graph interface to access the graph data in
@@ -108,7 +121,7 @@
 edge properties, including index, are accessed via property map objects. The `property_map<>` class is
 used to obtain the property map type for a specific property (specified by `vertex_index_t`, one of the
 Boost.Graph predefined properties) and function call `get(vertex_index, g)` returns the actual
-property map object. 
+property map object.
 
 
  // ...
@@ -132,7 +145,7 @@
    return 0;
  }
 
-The output is: 
+The output is:
 
 [pre
  vertices(g) = 0 1 2 3 4
@@ -147,7 +160,7 @@
 can be used to assign the parts of a std::pair into two separate variables, in this case `ei`
 and `ei_end`. This is usually more convenient than creating a `std::pair` and is our method of
 choice for Boost.Graph.
-  
+
  // ...
  int main(int,char*[])
  {
@@ -173,8 +186,8 @@
 view of a particular vertex. We will look at the vertices' in-edges, out-edges, and its adjacent
 vertices. We will encapsulate this in an "exercise vertex" function, and apply it to each vertex
 in the graph. To demonstrate the STL-interoperability of Boost.Graph, we will use the STL `for_each()`
-function to iterate through the vertices and apply the function. 
-  
+function to iterate through the vertices and apply the function.
+
  //...
  int main(int,char*[])
  {
@@ -187,8 +200,8 @@
 needed when we access information about each vertex; using a functor gives us a place to keep a
 reference to the graph object during the execution of the `std::for_each()`. Also we template the
 functor on the graph type so that it is reusable with different graph classes. Here is the start
-of the exercise_vertex functor: 
-  
+of the exercise_vertex functor:
+
  template <class Graph> struct exercise_vertex {
    exercise_vertex(Graph& g_) : g(g_)
    { }
@@ -210,8 +223,8 @@
 vertex_descriptor type is obtained through the graph_traits class. The typename keyword used below
 is necessary because the type on the left hand side of the scope :: operator (the `graph_traits<Graph>`
 type) is dependent on a template parameter (the `Graph` type). Here is how we define the functor's
-apply method: 
-  
+apply method:
+
  template <class Graph> struct exercise_vertex {
    // ... continued from above
 
@@ -234,8 +247,9 @@
 gives an edge descriptor object. An edge descriptor plays the same kind of role as the vertex
 descriptor object, it is a "black box" provided by the graph type. The following code snippet prints
 the source-target pairs for each out-edge of vertex, v.
-  
- template <class Graph> struct exercise_vertex {
+
+ template <class Graph>
+ struct exercise_vertex {
    //... continued from above
 
    void operator()(const Vertex& v) const
@@ -260,7 +274,7 @@
    // ...
  };
 
-For vertex 0 the output is: 
+For vertex 0 the output is:
 [pre
  out-edges: (0,1) (0,2) (0,3) (0,4)
 ]
@@ -268,8 +282,8 @@
 The `in_edges()` function of the BidirectionalGraph interface provides access to all the in-edges
 of a vertex through in-edge iterators. The in_edges() function is only available for the
 `adjacency_list<>` if `bidirectionalS` is supplied for the Directed template parameter. There is an
-extra cost in space when `bidirectionalS` is specified instead of `directedS`. 
-  
+extra cost in space when `bidirectionalS` is specified instead of `directedS`.
+
  template <class Graph> struct exercise_vertex {
    // ... continued from above
 
@@ -291,7 +305,7 @@
    // ...
  };
 
-For vertex 0 the output is: 
+For vertex 0 the output is:
 [pr
  in-edges: (2,0) (3,0) (4,0)
 ]
@@ -302,8 +316,8 @@
 about the vertices. Therefore the graph interface also includes the `adjacent_vertices()` function
 of the AdjacencyGraph interface which provides direct access to the adjacent vertices. This function
 returns a pair of adjacency iterators. Dereferencing an adjacency iterator gives a vertex descriptor
-for an adjacent vertex. 
-  
+for an adjacent vertex.
+
  template <class Graph> struct exercise_vertex {
    // ... continued from above
 
@@ -322,7 +336,7 @@
    //...
  };
 
-For vertex 4 the output is: 
+For vertex 4 the output is:
 [pre
  adjacent vertices: 0 1
 ]
@@ -337,7 +351,7 @@
 kind is called an externally stored property. Boost.Graph uses a uniform mechanism to access both kinds of
 properties inside its graph algorithms called the property map interface, described in Section
 Property Map Concepts. In addition, the PropertyGraph concept defines the interface for obtaining
-a property map object for an internally stored property. 
+a property map object for an internally stored property.
 
 The Boost.Graph adjacency_list class allows users to specify internally stored properties through plug-in
 template parameters of the graph class. How to do this is discussed in detail in Section Internal
@@ -347,11 +361,11 @@
 specified for the VertexList template parameter, vertices are automatically assigned indices, which
 can be accessed via the property map for the vertex_index_t. Edges are not automatically assigned
 indices. However the property mechanism can be used to attach indices to the edges which can be
-used to index into other externally stored properties. 
+used to index into other externally stored properties.
 
 In the following example, we construct a graph and apply `dijkstra_shortest_paths()`. The complete
 source code for the example is in examples/dijkstra-example.cpp. Dijkstra's algorithm computes the
-shortest distance from the starting vertex to every other vertex in the graph. 
+shortest distance from the starting vertex to every other vertex in the graph.
 
 Dijkstra's algorithm requires that a weight property is associated with each edge and a distance
 property with each vertex. Here we use an internal property for the weight and an external property
@@ -362,9 +376,9 @@
 `adjacency_list<>` (see Section Choosing the Edgelist and VertexList). The directedS type specifies
 that the graph should be directed (versus undirected). The following code shows the specification of
 the graph type and then the initialization of the graph. The edges and weights are passed to the
-graph constructor in the form of iterators (a pointer qualifies as a /RandomAccessIterator/). 
+graph constructor in the form of iterators (a pointer qualifies as a /RandomAccessIterator/).
 
- typedef adjacency_list<listS, vecS, directedS, 
+ typedef adjacency_list<listS, vecS, directedS,
                         no_property,                 // no additional vertex properties
                         property<edge_weight_t, int> // edges have integer edge weight
                        > Graph;
@@ -372,9 +386,9 @@
  typedef std::pair<int,int> E;
 
  const int num_nodes = 5;
- E edges[] = { E(0,2), 
+ E edges[] = { E(0,2),
                E(1,1), E(1,3), E(1,4),
-               E(2,1), E(2,3), 
+               E(2,1), E(2,3),
                E(3,4),
                E(4,0), E(4,1) };
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};
@@ -385,8 +399,8 @@
 random access iterators as property maps, so we can just pass the beginning iterator of the
 distance vector to Dijkstra's algorithm. Continuing the above example, the following code shows
 the creation of the distance vector, the call to Dijkstra's algorithm (implicitly using the
-internal edge weight property), and then the output of the results. 
-  
+internal edge weight property), and then the output of the results.
+
  // vector for storing distance property
  std::vector<int> d(num_vertices(G));
 
@@ -399,11 +413,11 @@
  std::cout << "distances from start vertex:" << ;
  graph_traits<Graph>::vertex_iterator vi;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
-   std::cout << "distance(" << index(*vi) << ") = " 
+   std::cout << "distance(" << index(*vi) << ") = "
              << d[*vi] << ;
  std::cout << ;
 
-The output is: 
+The output is:
 [pre
  distances from start vertex:
  distance(0) = 0
@@ -417,7 +431,7 @@
 Often times an algorithm in a library almost does what you need, but not quite. For example, in
 the previous section we used Dijkstra's algorithm to calculate the shortest distances to each
 vertex, but perhaps we also wanted to record the tree of shortest paths. One way to do this is
-to record the predecessor (parent) for each node in the shortest-paths tree. 
+to record the predecessor (parent) for each node in the shortest-paths tree.
 
 It would be nice if we could avoid rewriting Dijkstra's algorithm, and just add that little bit
 extra needed to record the predecessors [1]. In the STL, this kind of extensibility is provided
@@ -439,7 +453,7 @@
 this visitor will only be filling in one of the visitor methods, we will inherit from
 `dijkstra_visitor` which will provide empty methods for the rest. The constructor of the
 `predecessor_recorder` will take the property map object and save it away in a data member.
-  
+
  template <class PredecessorMap>
  class record_predecessors : public dijkstra_visitor<>
  {
@@ -466,8 +480,8 @@
 shortest-paths tree so we specify `tree_edge_tag`.
 
 As a finishing touch, we create a helper function to make it more convenient to create predecessor
-visitors. All Boost.Graph visitors have a helper function like this. 
-  
+visitors. All Boost.Graph visitors have a helper function like this.
+
  template <class PredecessorMap>
  record_predecessors<PredecessorMap>
  make_predecessor_recorder(PredecessorMap p) {
@@ -477,25 +491,25 @@
 We are now ready to use the `record_predecessors` in Dijkstra's algorithm. Luckily, Boost.Graph's
 Dijkstra's algorithm is already equipped to handle visitors, so we just pass in our new visitor.
 In this example we only need to use one visitor, but Boost.Graph is also equipped to handle the use
-of multiple visitors in the same algorithm (see Section Visitor Concepts). 
-  
+of multiple visitors in the same algorithm (see Section Visitor Concepts).
+
  using std::vector;
  using std::cout;
  using std::endl;
  vector<Vertex> p(num_vertices(G)); //the predecessor array
- dijkstra_shortest_paths(G, s, distance_map(&d[0]). 
+ dijkstra_shortest_paths(G, s, distance_map(&d[0]).
                          visitor(make_predecessor_recorder(&p[0])));
 
  cout << "parents in the tree of shortest paths:" << endl;
  for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
    cout << "parent(" << *vi;
    if (p[*vi] == Vertex())
-     cout << ") = no parent" << endl; 
-   else 
+     cout << ") = no parent" << endl;
+   else
      cout << ") = " << p[*vi] << endl;
  }
 
-The output is: 
+The output is:
 [pre
  parents in the tree of shortest paths:
  parent(0) = no parent