[Boost-commit] svn:boost r7482

From: asutton_at_[hidden]
Date: 2007-07-19 09:59:24

Author: asutton
Date: 2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
New Revision: 7482
URL: http://svn.boost.org/trac/boost/changeset/7482

Log:
Moved all docs up one level and got rid of some cruft

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2
   sandbox/SOC/2007/graphs/libs/graph/doc/bibliography.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/a_star_visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dfs_visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/incidence_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitor.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/guide/
   sandbox/SOC/2007/graphs/libs/graph/doc/guide/adjacency_list.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/guide/directed_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/guide/guide.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/guide/undirected_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/history.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/introduction.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/adjacency_list.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/connected_components.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/edge_list.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/strong_components.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/theory.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/tour.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/tutorial.qbk

Added: sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,79 @@
+
+# Copyright John Maddock 2005. Use, modification, and distribution are
+# subject to 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)
+
+using quickbook ;
+
+xml graph : graph.qbk ;
+
+boostbook standalone
+    :
+        graph
+    :
+        # HTML options first:
+        # Use graphics not text for navigation:
+        <xsl:param>navig.graphics=1
+        # How far down we chunk nested sections, basically all of them:
+        <xsl:param>chunk.section.depth=10
+        # Don't put the first section on the same page as the TOC:
+        <xsl:param>chunk.first.sections=1
+        # How far down sections get TOC's
+        <xsl:param>toc.section.depth=10
+        # Max depth in each TOC:
+        <xsl:param>toc.max.depth=4
+        # How far down we go with TOC's
+        <xsl:param>generate.section.toc.level=10
+        # Logo location:
+        <xsl:param>boost.logo=../boost.png
+        <xsl:param>annotation.support=1
+
+        # The page style
+        <xsl:param>page.style="'website'"
+        # Show chapters select box
+        <xsl:param>grouped.links.chapters.show="'true'"
+        # GroupedLinks xml definition chapters location
+        <xsl:param>grouped.links.chapters.xml="'boost_libs_grouped_links.xml'"
+        # Select the base url for the chapters GroupedLinks
+        <xsl:param>grouped.links.chapters.url="'http://www.boost.org/libs/'"
+        # Show sections select box
+        <xsl:param>grouped.links.sections.show="'true'"
+        # GroupedLinks xml definition sections location
+        <xsl:param>grouped.links.sections.xml="'sections_grouped_links.xml'"
+        # Select the base url for the chapters GroupedLinks
+        <xsl:param>grouped.links.sections.url="'./'"
+        # Show the Google Search Box
+        <xsl:param>search.box.show="'true'"
+        # Location of the cse defintion
+        <xsl:param>search.box.cse.definition.src="'http://www.drivehq.com/web/matias.capeletto/bimap/doc/html/context8.xml'"
+
+        # PDF Options:
+        # TOC Generation: this is needed for FOP-0.9 and later:
+        # <xsl:param>fop1.extensions=1
+        <xsl:param>xep.extensions=1
+        # TOC generation: this is needed for FOP 0.2, but must not be set to zero for FOP-0.9!
+        <xsl:param>fop.extensions=0
+        # No indent on body text:
+        <xsl:param>body.start.indent=0pt
+        # Margin size:
+        <xsl:param>page.margin.inner=0.5in
+        # Margin size:
+        <xsl:param>page.margin.outer=0.5in
+        # Yes, we want graphics for admonishments:
+        <xsl:param>admon.graphics=1
+        # Set this one for PDF generation *only*:
+        # default pnd graphics are awful in PDF form,
+        # better use SVG's instead:
+        #<xsl:param>admon.graphics.extension=".svg"
+    ;
+
+
+
+
+
+
+
+
+
+
+

Added: sandbox/SOC/2007/graphs/libs/graph/doc/bibliography.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/bibliography.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,19 @@
+[/
+ / Copyright (c) 2007 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)
+ /]
+
+[bibliography]
+
+[bibentry
+    [authors [Sutter, Herb], [Alexandrescu, Andrei]]
+    [title C++ Coding Standards: 101 Rules, Guidelines, and Best Practices]
+    [book
+        [publisher Addison Wesley]
+        [copyright 1985 Pearson Education, Inc.]
+    [pages 220]
+]
+
+[endbib]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,41 @@
+[/
+ / Copyright (c) 2007 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)
+ /]
+
+[/
+ / This file contains Boost-defined concepts
+ /]
+
+
+[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
+
+[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
+[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
+[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
+
+[template BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor Descriptor]]
+[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
+[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
+[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
+[template BoostVertexListGraph[] [link boost_graph.concepts.graph_concepts.vertex_list_graph VertexListGraph]]
+[template BoostEdgeListGraph[] [link boost_graph.concepts.graph_concepts.edge_list_graph EdgeListGraph]]
+[template BoostAdjacencyGraph[] [link boost_graph.concepts.graph_concepts.adjacency_graph AdjacencyGraph]]
+[template BoostAdjacencyMatrix[] [link boost_graph.concepts.graph_concepts.adjacency_matrix AdjacencyMatrix]]
+[template BoostMutableGraph[] [link boost_graph.concepts.graph_concepts.mutable_graph MutableGraph]]
+[template BoostPropertyGraph[] [link boost_graph.concepts.graph_concepts.property_graph PropertyGraph]]
+[template BoostMutablePropertyGraph[] [link boost_graph.concepts.graph_concepts.mutable_property_graph MutablePropertyGraph]]
+
+[template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
+[template BoostBFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
+[template BoostDFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
+[template BoostDijkstraVisitor[] [link boost_graph.concepts.visitor_concepts.dijksta_visitor DijkstraVisitor]]
+[template BoostBellmanfordVisitor[] [link boost_graph.concepts.visitor_concepts.bellmanford_visitor BellmanFordVisitor]]
+[template BoostAStarVisitor[] [link boost_graph.concepts.visitor_concepts.a_star_visitor A\*Visitor]]
+[template BoostEventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
+[template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
+
+[/ A bunch of miscellaneus concepts]
+[template BoostColorValue[] [link boost_graph.concepts.miscellaneous_concepts.color_value ColorValue]]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,37 @@
+[/
+ / Copyright (c) 2007 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)
+ /]
+
+[/
+ / This file contains references to Boost.Graph reference docs
+ /]
+
+[/ Graph traits and types /]
+[template boost_graph_traits[] [link boost_graph.reference_guide.traits_classes.graph_traits [^graph_traits]]]
+[template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph [^undirected_graph]]]
+[template boost_directed_graph[] [link boost_graph.reference_guide.graph_types.directed_graph [^directed_graph]]]
+[template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list [^adjacecncy_list]]]
+[template boost_edge_list[] [link boost_graph.reference_guide.graph_types.edge_list [^edge_list]]]
+
+[/ Visitor types /]
+[template boost_null_visitor[] [link boost_graph.reference_guide.visitor_types.null_visitor [^null_visitor]]]
+[template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor [^bfs_visitor]]]
+[template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor [^dfs_visitor]]]
+[template boost_predecessor_recorder[] [link boost_graph.reference_guide.event_visitors.predecessor_recorder [^predecessor_recorder]]]
+[template boost_distance_recorder[] [link boost_graph.reference_guide.event_visitors.distance_recorder [^distance_recorder]]]
+[template boost_time_stamper[] [link boost_graph.reference_guide.event_visitors.time_stamper [^time_stamper]]]
+[template boost_property_writer[] [link boost_graph.reference_guide.event_visitors.property_writer [^property_writer]]]
+
+[/ Core algorithms /]
+[template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search [^breadth_first_search()]]]
+[template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search [^depth_first_search()]]]
+
+[/ Path algorithms /]
+[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths [^dijkstra_shortest_paths()]]]
+[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths [^bellman_ford_shortest_paths()]]]
+
+
+[template boost_connected_components[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/a_star_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/a_star_visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,72 @@
+[/
+ / Copyright (c) 2007 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 Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::vertex_descriptor`]
+        [
+            A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+            must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+            descriptors are almost always passed by value.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_descriptor`]
+        [
+            An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+            must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+            are almost always passed by value.
+        ]
+    ]
+    [
+        [`graph_traits<G>::directed_category`]
+        [
+            This type shall be convertible to `directed_tag` or `undirected_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_parallel_category`]
+        [
+            This describes whether the graph class allows the insertion of parallel edges
+            (multiple edges between the same source and target vertices). The two tags are
+            `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This describes the ways in which the vertices and edge of the graph can be visited.
+            The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+            `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`graph_traits<G>::null_vertex()`]
+        [
+            Returns a special `vertex_descriptor` which does not refer to any vertex for graphs
+            of type `G`. Note that default initialization of `vertex_descriptors` are /not/
+            guaranteed to be equal to then `null_vertex()`.
+
+            *Returns* `vertex_descriptor`
+        ]
+    ]
+]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,69 @@
+[/
+ / Copyright (c) 2007 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 Adjacency Graph]
+The AdjacencyGraph concept provides and interface for efficient access of the adjacent vertices
+to a vertex in a graph. This is quite similar to the IncidenceGraph concept (the target of an
+out-edge is an adjacent vertex). Both concepts are provided because in some contexts there is only
+concern for the vertices, whereas in other contexts the edges are also important.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `adjacency_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::adjacency_iterator`]
+        [
+            An adjacency iterator for a vertex v provides access to the vertices adjacent to v.
+            As such, the value type of an adjacency iterator is the vertex descriptor type of its
+            graph. An adjacency iterator must meet the requirements of [BoostMultiPassInputIterator].
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`adjacent_vertices(v,g)`]
+        [
+            Returns an iterator-range providing access to the vertices adjacent to vertex `v` in
+            the graph `g`.
+
+            *Returns* `std::pair<adjacency_iterator, adjacency_iterator>`
+        ]
+    ]
+]
+
+[h4 Complexity Guarantees]
+The `adjacent_vertices(v,g)` function must return in constant time.
+
+[h4 Design Rationale]
+The AdjacencyGraph concept is somewhat frivolous since [BoostIncidenceGraph] really covers the same
+functionality (and more). The AdjacencyGraph concept exists because there are situations when
+`adjacent_vertices()` is more convenient to use than `out_edges()`. If you are constructing a graph
+class and do not want to put in the extra work of creating an adjacency iterator, have no fear. There
+is an adaptor class named `adjacency_iterator` that you can use to create an adjacency iterator out
+of an out-edge iterator.
+
+[h4 Notes]
+The case of a /multigraph/ (where multiple edges can connect the  same two vertices) brings up an issue
+as to whether the iterators returned by the `adjacent_vertices()` function access a range that includes
+each adjacent vertex once, or whether it should match the behavior of the `out_edges()` function, and
+access a range that may include an adjacent vertex more than once. For now the behavior is defined to
+match that of `out_edges()`, though this decision may need to be reviewed in light of more experience
+with graph algorithm implementations.
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/adjacency_matrix.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,50 @@
+[/
+ / Copyright (c) 2007 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 Adjacency Matrix]
+The AdjacencyMatrix concept refines `Graph` concept and adds the requirement for efficient access
+to any edge in the graph given the source and target vertices. No Boost.Graph algorithms currently
+use this concept. However there are algorithms not yet implemented such as Floyd-Warshall that
+would require this concept.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `adjacency_matrix_tag`.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`edge(u,v,g)`]
+        [
+            Returns a pair consisting of a flag saying whether there exists an edge between `u` and
+            `v` in graph g, and consisting of the edge descriptor if the edge was found.
+
+            *Returns* `std::pair<edge_iterator, bool>`
+        ]
+    ]
+]
+
+[h4 Complexity Guarantees]
+The `edge(u,v,g)` function must return in constant time.
+
+[h4 Notes]
+A number of graph classes (notably [boost_undirected_graph], [boost_directed_graph] and
+[boost_adjacency_list]) provide non-constant time implementations of this interface. Although
+the function exists, none of these classes are documented as modeling this concept.
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bellman_ford_visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,70 @@
+[/
+ / Copyright (c) 2007 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 Bellman Ford Visitor]
+This concept defines the visitor interface for [boost_bellman_ford_shortest_paths]. Users
+can define a class with the Bellman Ford Visitor interface and pass and object of the
+class to [boost_bellman_ford_shortest_paths], thereby augmenting the actions taken during the
+graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`vis.examine_edge(v,g)`]
+        [
+            This is invoked on every out-edge of each vertex after it is discovered.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.edge_relaxed(e,g)`]
+        [
+            If the relaxation predicate holds for this given edge then this method is invoked.
+            See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.edge_not_relaxed(e,g)`]
+        [
+            If the relaxation predicate does not hold for this edge, then this method is invoked.
+            See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.edge_minimized(e,g)`]
+        [
+            After the `num_vertices(g)` iterators through the edge det of the graph is complete,
+            one last iteration is made to test whether each edge was minimized. If the edge is
+            minimized then this function is invoked.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.edge_relaxed(e,g)`]
+        [
+            If the edge is not minimized then this function is invoked. This happens when there
+            is a negative weight cycle in the graph.
+
+            *Returns* `void`
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_bellman_ford_visitor]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bfs_visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,105 @@
+[/
+ / Copyright (c) 2007 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 Breadth-First Search Visitor]
+This concept defines the visitor interface for [booost_breadth_first_search] algorithm. Users
+can define a class with the BFS Visitor interface and pass and object of the class to
+[boost_breadth_first_search], thereby augmenting the actions taken during the graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`vis.initialize_vertex(v,g)`]
+        [
+            This is invoked on every vertex of the graph before the start of the graph search.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.discover_vertex(v,g)`]
+        [
+            This is invoked when a vertex is encountered for the first time.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.examine_vertex(v,g)`]
+        [
+            This is invoked on a vertex as it is popped from the queue. This happens immediately
+            before `examine_edge(v,g)` s invoked on each of the out-edges of vertex `v`.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.examine_edge(e,g)`]
+        [
+            This is invoked on every out-edge of each vertex after it is discovered.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.tree_edge(e,g)`]
+        [
+            This is invoked on each edge as it becomes a member of the eges that the form the
+            search tree.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.non_tree_edge(v,g)`]
+        [
+            This is invoked on back or cross edges for directed graphs and cross edges
+            for undirected graphs.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.gray_target(e,g)`]
+        [
+            This is invoked on the subset of non-tree-edges who's target vertex is colored gray
+            at the time of examination. The color gray indicates that the vertex is currently
+            in the queue.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.black_target(v,g)`]
+        [
+            This is invoked on the subset of non-tree edges who's target vertex is colored black
+            at the time of examination. The color black indicates that the vertex has been removed
+            from the queue.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.finish_vertex(v,g)`]
+        [
+            This is invoked on a vertex after all of its out edges have been added to the search
+            tree and all of the adjacenct vertices have been discovered, but before the out-edges
+            of the adjacent vertices have been examined.
+
+            *Returns* `void`
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_bfs_visitor]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/bidirectional_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,76 @@
+[/
+ / Copyright (c) 2007 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 Bidirectional Graph]
+The BidirectionalGraph concept refines IncidenceGraph and adds the requirement for efficient
+access to the in-edges of each vertex. This concept is separated from IncidenceGraph because for
+directed graphs efficient access to in-edges typically requires more storage space, and many
+algorithms do not require access to in-edges. For undirected graphs this is not an issue, since
+the in_edges() and out_edges() functions are the same, they both return the edges incident to
+the vertex.
+
+[heading Refinement Of]
+[BoostIncidenceGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `bidirectional_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::in_edge_iterator`]
+        [
+            An in-edge iterator for a vertex v provides access to the in-edges of a vertex. As
+            such, the value type of an in-edge iterator is the edge descriptor type of its graph.
+            An in-edge iterator must meet the requirements of MultiPassInputIterator.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`in_edges(v,g)`]
+        [
+            Returns an iterator range providing access to the in-edges (for directed graphs)
+            or the incident edges (for undirected graphs). The target vertex of an edge obtained
+            via an in-edge iterator is guaranteed to be the vertex `v` in the call to
+            `in_edges(v,g)`, and the source vertex must be adjacenct to `v`.
+
+            *Returns* `std::pair<in_edge_iterator, in_edge_iterator>`
+        ]
+    ]
+    [
+        [`in_degree(v,g)`]
+        [
+            Returns the number of in-edges (for directed graphs) or the number of incident
+            edges (for undirected graphs) of the vertex `v`.
+
+            *Returns* `degree_size_type`.
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list] with the `Directed` template parameter as `bidirectionalS` or
+`undirectedS`.
+
+[h4 Complexity Guarantees]
+The `in_edges(g)` function is required to return in constant time.
+
+The `in_degree()` and `degree()` functions must be linear in the number of in-edges (for
+directed graph) or incident edges (for undirected graphs).
+
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/concepts.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,36 @@
+[/
+ / Copyright (c) 2007 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 Concepts]
+This section provides a detailed listing of the type concepts in the Boost.Graph
+library.
+
+[heading Notation]
+For the following sections, we use the following notional convents:
+
+[table
+    [[Object] [Type]]
+    [[G] [A type that is a model of a [BoostGraph] (or refinement thereof)]]
+    [[g] [An object of type G]]
+    [[u,v] [Objects of type `graph_traits<G>::vertex_descriptor`]]
+    [[e] [An object of type `graph_traits<G>::edge_descriptor`]]
+    [[vi] [An object of type `graph_traits<G>::vertex_iterator`]]
+    [[ei] [An object of type `graph_traits<G>::edge_iterator`]]
+    [[vp] [An object of type `G::vertex_property_type`]]
+    [[ep] [An object of type `G::edge_property_type`]]
+    [[Property] [A type used to specify a vertex or edge property. Also called a /tag/.]]
+    [[p] [An object of type Property]]
+    [[Predicate] [A function that, given an argument, returns true or false]]
+    [[pred] [An object of type [SgiPredicate]]]
+    [[V] [A type that is a model of a [BoostVisitor] (or refinement thereof)]]
+    [[vis] [An object of type V]]
+]
+
+[include graphs.qbk]
+[include visitors.qbk]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/descriptor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,28 @@
+[/
+ / Copyright (c) 2007 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 Descriptor]
+The Descriptor concept describes requirements common to vertex and edge descriptors of
+all graph types.
+
+[heading Refinement Of]
+[SgiDefaultConstructible], [SgiCopyConstructible], [SgiAssignable], [SgiEqualityComparable],
+and [SgiLessThanComparable].
+
+[heading Associated Types]
+There are no associated types of a Descriptor.
+
+[heading Valid Expressions]
+Beyond the requirements of the refined concepts, the descriptor does not require any
+additional valid expressions.
+
+[heading Notes]
+Note that because both model the [SgiLessThanComparable] concept, they can be used as
+keys in any associative container modeling the [SgiAssociativeContainer] concepte
+(e.g., `std::map`, `std::set`, etc).
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dfs_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dfs_visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,99 @@
+[/
+ / Copyright (c) 2007 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 Depth-First Search Visitor]
+This concept defines the visitor interface for [booost_depth_first_search] algorithm. Users
+can define a class with the DFS Visitor interface and pass and object of the class to
+[boost_depth_first_search], thereby augmenting the actions taken during the graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`vis.initialize_vertex(v,g)`]
+        [
+            This is invoked on every vertex of the graph before the start of the graph search.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.start_vertex(v,g)`]
+        [
+            This is invoked on the source veretx once before the start of the search.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.discover_vertex(v,g)`]
+        [
+            This is invoked when a vertex is encountered for the first time.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.examine_edge(e,g)`]
+        [
+            This is invoked on every out-edge of each vertex after it is discovered.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.tree_edge(e,g)`]
+        [
+            This is invoked on each edge as it becomes a member of the eges that the form the
+            search tree.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.back_edge(v,g)`]
+        [
+            This is invoked on the back edges of the graph. For an unidrected graph there
+            is some ambiguity between tree edges and back edges since the edge /(u,v)/
+            and /(v,u)/ are the same edge, but both `tree_edge(v,g)` and `back_edge(v,g)`
+            will be invoked. One way to resolve this ambiguity is to record the tree
+            edges and then disregard the back edges that are already marked as tree edges.
+            An easy way to record tree edges is to record predecessors at the `tree_edge`
+            event point.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.forward_or_cross_edge(e,g)`]
+        [
+            This is invoked on forward or cross edges in the graph. In an undirected graph,
+            this method is never called.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.finish_vertex(v,g)`]
+        [
+            This is invoked on a vertex after all `finish_vertex(x,g)` has been invoked for
+            all vertices in the search tree rooted at `v` (i.e., after all its children
+            have finished). If `v` is a leaf in the search tree, `finish_vertex(v,g)` is
+            called after all its out-edges have been examined.
+
+            *Returns* `void`
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_dfs_visitor]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/dijkstra_visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,87 @@
+[/
+ / Copyright (c) 2007 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 Dijkstra Visitor]
+This concept defines the visitor interface for [boost_dijkstra_shortest_paths] and related
+algorithms. The user can create a class that matches this interface, and then pass objects
+of the class into [boost_dijkstra_shortest_paths] to augment the actions taken during the
+search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`vis.initialize_vertex(v,g)`]
+        [
+            This is invoked on every vertex of the graph before the start of the graph search.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.discover_vertex(v,g)`]
+        [
+            This is invoked when a vertex is encountered for the first time. This happens immediately
+            before `examine_edge()` is invoked on each of the out-edges of `v`.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.examine_vertex(v,g)`]
+        [
+            This is invoked on a vertex as it is popped from the queue. This happens immediately
+            before `examine_edge(v,g)` s invoked on each of the out-edges of vertex `v`.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.examine_edge(v,g)`]
+        [
+            This is invoked on every out-edge of each vertex after it is discovered.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.edge_relaxed(e,g)`]
+        [
+            If the relaxation predicate holds for this given edge then this method is invoked.
+            See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.edge_not_relaxed(e,g)`]
+        [
+            If the relaxation predicate does not hold for this edge, then this method is invoked.
+            See [boost_dijkstra_shortest_paths] for more information on relaxation.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`vis.finish_vertex(v,g)`]
+        [
+            This is invoked on a vertex after all of its out edges have been added to the search
+            tree and all of the adjacent vertices have been discovered (but before their out edgs)
+            have been examined).
+
+            *Returns* `void`
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_dijkstra_visitor]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_list_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,98 @@
+[/
+ / Copyright (c) 2007 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 Edge List Graph]
+The EdgeListGraph concept refines the [BoostGraph] concept, and adds the requirement
+for efficient access to all the edges in a graph.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `edge_list_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_iterator`]
+        [
+            An edge iterator (obtained via edges(g)) provides access to all of the edges
+            in a graph. An edge iterator type must meet the requirements of
+            [BoostMultiPassInputIterator]. The value type of the edge iterator must be the
+            same as the edge descriptor of the graph.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edges_size_type`]
+        [
+            The unsigned integer type used to represent the number of edges in the graph.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`edges(g)`]
+        [
+            Returns an iterator range providing access to all the edges in the graph `g`.
+
+            *Returns* `std::pair<edge_iterator, edge_iterator>`
+        ]
+    ]
+    [
+        [`num_edges(g)`]
+        [
+            Returns the number of edges in the graph `g`.
+
+            *Returns* `edges_size_type`
+        ]
+    ]
+    [
+        [`source(e,g)`]
+        [
+            If `e` is an edge /(u,v)/ in `g`, this function returns the source vertex `u`.
+
+            *Returns* `vertex_descriptor`
+        ]
+    ]
+    [
+        [`target(e,g)`]
+        [
+            If `e` is an edge /(u,v)/ in `g`, this function returns the target vertex `v`.
+
+            *Returns* `vertex_descriptor`
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list]
+* [boost_edge_list]
+
+[h4 Complexity Guarantees]
+The `edges(g)`, `source(e,g)`, and `target(e,g)` functions must return in constant time.
+
+[h4 Design Rationale]
+One issue in the design of this concept is whether to include the refinement from the
+[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+of a graph is orthogonal to traversing out-edges, so it would make sense to have a edgeListGraph
+concept that only includes edge traversal. However, such a concept would no longer really be a
+graph, but would just be a set, and the STL already has concepts for dealing with such things.
+However, there are many BGL algorithms that need to traverse the vertices and out-edges of a graph,
+so for convenience a concept is needed that groups these requirements together, hence the edgeListGraph
+concept.
+
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,175 @@
+[/
+ / Copyright (c) 2007 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 Event Visitor]
+This concept defines the interface for single-event visitors. An EventVisitor has an
+/apply/ member function (`operator()`) which is invoked within the graph algorithm
+at the event-point specified by the `event_filter` typedef within the type modeling
+the EventVisitor concept. EventVisitors can be combined into an [BoostEventVistorList].
+
+The following is the list of event tags that can be invoked in Boost.Graph algorithms.
+Each tag corresponds to a member function of the visitor for an algorithm. For example,
+the [BoostBFSVisitor] of [boost_breadth_first_search] has a `cycle_edge()` member function.
+The corresponding tag is `on_cycle_edge`. The first argument in the event visitor's
+`operator()` must be either an edge or vertex depending on the event tag.
+
+[h4 Event Tags]
+[table
+    [[Type] [Description]]
+    [
+        [on_initialize_vertex]
+        [
+            An event tag corresponding to the initialization of a vertex. The parameter
+            type associated with this event is `vertex_descriptor`.
+        ]
+    ]
+    [
+        [on_start_vertex]
+        [
+            In algorithms that without explicit starting points, this event tag
+            corresponds to the selection of a starting vertex. The parameter
+            type associated with this event is `vertex_descriptor`.
+        ]
+    ]
+    [
+        [on_discover_vertex]
+        [
+            An event tag that corresponds to a vertex that is being used for
+            the first time. The parameter type associated with this event is
+            `vertex_descriptor`.
+        ]
+    ]
+    [
+        [on_examine_edge]
+        [
+            An event tag that corresponds to the examination of edges for recently
+            discovered vertices. The parameter type associated with this event
+            is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_tree_edge]
+        [
+            For algorithms whose iterations of a vertex set implicitly define a
+            tree (such as [boost_breadth_first_search] or [boost_depth_first_search]),
+            this event tag corresponds to the identification of an edge that acts
+            as an edge in the search tree. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_cycle_edge]
+        [
+            For algorithms capable of detecting cycles in graphs such as
+            [boost_depth_first_search], this event tag is associated with discovery
+            of an edge that creates a cycle within the graph. The parameter type
+            associated with this event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_forward_or_cross_edge]
+        [
+            Forward and cross edges refer to types of edges that can be found by
+            different types of searches on graph (e.g., [boost_depth_first_search]).
+            This event tag corresponds to the identification of such an edge by
+            the algorithm. The parameter type associated with this event is
+            `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_back_edge]
+        [
+            Back edges refer to types of edges that can be found by different types
+            of searches on a graph (e.g., [boost_breadth_first_search] and
+            [boost_depth_first_search]). This event tag corresponds to the identification
+            of such an edge by the algorithm. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_finish_vertex]
+        [
+            The inverse event of `on_discover_vertex`, this event tag corresponds to
+            the completion of an iteration of an algorithm that is operating on a
+            vertex. The parametet type associated with this event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_relaxed]
+        [
+            For algorithms implementing edge relaxation (e.g.,
+            [boost_dijkstra_shortest_paths]), this event corresponds to the case
+            where an edge is relaxed. The parameter type associated with this event
+            is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_not_relaxed]
+        [
+            For algorithms implementing edge relaxation (e.g.,
+            [boost_dijkstra_shortest_paths]), this event corresponds to the case
+            where an edge is not relaxed. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_minimized]
+        [
+            For algorithms implementing edge minimization (e.g.,
+            [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+            where an edge is minimized. The parameter type associated with this event
+            is `edge_descriptor`.
+        ]
+    ]
+    [
+        [on_edge_not_minimized]
+        [
+            For algorithms implementing edge minimization (e.g.,
+            [boost_bellman_ford_shortest_paths]), this event corresponds to the case
+            where an edge is not minimized. The parameter type associated with this
+            event is `edge_descriptor`.
+        ]
+    ]
+]
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`V::event_filter`]
+        [
+            A tag to specify on which even the visitor should be invoked.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`vis(x,g)`]
+        [
+            Invokes the `operator()` member function of an object `vis` of type
+            `V`. The parameter `x` is either a vertex or edge of the graph `g`. The
+            specific type of parameter depends on `V::event_filter`.
+
+            *Returns* `void`
+        ]
+    ]
+]
+
+[h4 Models]
+* [boost_predecessor_recorder]
+* [boost_distance_recorder]
+* [boost_time_stamper]
+* [boost_property_writer]
+* [boost_null_visitor]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/event_visitor_list.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,70 @@
+[/
+ / Copyright (c) 2007 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 Event Visitor List]
+An EventVisitorList is either an [BoostEventVisitor], or a list of [BoostEventVisitor]
+combined using `std::pair`. Each graph algorithm defines visitor adaptors that convert an
+EventVisitorList into the particular kind of visitor needed by the algorithm. In the
+following example we will show how to combine event visitors into a list using `std::pair`
+and how to use an algorithm's visitor adaptor class.
+
+Suppose we would like to print out the parenthesis structure of the discover/finish times
+of vertices in a depth-first search. We can use the Boost.Graph algorithm [boost_depth_first_search]
+and two event visitors to accomplish this. The complete source code for the following example
+is in `examples/dfs_parenthesis.cpp`. First we define the two event visitors. We use
+`on_discover_vertex` and `on_finish_vertex` as the event points, selected from the list of
+event points specified in [BoostDFSVisitor].
+
+    struct open_paren : public base_visitor<open_paren>
+    {
+        typedef on_discover_vertex event_filter;
+
+        template <class Vertex, class Graph>
+        void operator ()(Vertex v, Graph& G)
+        {
+            cout << "(" << v;
+        }
+    };
+
+
+    struct close_paren : public base_visitor<clsoe_paren>
+    {
+        typedef on_discover_vertex event_filter;
+
+        template <class Vertex, class Graph>
+        void operator ()(Vertex v, Graph& G)
+        {
+            cout << v << ")";
+        }
+    };
+
+Next, we create two event visitor objects and combine them so the resultant type models
+the EventVisitorList concept.
+
+    make_pair(open_paren(), close_paren());
+
+Next we want to pass this list into [boost_depth_first_search], but it is
+expecting a [BoostDFSVisitor], not a [EventVisitorList]. We therefore use the [boost_dfs_visitor]
+adaptor which turns an [BoostEventVisitor] list into a [BoostDFSVisitor]. Like all of the visitor
+adaptors, [dfs_visitor] has a creation function called [boost_make_dfs_visitor].
+
+    make_dfs_visitor((open_paren(), close_paren()));
+
+Now we can pass the resulting visitor object into [boost_depth_first_search] as follows.
+
+    depth_first_search(
+        G,
+        make_dfs_visitor(make_pair(open_paren(), close_paren())));
+
+For creating a list of more than two event visitors, nest calls to `make_pair` in the following way
+to recursively produce an EventVisitorList.
+
+    make_pair(visitor1,
+        make_pair(visitor2, ...
+            make_pair(visitorN - 1, visitorN)...))
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,72 @@
+[/
+ / Copyright (c) 2007 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 Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::vertex_descriptor`]
+        [
+            A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+            must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+            descriptors are almost always passed by value.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_descriptor`]
+        [
+            An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+            must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+            are almost always passed by value.
+        ]
+    ]
+    [
+        [`graph_traits<G>::directed_category`]
+        [
+            This type shall be convertible to `directed_tag` or `undirected_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_parallel_category`]
+        [
+            This describes whether the graph class allows the insertion of parallel edges
+            (multiple edges between the same source and target vertices). The two tags are
+            `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This describes the ways in which the vertices and edge of the graph can be visited.
+            The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+            `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`graph_traits<G>::null_vertex()`]
+        [
+            Returns a special `vertex_descriptor` which does not refer to any vertex for graphs
+            of type `G`. Note that default initialization of `vertex_descriptors` are /not/
+            guaranteed to be equal to then `null_vertex()`.
+
+            *Returns* `vertex_descriptor`
+        ]
+    ]
+]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,234 @@
+[/
+ / Copyright (c) 2007 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 Graph Concepts]
+The heart of the Boost Graph Library (BGL) is the interface, or concepts (in the
+parlance of generic programming), that define how a graph can be examined and
+manipulated in a data-structure neutral fashion. In fact, the BGL interface need
+not even be implemented using a data-structure, as for some problems it is easier
+or more efficient to define a graph implicitly based on some functions.
+
+The Boost.Graph interface does not appear as a single graph concept. Instead it is
+factored into much smaller peices. The reason for this is that the purpose of a
+concept is to summarize the requirements for particular algorithms. Any one algorithm
+does not need every kind of graph operation, typically only a small subset. Furthermore,
+there are many graph data-structures that can not provide efficient implementations of
+all the operations, but provide highly efficient implementations of the operations
+necessary for a particular algorithm . By factoring the graph interface into many smaller
+concepts we provide the graph algorithm writer with a good selection from which to choose
+the concept that is the closest match for their algorithm.
+
+Figure 1 shows the refinements relations between the graph concepts. The reason for
+factoring the graph interface into so many concepts is to encourage algorithm interfaces
+to require and use only the minimum interface of a graph, thereby increasing the
+usability of the algorithm.
+
+[$images/concepts/graph_concepts.png]
+
+Table 1 gives a summary of the valid expressions and associated types for the graph
+concepts and provides links to the detailed descriptions of each of the concepts.
+The notation used in the table is as follows.
+
+[table
+    [[Expression] [Return Type or Description]]
+    [[[*[BoostGraph]]]]
+    [[`graph_traits<G>::vertex_descriptor`] [The type for vertex representative objects.]]
+    [[`graph_traits<G>::edge_descriptor`] [The type for edge representative objects.]]
+    [[`graph_traits<G>::directed_category`] [Graph is directed or undirected?]]
+    [[`graph_traits<G>::edge_parallel_category`] [Graph allows parallel edges?]]
+    [[`graph_traits<G>::traversal_category`] [The ways in which the vertices and edges can be traversed.]]
+    [[[*[BoostIncidenceGraph]]]]
+    [[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
+    [[`graph_traits<G>::out_edge_iterator`] [Type for iterating over out edges.]]
+    [[`out_edges(v,g)`] [`std::pair<out_edge_iterator, out_edge_iterator>`]]
+    [[`out_degree(v,g)`] [`degree_size_type`]]
+    [[`source(e,g)`] [`vertex_descriptor`]]
+    [[`target(e,g)`] [`vertex_descriptor`]]
+    [[[*[BoostBidirectionalGraph]]]]
+    [[`graph_traits<G>::in_edge_iterator`] [Type for iterating over in edges.]]
+    [[`in_edges(v,g)`] [`std::pair<in_edge_iterator,in_edge_iterator>`]]
+    [[`in_degree(v,g)`] [`degree_size_type`]]
+    [[`degree(v,g)`] [`degree_size_type`]]
+    [[[*[BoostAdjacencyGraph]]]]
+    [[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
+    [[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
+    [[[*[BoostVertexListGraph]]]]
+    [[`graph_traits<G>::vertex_iterator`] [Type for iterating over vertices.]]
+    [[`graph_traits<G>::vertices_size_type`] [Unsigned integer type for the number of vertices.]]
+    [[`vertices(g)`] [`std::pair<vertex_iterator,vertex_iterator>`]]
+    [[`num_vertices(g)`] [`vertices_size_type`]]
+    [[[*[BoostEdgeListGraph]]]]
+    [[`graph_traits<G>::edge_iterator`] [Type for iterating over edges.]]
+    [[`graph_traits<G>::edges_size_type`] [Unsigned integer type for the number of edges.]]
+    [[`edges(g)`] [`std::pair<edge_iterator, edge_iterator>`]]
+    [[`num_edges(g)`] [`edges_size_type`]]
+    [[`source(e,g)`] [`vertex_descriptor`]]
+    [[`target(e,g)`] [`vertex_descriptor`]]
+    [[[*[BoostAdjacencyMatrix]]]]
+    [[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
+    [[[*[BoostMutableGraph]]]]
+    [[`add_vertex(g)`] [`vertex_descriptor`]]
+    [[`clear_vertex(v,g)`] [`void`]]
+    [[`clear_out_edges(v,g)`] [`void`]]
+    [[`clear_in_edges(v,g)`] [`void`]]
+    [[`add_edge(u,v,g)`] [`std::pair<edge_descriptor,bool>`]]
+    [[`remove_edge(u,v,g)`] [`void`]]
+    [[`remove_edge(e,g)`] [`void`]]
+    [[`remove_edge(ei,g)`] [`void`]]
+    [[`remove_edge_if(pred,g)`] [`void`]]
+    [[`remove_out_edge_if(v,pred,g)`] [`void`]]
+    [[`remove_in_edge_if(v,pred,g)`] [`void`]]
+    [[[*[BoostPropertyGraph]]]]
+    [[`property_map<G,Property>::type`] [Type for a mutable property map.]]
+    [[`property_map<G,Property>::const_type`] [Type for a non-mutable property map.]]
+    [[`get(p,g)`] [Function to get a property map.]]
+    [[`get(p,g,x)`] [Get the property value for vertex or edge `x`]]
+    [[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
+    [[[*[BoostMutablePropertyGraph]]]]
+    [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
+    [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
+]
+
+[include descriptor.qbk]
+[include graph.qbk]
+[include incidence_graph.qbk]
+[include bidirectional_graph.qbk]
+[include adjacency_graph.qbk]
+[include vertex_list_graph.qbk]
+[include edge_list_graph.qbk]
+[include adjacency_matrix.qbk]
+[include mutable_graph.qbk]
+[include property_graph.qbk]
+[include mutable_property_graph.qbk]
+
+[h3 Pseudo-Concepts]
+The concepts above describe the type and functional requirements of graphs. However,
+these do not directly common concepts such as "directed graph" or "multigraph". As
+such, there are a number of pseudo-concepts with which we can also describe graph objects.
+
+[h4 Directed and Undirected Graphs]
+The interface that Boost.Graph provides for accessing and manipulating an undirected
+graph is the same as the interface for directed graphs described in the following
+sections, however there are some differences in the behaviour and semantics. For example,
+in a directed graph we can talk about out-edges and in-edges of a vertex. In an
+undirected graph there is no "in" and "out", there are just edges incident to a vertex.
+Nevertheless, in Boost.Graph we still use the `out_edges()` function (or `in_edges()`)
+to access the incident edges in an undirected graph. Similarly, an undirected edge has
+no "source" and "target" but merely an unordered pair of vertices, but we still use
+`source()` and `target()` to access these vertices. The reason Boost.Graph does not
+provide a separate interface for undirected graphs is that many algorithms on directed
+graphs also work on undirected graphs, and it would be inconvenient to have to duplicate
+the algorithms just because of an interface difference. When using undirected graphs
+just mentally disregard the directionality in the function names. The example below
+demonstrates using the `out_edges()`, `source()`, and `target()` with an undirected
+graph. The source code for this example and the following one can be found in
+`examples/undirected.cpp`.
+
+
+    const int V = 2;
+    typedef ... UndirectedGraph;
+    UndirectedGraph graph(V);
+
+    std::cout << "the edges incident to v: ";
+    boost::graph_traits<UndirectedGraph>::out_edge_iterator e, e_end;
+    boost::graph_traits<UndirectedGraph>::vertex_descriptor  s = vertex(0, graph);
+    for(tie(e, e_end) = out_edges(s, graph); e != e_end; ++e) {
+        std::cout << "(" << source(*e, graph)
+                  << "," << target(*e, graph)
+                  << ")" << endl;
+    }
+
+Even though the interface is the same for undirected graphs, there are some behavioral
+differences because edge equality is defined differently. In a directed graph,
+edge /(u,v)/ is never equal to edge /(v,u)/, but in an undirected graph they may
+be equal. If the undirected graph is a multigraph then /(u,v)/ and /(v,u)/ might be
+parallel edges. If the graph is not a multigraph then /(u,v)/ and /(v,u)/ must be the
+same edge.
+
+In the example below the edge equality test will return false for the directed graph
+and true for the undirected graph. The difference also affects the meaning of `add_edge()`.
+In the example below, if we had also written `add_add(v, u, graph)`, this would have
+added a parallel edge between `u` and `v` (provided the graph type allows parallel edges -
+which most do). The difference in edge equality also affects the association of edge
+properties. In the directed graph, the edges /(u,v)/ and /(v,u)/ can have distinct
+weight values, whereas in the undirected graph the weight of /(u,v)/ is the same as
+the weight of /(v,u)/ since they are the same edge.
+
+    typedef ... DirectedGraph;
+    typedef ... UndirectedGraph;
+
+    DirectedGraph digraph(V);
+    UndirectedGraph graph(V)
+
+    {
+        boost::graph_traits<DirectedGraph>::vertex_descriptor u, v;
+        u = vertex(0, digraph);
+        v = vertex(1, digraph);
+        add_edge(digraph, u, v, Weight(1.2));
+        add_edge(digraph, v, u, Weight(2.4));
+        boost::graph_traits<DirectedGraph>::edge_descriptor e1, e2;
+        bool found;
+        tie(e1, found) = edge(u, v, digraph);
+        tie(e2, found) = edge(v, u, digraph);
+        std::cout << "in a directed graph is ";
+        std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+        property_map<DirectedGraph, edge_weight_t>::type
+        weight = get(edge_weight, digraph);
+        cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+        cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+    }
+
+    {
+        boost::graph_traits<UndirectedGraph>::vertex_descriptor u, v;
+        u = vertex(0, graph);
+        v = vertex(1, graph);
+        add_edge(graph, u, v, Weight(3.1));
+        boost::graph_traits<UndirectedGraph>::edge_descriptor e1, e2;
+        bool found;
+        tie(e1, found) = edge(u, v, graph);
+        tie(e2, found) = edge(v, u, graph);
+        std::cout << "in an undirected graph is ";
+        std::cout << "(u,v) == (v,u) ? " << (e1 == e2) << std::endl;
+
+        property_map<UndirectedGraph, edge_weight_t>::type
+        weight = get(edge_weight, graph);
+        cout << "weight[(u,v)] = " << get(weight, e1) << endl;
+        cout << "weight[(v,u)] = " << get(weight, e2) << endl;
+    }
+
+The output is:
+
+[pre
+in a directed graph is (u,v) == (v,u) ? 0
+weight\[(u,v)\] = 1.2
+weight\[(v,u)\] = 2.4
+in an undirected graph is (u,v) == (v,u) ? 1
+weight\[(u,v)\] = 3.1
+weight\[(v,u)\] = 3.1
+]
+
+[h4 Multigraphs]
+A /multigraph/ is a graph (either directed or undirected) that has parallel edges
+between vertices. The Boost.Graph types are mostly unrestrictive about the addition
+of parallel edges, meaning that it is fairly easy to actually create multigraphs
+without any additional work.
+
+There are certain sets of graph types that do not allow the addition of parallel edges.
+Specifically, if the EdgeList and OutEdgeList of an [boost_adjacency_list] models an
+associative container, then the graph cannont be a multigraph.
+
+*Document this a little better*
+
+[h3 Indexed Graphs]
+Although not explicitly documented (yet), there's a concept of a Vertex-Indexed graph
+that has some valid expressions related specifically to operations on vertex index
+property of the graph. The [boost_undirected_graph] class has some addiitonal methods
+that can also be ported.
+
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/incidence_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/incidence_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,95 @@
+[/
+ / Copyright (c) 2007 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 Incidence Graph]
+The IncidenceGraph concept provides an interface for efficient access to the out-edges
+(for directed graphs) or incident edges (for undirected graphs) of each vertex in
+the graph.
+
+[h4 Refinement Of]
+[BootGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `incidence_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::degree_size_type`]
+        [
+            The unsigned integral type used for representing the number of edges incident
+            to a vertex. The `degree_size_type` must meet the requirements of the
+            UnsignedIntegral concept.
+        ]
+    ]
+    [
+        [`graph_traits<G>::out_edge_iterator`]
+        [
+            An out-edge iterator for a vertex /v/ provides access to the out-edges of the
+            vertex. As such, the value type of an out-edge iterator is the `edge_descriptor`
+            type of the graph. An out-edge iterator must meet the requirements of
+            MultiPassInputIterator.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`source(e,g)`]
+        [
+            If `e` represents the edge /(u,v)/, this function returns the vertex descriptor
+            for /u/.
+
+            *Returns* `vertex_descriptor`.
+        ]
+    ]
+    [
+        [`target(e,g)`]
+        [
+            If `e` represents the edge /(u,v)/, this function returns the vertex descriptor
+            for /v/.
+
+            *Returns* `vertex_descriptor`.
+        ]
+    ]
+    [
+        [`out_edges(v,g)`]
+        [
+            Returns an iterator range providing access to the out-edges (for directed graphs)
+            or the incident edges (for undirected graphs). The source vertex of an edge obtained
+            via an out-edge iterator is guaranteed to be the vertex `v` in the call to
+            `out_edges(v,g)`, and the target vertex must be adjacenct to `v`.
+
+            *Returns* `std::pair<out_edge_iterator, out_edge_iterator>`
+        ]
+    ]
+    [
+        [`out_degree(v,g)`]
+        [
+            Returns the number of out-edges (for directed graphs) or the number of incident
+            edges (for undirected graphs) of the vertex `v`.
+
+            *Returns* `degree_size_type`.
+        ]
+    ]
+]
+
+[h4 Notes]
+For undirected graphs, the edge /(u,v)/ is the same as edge /(v,u)/, so without some extra
+guarantee an implementation would be free use any ordering for the pair of vertices in an
+out-edge. For example, if you call `out_edges(u, g)`, and `v` is one of the vertices adjacent
+to `u`, then the implementation would be free to return /(v,u)/ as an out-edge which would be
+non-intuitive and cause trouble for algorithms. Therefore, the extra requirement is added that
+the out-edge connecting `u` and `v` must be given as /(u,v)/ and not /(v,u)/.
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,174 @@
+[/
+ / Copyright (c) 2007 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 Mutable Graph]
+A MutableGraph can be changed via the addition or removal of edges and vertices.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`add_edge(u,v,g)`]
+        [
+            Add a new vertex to the graph. The `vertex_descriptor` for the new vertex is returned.
+
+            *Returns* `vertex_descriptor`
+        ]
+    ]
+    [
+        [`clear_vertex(v,g)`]
+        [
+            Removes all edges incident (both in-edges and out-edges for directed graphs) to the
+            vertex `v`.
+
+            *Returns* `void`
+
+            *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+            *Postcondition* `u` does not appear as a source or target of any edge in `g`.
+        ]
+    ]
+    [
+        [`clear_out_edges(v,g)`]
+        [
+            Removes all edges out-edges of the vertex `v`. For undirected graphs this is functionally
+            equivalent to `clear_vertex(v,g)`.
+
+            *Returns* `void`
+
+            *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+            *Postcondition* `u` does not appear as a source of any edge in `g`.
+        ]
+    ]
+    [
+        [`clear_in_edges(v,g)`]
+        [
+            Removes all edges in-edges of the vertex `v`. For undirected graphs this is functionally
+            equivalent to `clear_vertex(v,g)`.
+
+            *Returns* `void`
+
+            *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+            *Postcondition* `u` does not appear as a target of any edge in `g`.
+        ]
+    ]
+    [
+        [`remove_vertex(v,g)`]
+        [
+            Remove the vertex `v` from the vertex set of the graph. Note that undefined behavior may
+            result if there are edges remaining in the graph who's target is `u`. The `clear_vertex(v,g)`
+            function should be called first to ensure the preconditions.
+
+            *Returns* `vertex_descriptor`
+
+            *Precondition* `u` is a valid `vertex_descriptor` in `g` and does not appear as the source
+            or target of any edge in `g`.
+
+            *Postcondition* `u` is not longer in the vertex set of `g`, nor is `u` a valid descriptor.
+        ]
+    ]
+    [
+        [`add_edge(u,v,g)`]
+        [
+            Inserts the edge /(u,v)/ into the graph, and returns an edge descriptor pointing to the new edge.
+            If the graph disallows parallel edges, and the edge /(u,v)/ is already in the graph, then the boolean
+            flag returned is false and the returned edge descriptor points to the already existing edge. Note
+            that for undirected graphs, /(u,v)/ is the same edge as /(v,u)/, so after a call to the function
+            `add_edge(u,v,g)`, this implies that edge /(u,v)/ will appear in the out-edges of `u` and /(u,v)/
+            (or equivalently /(v,u)/) will appear in the out-edges of `v`. Put another way, `v` will be adjacent
+            to `u` and `u` will be adjacent to `v`.
+
+            *Returns* `vertex_descriptor`
+
+            *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+            *Postcondition* The returned `edge_descriptor` points to a valid edge in `g`.
+        ]
+    ]
+    [
+        [`remove_edge(u,v,g)`]
+        [
+            Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences
+            of /(u,v)/.
+
+            *Returns* `void`
+
+            *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+            *Postcondition* The edge /(u,v)/ is no longer in the edge set of `g`.
+        ]
+    ]
+    [
+        [`remove_edge(e,g)`]
+        [
+            Remove the edge `e` from the graph.
+
+            *Returns* `void`
+
+            *Precondition* `e` is an edge in the graph.
+
+            *Postcondition* The edge `e` is no longer in the edge set of `g`.
+        ]
+    ]
+    [
+        [`remove_edge(ei,g)`]
+        [
+            Remove the edge pointed to by the edge iterator `ei` from the graph. This expression is only required
+            when `g` also models [BoostIncidenceGraph].
+
+            *Returns* `void`
+
+            *Precondition* `*ei` is an edge in the graph.
+
+            *Postcondition* The edge `*ei` is no longer in the edge set of `g`.
+        ]
+    ]
+    [
+        [`remove_edge_if(pred,g)`]
+        [
+            Remove all edges from the graph `g` for which the predicate `pred` returns true.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`remove_out_edge_if(v,pred,g)`]
+        [
+            Remove all out-edges of the vertex `v` for which the predicate `pred` returns true.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`remove_in_edge_if(v,pred,g)`]
+        [
+            Remove all in-edges of the vertex `v` for which the predicate `pred` returns true.
+
+            *Returns* `void`
+        ]
+    ]
+]
+
+[h4 Complexity Guarantees]
+* Vertex insertion is guaranteed to be amortized constant time.
+* Clearing  avertex is /O(E + V)/.
+* Vertex removal is /O(E + V)/.
+* Edge insertion must be either amortized constant time of it can be /O(log(E/V))/ if the insertion checks
+to prevent the addition of parallel edges (which is a "feature" of some graph types).
+* Edge removal is guaranteed to be /O(E)/.
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,64 @@
+[/
+ / Copyright (c) 2007 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 Mutable Property Graph]
+A MutablePropertyGraph is a [BoostMutableGraph] with properties attached internally to the
+vertices and edges. When adding vertices and edges the value of the properties can be given.
+
+[h4 Refinement Of]
+[BoostMutableGraph] and [BoostPropertyGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::vertex_property_type`]
+        [
+            The property type associated with vertices in the graph `G`. This type is not
+            guaranteed to be the same as the `VertexProperties` template parameter.
+        ]
+    ]
+    [
+        [`graph_traits<G>::edge_property_type`]
+        [
+            The property type associated with edges in the graph `G`. This type is not
+            guaranteed to be the same as the `EdgeProperties` template parameter.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`add_vertex(vp,g)`]
+        [
+            Add a new vertex to the graph and copy vertex properties `vp` into the property
+            for the new vertex. The `vertex_descriptor` is returned.
+
+            *Returns* `vertex_descriptor`
+        ]
+    ]
+    [
+        [`add_edge(u,v,ep,g)`]
+        [
+            Inserts the edge /(u,v)/ into the graph, and copies object `ep` into the property
+            for that edge.
+
+            *Returns* `property_traits<property_map<G,Property>::const_type>::value_type`
+
+            *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+            *Postcondition* The returned `edge_descriptor` points to a valid edge in `g`.
+        ]
+    ]
+]
+
+[h4 Complexity Guarantees]
+The `get(p,g)` function must return in constant time.
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,86 @@
+[/
+ / Copyright (c) 2007 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 Property Graph]
+A PropertyGraph is a graph that has some property associated with each of the vertices or edges
+in the graph. As a given graph may have several properties associated with each vertex or edge,
+a /tag/ is used to identity which property is being accessed. The graph provides a function which
+returns a property map object and also the value corresponding to a vertex or edge and its
+indicated property.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`property_map<G, Property>::type`]
+        [
+            The type of the property map for the property specified by `Property`. This type must
+            be a model of [BoostReadWritePropertyMap] with a key type the same as the graph's
+            `vertex_descriptor` or `edge_descriptor` types.
+        ]
+    ]
+    [
+        [`property_map<G, Property>::const_type`]
+        [
+            The type of the property map for the property specified by `Property`. This type must
+            be a model of [BoostReadablePropertyMap] with a key type the same as the graph\'s
+            `vertex_descriptor` or `edge_descriptor` types.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`get(p,g)`]
+        [
+            Returns the property map specified by the property identified by the tag `p`. The parameter
+            `p` is only used to convey type information and has no value.
+
+            *Returns* `property_map<G,Property>::type` if `g` is mutable and
+            `property_map<G,Property>::const_type` otherwise.
+        ]
+    ]
+    [
+        [`get(p,g,x)`]
+        [
+            Returns the property /value/ specified by the type of property tag `p` for the given
+            vertex or edge descriptor `x`. The object `p` is only used to convey type information
+            and has no value. This function is equivalent to `get(get(p,g),x)`.
+
+            *Returns* `property_traits<property_map<G,Property>::const_type>::value_type`
+        ]
+    ]
+    [
+        [`put(p,g,x,v)`]
+        [
+            Set the property /value/ specified by the type of property tag `p` for the given
+            vertex or edge descriptor `x` to the value `v`. The object `p` is only used to
+            convey type information and has no value.
+
+            *Returns* `void`
+        ]
+    ]
+    [
+        [`out_degree(v,g)`]
+        [
+            Returns the number of out-edges (for directed graphs) or the number of incident
+            edges (for undirected graphs) of the vertex `v`.
+
+            *Returns* `degree_size_type`.
+        ]
+    ]
+]
+
+[h4 Complexity Guarantees]
+The `get(p,g)` function must return in constant time.
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_list_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,75 @@
+[/
+ / Copyright (c) 2007 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 Vertex List Graph]
+The VertexListGraph concept refines the [BoostGraph] concept, and adds the requirement
+for efficient traversal of all the vertices in a graph.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<G>::traversal_category`]
+        [
+            This tag type must be convertible to `vertex_list_graph_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<G>::vertex_iterator`]
+        [
+            A vertex iterator (obtained via vertices(g)) provides access to all of the vertices in
+            a graph. A vertex iterator type must meet the requirements of [BoostMultiPassInputIterator].
+            The value type of the vertex iterator must be the vertex descriptor of the graph.
+        ]
+    ]
+    [
+        [`graph_traits<G>::vertices_size_type`]
+        [
+            The unsigned integer type used to represent the number of vertices in the graph.
+        ]
+    ]
+]
+
+[h4 Valid Expressions]
+[table
+    [[Expression] [Description]]
+    [
+        [`vertices(g)`]
+        [
+            Returns an iterator range providing access to all the vertices in the graph `g`.
+
+            *Returns* `std::pair<vertex_iterator, vertex_iterator>`
+        ]
+    ]
+    [
+        [`num_vertices(g)`]
+        [
+            Returns the number of vertices in the graph `g`.
+
+            *Returns* `vertices_size_type`
+        ]
+    ]
+]
+
+[h4 Complexity Guarantees]
+The `vertices(g)` function must return in constant time.
+
+[h4 Design Rationale]
+One issue in the design of this concept is whether to include the refinement from the
+[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+of a graph is orthogonal to traversing out-edges, so it would make sense to have a VertexListGraph
+concept that only includes vertex traversal. However, such a concept would no longer really be a
+graph, but would just be a set, and the STL already has concepts for dealing with such things.
+However, there are many BGL algorithms that need to traverse the vertices and out-edges of a graph,
+so for convenience a concept is needed that groups these requirements together, hence the VertexListGraph
+concept.
+
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitor.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,20 @@
+[/
+ / Copyright (c) 2007 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 Visitor]
+This concept defines the basic requirements of all visitor concepts in the Boost.Graph
+library.
+
+[h4 Refinement Of]
+[SgiCopyConstructible]
+
+[h4 Design Rationale]
+This concpet is provided primarily as a base concept for its refinements. Its sole purpose
+is to require that instances of concepts be copy-constructible, which is how they are
+passed to different graph algorithms.
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/visitors.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,27 @@
+[/
+ / Copyright (c) 2007 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 Visitor Concepts]
+The visitor concepts plays the same role in Boost.Graph as functors play in the STL.
+Functors provide a mechanism for extending an algorithm; for customizing what is done
+at each step of the algorithm. Visitors allow the user to insert their own operations
+at various steps within a graph algorithm. Unlike the STL algorithms, graph algorithms
+typically have multiple event points where one may want to insert a call-back via a
+functor. Therefore visitors do not have a single operator() method like a functor, but
+instead have several methods that correspond to the various event points. Each
+algorithm has a different set of event points, which are described by the following
+visitor concepts:
+
+[include visitor.qbk]
+[include bfs_visitor.qbk]
+[include dfs_visitor.qbk]
+[include dijkstra_visitor.qbk]
+[include bellman_ford_visitor.qbk]
+[include event_visitor.qbk]
+[include event_visitor_list.qbk]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,55 @@
+[/
+ / Copyright (c) 2007 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)
+ /]
+
+[library Boost.Graph
+    [quickbook 1.3]
+    [authors [Siek, Jeremy], [Lee, Lie-Quan], [Lumsdaine, Andrew]]
+    [copyright 2000 2001 Jeremy Siek, Lie-Quan Lee, Andrew Lumsdaine]
+    [category graph]
+    [id graph]
+    [dirname graph]
+    [purpose
+        Graph data structures and algorithms.
+    ]
+    [license
+            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])
+    ]
+]
+
+[/ Templates /]
+[template super[x] '''<superscript>'''[x]'''</superscript>''']
+[template sub[x] '''<subscript>'''[x]'''</subscripts>''']
+
+[template figure[path caption]
+'''
+<mediaobject>
+    <imageobject>
+        <imagedata fileref="'''[path]'''" align="center"/>
+    </imageobject>
+    <caption>
+        <para style="text-align: center">'''[caption]'''</para>
+    </caption>
+</mediaobject>
+'''
+]
+
+
+
+[include sgi_concepts.qbk]
+[include boost_concepts.qbk]
+[include boost_reference.qbk]
+
+[/ Contents ]
+[include introduction.qbk]
+[include history.qbk]
+[include guide/guide.qbk]
+[include concepts/concepts.qbk]
+[include reference/reference.qbk]
+
+[/ [include bibliography.qbk] /]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/adjacency_list.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/adjacency_list.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,480 @@
+[/
+ / Copyright (c) 2007 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 The Adjacency List]
+As mentioned in the Tour, the `adjacency_list` has seven template parameters. Three are
+used to select storage types for the vertex list, the edge list and the out edge list,
+and the remaining three define the interior properties of vertices, edges, and the
+graph itself.
+
+[h2 Choosing the Edgelist and VertexList]
+This section focuses on how to decide which version of the `adjacency_list` class to use in different
+situations. The adjacency_list is like a swiss-army knife in that it can be configured in many ways.
+The parameters that we will focus on in this section are `OutEdgeList` and `VertexList`, which control
+the underlying data structures that will be used to represent the graph. The choice of `OutEdgeList` and
+`VertexList` affects the time complexity of many of the graph operations and the space complexity of the
+graph object.
+
+Boost.Graph uses containers from the STL such as `std::vector`, `std::list`, and `std::set` to represent
+the set of vertices and the adjacency structure (out-edges and in-edges) of the graph. There are several
+selector types that are used to specify the choice of container for `OutEdgeList` and `VertexList`. 
+
+* `vecS` selects `std::vector`.
+* `listS` selects `std::list`.
+* `slistS` selects `std::slist`.
+* `setS` selects `std::set`.
+* `multisetS` selects `std::multiset`.
+* `hash_setS` selects `std::hash_set`.
+
+[h3 Choosing the VertexList Type]
+The VertexList parameter determines what kind of container will be used to represent the vertex set, or
+two-dimensional structure of the graph. The container must model /Sequence/ or /RandomAccessContainer/. In
+general, listS is a good choice if you need to add and remove vertices quickly. The price for this is extra
+space overhead compared to choosing `vecS`.
+
+[h4 Space Complexity of the VertexList]
+The `std::list` has a higher per-vertex space overhead than the `std::vector`, storing three extra pointers
+per vertex.
+
+[h4 Time Complexity of the VertexList]
+The choice of VertexList affects the time complexity of the following operations. 
+
+[table VertexList Storage Options
+	[[Operation] [Performance Considerations]]
+	[
+		[`add_vertex()`]
+		[
+			This operation is amortized constant time for both vecS and listS (implemented with
+			`push_back()`). However, when the VertexList type is `vecS` the time for this operation
+			is occasionally large because the vector will be reallocated and the whole graph copied
+			but is still amortized constant time.
+		]
+	]
+	[
+		[`remove_vertex()`]
+		[
+			This operation is constant time for listS and O(V + E) for vecS. The large time
+			complexity for vecS is because the vertex descriptors (which in this case are indices
+			that correspond to the vertices' place in the vertex list) must be adjusted in the
+			out-edges for the whole graph.
+		]
+	]
+	[
+		[`vertex()`]
+		[
+			This operation is constant time for vecS and for `listS`.
+		]
+	]
+]
+
+[h3 Choosing the OutEdgeList Type]
+The OutEdgeList parameter determines what kind of container will be used to store the out-edges (and
+possibly in-edges) for each vertex in the graph. The containers used for edge lists must either satisfy
+the requirements for Sequence or for AssociativeContainer. 
+
+One of the first things to consider when choosing the OutEdgeList is whether you want `adjacency_list` to
+enforce the absence of parallel edges in the graph (that is, enforce that the graph not become a multi-graph).
+If you want this enforced then use the setS or hash_setS selectors. If you want to represent a
+multi-graph, or know that you will not be inserting parallel edges into the graph, then choose one of
+the Sequence types: `vecS`, `listS`, or `slistS`. You will also want to take into account the differences in
+time and space complexity for the various graph operations. Below we use V for the total number of vertices
+in the graph and E for the total number of edges. Operations not discussed here are constant time. 
+
+[h4 Space Complexity of the OutEdgeList]
+The selection of the OutEdgeList affects the amount of space overhead per edge in the graph object. In the
+order of least space to most space, the selectors are `vecS`, `slistS`, `listS`, and `setS`. 
+
+[h4 Time Complexity of the OutEdgeList]
+In the following description of the time complexity for various operations, we use E/V inside of the "big-O"
+notation to express the length of an out-edge list. Strictly speaking this is not accurate because E/V merely
+gives the average number of edges per vertex in a random graph. The worst-case number of out-edges for a vertex
+is V (unless it is a multi-graph). For sparse graphs E/V is typically much smaller than V and can be considered
+a constant. 
+
+[table OutEdgeList Storage Options
+	[[Operation] [Performance Considerations]]
+	[
+		[`add_edge()`]
+		[
+			When the OutEdgeList is a UniqueAssociativeContainer like `std::set` the absence of
+			parallel edges is enforced when an edge is added. The extra lookup involved has time
+			complexity O(log(E/V)). The OutEdgeList types that model Sequence do not perform this
+			check and therefore add_edge() is amortized constant time. This means that it if you
+			don't care whether the graph has parallel edges, or know that the input to the
+			graph does not contain them, then it is better to use the sequence-based OutEdgeList.
+			The `add_edge()` for the sequence-based OutEdgeList is implemented with `push_front()`
+			or `push_back()`. However, for `std::list` and `std::slist` this operation will
+			typically be faster than with `std::vector` which occasionally reallocates
+			and copies all elements.
+		]
+	]
+	[
+		[`remove_edge()`]
+		[
+			For sequence-based OutEdgeList types this operation is implemented with `std::remove_if()`
+			 which means the average time is E/V. For set-based OutEdgeList types this is implemented
+			with the `erase()` member function, which has average time log(E/V).
+		]
+	]
+	[
+		[`edge()`]
+		[
+			The time complexity for this operation is O(E/V) when the OutEdgeList type is a Sequence
+			and it is O(log(E/V)) when the OutEdgeList type is an AssociativeContainer.
+		]
+	]
+	[
+		[`clear_vertex()`]
+		[
+			For directed graphs with sequence-based OutEdgeList types the time complexity is O(V + E),
+			while for associative container based OutEdgeList types the operation is faster, with
+			time complexity O(V log(E/V)). For undirected graphs this operation is O(E2/V2) or
+			O(E/V log(E/V)).
+		]
+	]
+	[
+		[`remove_vertex()`]
+		[
+			The time complexity for this operation is O(V + E) regardless of the OutEdgeList type.
+		]
+	]
+	[
+		[`out_edge_iterator::operator++()`]
+		[
+			This operation is constant time and exhibits a similar speed ordering as
+			the `out_edge_iterator` with respect to the OutEdgeList selection. 
+		]
+	]
+
+	[
+		[`in_edge_iterator::operator++()`]
+		[
+			This operation is constant time and fast (same speed as incrementing a pointer).
+			The selection of OneD does not affect the speed of this operation. 
+		]
+	]
+	[
+		[`vertex_iterator::operator++()`]
+		[
+			This operation is constant time and exhibits a similar speed ordering as the
+			out_edge_iterator with respect to the OutEdgeList selection. Traversing through the
+			whole edge set is O(V + E). 
+		]
+	]
+	[
+		[`adjacency_iterator::operator++()`]
+		[
+			This operation is constant time and exhibits a similar speed ordering as
+			the out_edge_iterator with respect to the OutEdgeList selection. 
+		]
+	]
+]
+
+[h2 Directed and Undirected Adjacency Lists]
+The `adjacency_list` class can be used to represent both directed and undirected graphs, depending on the
+argument passed to the Directed template parameter. Selecting `directedS` or `bidirectionalS` choose a directed
+graph, whereas `undirectedS` selects the representation for an undirected graph. See Section Undirected Graphs
+for a description of the difference between directed and undirected graphs in Boost.Graph. The `bidirectionalS`
+selector specifies that the graph will provide the `in_edges()` function as well as the `out_edges()` function.
+This imposes twice as much space overhead per edge, which is why `in_edges()` is optional.
+
+[h2 Internal Properties]
+Properties can be attached to the vertices or edges of an `adjacency_list` graph via the property interface.
+The template parameters VertexProperty and EdgeProperty of the `adjacency_list` class are meant to be filled
+by these interior properties.
+
+[note The Boost Graph Library supports two interchangeable methods for specifying interior properties:
+bundled properties and property lists. The former is easier to use and requires less effort, whereas the
+latter is compatible with older, broken compilers and is backward-compatible with Boost versions prior to
+1.32.0. If you absolutely require these compatibility features, read on to learn about property lists.
+Otherwise, we strongly suggest that you read about the bundled properties mechanism.]
+
+One may specify internal properties via property lists, which are built from instances of the property class
+declared as follows. 
+
+ template <class PropertyTag, class T, class NextProperty = no_property> struct property;
+
+The PropertyTag template parameter is a tag class that simply identifies or gives a unique name to the property.
+There are several predefined tags, and it is easy to add more.
+
+ struct vertex_index_t { };
+ struct vertex_index1_t { };
+ struct vertex_index2_t { };
+ struct edge_index_t { };
+ struct graph_name_t { };
+ struct vertex_name_t { };
+ struct edge_name_t { };
+ struct edge_weight_t { };
+ struct edge_weight2_t { };
+ struct edge_capacity_t { };
+ struct edge_residual_capacity_t { };
+ struct edge_reverse_t { };
+ struct vertex_distance_t { };
+ struct vertex_root_t { };
+ struct vertex_all_t { };
+ struct edge_all_t { };
+ struct graph_all_t { };
+ struct vertex_color_t { };
+ struct vertex_rank_t { };
+ struct vertex_predecessor_t { };
+ struct vertex_isomorphism_t { };
+ struct vertex_invariant_t { };
+ struct vertex_invariant1_t { };
+ struct vertex_invariant2_t { };
+ struct vertex_degree_t { };
+ struct vertex_out_degree_t { };
+ struct vertex_in_degree_t { };
+ struct vertex_discover_time_t { };
+ struct vertex_finish_time_t { };
+
+The T template parameter of property specifies the type of the property values. The type T must be Default
+Constructible, Assignable, and Copy Constructible. Like the containers of the C++ Standard Library, the
+property objects of type T are held by-value inside of the graph.
+
+The NextProperty parameter allows property types to be nested, so that an arbitrary number of properties
+can be attached to the same graph. 
+
+The following code shows how a vertex and edge property type can be assembled and used to create a graph type.
+We have attached a distance property with values of type float and a name property with values of type
+std::string to the vertices of the graph. We have attached a weight property with values of type float to
+the edges of the graph. 
+
+ // specify property types fora graph
+ typedef property<vertex_distance_t, float, property<vertex_name_t, std::string> > VertexProperty;
+ typedef property<edge_weight_t, float> EdgeProperty;
+
+ // specify the graph has having the above properties
+ typedef adjacency_list<mapS, vecS, undirectedS, 
+                        VertexProperty, EdgeProperty> Graph;
+
+ // instantiate the graph with N (a compile-time constant integer) vertices
+ Graph g(N);
+
+The property values are then read from and written to using property maps. See Section Interior Properties
+for a description of how to obtain property maps from a graph, and read Section Property Maps for how to use
+property maps.
+
+[h3 Built-in Vertex and Edge Properties]
+Even if a graph type is instantiated without any user-specified properties, Boost.Graph will define a few
+default properties for both vertices and edges. These are always available in algorithms through the
+property map interfaces.
+
+Vertices have the following properties:
+
+Edges have the following properties:
+
+[h3 Custom Edge Properties]
+Creating your own property types and properties is easy; just define a tag class for your new property.
+The property tag class will need to define num with a unique integer ID, and kind which should be either
+edge_property_tag, vertex_property_tag, or graph_property_tag.
+
+ struct flow_t {
+   typedef edge_property_tag kind;
+ };
+
+ struct capacity_t { 
+   typedef edge_property_tag kind;
+ };
+
+You can also use enum's instead of struct's to create tag types. Create an enum type for each property.
+The first part of the name of the enum type must be edge, vertex, or graph followed by an underscore,
+the new property name, and a _t at the end. Inside the enum, define a value with the same name minus the
+_t. Then invoke the BOOST_INSTALL_PROPERTY macro. 
+
+ enum edge_flow_t { edge_flow };
+ enum edge_capacity_t { edge_capacity };
+
+ namespace boost {
+   BOOST_INSTALL_PROPERTY(edge, flow);
+   BOOST_INSTALL_PROPERTY(edge, capacity);
+ }
+
+Now you can use your new property tag in the definition of properties just as you would one of the builtin tags. 
+
+ typedef property<capacity_t, int> Cap;
+ typedef property<flow_t, int, Cap> EdgeProperty;
+ typedef adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;
+
+Just as before, the property maps for these properties can be obtained from the graph via the get(Property, g) function. 
+
+ property_map<Graph, capacity_t>::type capacity = get(capacity_t(), G);
+ property_map<Graph, flow_t>::type flow = get(flow_t(), G);
+
+The file edge_property.cpp shows the complete source code for this example. 
+  
+[h3 Custom Vertex Properties]
+Creating your own properties to attach to vertices is just as easy as for edges. Here we want to attach people's
+first names to the vertices in the graph. 
+
+ struct first_name_t {
+   typedef vertex_property_tag kind;
+ };
+
+Now we can use the new tag in the property class and use that in the assembly of a graph type. The following
+code shows creating the graph type, and then creating the graph object. We fill in the edges and also assign
+names to the vertices. The edges will represent "who owes who";
+
+ typedef property<first_name_t, std::string> FirstNameProperty;
+ typedef adjacency_list<vecS, vecS, directedS, 
+                        FirstNameProperty> MyGraphType;
+
+ typedef pair<int,int> Pair;
+ Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3), 
+                         Pair(0,4), Pair(2,0), Pair(3,0), 
+                         Pair(2,4), Pair(3,1), Pair(3,4), 
+                         Pair(4,0), Pair(4,1) };
+    
+ MyGraphType G(5);
+ for (int i = 0; i < 11; ++i) {
+   add_edge(edge_array[i].first, edge_array[i].second, G);
+ }
+
+ property_map<MyGraphType, first_name_t>::type name = get(first_name_t(), G);
+
+ boost::put(name, 0, "Jeremy");
+ boost::put(name, 1, "Rich");
+ boost::put(name, 2, "Andrew");
+ boost::put(name, 3, "Jeff");
+ name[4] = "Kinis";  // you can also use the operator[] too
+
+ who_owes_who(edges(G).first, edges(G).second, G);
+
+The `who_owes_who()` function written for this example was implemented in a generic style. The input is
+templated so we do not know the actual graph type. To find out the type of the property map for our
+first-name property, we need to use the property_map traits class. The const_type is used since the graph
+parameter is const. Once we have the property map type, we can deduce the value type of the property using
+the property_traits class. In this example, we know that the property's value type will be `std::string`, but
+written in this generic fashion the `who_owes_who()` function could work with other property value types. 
+
+ template <class EdgeIter, class Graph>
+ void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
+ {
+   // Access the propety acessor type for this graph
+   typedef typename property_map<Graph, first_name_t>::const_type NameMap;
+   typedef typename boost::property_traits<NameMap>::value_type NameType;
+
+   NameMap name = get(first_name, G);
+   NameType src_name, targ_name;
+
+   while (first != last) {
+     src_name = boost::get(name, source(*first, G));
+     targ_name = boost::get(name, target(*first, G));
+     cout << src_name << " owes " 
+          << targ_name << " some money" << "\n";
+     ++first;
+   }
+ }
+
+The output is: 
+
+ Jeremy owes Rich some money
+ Jeremy owes Andrew some money
+ Jeremy owes Jeff some money
+ Jeremy owes Kinis some money
+ Andrew owes Jeremy some money
+ Andrew owes Kinis some money
+ Jeff owes Jeremy some money
+ Jeff owes Rich some money
+ Jeff owes Kinis some money
+ Kinis owes Jeremy some money
+ Kinis owes Rich some money
+
+The complete source code to this example is in the file interior_property_map.cpp. 
+
+[h3 Customizing the Adjacency List Storage]
+The `adjacency_list` is constructed out of two kinds of containers. One type of container to hold all the
+vertices in the graph, and another type of container for the out-edge list (and potentially in-edge list)
+for each vertex. Boost.Graph provides selector classes that allow the user to choose between several of the
+containers from the STL. It is also possible to use your own container types. When customizing the VertexList
+you need to define a container generator as described below. When customizing the OutEdgeList you will need
+to define a container generator and the parallel edge traits. The file container_gen.cpp has an example of
+how to use a custom storage type.
+
+[h4 Container Generator]
+The `adjacency_list` class uses a traits class called `container_gen` to map the OutEdgeList and VertexList
+selectors to the actual container types used for the graph storage. The default version of the traits class
+is listed below, along with an example of how the class is specialized for the listS selector.
+
+ namespace boost {
+   template <class Selector, class ValueType>
+   struct container_gen { };
+
+   template <class ValueType>
+   struct container_gen<listS, ValueType> {
+     typedef std::list<ValueType> type;
+   };
+ }
+
+To use some other container of your choice, define a selector class and then specialize the `container_gen`
+for your selector.
+
+ struct custom_containerS { }; // your selector
+
+ namespace boost {
+   // the specialization for your selector
+   template <class ValueType>
+   struct container_gen<custom_containerS, ValueType> {
+     typedef custom_container<ValueType> type;
+   };
+ }
+
+There may also be situations when you want to use a container that has more template parameters than
+just ValueType. For instance, you may want to supply the allocator type. One way to do this is to
+hard-code in the extra parameters within the specialization of container_gen. However, if you want more
+flexibility then you can add a template parameter to the selector class. In the code below we show how
+to create a selector that lets you specify the allocator to be used with the `std::list`. 
+
+ template <class Allocator>
+ struct list_with_allocatorS { };
+
+ namespace boost {
+   template <class Alloc, class ValueType>
+   struct container_gen<list_with_allocatorS<Alloc>, ValueType>
+   {
+     typedef typename Alloc::template rebind<ValueType>::other Allocator;
+     typedef std::list<ValueType, Allocator> type;
+   };
+ }
+
+ // now you can define a graph using std::list and a specific allocator  
+ typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
+
+[h4 Push and Erase for the Custom Container]
+You must also tell the `adjacency_list` how elements can be efficiently added and removed from the
+custom container. This is accomplished by overloading the `push()` and `erase()` functions for the custom
+container type. The `push()` function should return an iterator pointing to the newly inserted element
+and a bool flag saying whether the edge was inserted.
+
+ template <class T>
+ std::pair<typename custom_container<T>::iterator, bool>
+ push(custom_container<T>& c, const T& v)
+ {
+   // this implementation may need to change for your container
+   c.push_back(v);
+   return std::make_pair(boost::prior(c.end()), true);
+ }
+
+ template <class T>
+ void erase(custom_container<T>& c, const T& x)
+ {
+   // this implementation may need to change for your container
+   c.erase(std::remove(c.begin(), c.end(), x), c.end());
+ }
+
+There are default `push()` and `erase()` functions implemented for the STL container types. 
+
+[h4 Parallel Edge Traits]
+When customizing the OutEdgeList, you must also specialize the `parallel_edge_traits` class to specify whether
+the container type allows parallel edges (and is a Sequence) or if the container does not allow parallel
+edges (and is an AssociativeContainer). 
+
+ template <>
+ struct parallel_edge_traits<custom_containerS> {
+   typedef allow_parallel_edge_tag type;
+ };
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/directed_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/directed_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,371 @@
+[/
+ / Copyright (c) 2007 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 Directed Graphs]
+Like the previous section, here we take a look at how to solve different
+types graph problems using the Boost.Graph library. In this case however,
+the problems being addressed are better modeled with directed graphs. A
+directed graph (also a /digraph/) is one in which edges can only be traversed
+in a specific direction.
+
+In this section we are concerned with /dependency graphs/. A dependency graph
+describes a relationship between two entities in which one (/source/) requires
+a second (/target/). The source is said to be dependant upon the target.
+Dependency graphs arise in many, many real-world situations such as source
+code analysis, software installation, "tech-trees" in computer games, etc.
+In this example, we will look at a common dependency graph: dependencies
+between software documents and build targets.
+
+[h3 File Dependencies]
+If you've ever typed `make` and wondered how the program decides the order
+tasks to build, then this tutorial is for you. The make software relies on
+dependency information explicitly encoded into Makefiles. Binaries (executable
+programs and libraries) depend on sets of source files. Source files, which
+implement program features, depend on header files, which expose type and
+function declarations. These, in turn, might depend on generated source files
+generated by `lex`, `yacc` or any other of an assortment of code-generating
+tools. These dependencies can be modeled with a directed graph.
+
+For this example, we're actually going to use some of the files that actually
+implement the examples described in this user's guide. Their dependencies are
+shown in figure 1. Path names have been omitted for readability.
+
+[$images/guide/files.png]
+
+From this graph, it should be relatively easy to see that the build should
+start at the bottom and proceed "upwards" with the executable programs being
+built last - maybe. There are actually two different approaches to bulding
+these programs:
+
+* One at a time. This is probably what you're used to seeing. The compiler
+builds file A, followed by file B, and finally file C.
+* In parallel. If you're lucky enough to have a multi-processor computer
+available to you we might be able to process (compile) a number of different
+files at the same time by distributing the tasks to different processors.
+
+The solution to both of these problems is addressed by topologically sorting
+the graph. This provies the schedule of files to be processed by ordering
+the vertices based on their dependencies.
+
+A third problem we might encounter is that of cycles in the dependency
+graph. Cycles are bad since topological sorts will not work in their presence.
+
+[h4 Makefiles and Graphs]
+The first step in implementing a make-ordering for source files is acquiring
+some data. For this example, we our program will parse files in a stripped down,
+Makefile-like format. The input looks something like something like this.
+
+[pre
+undirected_graph.hpp :  adjacency_list.hpp
+directed_graph.hpp :    adjacency_list.hpp
+movies.hpp :            undirected_graph.hpp
+movies.cpp :            movies.hpp tokenizer.hpp
+kevin_bacon.cpp :       movies.hpp visitors.hpp breadth_first_search.hpp
+kevin_bacon.exe :       movies.cpp kevin_bacon.cpp
+build_order.cpp :       directed_graph.hpp topological_sort.hpp
+build_order.exe :       build_order.cpp
+]
+
+Obviously, we're going to have to build a parser for this input format. Just as
+before our program starts by defining aliases for commonly used template types.
+
+ struct Target;
+
+ typedef boost::directed_graph<Target> Graph;
+ typedef Graph::vertex_descriptor Vertex;
+ typedef Graph::edge_descriptor Edge;
+
+In this graph, vertex properties are encapsulated in a `Target` structure. For
+this application, a target is any named file that might appear in the dependency
+graph. Unlike the previous example, we really don't have any need for edge propreties,
+so we can simply omit that template parameter. The `Target` is defined as:
+
+ struct Target
+ {
+   int index;
+   std::string name;
+ };
+
+[note
+If you think you're seeing some similarities between the previous example, and this
+one... just wait. There are a number of common properties and tasks in many graph
+related problems such as indexing vertices, providing name labels, etc. Pay special
+attention to the method of adding vertices to the graph - the mapping of a unique
+name to a vertex is nearly ubiquitous in the setup of graph problems.
+]
+
+Likewise, we'll go ahead and predefine a property map that will be used later.
+We also need a mapping of target name to vertex so we don't duplicate vertices
+and have a convenient lookup tool later on.
+
+ typedef boost::property_map<Graph::type, int Target::*>::type TargetIndexMap;
+ typedef std::map<std::string, Vertex> TargetMap;
+
+We can now start building a program to parse the input data and build a dependency
+graph.
+
+ using namespace std;
+ using namespace boost;
+
+ int main()
+ {
+   typedef char_separator<char> separator;
+   typedef tokenizer<separator> tokenizer;
+
+   Graph grapg;
+   TargetMap targets;
+
+   for(string line; getline(cin, line); ) {
+     // skip comment and blank lines
+     if(line[0] == '#' || line.empty()) {
+       continue;
+     }
+
+     // split the string on the dependency
+     size_t index = line.find_first_of(':');
+     if(index == string::npos) {
+       continue;
+     }
+     string target = trim_copy(line.substr(0, index));
+     string deps = trim_copy(line.substr(index + 1));
+
+     // add the target to the build graph
+     Vertex u = add_target(graph, targets, target);
+
+     // tokenize the dependencies
+     separator sep(" \t");
+     tokenizer tok(deps, sep);
+     tokenizer::iterator i = tok.begin(), j = tok.end();
+     for( ; i != j; ++i) {
+       string dep = *i;
+
+       // add this dependency as a target
+       Vertex v = add_target(graph, targets, dep);
+
+       // add the edge
+       add_dependency(graph, u, v);
+     }
+   }
+
+   // ...to be continued...
+
+This is a fairly large chunk of code that implements input parsing and graph construction
+with the help of the `add_target()` and `add_dependency()` functions. Essentially, this
+snippet creates a vertex (target) for each file named in the input file. A dependency
+edge is added between the first target (preceeding the ':' character) and each subsequent
+target (white space separated list following the ':'). The `add_target()` and `add_dependency()`
+method are implemented as:
+
+ Vertex add_target(Graph& graph, TargetMap& targets, const string& name)
+ {
+   Vertex v;
+   TargetMap::iterator it;
+   bool inserted;
+   tie(it, inserted) = targets.insert(make_pair(name, Vertex()));
+   if(inserted) {
+     v = add_vertex(graph);
+     it->second = v;
+
+     graph[v].index = num_vertices(graph) - 1;
+     graph[v].name = name;
+   }
+   else {
+     v = it->second;
+   }
+   return v;
+ }
+
+You may notice that the `add_target()` function is nearly line-for-line identical to the
+`add_actor()` function in the previous example. This is no coincidence - both functions
+do exactly the same thing. They associate a vertex with a unique name and assign it an
+index that we can use later for various graph algorithms.
+
+ Edge add_dependency(Graph& graph, Vertex u, Vertex v)
+ {
+   return add_edge(v, u, graph).first;
+ }
+
+The `add_dependency()` method is considerably more terse than its undirected counter part,
+but essentially does the same thing. There is one very important difference, however:
+the direction of the edge is reversed to create a subtly different graph. Although
+the method is called to indicate that vertex `u` dependes on vertex `v`, the added edge
+actually indicates that vertex `v` satisfies the dependency of vertex `u`. In fact, this
+is the reverse of the original graph and is shown in Figure 2.
+
+[$images/guide/reverse.png]
+
+[h4 Obtaining the Make Order]
+We are now ready to compute the make order by running a topological sort. Thanks to a
+canned implementation, this is trivial.
+
+ int main()
+ {
+   // ...continued from above...
+
+   TargetIndexMap indices = get(&Target::index, graph);
+
+   typedef list<Vertex> MakeOrder;
+   MakeOrder order;
+   topological_sort(graph, front_inserter(order), vertex_index_map(indices));
+
+   BuildOrder::iterator i = order.begin(), j = order.end();
+   for( ; i != j; ++i) {
+     cout << graph[*i] << "\n";
+   }
+ }
+
+The `topological_sort()` algorithm takes an output iterator as the second parameter.
+Here, we use a standard front insertion iterator to prepend each target to the make
+order. The `vertex_index_map()` named parameter is also required for the implementation.
+After computation, we simply print the ordering to standard output.
+
+[h4 parallel Compilation]
+What if we have multiple processors available? Surely there is a way to determine if
+we can compile several independent files simultaneously, thereby reducing the overall
+build time. In fact, there is. Consider rephrasing the question to "what is the earliest
+time that a file can be built assuming that an unlimited number of files can be built
+at the same time?". In our simplified example, the only criteria for when a file can
+be built is that it has no dependencies (i.e., in edges). Further simplifiying the
+example, we assume that each file takes the same amount of time to build (1 time unit).
+
+For parallel compilation, we can build all files with zero dependencies in the first
+time unit at the same time. For each file, the time at which it can be built is one
+more than the maximum build time of the files on which it depends. In this example,
+`adjacency_list.hpp` is one of the files that will compile first (in parallel).
+The `directed_graph.hpp` file will compile in the second time step, and `build_order.cpp`
+in the third.
+
+To implement this, we need a vector that represents the time slots in which each vertex
+will be built. By visiting the vertices in topological order, we ensure that we can
+assigned the correct time slot to each vertex since values "propogate" down the ordering.
+Just for fun, we'll merge the time ordering with the output so we can see a) the order
+in which each file is built and b) the time slot it could be built in.
+
+ int main()
+ {
+   // ...continued from above...
+  vector<int> time(num_vertices(graph), 0);
+   BuildOrder::iterator i = order.begin(), j = order.end();
+   for( ; i != j; ++i) {
+     int slot = -1;
+     Graph::in_edge_iterator j, k;
+     for(tie(j, k) = in_edges(*i, graph); j != k; ++j) {
+       Vertex v = source(*j, graph);
+       slot = std::max(time[graph[v].index], slot);
+     }
+     time[g[*i].index] = slot + 1;
+
+     cout << g[*i].name << "\t[" << time[g[*i].index] << "]\n";
+   }
+ }
+
+This is a code may be a little dense, but demonstrates two important aspects of
+the Boost.Graph library. First this demonstrates the importantance of vertex
+indices. Despite their instability with mutable graphs, many (most?) graph algorithms
+use vertex indices to efficiently associate extra data with a vertex. In fact, this
+approach is so ubiquitous in the examples that it leads many to believe the
+`vertex_descriptor` is always the index of a vertex.
+
+[warning
+A `vertex_descriptor` is *not* its index in the graphs container of vectors!
+]
+
+The second important aspect this demonstrates is the construction of an /external
+property/ for vertices. Although we don't use the `time` vector in any additional
+computations, we could easily turn it into a property map for use with other
+algorithms.
+
+The output might something like this:
+
+[pre
+$ ./make_order < files
+topological_sort.hpp        [0]
+breadth_first_search.hpp    [0]
+visitors.hpp                [0]
+tokenizer.hpp               [0]
+adjacency_list.hpp          [0]
+directed_graph.hpp          [1]
+build_order.cpp             [2]
+build_order.exe             [3]
+undirected_graph.hpp        [1]
+movies.hpp                  [2]
+kevin_bacon.cpp             [3]
+movies.cpp                  [3]
+kevin_bacon.exe             [4]
+]
+
+Although it probably won't since I doctored the tabbing for display purposes.
+
+[h4 Finding Cycles]
+Admittedly, cycles in dependency graphs for software probably don't occur so often
+that we need to develop special software to find them. However, if the dependency
+graph is big (think about all the source code, binaries, data files and thier
+dependencies that constitute a typical Linux distribution), then its possible that
+cycles creep into the graph. It might be nice to determine if there is such a cycle
+before actually trying to build it.
+
+To do this, we are going to provide a customized visitor for a depth-first search (DFS).
+Just like the custom visitors in our undirected graph examples, we overload a visitor
+event (here, the `back_edge` event) to indicate that a cycle has been found. Using the
+same setup as before, our visitor follows:
+
+ struct CycleDetector : public dfs_visitor<>
+ {
+   CycleDetector(bool& c)
+     : has_cycle(c)
+   {}
+
+   template <class Edge, class Graph>
+   void back_edge(Edge, Graph&)
+   {
+     has_cycle = true;
+   }
+
+   bool& has_cycle;
+ };
+
+ CycleDetector detect_cycles(bool& c)
+ { return CycleDetector(c); }
+
+That's it... When the `back_edge()` method is called, we know that a cycle exists
+in the graph. This literally indicates that there is an edge to a vertex that we
+have already visited, hence: a cycle. We also provide a helper function that
+instantiates the visitor.
+
+Using the cycle-detecting visitor is just as easy as before. After constructing the
+graph, we would find the following in the `main()` program.
+
+ int main()
+ {
+   // ...continued from above...
+
+   TargetIndexMap indices = get(&Target::index, g);
+
+   bool cycle = false;
+   depth_first_search(g,
+     vertex_index_map(indices).
+     visitor(detect_cycles(cycle)));
+   cout << "has cycle: " << cycle << "\n";
+ }
+
+Unfortunately, our test input file doesn't currently contain any cycles - a sign of
+good engineering - so we'll have to add one. Add the following lines to the input
+to create a completely superfluous cycle.
+
+[pre
+movies.exe :        kevin_bacon.exe
+kevin_bacon.exe :   movies.exe
+]
+
+Running the program on the modified input should yield:
+
+[pre
+$ ./cycle < files
+has cycle: 1
+]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/guide.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/guide.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,14 @@
+[/
+ / Copyright (c) 2007 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 User's Guide]
+
+[include undirected_graph.qbk]
+[include directed_graph.qbk]
+[include adjacency_list.qbk]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/guide/undirected_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/guide/undirected_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,473 @@
+[/
+ / Copyright (c) 2007 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 Undirected Graphs]
+In this section, our example revolves around a particular type of /social network/.
+A social network is a graph that models the relationships between people. Specifically,
+in this example we are looking at a graph that connects co-stars of films.
+
+[h3 Co-Star Graphs]
+The first example problem we want to look at is the "Six Degrees of Kevin Bacon"
+problem. In this problem, two actors are related if they appear in the same movie,
+which can be trivially represented using an undirected graph.
+
+For the Six Degrees problem, we define a citation graph such that each vertex in
+the graph represents an actor, and each edge connects two actors if and only if
+they appear in the same movie. Consider the example in Figure 1. Here we have
+ten relatively well-known actors and the movies in which they appear together -
+and yes, Kevin Bacon is actually in /Animal House/ (he plays a snotty Omega pledge
+in his film debut).
+
+[$images/guide/movie.png]
+
+Although this is a relatively simple graph, it isn't hard to imagine that it
+scales up fairly quickly. Consider what would happen if we added all of Kevin
+Bacon's co-stars from major motion picture in which he starred - and all of
+their co-stars. It's not hard to imagine that only three iterations might
+actually encompass all of Hollywood and beyond (Bollywood?). So what can we do
+with these graphs?
+
+For starters, we can identify two different problems of the "Six Degrees".
+
+* How far is every actor in the graph from Kevin Bacon? This gives us the number
+of steps between Mr. Bacon and any other actor. The distances from a central actor
+can give clues to the size (especially the diameter) of a graph.
+* What is the "fastest" way to travel along the co-star graph from Kevin Bacon
+to any other actor? This is more commonly known as the "Six Degrees of Kevin
+Bacon Game".
+
+These are actually two different instances of the same problem and can be solved
+using the same algorithm - a simple breadth-first search (BFS).
+
+[note
+The term "six degrees of separation" refers to the total distance one must travel
+in a social network to get from one's self to any other person in the network.
+This notion is supported through a number of social experiments, namely that of
+Stanley Milgram who coined the term "small world" with respect to social networks.
+His experiment showed that Americans are connected, on average by six friendships.
+The notion of a "small world" social network is now nearly synonymous with a
+graph having an average degree of connectivity (formally known as its /mean geodesic
+distance/) of just six steps.
+
+On a side note, the name "Six Degrees of Kevin Bacon" can be attributed to a
+producer on /The Jon Stewart Show/ when the creators (students from Abright
+College) made an appearence to discuss and demonstrate the concept.
+]
+
+[h4 Actors, Movies, and Graphs]
+
+Our program begins by inlcuding required headers and creating some convenient
+type aliases.
+
+ #include <string>
+ #include <map>
+ #include <boost/graph/undirected_graph.hpp>
+ #include <boost/graph/breadth_first_search.hpp>
+
+ struct Actor;
+ struct Movie;
+
+ typedef boost::undirected_graph<Actor, Movie> Graph;
+ typedef Graph::vertex_descriptor Vertex;
+ typedef Graph::edge_descriptor Edge;
+
+In this snippet, our `Actor` structure is going to represent the properties of each
+vertex in the graph while the `Movie` structure encapsulates edge information (i.e.,
+the movie that two actors appear in).
+
+The graph itself is defined by the type `boost::undirected_graph<Actor, Movie>`.
+Essentially, this states that each vertex will have properties given in the `Actor`
+structure, and that edges will have properties in the `Movie` structure. We also
+create some aliases for the graph's vertex and edge descriptors.
+
+[important
+Many of the examples in the Boost Graph Library treat vertex descriptors as the
+index of a vertex within the graph. It must be noted however, that this is not
+a reliable approach to indexing vertices and /will not/ work with the `undirected_graph`
+and `directed_graph` classes. Try to get in the habit of thinking of vertex and
+edge descriptors as opaque types and values - they are simply keys that provide
+access to the properties of their respective types.
+]
+
+In order to fully model our problem, we need to finish defining the `Actor` and
+`Movie` structures for our graph.
+
+ struct Actor
+ {
+   int distance;
+   std::string name;
+ };
+
+ struct Movie
+ {
+   std::string name;
+ };
+
+In this example, we are "internalizing" a couple of properties for each vertex.
+The `Actor::distance` property will be used to record the distance from each actor
+to Kevin Bacon. The `Actor::name` and `Movie::name` properties should be fairly
+self-explanatory. However in this example, we are going to require that all actors
+have unique names. We'll see why in a bit.
+
+We're also going to define a number of other types related to the graphs properties:
+/property maps/. These maps provide a mechanism for accessing the interior and exterior
+properties of vertices and edges in a uniform manner. In this example, all of the
+vertex and edge properties are internal, but we could easily make them external and
+have the program run just as quickly.
+
+ typedef boost::property_map<Graph, int Actor::*>::type ActorDistanceMap;
+
+The first template argument `Graph` defines the type of the graph that
+the property map is going to access. The second template argument with the somewhat
+peculiar syntax is the type of the property. These are pointers to `Actor` member
+variables of type `int`.
+
+Now that the preliminaries are out of the way, we need to concentrate on the construction
+of our graph. For this task, we're going to need another data structure that maps actor
+names to vertices in the graph. We're going to use this to prevent adding mulitple
+vertices for the same actor and later, to find the vertex in the graph that corresponds to
+Kevin Bacon.
+
+This program reads an input file from standard input. The input file is given in an edge-
+list format with semicolon separators. Each line corresponds to an edge, giving the two
+actors as the endpoints and the name of the movie they both appear in. For example:
+[pre
+Tim Matheson;Kevin Bacon;Animal House (1978)
+John Belushi;Kevin Bacon;Animal House (1978)
+Carrie Fisher;John Belushi;The Blues Brothers (1980)
+Mark Hamill;Carrie Fisher;Star Wars (1977)
+]
+
+The following function implements the input parser for the graph data.
+
+ #include <boost/tokenizer.hpp>
+
+ // the very important actor-to-vertex mapping
+ typedef std::map<std::string, Vertex> ActorMap;
+
+ using namespace std;
+ using namespace boost;
+
+ void build_costar_graph(istream& is, Graph& graph, ActorMap&)
+ {
+   // pull all of the data from std in.
+   for(string line; getline(is, line); ) {
+     // skip any comment or blank lines
+     if(line[0] == '#' || line.empty()) {
+       continue;
+     }
+
+     // tokenize the string
+     char_delimiters_separator<char> sep(false, "", ";");
+     tokenizer<> tok(line, sep);
+     tokenizer<>::iterator i = tok.begin();
+
+     // grab the names of the two actors and the movie title
+     string first = *i++;
+     string second = *i++;
+     string movie = *i++;
+
+     // get the vertices associated with the actors adding them
+     // to the graph if necessary
+     Vertex
+       u = add_actor(g, actors, first),
+       v = add_actor(g, actors, second);
+
+     // create an edge (movie) linking the actors
+     add_movie(g, u, v, movie);
+   }
+ }
+
+To finish graph construction, we need to implement the `add_actor()` and `add_movie()`
+functions:
+
+ Vertex add_actor(Graph& graph, ActorMap& actors, const string& name)
+ {
+   // try inserting the actors name into the actors map
+   Vertex v;
+   ActorMap::iterator it;
+   bool inserted;
+   tie(it, inserted) = actors.insert(make_pair(name, Vertex()));
+
+   if(inserted) {
+     // if the vertex was inserted into the map, we need to
+     // create a new vertex in the graph and make sure that
+    // the map references the correct vertex
+     v = add_vertex(graph);
+     it->second = v;
+
+     // configure the vertex properties
+     g[v].name = name;
+   }
+   else {
+     // otherwise, the name is already in the map, so
+     // return the vertex associated with it
+     v = it->second;
+   }
+
+   return v;
+ }
+
+ Edge add_movie(Graph& g, Vertex u, Vertex v, const string& movie)
+ {
+   Edge e;
+   bool inserted;
+   tie(e, inserted) = add_edge(u, v, g);
+   if(inserted) {
+     g[e].name = movie;
+   }
+   return e;
+ }
+
+There are several important features of these two functions to pay special attention to.
+The first is the use of the `tie()` constructor. This is arguably one of the most useful
+and most used functions (it's actually a type) in Boost.Graph. It simply takes the
+values returned in a `std::pair` and assigns them to the variables passed to the
+constructor. In this function it is more or less equivalent to:
+
+ std::pair<ActorMap::Iterator, bool> x = actors.insert(...);
+ ActorMap::iterator iter = x.first;
+ bool inserted = x.second;
+
+The second (and most important) is the assignment of the vertex properties. These
+two lines of code use the /bundled properties/ syntax to assign both an index
+and a name to the vertex that was just added to the graph.
+
+Our main program looks like this:
+
+ int main()
+ {
+   Graph graph;
+   ActorMap actors;
+   build_costar_graph(cin, graph, actors);
+
+   // ...to be continued...
+ }
+
+[h4 Distance To Kevin Bacon]
+Now, all we have left to do is assign distances to Kevin Bacon. To do this, we're going
+to use a breadth-first search (starting from Kevin Bacon) and simply record the "depth"
+of each vertex as the distance from Kevin to every other actor. Fortunately, Boost.Graph
+gives us lots of help in this area so we don't have to write much more code. Let's look
+at the main program.
+
+ int main()
+ {
+   // ...continued from above...
+
+   // find kevin (our starting point)
+   Vertex kevin = actors["Kevin Bacon"];
+
+   // get a property map and zero out kevin's distance-to-self
+   ActorDistanceMap distances = get(&Actor::distance, graph)
+   distances[kevin] = 0;
+
+   breadth_first_search(graph, kevin,
+     visitor(
+        make_bfs_visitor(record_distances(distances, on_tree_edge()))
+        )
+   );
+
+   // ...to be continued...
+
+This is actually the "meat" of the solution. First, get a reference to the vertex that
+represents Kevin Bacon - our `ActorMap` is very good at this. Next we have to get the
+property map for our actor's distances so we can set Kevin's distance to zero. In this
+case, the actor's distance is actually a /bundled property/ of the `Actor` structure.
+
+Finally, we invoke the `breadth_first_search()` on `graph` with `kevin` as our starting
+vertex. The `visitor()` function is actually a /named parameter/ - a function that assigns
+a value to a parameter of an algorithm. In this case, the parameter is the /visitor/
+parameter (as indicated by the function name). The value is in turn provided by the
+`make_bfs_visitor()` function, which creates visitor object depnding on the parameters.
+The `record_distances()` function creates a `distance_recorder` visitor. The `distances`
+argument is our property map, indicating that the visitor will operate on those values.
+Finally, the `on_tree_edge()` call instructs the `distance_recorder` to record distances
+when a new edge in the BFS tree is encountered. This BFS visitor will effectively compute
+the distance from a root vertex to all other vertices in the graph.
+
+This is a somewhat verbose way of writing the code. We could write it a little more
+succinctly, although it's somewhat less readable:
+
+ graph[kevin].distance = 0;
+ breadth_first_search(graph, kevin,
+    visitor(make_bfs_visitor(record_distances(get(&Actor::distance, graph), on_tree_edge())))
+ );
+
+After finishing, each vertex's distance property will be assigned. All there is left to do
+is display the numbers:
+
+ int main()
+ {
+   // ...continued from above...
+   Graph::vertex_iterator i, j;
+   for(tie(i, j) = vertices(g); i != j; ++i) {
+     cout << graph[*i].distance << " : " << graph[*i].name << "\n";
+   }
+ }
+
+The output should look something like this (note that $ is a shell prompt):
+[pre
+$ ./kevin_bacon < movies
+1 : Chris Penn
+1 : Sarah Jessica Parker
+2 : James Belushi
+2 : David Ogden Stiers
+3 : Mark Hamill
+3 : Dan Akroyd
+1 : John Belushi
+1 : Tim Matheson
+2 : Tom Hulce
+2 : Peter Riegert
+2 : Karen Allen
+2 : Mike Meyers
+2 : Sylvester Stallone
+2 : Eddie Murphy
+]
+
+[h4 The Kevin Bacon Game]
+Using the above algorithm we can find how far away each actor is from Kevin Bacon, but what
+if we want to know how to get there. For example, we know that Dan Akroyd is three steps away
+so what are the movies? We could look at the input file, but that won't really give us any
+advantage. A better solution would be to modify the program to record the shortest paths.
+
+Since the term /shortest paths/ arises in the problem description, we might be tempted to
+use a shortest paths algorithm such as Dijkstra's. However, if we think about the problem a
+little bit, we should realize that there aren't any edge weights - something required for
+Dijkstra's algorithm. We could implicitly treat all edges as having a weight of one, but
+that turns out to be somewhat ineffective. It turns out that we can use the same BFS
+algorithm to record shortest paths instead of (or in addition to) actors' distances to
+Kevin Bacon. Specifically, we can record each the parent of each vertex in the BFS tree
+and simply backtrack from a given actor to Kevin Bacon.
+
+There are only a couple of modifications that we really need to make. First, we want to
+add an extra property for each actor: its parent vertex in the search tree. For convenience,
+we are also going to add a new property map type.
+
+ struct Actor
+ {
+   // ...same as before...
+   Vertex parent;
+ };
+
+ // ...
+ typedef boost::property_map<Graph::type, &Vertex Actor::*>::type ActorParentMap;
+
+The only other changes are going to be in the `main()` program.
+
+ int main(int argc, char *argv[])
+ {
+   string src = "Kevin Bacon";
+   string tgt;
+
+   if(argc < 2) {
+     cerr << "usage: actor_paths actor [actor] < movies";
+     return -1;
+   }
+   else if(argc == 2) {
+     tgt = argv[1];
+   }
+   else {
+     src = argv[1];
+     tgt = argv[2];
+   }
+
+   Graph graph;
+   ActorMap actors;
+   build_costar_graph(cin, graph, actors);
+
+   // ...to be continued...
+
+This program accepts a couple of command line parameters. If one actor is given then
+we find the path to Kevin Bacon. If two actors are given, we find the shortest path
+between the two actors. We can now get the vertices for specified actors, and find
+the paths between them.
+
+   // ...continued from before...
+   Vertex u = find_actor_vertex(g, actors, src);
+   Vertex v = find_actor_vertex(g, actors, tgt);
+   if(u == Graph::null_vertex()) {
+     cerr << "could not find actor " << src << "\n";
+     return -1;
+   }
+   if(v == Graph::null_vertex()) {
+     cerr << "could not find actor " << tgt << "\n";
+     return -1;
+   }
+
+   // get the parents map for later use.
+   ActorParentMap parents = get(&Actor::parent, g);
+
+   breadth_first_search(graph, kevin,
+     visitor(
+        make_bfs_visitor(record_predecessors(distances, on_tree_edge()))
+        )
+   );
+
+   // ...to be continued...
+
+The `find_actor_vertex()` method is relatively trivial. We extracted it as a function
+so the program wouldn't be quite so repetitive.
+
+ Vertex find_actor_vertex(const Graph& g, const ActorMap& actors, const std::string& name)
+ {
+   Vertex v = Graph::null_vertex();
+   ActorMap::const_iterator i = actors.find(name);
+   if(i != actors.end()) {
+     v = i->second;
+   }
+   return v;
+ }
+
+Otherwise, the code is essentially the same as above. In this case, we're constructing
+a `predecessor_recorder` as the visitor to the BFS. In contrast to the `distance_recorder`
+this method stores the parents (or predecessor) of each vertex in the BFS tree. This is
+an important property because it allows us to backtrack from one endpoint in the graph
+to the starting point, showing the path from, say Kevin Bacon to any another actor.
+
+Backtracking is relatively easy.
+
+ int main(...)
+ {
+   // ...continued from before...
+   while(v != u) {
+     Vertex p = parents[v];
+     string from = g[v].name;
+     string to = g[p].name;
+
+     // find the edge so we can print the movie
+     Edge e;
+     bool found;
+     tie(e, found) = edge(v, p, g);
+
+     string movie = g[e].name;
+     cout << from << " starred with " << to << " in '" << movie << "'\n";
+
+     v = p;
+   }
+
+   return 0;
+ }
+
+Althgough we could simply backtrack over the parents and print the actors in a chain,
+we think it's more entertaining to know the movies that each pair co-stars in. To do
+this we use the `edge()` function to locate the edge corresponding edge connecting
+the two actors who costarred in a movie.
+
+The output might look something like:
+[pre
+$ ./six_degrees "Dan Akroyd" < movies
+Dan Akroyd starred with Carrie Fisher in 'The Blues Brothers (1980)'
+Carrie Fisher starred with Elisabeth Shue in 'Soapdish (1991)'
+Elisabeth Shue starred with Kevin Bacon in 'Hollow Man (2000)'
+]
+
+You now have a completely /unbeatable/ implementation of the "Six Degrees of Kevin
+Bacon" game - provided of course that you add a lot more movie data to the simple
+data set provided with this example.
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/history.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/history.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,110 @@
+[/
+ / Copyright (c) 2007 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 History]
+
+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). 
+
+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)
+was one of the first projects. Many of the lessons learned during construction of the MTL were
+applied to the design and implementation of the GGCL.
+
+Graph algorithms play an important role in sparse matrix computations, so the LSC had a need for
+a good graph library. However, none of the available graph libraries (LEDA, GTL, Stanford GraphBase)
+were written using the generic programming style of the STL, and hence did not fulfill the flexibility
+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. 
+
+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 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
+began working on the concept documentation for GGCL similar to Matt's STL documentation.
+
+While working at SGI, Jeremy heard about Boost and was excited to find a group of people interested
+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. 
+
+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.35.0
+  * 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.
+  * Enhancements
+    * LEDA Adaptor improvements, from Jens Muller.
+
+* Version 1.34.0
+  * 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.
+    * sorted_erdos_renyi_iterator, from Jeremiah Willcock of Indiana University.
+  * Enhancements
+    * biconnected_components now has a visitor parameter and supports named parameters, from Janusz Piwowarski.
+    * adjacency_matrix now models the Bidirectional Graph concept.
+    * adjacency_list is now Serializable, from Jeremy Siek of Rice University.
+    * Added edges_size_type and vertices_size_type to adjacency_list_traits, from Jeremy Siek of Rice University.
+    * Added operator< , etc. to the edge descriptor of adjacency_list, from Jeremy Siek of Rice University.
+  * Bug Fixes
+    * Fixed a bug that causes the relaxed heap to fail on x86 Linux.
+    * 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. 
+
+* Version 1.33.1
+  * 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 
+    * 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.
+    * fruchterman_reingold_force_directed_layout, from Doug Gregor and Indiana University.
+    * biconnected_components and articulation_points, from Indiana University.
+    * gursoy_atun_layout, from Jeremiah Willcock and Doug Gregor of Indiana University.
+    * king_ordering, from D. Kevin McGrath of Indiana University.
+    * erdos_renyi_iterator
+    * plod_iterator
+    * small_world_iterator
+  * Enhancements
+    * bellman_ford_shortest_paths now permits one to specify the starting vertex, so that it will perform its own initialization.
+    * undirected_dfs is now data-recursive, resulting in improved performance in some cases, from Synge Todo.
+    * dijkstra_shortest_paths now uses a relaxed heap [61] as its priority queue, improving its complexity to O(V log V) and improving real-world performance for larger graphs.
+    * read_graphviz now has a new, Spirit-based parser that works for all graph types and supports arbitrary properties on the graph, from Ron Garcia. The old, Bison-based GraphViz reader has been deprecated and will be removed in a future Boost release.
+    * write_graphviz now supports output of dynamic properties (as read in through the new read_graphviz).
+    * cuthill_mckee_ordering has been recast as an invocation of breadth_first_search and now supports graphs with multiple components.
+    * subgraph now supports bundled properties. get_property now refers to the subgraph property, not the root graph's property.
+    * filtered_graph now supports bundled properties.
+    * reverse_graph now supports bundled properties, set_property, and get_property.
+  * Bug fixes
+    * bellman_ford_shortest_paths now deals with unreachable vertices better.
+    * adjacency_list: parallel edge removal with OutEdgeListS = listS has been fixed. Copying and swapping has been fixed.
+    * Incremental connected components: fixed a bug in the incremental_components routine that may have caused incorrect results.
+    * The remove_out_edge_if function for an undirected adjacency_list has been rewritten and should no longer dereference singular iterators.
+    * write_graphviz now accepts a vertex_id parameter that is used to name the nodes.
+    * read_graphviz now accepts empty attribute lists.
+    * sequential_vertex_coloring has been updated, tested, and documented.
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/introduction.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/introduction.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,214 @@
+[/
+ / Copyright (c) 2007 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. 
+
+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.
+
+[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.
+
+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. 
+
+[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.
+
+[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
+
+[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!
+
+[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.
+
+[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()`.
+
+[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.
+
+[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 
+* 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:
+
+* Dijkstra's Shortest Paths
+* Bellman-Ford Shortest Paths
+* Johnson's All-Pairs Shortest Paths
+* Kruskal's Minimum Spanning Tree
+* Prim's Minimum Spanning Tree
+* Connected Components
+* Strongly Connected Components
+* Dynamic Connected Components (using Disjoint Sets)
+* Topological Sort
+* Transpose
+* Reverse Cuthill Mckee Ordering
+* Smallest Last Vertex Ordering
+* Sequential Vertex Coloring
+
+[h2 Data Structures]
+Boost.Graph currently provides two graph classes and an edge list adaptor:
+
+* adjacency_list
+* 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 `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):
+
+* [@http://www.cs.rpi.edu/~musser/gsd/ Generic Software Design Course at RPI]
+* [@http://alps.comp-phys.org/ The ALPS quantum mechanics project]
+* [@http://bioinformatics.icmb.utexas.edu/lgl/ Large Graph Layout at University of Texas]
+* [@http://www.cs.concordia.ca/~gregb/home/c691R-w2004.html Bioinformatics Algorithms at Concordia University]
+* [@http://photon.poly.edu/~hbr/cs903/ Algorithm Course at Polytechnic University in Brooklyn]
+* [@http://www.bioconductor.org/repository/devel/vignette/RBGL.pdf BGL interface for language R]
+* [@http://www.cuj.com/documents/s=8470/cuj0307tan/ CUJ Article about Electronic Design Automation]
+* [@http://rubyforge.org/projects/rgl/ A BGL-inspired Ruby Graph Library]
+* [@http://www.codeproject.com/cs/miscctrl/quickgraph.asp A BGL-inspired C# Graph Library]
+* [@http://map1.squeakfoundation.org/sm/package/5729d80a-822b-4bc2-9420-ef7ecaea8553 A BGL-inspired Squeak (Smalltalk) Graph Library]
+* [@http://www.datasim.nl/education/coursedetails.asp?coursecategory=CPP&coursecode=ADCPP BGL course at DataSim]
+* [@http://www.vrjuggler.org/ VR Juggler: Virtual Reality Tools]
+* [@http://hyperworx.org Hyperworx Platform Project]
+
+[h2 Publications about this Library]
+* Dr. Dobb's Sept. 2000 Article
+* OOPSLA'99 GGCL Paper
+* Lie-Quan Lee's Master's Thesis about GGCL(ps) (pdf)
+* Dietmar Kuhl's Master's Thesis: Design Pattern for the Implementation of Graph Algorithms
+* ISCOPE'99 Sparse Matrix Ordering (pdf)
+* 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. 
+
+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. 
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/adjacency_list.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/adjacency_list.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,411 @@
+[/
+ / Copyright (c) 2007 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 Adjacency List]
+
+[warning
+This reference is missing documentation for a number of associated types and
+methods.
+]
+
+[h4 Missing or Incorrect Documentation]
+* `edge_iterator`
+* `clear_in_edges()`
+* `clear_out_edges()`
+
+The adjacency_list class implements a generalized adjacency list graph structure.
+The template parameters provide many configuration options so that you can pick a
+version of the class that best meets your needs. An adjacency-list is basically a
+two-dimensional structure, where each element of the first dimension represents a
+vertex, and each of the vertices contains a one-dimensional structure that is its
+edge list. Figure 1 shows an adjacency list representation of a directed graph.
+
+The VertexList template parameter of the adjacency_list class controls what kind
+of container is used to represent the outer two-dimensional container. The
+OutEdgeList template parameter controls what kind of container is used to represent
+the edge lists. The choices for OutEdgeList and VertexList will determine the space
+complexity of the graph structure, and will determine the time complexity of the
+various graph operations. The possible choices and tradeoffs are discussed in
+Section Choosing the Edgelist and VertexList.
+
+The Directed template parameter controls whether the graph is directed, undirected,
+or directed with access to both the in-edges and out-edges (which we call
+bidirectional). The bidirectional graph takes up twice the space (per edge) of a
+directed graph since each edge will appear in both an out-edge and in-edge list.
+Figure 2 shows an adjacency list representation of an undirected graph.
+
+A tutorial on how to use the adjacency_list class is in Section Using adjacency_list.
+
+[h3 Template Parameters]
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`OutEdgeList`]
+        [
+            The selector for the container used to represent the edge-list for each
+            of the vertices.
+        ]
+        [`vecS`]
+    ]
+    [
+        [`VertexList`]
+        [
+            The selector for the container used to represent the vertex-list of the graph.
+        ]
+        [`vecS`]
+    ]
+    [
+        [`Directed`]
+        [
+            A selector to choose whether the graph is directed, undirected, or
+            directed with bidirectional edge access (access to both out-edges
+            and in-edges). The options are directedS, undirectedS, and
+            bidirectionalS.
+        ]
+        [`directedS`]
+    ]
+    [
+        [`VertexProperties`]
+        [Specifies internal properties for vertices.]
+        [`no_property`]
+    ]
+    [
+        [`EdgeProperties`]
+        [Specifies internal properties for edges.]
+        [`no_property`]
+    ]
+    [
+        [`GraphProperties`]
+        [Specifies internal properties for the graph object.]
+        [`no_property`]
+    ]
+    [
+        [`EdgeList`]
+        [
+            The selector for the container used to represent the edge-list for
+            the graph.
+        ]
+        [`listS`]
+    ]
+]
+
+[h4 Model of]
+VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable,
+and Serializable.
+
+[h4 Where Defined]
+
+`boost/graph/adjacency_list.hpp`
+
+The serialization functionality is in `boost/graph/adj_list_serialize.hpp`.
+
+[h3 Vertex and Edge Properties]
+Properties such as color, distance, weight, and user-defined properties can be
+attached to the vertices and edges of the graph using properties. The property
+values can be read from and written to via the property maps provided by the
+graph. The property maps are obtained via the get(property, g) function. How
+to use properties is described in Section Internal Properties . The property
+maps are objects that implement the interface defined in Section Property Map
+Concepts or may be bundled properties, which have a more succinct syntax. The
+types of all property values must be Copy Constructible, Assignable, and
+Default Constructible. The property maps obtained from the adjacency_list class
+are models of the Lvalue Property Map concept. If the adjacency_list is const,
+then the property map is constant, otherwise the property map is  mutable.
+
+If the VertexList of the graph is vecS, then the graph has a builtin vertex
+indices accessed via the property map for the vertex_index_t property. The
+indices fall in the range [0, num_vertices(g)) and are contiguous. When a
+vertex is removed the indices are adjusted so that they retain these
+properties. Some care must be taken when using these indices to access exterior
+ roperty storage. The property map for vertex index is a model of Readable
+Property Map.
+
+[h3 Iterator and Descriptor Stability/Invalidation]
+Some care must be taken when changing the structure of a graph (via adding or
+removing edges). Depending on the type of adjacency_list and on the operation,
+some of the iterator or descriptor objects that point into the graph may become
+invalid. For example, the following code will result in undefined (bad)
+behavior:
+
+ typedef adjacency_list<listS, vecS> Graph; // VertexList = vecS
+ Graph G(N);
+
+ // Fill in the graph...
+
+ // Attempt to remove all the vertices. Wrong!
+ graph_traits<Graph>::vertex_iterator vi, vi_end;
+ for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
+   remove_vertex(*vi, G);
+ }
+
+  // Remove all the vertices. This is still wrong!
+  graph_traits<Graph>::vertex_iterator vi, vi_end, next;
+  tie(vi, vi_end) = vertices(G);
+  for(next = vi; vi != vi_end; vi = next) {
+    ++next;
+    remove_vertex(*vi, G);
+  }
+
+The reason this is a problem is that we are invoking remove_vertex(), which
+when used with an adjacency_list where VertexList=vecS, invalidates all
+iterators and descriptors for the graph (such as vi and vi_end), thereby
+causing trouble in subsequent iterations of the loop.
+
+If we use a different kind of `adjacency_list`, with `VertexList` as `listS`,
+then the iterators are not invalidated by calling remove_vertex unless the
+iterator is pointing to the actual vertex that was removed. The following code
+demonstrates this.
+
+ typedef adjacency_list<listS, listS> Graph; // VertexList = listS
+ Graph G(N);
+
+ // Fill in the graph...
+
+ // Attempt to remove all the vertices. Wrong!
+ graph_traits<Graph>::vertex_iterator vi, vi_end;
+ for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
+   remove_vertex(*vi, G);
+ }
+
+ // Remove all the vertices. This is OK.
+ graph_traits<Graph>::vertex_iterator vi, vi_end, next;
+ tie(vi, vi_end) = vertices(G);
+ for(next = vi; vi != vi_end; vi = next) {
+   ++next;
+   remove_vertex(*vi, G);
+ }
+
+The stability issue also affects vertex and edge descriptors. For example,
+suppose you use vector of vertex descriptors to keep track of the parents
+(or predecessors) of vertices in a shortest paths tree (see
+`examples/dijkstra-example.cpp`). You create the parent vector with a call
+to dijkstra_shortest_paths(), and then remove a vertex from the graph.
+Subsequently you try to use the parent vector, but since all vertex descriptors
+have become invalid, the result is incorrect.
+
+ std::vector<Vertex> parent(num_vertices(G));
+ std::vector<Vertex> distance(num_vertices(G));
+
+ dijkstra_shortest_paths(G, s,
+   distance_map(&distance[0])
+   .predecessor_map(&parent[0]));
+
+ remove_vertex(s, G); // Bad idea! Invalidates vertex descriptors in parent vector.
+
+ // The following will produce incorrect results
+ for(tie(vi, vend) = vertices(G); vi != vend; ++vi) {
+   std::cout << p[*vi] << " is the parent of " << *vi << std::endl;
+ }
+
+Note that in this discussion iterator and descriptor invalidation is concerned
+with the invalidation of iterators and descriptors that are not directly
+affected by the operation. For example, performing `remove_edge(u, v, g)` will
+always invalidate any edge descriptor for /(u,v)/ or edge iterator pointing to
+/(u,v)/, regardless of the kind `adjacency_list`. In this discussion of iterator
+and descriptor invalidation, we are only concerned with the affect of
+`remove_edge(u, v, g)` on edge descriptors and iterators that point to other
+edges (not /(u,v)/).
+
+In general, if you want your vertex and edge descriptors to be stable (never
+invalidated) then use listS or setS for the VertexList and OutEdgeList template
+parameters of adjacency_list. If you are not as concerned about descriptor and
+iterator stability, and are more concerned about memory consumption and graph
+traversal speed, use vecS for the VertexList and/or OutEdgeList template
+parameters.
+
+The following table summarizes which operations cause descriptors and iterators
+to become invalid. In the table, OEL is an abbreviation for OutEdgeList and VL
+means VertexList. The "Adjacency Iterator" category includes the `out_edge_iterator`,
+`in_edge_iterator`, and `adjacency_iterator types`. A more detailed description of
+descriptor and iterator invalidation is given in the documentation for each
+operation.
+
+[table
+    [[Function] [Vertex Descriptor] [Edge Descriptor] [Vertex Iterator] [Edge Iterator] [Adjacency Iterator]]
+    [
+        [`add_edge()`]
+        [Valid]
+        [Valid]
+        [Valid]
+        [
+            OEL = `vecS` &&
+
+            Directed = `directedS`]
+        [OEL = `vecS`]
+    ]
+    [
+        [
+            `remove_edge()`
+
+            `remove_edge_if()`
+
+            `remove_out_edge_if()`
+
+            `remove_in_edge_if()`
+
+            `clear_vertex()`
+        ]
+        [Valid]
+        [Valid]
+        [Valid]
+        [
+            OEL = `vecS` &&
+
+            Directed = `directedS`]
+        [OEL = `vecS`]
+    ]
+    [
+        [`add_vertex()`]
+        [Valid]
+        [Valid]
+        [Valid]
+        [Valid]
+        [Valid]
+    ]
+    [
+        [`remove_vertex()`]
+        [VL = `vecS`]
+        [VL = `vecS`]
+        [VL = `vecS`]
+        [VL = `vecS`]
+        [VL = `vecS`]
+    ]
+]
+
+[h3 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<adjancency_list>::vertex_descriptor`]
+        [
+            The type for the vertex descriptors associated with the `adjacency_list`.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::edge_descriptor`]
+        [
+            The type for the edge descriptors associated with the `adjacency_list`.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::vertex_iterator`]
+        [
+            The type for iterators returned by `vertices()`. The concept modeled by this
+            type varies with the type of the `VertexList` parameter. If the `VertexList`
+            selector is `vecS`, then this type models the `RandomAccessIterator` concept.
+            In all other cases, it is a model of `BidirectionalIterator`.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::out_edge_iterator`]
+        [
+            The type for iterators returned by `edges()`. The concept modeled by this type
+            depends on the `OutEdgeList` parameter. If the selector is `vecS` then the
+            iterator is a model of `RandomAccessIterator`. If the selector is `slistS`
+            then it is a model of `ForwardIterator`. Otherwise, the iterator models
+            `BidirectionalIterator`.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::in_edge_iterator`]
+        [
+            This type is only valid if the `Directed` parameter is given as `bidirectionalS`.
+            The concepts modeled by this type are the same as the `out_edge_iterator`.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::adjacency_iterator`]
+        [
+            The type for iterators returned by `adjacent_vertices()`. The concepts modeled
+            by this type are the same as `out_edge_iterator`. Dereferencing these types,
+            however, will result in vertex descriptors rather than edge descriptors.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::inv_adjacency_iterator`]
+        [
+            The type for iterators returned by `inv_adjacent_vertices()`. The concepts
+            modeled by this type are identical to hose of the `adjacency_iterator`.
+        ]
+    ]
+    [
+        [`graph_traits<adjancency_list>::directed_category`]
+        [
+            Provides inforamtion about whether the graph is undirected (`undirected_tag`),
+            directed (`directed_tag`), or bidirectional (`bidirectional_tag`).
+        ]
+    ]
+    [
+        [`graph_traits<adjacency_list>::edge_parallel_category`]
+        [
+            This describes whether the class allows the insertion of parallel edges; those
+            with the same source and target. When `EdgeList` is selected as `setS` or
+            `hash_setS`, this type is set to `disallow_parallel_edge_tag`. Otherwise it
+            is `allow_parallel_edge_tag`.
+        ]
+    ]
+    [
+        [`graph_traits<adjacency_list>::vertices_size_type`]
+        [The type used for dealing with the number of vertices in the graph. ]
+    ]
+    [
+        [`graph_traits<adjacency_list>::edge_size_type`]
+        [The type used for dealing with the number of edges in the graph. ]
+    ]
+    [
+        [`graph_traits<adjacency_list>::degree_size_type`]
+        [The type used for dealing with the number of edges incident to a vertex in the graph. ]
+    ]
+    [
+        [
+            `property_map<adjacency_list, Property>::type`
+
+            `property_map<adjacency_list, Property>::const_type`
+        ]
+        [
+            The property map type for vertex or edge properties in the graph. The specific
+            property is specified by the `Property` template argument, and must match one of
+            the properties specified in the `VertexProperties` or `EdgeProperties` for the
+            graph.
+        ]
+    ]
+    [
+        [`graph_property<adjacency_list, Property>::type`]
+        [
+            The value type ofor the graph property specified by the `Property` parameter.
+        ]
+    ]
+    [
+        [`adjacency_list::out_edge_list_selector`]
+        [The instantiated type of the `OutEdgeList` template parameter.]
+    ]
+    [
+        [`adjacency_list::vertex_list_selector`]
+        [The instantiated type of the `VertexList` template parameter.]
+    ]
+    [
+        [`adjacency_list::directed_selector`]
+        [The instantiated type of the `Directed` template parameter.]
+    ]
+    [
+        [`adjacency_list::edge_list_selector`]
+        [The instantiated type of the `EdgeList` template parameter.]
+    ]
+]
+
+[h3 Member Functions]
+[table
+    [[Member Function] [Description]]
+    [
+        [`adjacency_list(const GraphProperties& = GraphProperties()`]
+        [
+            The default constructor creates an empty graph with no vertices or edges.
+        ]
+    ]
+]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/breadth_first_search.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,153 @@
+[/
+ / Copyright (c) 2007 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 Breadth-First Search]
+    template <class Graph, class P, class T, class R>
+    void
+    breadth_first_search(Graph& g,
+                        typename graph_traits<Graph>::vertex_descriptor s,
+                        bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+    template <class Graph, class Buffer, class Visitor, class P, class T, class R>
+    void
+    breadth_first_search(Graph& g,
+                        typename graph_traits<Graph>::vertex_descriptor s,
+                        Buffer& q,
+                        Visitor vis,
+                        bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+The `breadth_first_search()` function performs a breadth-first traversal \[49\] of a directed or
+undirected graph. A breadth-first traversal visits vertices that are closer to the source before
+visiting vertices that are further away. In this context "distance" is defined as the number of edges
+in the shortest path from the source vertex. The `breadth_first_search()` function can be used to
+compute the shortest path from the source to all reachable vertices and the resulting shortest-path
+distances. For more definitions related to BFS, see section Breadth-First Search.
+
+BFS uses two data structures to to implement the traversal: a color marker for each vertex and
+a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered
+adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray
+vertices. The algorithm proceeds by removing a vertex /u/ from the queue and examining each out-edge
+/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
+queue. After all of the out-edges are examined, vertex u is colored black and the process is
+repeated. Pseudo-code for the BFS algorithm is a listed below.
+
+[pre
+BFS(G, s)
+    for each vertex u in V\[G\]           initialize vertex u
+        color\[u\] := WHITE
+        d\[u\] := infinity
+        p\[u\] := u
+    end for
+
+    color\[s\] := GRAY
+    d\[s\] := 0
+    ENQUEUE(Q, s)                       discover vertex s
+
+    while not EMPTY(Q)
+        u := DEQUEUE(Q)                 examine vertex u
+        for each vertex v in adj\[u\]     examine edge /(u,v)/
+            if(color\[v\] = WHITE)        /(u,v)/ is a tree edge
+                color\[v\] := GRAY
+                d\[v\] := d\[u\] + 1
+                p\[v\] := u
+                ENQUEUE(Q, v)           discover vertex v
+            else                        /(u,v)/ is a non-tree edge
+                if (color\[v\] = GRAY)    /(u,v)/ has a gray target
+                ...
+                else                    /(u,v)/ has a black target
+                ...
+            end if
+        end for
+        color\[u\] := BLACK               finsih vertex u
+    end while
+    return (d, p)
+]
+
+[heading Where Defined]
+`boost/graph/breadth_first_search.hpp`
+
+[heading Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [in] [`Graph& g`]
+        [
+            A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
+            and [BoostIncidenceGraph].
+        ]
+    ]
+    [
+        [in] [`vertex_descriptor s`]
+        [
+            The source vertex where the search is started. This must be a valid vertex descriptor of
+            `g`.
+        ]
+    ]
+]
+
+[heading Named Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [in] [`visitor(Visitor vis)`]
+        [
+            A visitor object that is inovked inside the algorithm at event points specified by the
+            [BoostBFSVisitor]. The `vis` object must be model the [BoostBFSVisitor] concept.
+
+            *Default* `bfs_visitor<null_visitor>`.
+        ]
+    ]
+    [
+        [in] [`vertex_index_map(VeretxIndexMap index_map)`]
+        [
+            This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+            This parameter is only necessary when the default color property map is
+            used. The type VertexIndexMap must be a model of ReadablePropertyMap. 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.
+
+            *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+            that your graph has an interior `vertex_index` property. For example
+            `adjacency_list` with `VertexList=listS` does not have an interior
+            `vertex_index` property.
+        ]
+    ]
+    [
+        [util] [`color_map(ColorMap color)`]
+        [
+            This is used by the algorithm to keep track of its progress through the
+            graph. The type ColorMap must be a model of ReadWritePropertyMap and
+            its key type must be the graph's `vertex_descriptor` type and the value
+            type of the color map must model ColorValue.
+
+            *Default* An `iterator_property_map` create from a `std::vector` of
+            `default_color_type` of size `num_vertices(g)` and using `index_map` as
+            the index map (to access colors for a vertex).
+        ]
+    ]
+    [
+        [util] [`buffer(Buffer& q)`]
+        [
+            The queue used to determine the order in which vertices will be discovered.
+            If a FIFO queue is used, then the traversal will be according to the usual
+            BFS ordering. Other types of queues can be used, but the traversal order will
+            be different. For example Dijkstra's algorithm can be implemented using a
+            priority queue. The type Buffer must be a model of [NoConcept Buffer].
+
+            The `value_type` of the buffer must be the vertex_descriptor type for the graph.
+
+            *Default* `boost::queue`
+        ]
+    ]
+]
+
+[heading Complexity]
+The time complexity is /O(E + V)/.
+
+[heading Example]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connected_components.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/connected_components.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,94 @@
+[/
+ / Copyright (c) 2007 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 Connected Components]
+    template <class Graph, class ComponentMap, class P, class T, class R>
+    typename property_traits<ComponentMap>::value_type
+    connected_components(const Graph &g, ComponentMap c,
+                        const bgl_named_params<P,T,R>& params = ``/defaults/``);
+
+
+The connected_components() functions compute the connected components of an undirected
+graph using a DFS-based approach. A connected component of an undirected graph is a
+set of vertices that are all reachable from each other. If the connected components
+need to be maintained while a graph is growing the disjoint-set based approach of
+function `incremental_components()` is faster. For "static" graphs this DFS-based
+approach is faster \[8\].
+
+The output of the algorithm is recorded in the component property map, which will
+contain numbers giving the component number assigned to each vertex. This algorithm
+returns the total number of connected components in the graph.
+
+[heading Where Defined]
+`boost/graph/connected_components.hpp`
+
+[heading Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [in] [`const Graph& g`]
+        [
+            The /undirected/ graph for which connected components are being found.
+            This graph must be a model of VertexListGraph and Incidence Graph.
+        ]
+    ]
+    [
+        [out] [`ComponentMap c`]
+        [
+            The algorithm computes how many connected components are in the graph,
+            and assigning each component an integer label. The algorithm then records
+            which component each vertex in the graph belongs to by recording the
+            component number in the component property map. The ComponentMap type
+            must be a model of WritablePropertyMap. The value type shouch be an
+            integer type, preferably the same as the `vertices_size_type` of the
+            graph. The key type must be the graph's `vertex_descriptor` type.
+        ]
+    ]
+]
+
+[heading Named Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [util] [`color_map(ColorMap color)`]
+        [
+            This is used by the algorithm to keep track of its progress through the
+            graph. The type ColorMap must be a model of ReadWritePropertyMap and
+            its key type must be the graph's `vertex_descriptor` type and the value
+            type of the color map must model ColorValue.
+
+            *Default* An `iterator_property_map` create from a `std::vector` of
+            `default_color_type` of size `num_vertices(g)` and using `index_map` as
+            the index map (to access colors for a vertex).
+        ]
+    ]
+    [
+        [in] [`vertex_index_map(VertexIndexMap index_map)`]
+        [
+            This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+            This parameter is only necessary when the default color property map is
+            used. The type VertexIndexMap must be a model of ReadablePropertyMap. 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.
+
+            *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+            that your graph has an interior `vertex_index` property. For example
+            `adjacency_list` with `VertexList=listS` does not have an interior
+            `vertex_index` property.
+        ]
+    ]
+]
+
+[heading Complexity]
+This algorithm runs in /O(V + E)/.
+
+[heading Notes]
+This algorithm will not compile if passed a /directed/ graph.
+
+[heading Examples]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,207 @@
+[/
+ / Copyright (c) 2007 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 Connectivity Measures]
+
+    template <
+        typename Graph,
+        typename Components,
+        typename SizeType,
+        typename ComponentMap,
+        typename ColorMap,
+        typename VertexIndexMap
+    >
+    std::size_t
+    connectivity(
+        const Graph& _graph,
+        Components& _components,
+        SizeType _number = 0,
+        ComponentMap _component_map = ``['nothing]``,
+        ColorMap _color_map = ``['nothing]``,
+        VertexIndexMap _vertex_index_map = get(vertex_index, _graph));
+
+The `connectivity()` algorithm is a wrapper around the [boost_connected_components]
+algorithm that provides convenience for working with the resultant component maps.
+The parameters have, with the exeption of `_components`, the same purpose and requirements
+as documented in [boost_connected_components].
+
+The `_components` parameter will result in a sequence of "components" of the graph
+where each "component" is a sequence of vertices in the graph. After returning,
+the size of the `_components` parameter will be the number of connected components
+in the graph and each element in that sequence will contain a sequence of one or
+more vertices. Each vertex is assigned to only one component. The assignment is
+determined by the `_component_map`, whether passed to the algorithm or not.
+If a vertex `v` is mapped to component id `i` such that `_component_map[v] == i` then
+`v` will appear in the vertex sequence given by `_components[i]`.
+
+To help illustrate the structure and contents of the `_components` parameter,
+suppose, that after running [boost_connected_components], a graph is decomposed
+into two components.
+
+[figure
+    images/reference/connected_components_after.png
+    Figure 1. Components found after running [boost_connected_components]
+]
+
+Assume that we have stored each vertex into a vector, `v`, such that `v[i]`
+denotes the ['i[super th]] vertex in the graph above. The `_component_map` used
+for this decomposition associates each vertex with a component id.
+
+    _component_map[ v[0] ] == 0;
+    _component_map[ v[1] ] == 0;
+    _component_map[ v[2] ] == 0;
+    _component_map[ v[3] ] == 1;
+    _component_map[ v[4] ] == 1;
+
+However, the `_components` parameter associates each component with the vertices that
+comprise that component. Therefore, contents of the output sequence `_components` will
+be (in pseudo-C++):
+
+    _components[0] == { v[0], v[1], v[2] };
+    _components[1] == { v[0], v[1], v[2] };
+
+This function returns the number of connected components in the graph.
+
+There are two distinct methods for calling this function: with or without the
+`_component_map` parameter. If the `_component_map` /is not/ given, then the
+algorithm must first compute the connected components of `_graph`. In this case,
+the user may need to supply the `_vertex_index_map` or an alternate `_color_map`.
+Calling the [boost_connectivity] function in this way will not provide access
+to a `_component_map` for the graph.
+
+If the _component_map /is/ given, then the algorithm assumes that connected
+components have already been assigned in the `_component_map`. In this case,
+`_color_map` and `_vertex_index_map` parameters are effectively ignored. Additionally
+the caller may pass the `_number` parameter to the function. If /not/ passed,
+the computation is required to determine the number of components in the graph
+by examining the `_component_map`. Passing `_number` as the return value of
+[boost_connected_components] allows this operation to be bypassed.
+
+[note
+This hasn't been tested very will for directed graphs. In fact, testing
+will probably result in the creation of `strong_connecity` which forwards the
+call to `strong_connected_components`.
+]
+
+[h5 Where Defined]
+`boost/graph/connectivity.hpp`
+
+[h5 Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [required, in] [`Graph _graph`]
+        [
+            The graph object for which the distribution will be computed. If
+            the `_distribution` or `_in_distribution` arguments are supplied
+            when calling this function then `_graph` must be a model of
+            [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+            then `_graph` must be a model of [BoostIncidenceGraph].
+        ]
+    ]
+    [
+        [required, out] [`Components _components`]
+        [
+            The components parameter provides storage for the assignment of
+            vertices to components. The `ComponentMap` parameter must be a
+            model of [SgiRandomAccessContainer] whose index type must be convertible
+            to the graphs `vertices_size_type`, and whose `value_type` must be
+            a model of [SgiBackInsertionSequence]. In turn, the `value_type` of
+            this [SgiBackInsertionSequence] must be the `vertex_descriptor` type
+            of `_graph`.
+        ]
+    ]
+    [
+        [optional, in] [`SizeType _number`]
+        [
+            This is the number of components in the graph as returned by a
+            prior call to [boost_connected_components]. The SizeType must
+            be convertible to the `vertices_size_type` of `Graph`.
+
+            *Default* /not given/
+        ]
+    ]
+    [
+        [optional, in] [`ComponentMap _component_map`]
+        [
+            The component map that represents the assignment of vertices to
+            distinct components in the graph. The `ComponentMap` must be
+            a model of [BoostReadablePropertyMap]. The `value_type` should be
+            integral, preferably the same as `vertices_size_type` for the
+            graph. The `key_type` must be the graph's `vertex_descriptor`.
+
+            *Default* /not given/
+        ]
+    ]
+    [
+        [optional, in] [`ColorMap _color_map`]
+        [
+            This is used by the [boost_connected_components] algorithm to keep
+            track of its progress through the graph. The type `ColorMap` must
+            be a model of [BoostReadWritePropertyMap], it's `key_type` must be
+            the `vertex_descriptor` type of `_graph` and its `value_type` must
+            be a model of [BoostColorValue].
+
+            *Default* /not given/
+        ]
+    ]
+    [
+        [optional, in] [`VertexIndexMap _vertex_index_map`]
+        [
+            This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+            This parameter is necessary only `Graph` does not have built-in vertices
+            and/or a correct ordering on them.
+
+            *Default* `get(vertex_index, g)`
+        ]
+    ]
+]
+
+[h5 Return Value]
+This function returns the number of connected components. When the return value of
+this function is equal to `1`, then the graph is a single connected component.
+
+[h5 Complexity]
+This function has time complexity /O(V)/ and space complexity /O(V)/ (since each
+vertex is assigned to a component in the _components_vector).
+
+[h5 Examples]
+
+[note These are going to be expanded...]
+
+When a component map is not provided:
+
+    typedef undirected_graph<> Graph;
+    typedef graph_traits<Graph>::vertex_descriptor Vertex;
+    typedef vector<Vertex> Component;
+    typedef vector<Component> ComponentList;
+
+    Graph g;
+    // build a graph
+
+    ComponentList components;
+    connected_components(g, components);
+
+    size_t c = 0;
+    BOOST_FOREACH(Component comp, components) {
+        cout << "component: " << c++ << " : ";
+        BOOST_FOREACH(Vertex v, comp) {
+            cout << get(vertex_index, g, v) << " ";
+        }
+        cout << "\n";
+    }
+
+If the component map /is/ available...
+
+    // write some code to that effect.
+
+[h5 Details]
+The signature of this function may change in the future to include a new parameter, `_number`,
+which indicates the number of components computed by [boost_connected_components]. This
+introduces a new calling "profile" that would bypass the computation of the number of components.
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/depth_first_search.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,161 @@
+[/
+ / Copyright (c) 2007 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 Depth-First Search]
+    template <class Graph, class P, class T, class R>
+    void
+    depth_first_search(Graph& g,
+                       bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+    template <class Graph, class Visitor, class ColorMap>
+    void
+    depth_first_search(Graph& g,
+                        Visitor vis,
+                        ColorMap color,
+                        typename graph_traits<Graph>::vertex_descriptor s)
+
+The `depth_first_search()` function performs a depth-first traversal of the vertices
+in a directed graph. When possible, a depth-first traversal chooses a vertex adjacent
+to the current vertex to visit next. If all adjacent vertices have already been
+discovered, or there are no adjacent vertices, then the algorithm backtracks to the
+last vertex that had undiscovered neighbors. Once all reachable vertices have been
+visited, the algorithm selects from any remaining undiscovered vertices and continues
+the traversal. The algorithm finishes when all vertices have been visited. Depth-first
+search is useful for categorizing edges in a graph, and for imposing an ordering on the
+vertices. Section /Depth-First Search/ describes the various properties of DFS and
+walks through an example.
+
+Similar to BFS, color markers are used to keep track of which vertices have been
+discovered. White marks vertices that have yet to be discovered, gray marks a
+vertex that is discovered but still has vertices adjacent to it that are undiscovered.
+A black vertex is discovered vertex that is not adjacent to any white vertices.
+
+The `depth_first_search()` function invokes user-defined actions at certain event-points
+within the algorithm. This provides a mechanism for adapting the generic DFS algorithm
+to the many situations in which it can be used. In the pseudo-code below, the event
+points for DFS are indicated in by the triangles and labels on the right. The user-defined
+actions must be provided in the form of a visitor object, that is, an object whose type
+meets the requirements for a [BoostDFSVisitor]. In the pseudo-code we show the algorithm
+computing predecessors /p/, discovery time /d/ and finish time /t/. By default, the
+`depth_first_search()` function does not compute these properties, however there are
+pre-defined visitors such as [boost_predecessor_recorder] and [boost_time_stamper] that
+can be used to do this.
+
+[pre
+DFS(G)
+    for each vertex u in V              initialize vertex u
+        color\[u\] := WHITE
+        p\[u\] = u
+    end for
+
+    time := 0
+    if there is a starting vertex s
+        call DFS-VISIT(G, s)            start vertex /s/
+
+    for each vertex u in V
+        if color\[u\] = WHITE             start vertex /u/
+        call DFS-VISIT(G, u)
+    end for
+
+    return (p,d_time,f_time)
+
+DFS-VISIT(G, u)
+    color\[u\] := GRAY                    discover vertex /u/
+    d_time\[u\] := time := time + 1
+
+    for each v in Adj\[u\]                examine edge /(u,v)/
+        if (color\[v\] = WHITE)           /(u,v)/ is a tree edge
+            p\[v\] = u
+            call DFS-VISIT(G, v)
+        else if (color\[v\] = GRAY)       /(u,v)/ is a back edge
+            ...
+        else if (color\[v\] = BLACK)      /(u,v)/ is a cross or forward edge
+            ...
+    end for
+
+    color\[u\] := BLACK                   finish vertex /u/
+    f_time\[u\] := time := time + 1
+]
+
+[heading Where Defined]
+`boost/graph/depth_first_search.hpp`
+
+[heading Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [in] [`Graph& g`]
+        [
+            A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
+            and [BoostIncidenceGraph].
+        ]
+    ]
+    [
+        [in] [`vertex_descriptor s`]
+        [
+            This specifies the vertex that the depth-first search should originate from. Note
+            that this can also be given as a named parameter.
+        ]
+    ]
+]
+
+[heading Named Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [in] [`visitor(Visitor vis)`]
+        [
+            A visitor object that is inovked inside the algorithm at event points specified by the
+            [BoostDFSVisitor]. The `vis` object must be model the [BoostDFSVisitor] concept.
+
+            *Default* `bfs_visitor<null_visitor>`.
+        ]
+    ]
+    [
+        [in] [`root_vertex(vertex_descriptor s)`]
+        [
+            This specifies the vertex that the depth-first search should originate from.
+
+            *Default* `*vertices(g).first`
+        ]
+    ]
+    [
+        [in] [`vertex_index_map(VeretxIndexMap index_map)`]
+        [
+            This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+            This parameter is only necessary when the default color property map is
+            used. The type VertexIndexMap must be a model of ReadablePropertyMap. 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.
+
+            *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+            that your graph has an interior `vertex_index` property. For example
+            `adjacency_list` with `VertexList=listS` does not have an interior
+            `vertex_index` property.
+        ]
+    ]
+    [
+        [util] [`color_map(ColorMap color)`]
+        [
+            This is used by the algorithm to keep track of its progress through the
+            graph. The type ColorMap must be a model of ReadWritePropertyMap and
+            its key type must be the graph's `vertex_descriptor` type and the value
+            type of the color map must model ColorValue.
+
+            *Default* An `iterator_property_map` create from a `std::vector` of
+            `default_color_type` of size `num_vertices(g)` and using `index_map` as
+            the index map (to access colors for a vertex).
+        ]
+    ]
+]
+
+[heading Complexity]
+The time complexity is /O(E + V)/.
+
+[heading Example]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/directed_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,779 @@
+[/
+ / Copyright (c) 2007 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 Directed Graph]
+This section provides detailed information about the `directed_graph` class,
+its associated types, member functions and non-member interface. A directed
+graph is one in which edges have distinct direction. Edges flow from a /source/
+vertex to a /target/ and are generally only traversed through the outgoing
+edges of a vertex. However, incoming edges are also accessible. The class
+provides a general purpose implementation of directed graphs and can be
+used with algorithms in the Boost Graph Library.
+
+[h4 Notation]
+The following notation is used in this documentation. The following type names
+are generally meant to mean the following:
+[table
+    [[Used Type] [Actual Type]]
+    [
+        [`directed_graph`]
+        [
+            `directed_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
+            arguments that correspond to user-defined or default verex properties,
+            edge properties, and graph properties.
+        ]
+    ]
+    [
+        [`vertex_descriptor`]
+        [`directed_graph<VP,EP,GP>::vertex_descriptor`]
+    ]
+    [
+        [`edge_descriptor`]
+        [`directed_graph<VP,EP,GP>::edge_descriptor`]
+    ]
+    [
+        [`vertex_iterator`]
+        [`directed_graph<VP,EP,GP>::vertex_iterator`]
+    ]
+    [
+        [`edge_iterator`]
+        [`directed_graph<VP,EP,GP>::edge_iterator`]
+    ]
+]
+
+Moreover, objects with the following names are generally expected to have the
+following types.
+
+[table
+    [[Object Name] [Type]]
+    [[`g`] [`directed_graph`]]
+    [[`u`, `v`] [`vertex_descriptor`]]
+    [[`e`] [`edge_descriptor`]]
+    [[`i`] [`vertex_iterator` or `edge_iterator`]]
+    [[`p`] [A property tag (usually a template parameter)]]
+    [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
+    [[`v`] [The value of a property (usually a template parameter)]]
+]
+
+[h4 Descriptor and Iterator Stability]
+With the `directed_graph` class, descriptors and iterators remain stable after
+all operations except descriptors and iterators to those edges or vertices being
+removed. Removing a vertex or edge will not invalidate descriptors or iterators
+referencing other vertices or edges.
+
+For example, consider the following code:
+
+    directed_graph<> g;
+    directed_graph<>::vertex_descriptor u = add_vertex(g);
+    directed_graph<>::vertex_descriptor v = add_vertex(g);
+    directed_graph<>::vertex_descriptor w = add_vertex(g);
+    remove_vertex(u);
+    add_edge(v, w, g);
+
+After running this program, the descriptor `u` will be invalid but `v` and `w` will
+still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
+property does not hold for all graph types.
+
+[h4 Vertex Indexing and Stability]
+The `directed_graph` class provides a built-in internal properties for vertex
+types, and will provide some degree of automated index management. Algorithms
+that use vertex indices generally assume that they are in the range
+\[0, `num_vertices(g)`). With the `directed_graph` class vertex indices will
+be in this continuous range until a vertex is removed from the graph. This is
+the only operation that invalidates vertex indices, but the vertices will need
+to be renumbered using the `renumber_vertex_indices()` function.
+
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
+[h4 Template Parameters]
+There are three parameters to the `directed_graph` class.
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`VertexProperties`]
+        [Specifies internal properties for vertices of the graph.]
+        [`no_property`]
+    ]
+    [
+        [`EdgeProperties`]
+        [Specifies internal properties for edges of the graph.]
+        [`no_property`]
+    ]
+    [
+        [`GraphProperties`]
+        [Specifies internal properties for the graph itself.]
+        [`no_property`]
+    ]
+]
+
+[h5 Model Of]
+[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
+[BoostMutableGraph], and [BoostPropertyGraph].
+
+[h5 Where Defined]
+`boost/graph/directed_graph.hpp`
+
+[h4 Associated Types]
+There are a number of useful types associated with the `directed_graph` class.
+Most of these are accessed through [boost_graph_traits] or other template classes.
+For convenience these types have been grouped by purpose.
+
+[h5 Descriptor Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<directed_graph>::vertex_descriptor`]
+        [
+            The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
+            models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::edge_descriptor`]
+        [
+            The type for the edge descriptors associated with the graph. The `edge_descriptor`
+            models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+        ]
+    ]
+]
+
+Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
+[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
+`std::tr1::unordered_map` respectively.
+
+[h5 Iterator Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<directed_graph>::vertex_iterator`]
+        [
+            The type for iterators returned by `vertices()`. Verex iterators are
+            models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::edge_iterator`]
+        [
+            The type for iterators returned by `edges()`. Edge iterators are
+            models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::out_edge_iterator`]
+        [
+            The type for iterators returned by `out_edges()`. Out-edge iterators
+            are models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::in_edge_iterator`]
+        [
+            The type for iterators returned by `in_edges()`. In-edge iterators
+            are models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::adjacency_iterator`]
+        [
+            The type for iterators returned by `adjacent_vertices`. Adjacency
+            iterators are models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+]
+
+[h5 Miscellaneous Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<directed_graph>::vertices_size_type`]
+        [The type used for dealing with the number of vertices in the graph.]
+    ]
+    [
+        [`graph_traits<directed_graph>::edge_size_type`]
+        [The type used for dealing with the number of edges in the graph.]
+    ]
+    [
+        [`graph_traits<directed_graph>::degree_size_type`]
+        [The type used for dealing with the number of edges incident to a vertex in the graph.]
+    ]
+    [
+        [`directed_graph::vertex_index_type`]
+        [The integral type representing vertex indices (generally `unsigned int`).]
+    ]
+    [
+        [
+            `property_map<directed_graph, Property>::type`
+
+            `property_map<directed_graph, Property>::const_type`
+        ]
+        [
+            The property map type for vertex or edge properties in the graph. The specific
+            property is specified by the `Property` template argument, and must match one of
+            the properties specified in the `VertexProperties` or `EdgeProperties` for the
+            graph.
+        ]
+    ]
+    [
+        [`graph_property<directed_graph, Property>::type`]
+        [
+            The value type for the graph property specified by the `Property` parameter.
+            `Property` must be one of the types in the `GraphProperties` template argument.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::directed_category`]
+        [
+            This is always `bidirectional_tag`, indicating that the graph supports in- and
+            out-edge operations.
+        ]
+    ]
+    [
+        [`graph_traits<directed_graph>::edge_parallel_category`]
+        [
+            This is always `allow_parallel_edges_tag`, indicating that multiple edges
+            may be added between two vertices (i.e., graphs can be /multigraphs/).
+        ]
+    ]
+]
+
+[h4 Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+directed_graph(const GraphProperties& p = GraphProperties())
+``
+        ]
+        [The default constructor creates a graph with no vertices or edges.]
+    ]
+    [
+        [
+``directed_graph(const directed_graph& g)
+``
+        ]
+        [The copy constructor creates a copy of the given graph `g`.]
+    ]
+    [
+        [
+``
+directed_graph(vertices_size_type n,
+                 const GraphProperties& p = GraphProperties())
+``
+        ]
+        [The default constructor creates a graph with `n` vertices and no edges.]
+    ]
+    [
+        [
+``directed_graph& operator =(const directed_graph& g)
+``
+        ]
+        [Copies the edges and vertices of the graph `g`.]
+    ]
+]
+
+[h4 Non-member Functions]
+[h5 Non-member Accessors]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+std::pair<vertex_iterator, vertex_iterator>
+vertices(const directed_graph& g)
+``
+        ]
+        [Returns an iterator range providing access to the vertex list of `g`.]
+    ]
+    [
+        [
+``
+std::pair<edge_iterator, edge_iterator>
+edges(const directed_graph& g)
+``
+        ]
+        [Returns an iterator range providing access to the edge list of `g`.]
+    ]
+    [
+        [
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+out_edges(vertex_descriptor v,
+          const directed_graph& g)
+``
+        ]
+        [
+            Returns an iterator range providing access to the out-edges of
+            vertex `v` in the graph `g`.
+        ]
+    ]
+    [
+        [
+``
+std::pair<in_edge_iterator, in_edge_iterator>
+in_edges(vertex_descriptor v,
+         const directed_graph& g)
+``
+        ]
+        [
+            Returns an iterator range providing access to the in-edges of
+            vertex `v` in the graph `g`.
+        ]
+    ]
+    [
+        [
+``
+std::pair<adjacency_iterator, adjacency_iterator>
+adjacent_vertices(vertex_descriptor v,
+                  const directed_graph& g)
+``
+        ]
+        [
+            Returns an iterator range providing access to the adjacenct vertices
+            of vertex `v` in the graph `g`. Note that this is functionally
+            equivalent to iterating over the targets of all out-edges of `v`.
+        ]
+    ]
+    [
+        [
+``
+vertices_size_type
+num_vertices(const directed_graph& g)
+``
+        ]
+        [Returns the number of vertices in the graph `g`.]
+    ]
+    [
+        [
+``
+edge_size_type
+num_edges(const directed_graph& g)
+``
+        ]
+        [Returns the number of edges the graph `g`.]
+    ]
+    [
+        [
+``
+degree_size_type
+degree(vertex_descriptor v,
+       const directed_graph& g)
+``
+        ]
+        [
+            Returns the total degree of vertex `v` in the graph `g`. This is
+            functionally equivalent `out_degree(v,g) + in_degree(v,g)`.
+        ]
+    ]
+    [
+        [
+``
+degree_size_type
+out_degree(vertex_descriptor v,
+           const directed_graph& g)
+``
+        ]
+        [
+            Returns the out-degree of vertex `v` in the graph `g`. In an
+            `directed_graph` this is equal to `in_degree(v, g)`.
+        ]
+    ]
+    [
+        [
+``
+degree_size_type
+in_degree(vertex_descriptor v,
+          const directed_graph& g)
+``
+        ]
+        [
+            Returns the in-degree of vertex `v` in the graph `g`. In an
+            `directed_graph` this is equal to `out_degree(v, g)`.
+        ]
+    ]
+    [
+        [
+``
+vertex_descriptor
+vertex(vertices_size_type n
+       const directed_graph& g)
+``
+        ]
+        [
+            Returns the /nth/ vertex in the graph `g`. With directed graphs,
+            this method is /O(n)/. As such its use with this type of graph is
+            discouraged.
+        ]
+    ]
+    [
+        [
+``
+std::pair<edge_descriptor, bool>
+edge(vertex_descriptor u,
+     vertex_descriptor v,
+     const directed_graph& g)
+``
+        ]
+        [
+            If the edge /(u,v)/ is in `g`, then this function returns the
+            descriptor for the edge connecting `u` and `v` with boolean value
+            set to `true`. Otherwise, the boolean value is `false` and the
+            edge descriptor is invalid.
+        ]
+    ]
+    [
+        [
+``
+vertex_size_type
+get_vertex_index(vertex_descriptor v,
+                 const directed_graph& g)
+``
+        ]
+        [
+            Returns the vertex index of the given vertex descriptor v. Note
+            that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+            This function is an alias for `get(vertex_index,g,v)`.
+        ]
+    ]
+    [
+        [
+``
+vertex_size_type
+max_vertex_index(vertex_descriptor v,
+                 const directed_graph& g)
+``
+        ]
+        [
+            Returns the vertex index of the given vertex descriptor v. Note
+            that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+            This function is an alias for `get(vertex_index,g,v)`.
+        ]
+    ]
+]
+
+[h5 Non-member Modifiers]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+vertex_descriptor
+add_vertex(directed_graph& g)
+``
+        ]
+        [Adds a vertex to `g` and returns a descriptors for the new vertex.]
+    ]
+    [
+        [
+``
+void
+clear_vertex(vertex_descriptor v,
+             directed_graph& g)
+``
+        ]
+        [
+            Removes all in- and out-edges of `v`, but leaves `v` in the graph `g`.
+            This is functioanlly equivalent to invoking `remove_edge()` on all
+            in- or out-edges of `v`, invalidating descriptors and iterators that
+            reference edges incident to `v`.
+        ]
+    ]
+    [
+        [
+``
+void
+clear_out_edges(vertex_descriptor v,
+                directed_graph& g)
+``
+        ]
+        [
+            Removes all out-edges from vertex `v`, but does not remove the vertex
+            itself. This is functionally equivalent to calling `remove_edge()` for
+            all out-edges of `v`, invalidating any descriptors and iterators that
+            reference edges incident to that vertex.
+        ]
+    ]
+    [
+        [
+``
+void
+clear_in_edges(vertex_descriptor v,
+               directed_graph& g)
+``
+        ]
+        [
+            Removes all in-edges from vertex `v`, but does not remove the vertex
+            itself. This is functionally equivalent to calling `remove_edge()` for
+            all in-edges of `v`, invalidating any descriptors and iterators that
+            reference edges incident to that vertex.
+        ]
+    ]
+    [
+        [
+``
+vertex_descriptor
+remove_vertex(vertex_descriptor v,
+              directed_graph& g)
+``
+        ]
+        [
+            Removes vertex `v` from the graph `g`. It is assumed that `v` has no
+            incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
+            before removing it.
+
+            Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
+            before calling this method, this operation will invalidate all vertex indices
+            in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
+            be renumbered using the `renumber_vertex_indices(g)` method. If possible,
+            prefer to remove groups of vertices at one time before renumbering since
+            renumbering is a /O(n)/ time operation.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_vertex_and_renumber_indices(vertex_iterator i,
+                                   directed_graph& g)
+``
+        ]
+        [
+            Removes the vertex indicated by the iterator `i` from the graph `g`. Like
+            the `remove_vertex(v,g)` function, it is expected that `*i` have no
+            incident edges at the time of removal.
+
+            As indicated by the name, this method will also renumber vertex indices
+            after the removal of `*i`. This operation iterates over vertices after
+            `i`, decrementing their index by 1. If your program removes several
+            vertices at once, prefer to call several `remove_vertex(v,g)` methods,
+            followed by `renumber_vertices(g)` before using `g` in an algorithm.
+        ]
+    ]
+    [
+        [
+``
+void
+renumber_vertex_indices(directed_graph& g)
+``
+        ]
+        [
+            Renumbers all interior vertex indices such that each vertex has an index
+            in the range \[0, `num_vertices(g)`). Generally, this function needs to
+            be called after removing vertices and before invoking different graph
+            algorithms.
+        ]
+    ]
+    [
+        [
+``
+std::pair<edge_descriptor, bool>
+add_edge(vertex_descriptor u,
+         vertex_descriptor v,
+         directed_graph& g)
+``
+        ]
+        [
+            Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
+            edge. For `directed_graph`s, the boolean value of the pair will always
+            be true.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge(vertex_descriptor u,
+            vertex_descriptor v,
+            directed_graph& g)
+``
+        ]
+        [
+            Removes the edge /(u,v)/from the graph. This operation invalidates any
+            descriptors or iterators referencing the edge. Note that `u` and `v` must
+            be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
+            (with multiple edges between /(u,v)/, this mehtod will cause the removal of
+            all such edges connecting `u` and `v`.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge(edge_descriptor e,
+            directed_graph& g)
+``
+        ]
+        [
+            Removes the edge `e` from the graph. If multuple edges exist from
+            /(`source(e,g)`, `target(e,g)`)/, then this method will remove only
+            the single, specified edge.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge(out_edge_iterator i,
+            directed_graph& g)
+``
+        ]
+        [
+            This is functionally equivalent to `remove_edge(*i, g)`.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge_if(Predicate p,
+               directed_graph& g)
+``
+        ]
+        [
+            Removes all edges from the graph that satisfy `predicate`. That is, if
+            `p()` returns true when applied to an edge, then that edge is removed.
+            The affect on descriptor and iterator is the same as that of invoking
+            `remove_edge()` for on each of the removed vertices.
+        ]
+    ]
+    [
+        [
+``
+template <class Predicate>
+void
+remove_out_edge_if(vertex_descriptor v,
+                   Predicate p,
+                   directed_graph& g)
+``
+        ]
+        [
+            Removes all edges out-edges from vertex`v` that satisfy `predicate`.
+            That is, if `p()` returns true when applied to an edge, then that edge
+            is removed. The affect on descriptor and iterator is the same as that
+            of invoking `remove_edge()` for on each of the removed vertices.
+        ]
+    ]
+    [
+        [
+``
+template <class Predicate>
+void
+remove_in_edge_if(vertex_descriptor v,
+                  Predicate p,
+                  directed_graph& g)
+``
+        ]
+        [
+            Removes all edges in-edges from vertex`v` that satisfy `predicate`.
+            That is, if `p()` returns true when applied to an edge, then that edge
+            is removed. The affect on descriptor and iterator is the same as that
+            of invoking `remove_edge()` for on each of the removed vertices.
+        ]
+    ]
+]
+
+[h5 Proprety Map Acessors]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+template <class Property>
+property_map<directed_graph, Property>::type
+get(Property, directed_graph& g)
+``
+
+``
+template <class Property>
+property_map<directed_graph, Property>::const_type
+get(Property, const directed_graph& g)
+``
+        ]
+        [
+            Returns the property map object for the vertex property specified by the
+            type `Property`. This type must match one of the properties specified in
+            the `VertexProperties` template argument.
+        ]
+    ]
+    [
+        [
+``
+template <class Property, class Descriptor>
+typename
+    property_traits<
+        property_map<directed_graph, Property>::const_type
+    >::value_type
+get(Property,
+    const directed_graph& g,
+    Descriptor d)
+``
+        ]
+        [
+            Returns the property value specified by the type `Property` for either
+            the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
+        ]
+    ]
+    [
+        [
+``
+template <class Property, class Descriptor, class Value>
+void
+put(Property,
+    const directed_graph& g,
+    Descriptor d,
+    Value v)
+``
+        ]
+        [
+            Sets the property value denoted by the type `Property` for either edge
+            or vertex descriptor `d` to the given value `v`.
+        ]
+    ]
+    [
+        [
+``
+template <class GraphProprety>
+typename graph_property<directed_graph, GraphProperty>::type&
+get_property(directed_graph& g, GraphProperty)
+``
+
+``
+template <class GraphProprety>
+const typename graph_property<directed_graph, GraphProperty>::type&
+get_property(const directed_graph& g, GraphProperty)
+``
+        ]
+        [
+            Returns the graph property specified by the type `GraphProperty` for
+            the graph `g`.
+        ]
+    ]
+    [
+        [
+``
+template <class GraphProprety, class Value>
+void
+set_property(const directed_graph& g, GraphProperty, Value v)
+``
+        ]
+        [
+            Sets the graph proeprty specified by the type `GraphProperty` to
+            the given value `v`. Note that `GraphProperty` must be one of
+            the properties in the `GraphProperties` template argument.
+        ]
+    ]
+]
+
+[h4 Rationale]
+Unlike most graph classes in Boost.Graph, the `directed_graph` does not model the
+[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+difficult from a usability standpoint to easily deduce the type to be passed as a
+property when adding vertices and edges - but especially vertices.
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,12 @@
+[/
+ / Copyright (c) 2007 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 Measures of Distances]
+
+
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distance_recorder.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,99 @@
+[/
+ / Copyright (c) 2007 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 Distance Recorder]
+
+    template <class DistanceMap, class EventTag>
+    class distance_recorder;
+
+This is an [BoostEventVisitor] that records the distance of a vertex (using a property
+map) from some source vertex during a graph search. When applied to edge /e = (u,v)/,
+the distance of /v/ is recorded to be one more than the distance of /u/. The distance
+recorder is typically used with the `on_tree_edge` or `on_relax_edge` events, and cannot
+be used with vertex events.
+
+The [boost_distance_recorder] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also,
+this event visitor can be combined with other event visitors using `std::pair` to form
+an [BoostEventVisitorList].
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`DistanceMap`]
+        [
+            A [BoostWritablePropertyMap] where the key type is of type `vertex_descriptor`
+            and the value type is numeric (usually an integer or the same type as the
+            edge weight).
+        ]
+    ]
+    [
+        [`EventTag`]
+        [
+            A tag used to specify when the recorder should be applied during the graph
+            algorithm. `EventTag` must be an edge event.
+        ]
+    ]
+]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`distance_recorder::event_filter`]
+        [
+            This type will be the same as the template parameter `EventTag`.
+        ]
+    ]
+]
+
+[h4 Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [`distance_recorder(DistanceMap pa)`]
+        [Construct a distance recorder object with a predecessor property map `pa`.]
+    ]
+    [
+        [
+``
+template <class Edge, class Graph>
+void operator()(Edge e, const Graph& g)
+``
+        ]
+        [
+            Given edge `e` as /(u,v)/, this records the distance of `v` as one
+            plus the distance of `u`.
+        ]
+    ]
+]
+
+[h4 Non-Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+template <class DistanceMap, class EventTag>
+distance_recorder<DistanceMap, EventTag>
+record_distances(DistanceMap pa, EventTag)
+``
+        ]
+        [
+            A convenience function for creating [boost_distance_recorder] instances.
+        ]
+    ]
+]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/distributions.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,175 @@
+[/
+ / Copyright (c) 2007 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 Degree Distributions]
+    void degree_distribution(
+        _graph,
+        _distribution = not_given(),
+        _out_distribution = not_given(),
+        _in_distribution = not_given())
+
+    void degree_histogram(
+        _graph,
+        _histogram = not_given(),
+        _out_histogram = not_given(),
+        _in_histogram = not_given())
+
+The degree distribution function compute distributions of the degrees
+of vertices in a graph. A distribution is mapping of an observable property
+to the number of occurences of that property. In this context, the observable
+property is the degree of a vertex (or in- and out-degree), which are in
+the range \[0, /max{degree(v)}/\] Where /max{degree(v)}/ is the maximum degree
+of any vertex in a graph /G/. Therefore, the output distribution is mapping
+of vertex degree to its number of occurences in a graph.
+
+This histogram functions are closely related to the degree distribution functions.
+However, instead of computing a mapping from vertex degree to the number of
+vertices, the histogram maps vertex degree to the /set of vertices/ that exhibit
+that degree. This is very useful if you want to quickly find all vertices with
+degree 0, or find the vertex with the highest degree.
+
+In both of these functions, the computation of distribution or histogram
+depends on which optional parameters are passed to the function. If called as:
+
+    degree_distribution(g, _distribution = dist, _in_distribution = in_dist);
+
+The algorithm will compute both the degree destribution and in-degree distributions.
+Note that for undirected graphs, all three distributions or histograms will be
+identical.
+
+[h5 Where Defined]
+`boost/graph/degree_distribution.hpp`
+
+[h5 Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [required, in] [`_graph`]
+        [
+            The graph object for which the distribution will be computed. If
+            the `_distribution` or `_in_distribution` arguments are supplied
+            when calling this function then `_graph` must be a model of
+            [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
+            then `_graph` must be a model of [BoostIncidenceGraph].
+        ]
+    ]
+    [
+        [optional, out]
+        [
+            `_distribution`
+
+            `_out_distribution`
+
+            `_in_distribution`
+        ]
+        [
+            The distribution parameters maps instances of vertex degree to the
+            number of observed vertices in the graph with that degree.
+
+            These parameters must model both the [SgiSequence] and
+            [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
+            distribution must be the same as `degree_size_type`. The `value_type` must
+            be integral (preferably unsigned).
+
+            If not supplied, these parameters assume the default value of `not_given`,
+            implying that no computation is performed.
+        ]
+    ]
+    [
+        [optional, out]
+        [
+            `_histogram`
+
+            `_out_histogram`
+
+            `_in_histogram`
+        ]
+        [
+            The distribution parameters maps instances of vertex degree to the
+            number of observed vertices in the graph with that degree.
+
+            The histogram output parameter must be a model of both [SgiSequence]
+            and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
+            distribution must be the same as `degree_size_type`. Additionally `value_type`
+            must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).
+
+            If not supplied, these parameters assume the default value of `not_given`,
+            implying that no computation is performed.
+        ]
+    ]
+]
+
+[h5 Return Value]
+Both functions return `void`.
+
+[h5 Complexity]
+The time complexity of all these functions is /O(V)/.
+
+The space complexity for the distributions functisons is /O(max{degree(v)})/ where
+/max{degree(v)}/ is the maxmimum degree of all vertices in a graph /G/.
+
+The space complexity for the histogram functions is /O(V + max{degree(v)})/.
+
+[h5 Notes]
+Because a graph may be a multigraph, there is no determinable upper bound on the
+size of the distribution or histogram parameters. As such they are required to
+be dynamically resized during the execution of the algorithm.
+
+The recommended type for the distribution parameters is:
+
+    std::vector<graph_traits<graph_type>::degree_size_type>
+
+where `graph_type` is the type of the `_graph` parameter. This satisfies the type
+requirements of the algorithms, and provides exceptional performance at the cost
+of extra memory overhead.
+
+The recommended type for the histogram parameters is:
+
+    std::vector<std::vector<graph_traits<graph_type>::vertex_descriptor> >
+
+Although this will consume more memory (due to the overhead of vector resizing),
+it may perform better than using `std::list` to store vertices of the same degree.
+This is because the `std::list::size()` function is not required to return in
+constant time.
+
+Note that if `dist` is the name of the output distribution after a call to
+`degree_distribution()` then the maximum degree is `dist.size() - 1`. The
+minimum degree corresponds to the index in `dist` with the first non-zero value.
+
+[h5 Examples]
+The first example show how to compute and print the degree distribution.
+
+    undirected_graph<> g;
+    // add vertices and edges to g
+
+    std::vector<size_t> dist;
+    degree_distribution(g, dist);
+    copy(dist.begin(), dist.end(), ostream_iterator<size_t>(cout, " "));
+
+The following example shows how to access the vertex (or vertices) with the maximum
+degree by using the `degree_histogram()` algorithm. This prints the index of that
+vertex.
+
+    undirected_graph<> g;
+    // add vertice and edges to g
+
+    typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
+    typedef std::vector<vertex_type> vertex_vector;
+
+    std::vector<vertex_vector> hist;
+    degree_histogram(g, hist);
+    cout << get_vertex_index(hist.back().back()) << "\n";
+
+[h5 Rationale]
+The use of these functions varies somewhat from typical use of named parameters
+where default values are simply used to supply default information. Here, they
+are used to control functionality. It should also be noted that if no parameters
+are supplied, this algorithm still runs in linear time. However, there is no
+additional overhead for not supplying a parameter because operations on the
+`not_given` type are no-opped (they are instantiated as empty functions).
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/edge_list.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/edge_list.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,10 @@
+[/
+ / Copyright (c) 2007 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 Edge List]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/predecessor_recorder.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,103 @@
+[/
+ / Copyright (c) 2007 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 Predecessor Recorder]
+
+    template <class PredecessorMap, class EventTag>
+    class predecessor_recorder;
+
+This is an [BoostEventVisitor] that records the predecessor (or parent) of a vertex in
+a predecessor property map. This is particularly useful in graph search algorithms where
+recording the predecessors is an efficient way to encode the search tree that was traversed
+during the search. The predecessor recorder is typically used with the `on_tree_edge` or
+`on_relax_edge events`, and cannot be used with vertex events.
+
+[boost_predecessor_recorder] can be used with graph algorithms by wrapping it with the
+algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also, this
+event visitor can be combined with other event visitors using `std::pair` to form an [BoostEventVisitorList].
+
+Algorithms such as Dijkstra's and breadth-first search will not assign a predecessor
+to the source vertex (which is the root of the search tree). Often times it is useful to
+initialize the source vertex's predecessor to itself, thereby identifying the root vertex
+as the only vertex which is its own parent. When using an algorithm like depth-first search
+that creates a forest (multiple search trees), it is useful to intialize the predecessor
+of every vertex to itself, so that all the root nodes can be distinguished.
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`PredecessorMap`]
+        [
+            A [BoostWritablePropertyMap] where the key type and value type are  of type
+            `vertex_descriptor`.
+        ]
+    ]
+    [
+        [`EventTag`]
+        [
+            A tag used to specify when the recorder should be applied during the graph
+            algorithm. `EventTag` must be an edge event.
+        ]
+    ]
+]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`predecessor_recorder::event_filter`]
+        [
+            This type will be the same as the template parameter `EventTag`.
+        ]
+    ]
+]
+
+[h4 Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [`predecessor_recorder(PredecessorMap pa)`]
+        [Construct a predecessor recorder object with a predecessor property map `pa`.]
+    ]
+    [
+        [
+``
+template <class Edge, class Graph>
+void operator()(Edge e, const Graph& g)
+``
+        ]
+        [
+            Given edge `e` as /(u,v)/, this records `u` as the predecessor (parent) of `v`.
+        ]
+    ]
+]
+
+[h4 Non-Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+template <class PredecessorMap, class EventTag>
+predecessor_recorder<PredecessorMap, EventTag>
+record_predecessors(PredecessorMap pa, EventTag)
+``
+        ]
+        [
+            A convenience function for creating [boost_predecessor_recorder] instances.
+        ]
+    ]
+]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/property_writer.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,103 @@
+[/
+ / Copyright (c) 2007 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 Property Writer]
+
+    template <class PropertyMap, class OutputIterator, class EventTag>
+    class property_writer;
+
+This is an [BoostEventVisitor] that can be used to output the property of a vertex
+or edge at some event-point within an algorithm.
+
+The [boost_property_writer] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor].
+Also, this event visitor can be combined with other event visitors using `std::pair` to
+form an [BoostEventVisitorList].
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`PropertyMap`]
+        [
+            A [BoostReadablePropertyMap] where the `key_type` is of type `vertex_descriptor`
+            of `edge_descriptor` (depending on the event tag) and the `value_type` type is
+            of the property is convertible to the `value_type` of the `OutputIterator`.
+        ]
+    ]
+    [
+        [`OutputIterator`]
+        [
+            The iterator type used to write the property values must be a model of
+            [SgiOutputIterator].
+        ]
+    ]
+    [
+        [`EventTag`]
+        [
+            A tag used to specify when the property writer should be applied during the graph
+            algorithm.
+        ]
+    ]
+]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`property_writer::event_filter`]
+        [
+            This type will be the same as the template parameter `EventTag`.
+        ]
+    ]
+]
+
+[h4 Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [`property_writer(PropertyMap pa, OutputIterator out)`]
+        [Construct a property writer object with a property map `pa` and an output iterator `out`.]
+    ]
+    [
+        [
+``
+template <class X, class Graph>
+void operator()(X x, const Graph& g)
+``
+        ]
+        [
+            This writes the property value for `x` to the output iterator. Specifically,
+            `*out++ = get(pa, x)`.
+        ]
+    ]
+]
+
+[h4 Non-Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+template <class PropertyMap, class OutputIterator, class EventTag>
+time_stamper<PropertyMap, OutputIterator, EventTag>
+stamp_times(Property pa, OutputIterator out, EventTag)
+``
+        ]
+        [
+            A convenience function for creating [boost_property_writer] instances.
+        ]
+    ]
+]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,68 @@
+[/
+ / Copyright (c) 2007 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 Reference Guide]
+
+[section Graph Types]
+[include undirected_graph.qbk]
+[include directed_graph.qbk]
+[include adjacency_list.qbk]
+[include edge_list.qbk]
+[endsect]
+
+[section Traits Classes]
+[endsect]
+
+[section Event Visitor List Adaptors]
+[include bfs_visitor.qbk]
+[include dfs_visitor.qbk]
+[include dijkstra_visitor.qbk]
+[include bellman_visitor.qbk]
+[include astar_visitor.qbk]
+[endsect]
+
+[section Event Visitors]
+[include predecessor_recorder.qbk]
+[include distance_recorder.qbk]
+[include time_stamper.qbk]
+[include property_writer.qbk]
+[endsect]
+
+[section Algorithms]
+[section Core Algorithms]
+[include breadth_first_search.qbk]
+[include depth_first_search.qbk]
+[endsect]
+
+[section Shortest Path Algorithms]
+[endsect]
+
+[section Minimum Spanning Tree Algorithms]
+[endsect]
+
+[section Connectivity Algorithms]
+[include connected_components.qbk]
+[include strong_components.qbk]
+[include connectivity.qbk]
+[endsect]
+
+[section Maximum Flow Algorithms]
+[endsect]
+
+[section Sparse Matrix Ordering Algorithms]
+[endsect]
+
+[section Layout Algorithms]
+[endsect]
+
+[section Graph Measures]
+[include distributions.qbk]
+[include distance.qbk]
+[endsect]
+[endsect]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/strong_components.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/strong_components.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,116 @@
+[/
+ / Copyright (c) 2007 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 Strongly Connected Components]
+
+ template <class Graph, class ComponentMap, class P, class T, class R>
+ typename property_traits<ComponentMap>::value_type
+ strong_components(const Graph &g, ComponentMap c,
+                   const bgl_named_params<P,T,R>& params = ``/defaults/``);
+
+The `strong_components()` functions compute the strongly connected components of a
+directed graph using Tarjan's algorithm based on DFS \[41\].
+
+The output of the algorithm is recorded in the component property map, which will
+contain numbers giving the component number assigned to each vertex. This algorithm
+returns the number of strongly connected components in the graph.
+
+[heading Where Defined]
+`boost/graph/strong_components.hpp`
+
+[heading Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [in] [`const Graph& g`]
+        [
+            The /directed/ graph for which connected components are being found.
+             This graph must be a model of VertexListGraph and Incidence Graph.
+        ]
+    ]
+    [
+        [out] [`ComponentMap c`]
+        [
+            The algorithm computes how many connected components are in the graph,
+            and assigning each component an integer label. The algorithm then records
+            which component each vertex in the graph belongs to by recording the
+            component number in the component property map. The ComponentMap type
+            must be a model of WritablePropertyMap. The value type shouch be an
+            integer type, preferably the same as the `vertices_size_type` of the
+            graph. The key type must be the graph's `vertex_descriptor` type.
+        ]
+    ]
+]
+
+[heading Named Parameters]
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [util] [`root_map(RootMap root_map)`]
+        [
+            This is used by the algorithm to record the candidate root vertex for each
+            vertex. By the end of the algorithm, there is a single root vertex for each
+            component and `get(root_map, v)` returns the root vertex for whichever
+            component vertex `v` is a member. The `RootMap` must be a ReadWritePropertyMap,
+            where the key type and the value type are the vertex descriptor type of the
+            graph.
+
+            *Default* An iterator_property_map created from a `std::vector` of
+            `vertex_descriptor`s of size `num_vertices(g)` and using the `index_map`
+            for accessing root vertices.
+        ]
+    ]
+    [
+        [util] [`discover_time_map(TimeMap time_map)`]
+        [
+            This is used by the algorithm to keep track of the DFS ordering of the vertices.
+            The `TimeMap` must be a model of ReadWritePropertyMap and its value type must
+            be an integer type. The key type must be the vertex descriptor type of the graph.
+
+            *Default* An iterator_property_map created from a `std::vector` of integers
+            of size `num_vertices(g)` and using the `index_map` for accessing root vertices.
+        ]
+    ]
+    [
+        [util] [`color_map(ColorMap color)`]
+        [
+            This is used by the algorithm to keep track of its progress through the
+            graph. The type ColorMap must be a model of ReadWritePropertyMap and
+            its key type must be the graph's `vertex_descriptor` type and the value
+            type of the color map must model ColorValue.
+
+            *Default* An `iterator_property_map` create from a `std::vector` of
+            `default_color_type` of size `num_vertices(g)` and using `index_map` as
+            the index map (to access colors for a vertex).
+        ]
+    ]
+    [
+        [in] [`vertex_index_map(VertexIndexMap index_map)`]
+        [
+            This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+            This parameter is only necessary when the default color property map is
+            used. The type VertexIndexMap must be a model of ReadablePropertyMap. 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.
+
+            *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+            that your graph has an interior `vertex_index` property. For example
+            `adjacency_list` with `VertexList=listS` does not have an interior
+            `vertex_index` property.
+        ]
+    ]
+]
+
+[heading Complexity]
+This algorithm runs in /O(V + E)/.
+
+[heading Notes]
+This algorithm will not compile if passed a /directed/ graph.
+
+[heading Examples]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/time_stamper.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,104 @@
+[/
+ / Copyright (c) 2007 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 Time Stamper]
+
+    template <class TimeMap, class TimeT, class EventTag>
+    class time_stamper;
+
+This is an [BoostEventVisitor] that can be used to "stamp" a time at some event-point
+within an algorithm. An example of this is recording the discover or finish time of
+a vertex during a graph search.
+
+The [boost_time_stamper] class can be used with graph algorithms by wrapping it with
+the algorithm specific adaptor, such as [boost_bfs_visitor] and [boost_dfs_visitor]. Also,
+this event visitor can be combined with other event visitors using `std::pair` to
+form an [BoostEventVisitorList].
+
+[h4 Model Of]
+[BoostEventVisitor]
+
+[h4 Where Defined]
+`boost/graph/visitors.hpp`
+
+[h4 Template Parameters]
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`TimeMap`]
+        [
+            A [BoostWritablePropertyMap] where the key type is of type `vertex_descriptor`
+            of `edge_descriptor` (depending on the event tag) and `TimeT` must be convertible
+            to the value type.
+        ]
+    ]
+    [
+        [`TimeT`]
+        [
+            The type of the time counter, which should be convertible to the `value_type` of
+            TimeMap.
+        ]
+    ]
+    [
+        [`EventTag`]
+        [
+            A tag used to specify when the time stamper should be applied during the graph
+            algorithm.
+        ]
+    ]
+]
+
+[h4 Associated Types]
+[table
+    [[Type] [Description]]
+    [
+        [`time_stamper::event_filter`]
+        [
+            This type will be the same as the template parameter `EventTag`.
+        ]
+    ]
+]
+
+[h4 Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [`time_stamper(Timemap pa, TimeT& t)`]
+        [Construct a time stamper object with a timestamp property map `pa` and time counter `t`.]
+    ]
+    [
+        [
+``
+template <class X, class Graph>
+void operator()(X x, const Graph& g)
+``
+        ]
+        [
+            This records the current timestamp for the edge or vertex in the property map
+            and increments the time count.
+        ]
+    ]
+]
+
+[h4 Non-Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+template <class TimeMap, class TimeT, class EventTag>
+time_stamper<TimeMap, EventTag>
+stamp_times(TimeMap pa, TimeT& t, EventTag)
+``
+        ]
+        [
+            A convenience function for creating [boost_time_stamper] instances.
+        ]
+    ]
+]
+
+[endsect]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/undirected_graph.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,743 @@
+[/
+ / Copyright (c) 2007 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 Undirected Graph]
+
+    template <class VertexProperties, class EdgeProperties, class GraphProperties>
+    class undirected_graph;
+
+This section provides detailed information about the `undirected_graph` class,
+its associated types, member functions and non-member interface. An undirected graph
+is one in which edges have no direction - this is to say that edges can be "traveled"
+in both directions. This class provides general purpose implementation of undirected
+graphs and can be used with algorithms in the Boost Graph Library.
+
+[h4 Notation]
+The following notation is used in this documentation. The following type names
+are generally meant to mean the following:
+
+[table
+    [[Used Type] [Actual Type]]
+    [
+        [`undirected_graph`]
+        [
+            `undirected_graph<VP,EP,GP>` where `VP`, `EP` and `GP` are template
+            arguments that correspond to user-defined or default verex properties,
+            edge properties, and graph properties.
+        ]
+    ]
+    [
+        [`vertex_descriptor`]
+        [`undirected_graph<VP,EP,GP>::vertex_descriptor`]
+    ]
+    [
+        [`edge_descriptor`]
+        [`undirected_graph<VP,EP,GP>::edge_descriptor`]
+    ]
+    [
+        [`vertex_iterator`]
+        [`undirected_graph<VP,EP,GP>::vertex_iterator`]
+    ]
+    [
+        [`edge_iterator`]
+        [`undirected_graph<VP,EP,GP>::edge_iterator`]
+    ]
+]
+
+Moreover, objects with the following names are generally expected to have the
+following types.
+
+[table
+    [[Object Name] [Type]]
+    [[`g`] [`undirected_graph`]]
+    [[`u`, `v`] [`vertex_descriptor`]]
+    [[`e`] [`edge_descriptor`]]
+    [[`i`] [`vertex_iterator` or `edge_iterator`]]
+    [[`p`] [A property tag (usually a template parameter)]]
+    [[`d`] [A vertex or edge descriptor (usually a template parameter)]]
+    [[`v`] [The value of a property (usually a template parameter)]]
+]
+
+[h4 Descriptor and Iterator Stability]
+With the `undirected_graph` class, descriptors and iterators remain stable after
+all operations except descriptors and iterators referencing the vertices and edges
+that have been removed. Removing a vertex or edge will not invalidate descriptors
+and iterators to other vertices or edges.
+
+For example, consider the following code:
+
+    undirected_graph<> g;
+    undirected_graph<>::vertex_descriptor u = add_vertex(g);
+    undirected_graph<>::vertex_descriptor v = add_vertex(g);
+    undirected_graph<>::vertex_descriptor w = add_vertex(g);
+    remove_vertex(u);
+    add_edge(v, w, g);
+
+After running this program, the descriptor `u` will be invalid but `v` and `w` will
+still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
+property does not hold for all graph types.
+
+[h4 Vertex Indexing and Stability]
+The `undirected_graph` class provides a built-in internal properties for vertex
+types, and will provide semi-automated index management. Algorithms that use vertex
+indices generally assume that they are in the range \[0, `num_vertices(g)`). With
+the `undirected_graph` class vertex indices will be in this continuous range until
+a vertex is removed from the graph. This is the only operation that invalidates
+vertex indices, but the vertices will need to be renumbered using the
+`renumber_vertex_indices(g)` function.
+
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
+[h4 Function Names for Directed and Undirected Graphs]
+Many of the  operations in the Boost Graph library are named in accordance
+with the concepts of directed graphs, specifically the use of out-edges as the
+canonical adjacencty list for vertices. As a result, undirected graphs also
+use the out-edge terminology to refern to its incident edges, but in-edge operations
+are identical in behavior to out-edge operations.
+
+There are three sets of operations that have multiple names and duplicate behaviors:
+`*degree()`-computing functions, `*_edge()`-iterating accessors, and the `remove_*_edge()`
+predicate-based functions. These functions are grouped together in their reference
+sections.
+
+This class also introduces two new functions, `incident_edges(g)` that returns an
+iterator range to the incident edges of `g`, and `remove_incident_edges_if(v,p,g)`.
+These are identical in behavior to their `in` and `out` counterparts.  These
+functions are only provided for semantic consistency so developers should be aware
+that these new functions are /not/ defined for any other graph classes in the
+Boost Graph Library.
+
+Developers of generic algoriths should be aware that, when generalizing an algorithm
+for both directed and undirected graphs, it is better to use the `out_degree(g)`
+function to access out-edges since it is guaranteed by every other graph class.
+
+[h5 Model Of]
+[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
+[BoostMutableGraph], and [BoostPropertyGraph].
+
+[h4 Template Parameters]
+There are only three parameters to the `undirected_graph` class.
+[table
+    [[Parameter] [Description] [Default]]
+    [
+        [`VertexProperties`]
+        [Specifies internal properties for vertices of the graph.]
+        [`no_property`]
+    ]
+    [
+        [`EdgeProperties`]
+        [Specifies internal properties for edges of the graph.]
+        [`no_property`]
+    ]
+    [
+        [`GraphProperties`]
+        [Specifies internal properties for the graph itself.]
+        [`no_property`]
+    ]
+]
+
+Additionally, the `undirected_graph` class provides a non-constant time implementation
+of the [BoostAdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
+the concept.
+
+[h4 Where Defined]
+`boost/graph/undirected_graph.hpp`
+
+[h4 Associated Types]
+There are a number of useful types associated with the `undirected_graph` class.
+Most of these are accessed through `graph_traits` or other template classes.
+For convenience these types have been grouped by purpose.
+
+[h5 Descriptor Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<undirected_graph>::vertex_descriptor`]
+        [
+            The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
+            models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::edge_descriptor`]
+        [
+            The type for the edge descriptors associated with the graph. The `edge_descriptor`
+            models the [BoostDescriptor] and [NoConcept Hashable] concepts.
+        ]
+    ]
+]
+
+Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
+[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
+`std::tr1::unordered_map` respectively.
+
+[h5 Iterator Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<undirected_graph>::vertex_iterator`]
+        [
+            The type for iterators returned by `vertices()`. Verex iterators are
+            models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::edge_iterator`]
+        [
+            The type for iterators returned by `edges()`. Edge iterators are
+            models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::out_edge_iterator`]
+        [
+            The type for iterators returned by `out_edges()`. Out-edge iterators
+            are models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::in_edge_iterator`]
+        [
+            The type for iterators returned by `in_edges()`. In-edge iterators
+            are models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::adjacency_iterator`]
+        [
+            The type for iterators returned by `adjacent_vertices`. Adjacency
+            iterators are models of the [SgiBidirectionalIterator] concept.
+        ]
+    ]
+]
+
+[h5 Miscellaneous Types]
+[table
+    [[Type] [Description]]
+    [
+        [`graph_traits<undirected_graph>::vertices_size_type`]
+        [The type used for dealing with the number of vertices in the graph.]
+    ]
+    [
+        [`graph_traits<undirected_graph>::edge_size_type`]
+        [The type used for dealing with the number of edges in the graph.]
+    ]
+    [
+        [`graph_traits<undirected_graph>::degree_size_type`]
+        [The type used for dealing with the number of edges incident to a vertex in the graph.]
+    ]
+    [
+        [`undirected_graph::vertex_index_type`]
+        [The integral type representing vertex indices (generally `unsigned int`).]
+    ]
+    [
+        [
+            `property_map<undirected_graph, Property>::type`
+
+            `property_map<undirected_graph, Property>::const_type`
+        ]
+        [
+            The property map type for vertex or edge properties in the graph. The specific
+            property is specified by the `Property` template argument, and must match one of
+            the properties specified in the `VertexProperties` or `EdgeProperties` for the
+            graph.
+        ]
+    ]
+    [
+        [`graph_property<undirected_graph, Property>::type`]
+        [
+            The value type for the graph property specified by the `Property` parameter.
+            `Property` must be one of the types in the `GraphProperties` template argument.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::directed_category`]
+        [
+            This is always `undirectedS`, indicating that the graph supports operations
+            for undirected graphs.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::edge_parallel_category`]
+        [
+            This is always `allow_parallel_edges_tag`, indicating that multiple edges
+            may be added between two vertices (i.e., graphs can be /multigraphs/).
+        ]
+    ]
+]
+
+[h4 Member Functions]
+[table
+    [[Function] [Description]]
+    [
+        [`undirected_graph(const GraphProperties& p = GraphProperties()`]
+        [The default constructor creates a graph with no vertices or edges.]
+    ]
+    [
+        [`undirected_graph(const undirected_graph& x`)]
+        [The copy constructor creates a copy of the given graph `x`.]
+    ]
+    [
+        [
+``
+undirected_graph(vertices_size_type n,
+                 const GraphProperties& p = GraphProperties())
+``
+        ]
+        [The default constructor creates a graph with `n` vertices and no edges.]
+    ]
+    [
+        [`undirected_graph& operator =(const undirected_graph& x)`]
+        [Copies the edges and vertices of the graph `x`.]
+    ]
+]
+
+[h4 Non-member Functions]
+[h5 Non-member Accessors]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+std::pair<vertex_iterator, vertex_iterator>
+vertices(const undirected_graph& g)
+``
+        ]
+        [Returns an iterator range providing access to the vertex list of `g`.]
+    ]
+    [
+        [
+``
+std::pair<edge_iterator, edge_iterator>
+edges(const undirected_graph& g)
+``
+        ]
+        [Returns an iterator range providing access to the edge list of `g`.]
+    ]
+    [
+        [
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+incident_edges(vertex_descriptor v, const undirected_graph& g)
+``
+
+``
+std::pair<out_edge_iterator, out_edge_iterator>
+out_edges(vertex_descriptor v, const undirected_graph& g)
+``
+
+``
+std::pair<in_edge_iterator, in_edge_iterator>
+in_edges(vertex_descriptor v, const undirected_graph& g)
+``
+        ]
+        [
+            Returns an iterator range providing access to the incident edges
+            of the vertex `v`. Because `g` is an undirected graph, these three
+            functions are guaranteed to return identical iterator ranges.
+        ]
+    ]
+    [
+        [
+``
+std::pair<adjacency_iterator, adjacency_iterator>
+adjacent_vertices(vertex_descriptor v,
+                  const undirected_graph& g)
+``
+        ]
+        [
+            Returns an iterator range providing access to the adjacenct vertices
+            of vertex `v` in the graph `g`. Note that this is functionally
+            equivalent to iterating over the targets of all incident edges of `v`.
+        ]
+    ]
+    [
+        [
+``
+vertices_size_type
+num_vertices(const undirected_graph& g)
+``
+        ]
+        [Returns the number of vertices in the graph `g`.]
+    ]
+    [
+        [
+``
+edge_size_type
+num_edges(const undirected_graph& g)
+``
+        ]
+        [Returns the number of edges the graph `g`.]
+    ]
+    [
+        [
+``
+degree_size_type
+degree(vertex_descriptor v,
+       const undirected_graph& g)
+``
+
+``
+degree_size_type
+out_degree(vertex_descriptor v,
+           const undirected_graph& g)
+``
+
+``
+degree_size_type
+in_degree(vertex_descriptor v,
+          const undirected_graph& g)
+``
+        ]
+        [
+            Returns the degree of the vertex `v`, which is the number of
+            edges incident to it. Because `g` is undirected, all three
+            functions return equal values.
+        ]
+    ]
+    [
+        [
+``
+vertex_descriptor
+vertex(vertices_size_type n
+       const undirected_graph& g)
+``
+        ]
+        [
+            Returns the /nth/ vertex in the graph `g`. With undirected graphs,
+            this method is /O(n)/. As such its use with this type of graph is
+            discouraged.
+        ]
+    ]
+    [
+        [
+``
+std::pair<edge_descriptor, bool>
+edge(vertex_descriptor u,
+     vertex_descriptor v,
+     const undirected_graph& g)
+``
+        ]
+        [
+            If the edge (`u`,`v`) is in `g`, then this function returns the
+            descriptor for the edge connecting `u` and `v` with boolean value
+            set to `true`. Otherwise, the boolean value is `false` and the
+            edge descriptor is invalid.
+        ]
+    ]
+    [
+        [
+``
+vertex_size_type
+get_vertex_index(vertex_descriptor v,
+                 const undirected_graph& g)
+``
+        ]
+        [
+            Returns the vertex index of the given vertex descriptor v. Note
+            that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+            This function is an alias for `get(vertex_index,g,v)`.
+        ]
+    ]
+    [
+        [
+``
+vertex_size_type
+max_vertex_index(vertex_descriptor v,
+                 const undirected_graph& g)
+``
+        ]
+        [
+            Returns the vertex index of the given vertex descriptor v. Note
+            that indices are /not/ required to be in the range \[0, `num_vertices(g)`).
+            This function is an alias for `get(vertex_index,g,v)`.
+        ]
+    ]
+]
+
+[h5 Non-member Modifiers]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+vertex_descriptor
+add_vertex(undirected_graph& g)
+``
+        ]
+        [Adds a vertex to `g` and returns a descriptors for the new vertex.]
+    ]
+    [
+        [
+``
+void
+clear_vertex(vertex_descriptor v,
+             undirected_graph& g)
+``
+        ]
+        [
+            Removes all in- and out-edges of `v`, but leaves `v` in the graph `g`.
+            This is functioanlly equivalent to invoking `remove_edge()` on all
+            in- or out-edges of `v`, potentially invalidating descriptors and
+            iterators.
+        ]
+    ]
+    [
+        [
+``
+vertex_descriptor
+remove_vertex(vertex_descriptor v,
+              undirected_graph& g)
+``
+        ]
+        [
+            Removes vertex `v` from the graph `g`. It is assumed that `v` has no
+            incident edges before removal. To ensure this is, call `clear_vertex(v, g)`
+            before removing it.
+
+            Assuming that the vertex indices were in the range \[0, `num_vertices(g)`)
+            before calling this method, this operation will invalidate all vertex indices
+            in the range (vertex_index(v, g), `num_vertices(g)`), requiring indices to
+            be renumbered using the `renumber_vertex_indices(g)` method. If possible,
+            prefer to remove groups of vertices at one time before renumbering since
+            renumbering is a /O(n)/ time operation.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_vertex_and_renumber_indices(vertex_iterator i,
+                                   undirected_graph& g)
+``
+        ]
+        [
+            Removes the vertex indicated by the iterator `i` from the graph `g`. Like
+            the `remove_vertex(v,g)` function, it is expected that `*i` have no
+            incident edges at the time of removal.
+
+            As indicated by the name, this method will also renumber vertex indices
+            after the removal of `*i`. This operation iterates over vertices after
+            `i`, decrementing their index by 1. If your program removes several
+            vertices at once, prefer to call several `remove_vertex(v,g)` methods,
+            followed by `renumber_vertices(g)` before using `g` in an algorithm.
+        ]
+    ]
+    [
+        [
+``
+void
+renumber_vertex_indices(undirected_graph& g)
+``
+        ]
+        [
+            Renumbers all interior vertex indices such that each vertex has an index
+            in the range \[0, `num_vertices(g)`). Generally, this function needs to
+            be called after removing vertices and before invoking graph algorithms.
+        ]
+    ]
+    [
+        [
+``
+std::pair<edge_descriptor, bool>
+add_edge(vertex_descriptor u,
+         vertex_descriptor v,
+         undirected_graph& g)
+``
+        ]
+        [
+            Adds the edge /(u,v)/ to the graph and returns a descriptor for the new
+            edge. For `undirected_graph`s, the boolean value of the pair will always
+            be true.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge(vertex_descriptor u,
+            vertex_descriptor v,
+            undirected_graph& g)
+``
+        ]
+        [
+            Removes the edge /(u,v)/ from the graph. This operation invalidates any
+            descriptors or iterators referencing the edge. Note that `u` and `v` must
+            be valid descriptors and /(u,v)/ must be in the graph. If `g` is a multigraph
+            (with multiple edges between /(u,v)/, this mehtod will cause the removal of
+            all such edges connecting `u` and `v`.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge(edge_descriptor e,
+            undirected_graph& g)
+``
+        ]
+        [
+            Removes the edge `e` from the graph. If multuple edges exist from
+            (`source(e,g)`, `target(e,g)`), then this method will remove only
+            the single, specified edge.
+        ]
+    ]
+    [
+        [
+``
+void
+remove_edge(out_edge_iterator i,
+            undirected_graph& g)
+``
+        ]
+        [
+            This is functionally equivalent to `remove_edge(*i, g)`.
+        ]
+    ]
+    [
+        [
+``
+template <class Predicate> void
+remove_edge_if(Predicate p, undirected_graph& g)
+``
+        ]
+        [
+            Removes all edges from the graph that satisfy `predicate`. That is, if
+            `p()` returns true when applied to an edge, then that edge is removed.
+            The affect on descriptor and iterator is the same as that of invoking
+            `remove_edge()` for on each of the removed vertices.
+        ]
+    ]
+    [
+        [
+``
+template <class Predicate> void
+remove_incident_edge_if(vertex_descriptor v, Predicate p
+                        undirected_graph& g)
+``
+
+``
+template <class Predicate> void
+remove_out_edge_if(vertex_descriptor v, Predicate p,
+                   undirected_graph& g)
+``
+
+``
+template <class Predicate> void
+remove_in_edge_if(vertex_descriptor v, Predicate p,
+                  undirected_graph& g)
+``
+        ]
+        [
+            Removes all edges incident-edges from vertex`v` that satisfy `predicate`.
+            That is, if `p()` returns true when applied to an edge, then that edge
+            is removed. The affect on descriptor and iterator is the same as that
+            of invoking `remove_edge()` for on each of the removed vertices.
+
+            Because this graph is undirected, these three funtions are identical
+            in behavior and run time.
+        ]
+    ]
+]
+
+[h5 Proprety Map Acessors]
+[table
+    [[Function] [Description]]
+    [
+        [
+``
+template <class Property>
+property_map<undirected_graph, Property>::type
+get(Property,
+    const undirected_graph& g)
+``
+        ]
+        [
+            Returns the property map object for the vertex property specified by the
+            type `Property`. This type must match one of the properties specified in
+            the `VertexProperties` template argument.
+        ]
+    ]
+    [
+        [
+``
+template <class Property, class Descriptor>
+typename
+    property_traits<
+        property_map<undirected_graph, Property>::const_type
+    >::value_type
+get(Property,
+    const undirected_graph& g,
+    Descriptor d)
+``
+        ]
+        [
+            Returns the property value specified by the type `Property` for either
+            the `vertex_descriptor` or `edge_descriptor` denoted by `d`.
+        ]
+    ]
+    [
+        [
+``
+template <class Property, class Descriptor, class Value>
+void
+put(Property,
+    const undirected_graph& g,
+    Descriptor d,
+    Value v)
+``
+        ]
+        [
+            Sets the property value denoted by the type `Property` for either edge
+            or vertex descriptor `d` to the given value `v`.
+        ]
+    ]
+    [
+        [
+``
+template <class GraphProperty>
+typename graph_property<undirected_graph, GraphProperty>::type&
+get_property(undirected_graph& g, GraphProperty)
+``
+
+``
+template <class GraphProperty>
+const typename graph_property<undirected_graph, GraphProperty>::type&
+get_property(const undirected_graph& g, GraphProperty)
+``
+        ]
+        [
+            Returns the graph property specified by the type `GraphProperty` for
+            the graph `g`. Here, GraphProperty must be one of the properties
+            in the `GraphProperties` template argument.
+        ]
+    ]
+    [
+        [
+``
+template <class GraphProprety, class Value>
+void
+set_property(const undirected_graph& g, GraphProperty, Value v)
+``
+        ]
+        [
+            Sets the graph proeprty specified by the type `GraphProperty` to
+            the given value `v`. Note that `GraphProperty` must be one of
+            the properties in the `GraphProperties` template argument.
+        ]
+    ]
+]
+
+[h4 Rationale]
+Unlike most graph classes in Boost.Graph, the `undirected_graph` does not model the
+[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+difficult (from a usability standpoint) to easily deduce the type to be passed as a
+property when adding vertices and edges - but especially vertices.
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,41 @@
+[/
+ / Copyright (c) 2007 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)
+ /]
+
+[/
+ / This file defines templates that expand to links to the SGI-defined
+ / STL concepts.
+ /]
+
+[/ Missing documentation /]
+[template NoConcept[x] [x]]
+
+[template SgiAssignable[] [@http://www.sgi.com/tech/stl/Assignable.html Assignable]]
+[template SgiDefaultConstructible[] [@http://www.sgi.com/tech/stl/DefaultConstructible.html DefaultConstructible]]
+[template SgiCopyConstructible[] [@http://www.sgi.com/tech/stl/CopyConstructible.html CopyConstructible]]
+[template SgiEqualityComparable[] [@http://www.sgi.com/tech/stl/EqualityComparable.html EqualityComparable]]
+[template SgiLessThanComparable[] [@http://www.sgi.com/tech/stl/LessThanComparable.html LessThanComparable]]
+
+[template SgiContainer[] [@http://www.sgi.com/tech/stl/Container.html Container]]
+[template SgiForwardContainer[] [@http://www.sgi.com/tech/stl/ForwardContainer.html ForwardContainer]]
+[template SgiReversibleContainer[] [@http://www.sgi.com/tech/stl/ReversibleContainer.html ReversibleContainer]]
+[template SgiRandomAccessContainer[] [@http://www.sgi.com/tech/stl/RandomAccessContainer.html RandomAccessContainer]]
+
+[template SgiSequence[] [@http://www.sgi.com/tech/stl/Sequence.html Sequence]]
+[template SgiFrontInsertionSequence[] [@http://www.sgi.com/tech/stl/FrontInsertionSequence.html FrontInsertionSequence]]
+[template SgiBackInsertionSequence[] [@http://www.sgi.com/tech/stl/BackInsertionSequence.html BackInsertionSequence]]
+
+[template SgiAssociativeContainer[] [@http://www.sgi.com/tech/stl/AssociativeContainer.html AssociativeContainer]]
+[template SgiSortedAssociativeContainer[] [@http://www.sgi.com/tech/stl/SortedAssociativeContainer.html SortedAssociativeContainer]]
+[template SgiHashedAssociativeContainer[] [@http://www.sgi.com/tech/stl/HashedAssociativeContainer.html HashedAssociativeContainer]]
+
+[template SgiInputIterator[] [@http://www.sgi.com/tech/stl/InputIterator.html BidirectionalIterator]]
+[template SgiOutputIterator[] [@http://www.sgi.com/tech/stl/OutputIterator.html OutputIterator]]
+[template SgiForwardIterator[] [@http://www.sgi.com/tech/stl/ForwardIterator.html ForwardIterator]]
+[template SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html BidirectionalIterator]]
+[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html RandomAccessIterator]]
+
+[template SgPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/theory.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/theory.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,252 @@
+[/
+ / Copyright (c) 2007 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 Review of Elementary Graph Theory]
+This chapter is meant as a refresher on elementary graph theory. If the reader has some previous
+acquaintance with graph algorithms, this chapter should be enough to get started. If the reader
+has no previous background in graph algorithms we suggest a more thorough introduction such as
+/Introduction to Algorithms/ by Cormen, Leiserson, and Rivest.
+
+[h2 The Graph Abstraction]
+A graph is a mathematical abstraction that is useful for solving many kinds of problems. Fundamentally,
+a graph consists of a set of vertices, and a set of edges, where an edge is something that connects two
+vertices in the graph. More precisely, a graph is a pair (V,E), where V is a finite set and E is a binary
+relation on V. V is called a vertex set whose elements are called vertices. E is a collection of edges,
+where an edge is a pair (u,v) with u,v in V. In a directed graph, edges are ordered pairs, connecting a
+source vertex to a target vertex. In an undirected graph edges are unordered pairs and connect the two
+vertices in both directions, hence in an undirected graph (u,v) and (v,u) are two ways of writing the same
+edge. 
+
+This definition of a graph is vague in certain respects; it does not say what a vertex or edge represents.
+They could be cities with connecting roads, or web-pages with hyperlinks. These details are left out of
+the definition of a graph for an important reason; they are not a necessary part of the graph abstraction.
+By leaving out the details we can construct a theory that is reusable, that can help us solve lots of
+different kinds of problems. 
+
+Back to the definition: a graph is a set of vertices and edges. For purposes of demonstration, let us
+consider a graph where we have labeled the vertices with letters, and we write an edge simply as a pair
+of letters. Now we can write down an example of a directed graph as follows: 
+
+ G = (V, E)
+ V = {v, b, x, z, a, y } 
+ E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) } 
+
+Figure 1 gives a pictorial view of this graph. The edge (x,x) is called a self-loop. Edges (b,y) and (b,y)
+are parallel edges, which are allowed in a multigraph (but are normally not allowed in a directed or
+undirected graph). 
+
+[$../images/review_figure_1.png]
+
+Next we have a similar graph, though this time it is undirected. Figure 2 gives the pictorial view.
+Self loops are not allowed in undirected graphs. This graph is the undirected version(b,y)), meaning it
+has the same vertices and the same edges with their directions removed. Also the self edge has been
+removed, and edges such as (a,z) and (z,a) are collapsed into one edge. One can go the other way,
+and make a directed version of an undirected graph be replacing each edge by two edges, one pointing
+in each direction.
+
+ G = (V, E)
+ V = {v, b, x, z, a, y }
+ E = { (b,y), (y,v), (z,a), (b,x), (x,v) }
+
+[$../images/review_figure_2.png]
+
+Now for some more graph terminology. If some edge (u,v) is in graph , then vertex v is adjacent to vertex u.
+In a directed graph, edge (u,v) is an out-edge of vertex u and an in-edge of vertex v. In an undirected graph
+edge (u,v) is incident on vertices u and v.
+
+In Figure 1, vertex y is adjacent to vertex b (but b is not adjacent to y). The edge (b,y) is an out-edge
+of b and an in-edge of y. In Figure 2, y is adjacent to b and vice-versa. The edge (y,b) is incident on
+vertices y and b. 
+
+In a directed graph, the number of out-edges of a vertex is its out-degree and the number of in-edges is
+its in-degree. For an undirected graph, the number of edges incident to a vertex is its degree. In Figure 1,
+vertex b has an out-degree of 3 and an in-degree of zero. In Figure 2, vertex b simply has a degree of 2.
+
+Now a path is a sequence of edges in a graph such that the target vertex of each edge is the source vertex
+of the next edge in the sequence. If there is a path starting at vertex u and ending at vertex v we say
+that v is reachable from u. A path is simple if none of the vertices in the sequence are repeated. The
+path <(b,x), (x,v)> is simple, while the path <(a,z), (z,a)> is not. Also, the path <(a,z), (z,a)> is called
+a cycle because the first and last vertex in the path are the same. A graph with no cycles is acyclic.
+
+A planar graph is a graph that can be drawn on a plane without any of the edges crossing over each other.
+Such a drawing is called a plane graph. A face of a plane graph is a connected region of the plane
+surrounded by edges. An important property of planar graphs is that the number of faces, edges, and
+vertices are related through Euler's formula: |F| - |E| + |V| = 2. This means that a simple planar graph
+has at most O(|V|) edges.
+
+[h2 Graph Data Structures]
+The primary property of a graph to consider when deciding which data structure to use is sparsity - the
+number of edges relative to the number of vertices in the graph. A graph where E is close to V2 is a
+/dense graph/, whereas a graph where E = alpha V and alpha is much smaller than V is a /sparse graph/. For
+dense graphs, the adjacency-matrix representation is usually the best choice, whereas for sparse graphs
+the adjacency-list representation is a better choice. Also the edge-list representation is a space efficient
+choice for sparse graphs that is appropriate in some situations.
+
+[h3 Adjacency Matrix Representation]
+An adjacency-matrix representation of a graph is a 2-dimensional V x V array. Each element in the array
+auv stores a Boolean value saying whether the edge (u,v) is in the graph. Figure 3 depicts an adjacency
+matrix for the graph in Figure 1 (minus the parallel edge (b,y)). The ammount of space required to store
+an adjacency-matrix is O(V2). Any edge can be accessed, added, or removed in O(1) time. To add or remove
+a vertex requires reallocating and copying the whole graph, an O(V2) operation. The `adjacency_matrix<>`
+class implements the Boost.Graph interface in terms of the adjacency-matrix data structure.
+
+[$../images/review_adjacency_matrix.gif]
+
+[h3 Adjacency List Representation]
+An adjacency-list representation of a graph stores an out-edge sequence for each vertex. For sparse
+graphs this saves space since only O(V + E) memory is required. In addition, the out-edges for each
+vertex can be accessed more efficiently. Edge insertion is O(1), though accessing any given edge is
+O(alpha), where alpha is the sparsity factor of the matrix (which is equal to the maximum number of
+out-edges for any vertex in the graph). Figure 4 depicts an adjacency-list representation of the
+graph in Figure 1. The adjacency_list class is an implementation of the adjacency-list representation.
+
+[$../images/review_adjacency_list.gif]
+
+[h3 Edge List Representation]
+An edge-list representation of a graph is simply a sequence of edges, where each edge is represented
+as a pair of vertex ID's. The memory required is only O(E). Edge insertion is typically O(1), though
+accessing a particular edge is O(E) (not efficient). Figure 5 shows an edge-list representation of the
+graph in Figure 1. The edge_list adaptor class can be used to create implementations of the edge-list
+representation.
+
+[$../images/review_edge_list.gif]
+
+[h3 Other Respresentations]
+Add something here to discuss optimized storage options for the graph. Specifically, we might
+mention the compressed-sparse-row graph representation and its possible uses.
+
+[h2 Graph Algorithms]
+Like all data structures, there are numerous algorithms that operate on them to solve various problems.
+In fact, there are often several different approaches to solving the same problem, each with different
+properties and complexities when running on graphs with different properties (e.g., directed vs. undirected
+or sparse vs. dense). The following sections briefly discuss a few such problems and algorithms.
+
+[h3 Graph Search Algorithms]
+Tree edges are edges in the search tree (or forest) constructed (implicitly or explicitly) by running a
+graph search algorithm over a graph. An edge (u,v) is a tree edge if v was first discovered while
+exploring (corresponding to the visitor explore() method) edge (u,v). Back edges connect vertices to
+their ancestors in a search tree. So for edge (u,v) the vertex v must be the ancestor of vertex u. Self
+loops are considered to be back edges. Forward edges are non-tree edges (u,v) that connect a vertex u
+to a descendant v in a search tree. Cross edges are edges that do not fall into the above three categories. 
+
+[h4 Breadth-First Search]
+Breadth-first search (BFS) is a traversal through a graph that touches all of the vertices reachable
+from a particular source vertex. In addition, the order of the traversal is such that the algorithm
+will explore all of the neighbors of a vertex before proceeding on to the neighbors of its neighbors.
+One way to think of breadth-first search is that it expands like a wave emanating from a stone dropped
+into a pool of water. Vertices in the same ``wave'' are the same distance from the source vertex. A
+vertex is discovered the first time it is encountered by the algorithm. A vertex is finished after
+all of its neighbors are explored. Here's an example to help make this clear. A graph is shown in
+Figure 6 and the BFS discovery and finish order for the vertices is shown below. 
+
+[$../images/review_bfs.gif]
+
+  order of discovery: s r w v t x u y 
+  order of finish: s r w v t x u y
+
+We start at vertex , and first visit r and w (the two neighbors of ). Once both neighbors of are visited,
+we visit the neighbor of r (vertex v), then the neighbors of w (the discovery order between r and w does
+not matter) which are t and x. Finally we visit the neighbors of t and x, which are u and y.
+
+For the algorithm to keep track of where it is in the graph, and which vertex to visit next, BFS needs
+to color the vertices (see the section on Property Maps for more details about attaching properties to
+graphs). The place to put the color can either be inside the graph, or it can be passed into the algorithm
+as an argument.
+
+[h4 Depth-First Search]
+A depth-first search (DFS) visits all the vertices in a graph. When choosing which edge to explore next,
+this algorithm always chooses to go ``deeper'' into the graph. That is, it will pick the next adjacent
+unvisited vertex until reaching a vertex that has no unvisited adjacent vertices. The algorithm will then
+backtrack to the previous vertex and continue along any as-yet unexplored edges from that vertex. After DFS
+has visited all the reachable vertices from a particular source vertex, it chooses one of the remaining
+undiscovered vertices and continues the search. This process creates a set of depth-first trees which together
+form the depth-first forest. A depth-first search categorizes the edges in the graph into three categories:
+tree-edges, back-edges, and forward or cross-edges (it does not specify which). There are typically many
+valid depth-first forests for a given graph, and therefore many different (and equally valid) ways to
+categorize the edges. 
+
+One interesting property of depth-first search is that the discover and finish times for each vertex form
+a parenthesis structure. If we use an open-parenthesis when a vertex is discovered, and a close-parenthesis
+when a vertex is finished, then the result is a properly nested set of parenthesis. Figure 7 shows DFS applied
+to an undirected graph, with the edges labeled in the order they were explored. Below we list the vertices of
+the graph ordered by discover and finish time, as well as show the parenthesis structure. DFS is used as the
+kernel for several other graph algorithms, including topological sort and two of the connected component
+algorithms. It can also be used to detect cycles (see the Cylic Dependencies  section of the File Dependency
+Example). 
+
+[$../images/review_dfs.gif]
+
+  order of discovery: a b e d c f g h i
+  order of finish: d f c e b a
+  parenthesis: (a (b (e (d d) (c (f f) c) e) b) a) (g (h (i i) h) g)
+
+[h4 Minimum Spanning Tree Problem]
+The minimum-spanning-tree (MST) problem is defined as follows: Given a graph /G=(V,E)/ find an acyclic
+subset /T/ of /E/ that connects all of the vertices in the graph and whose total weight is minimized, where
+the total weight is given by
+
+/w(T)/ = sum of /w(u,v)/ over all /(u,v)/ in T, where /w(u,v)/ is the weight on the edge /(u,v)/.
+
+/T/ is called the minimum spanning tree of /G/. It is important to note that a graph may have multiple MSTs.
+
+[h4 Shortest-Paths Algorithms]
+One of the classic problems in graph theory is to find the shortest path between two vertices in a graph.
+Formally, a path is a sequence of vertices <v0,v1,...,vk> in a graph G = (V, E) such that each vertex is
+connected to the next vertex in the sequence (the edges (vi,vi+1) for i=0,1,...,k-1 are in the edge set E).
+In the shortest-path problem, each edge is given a real-valued weight. We can therefore talk about the weight
+of a path
+ 
+/w(p)/ = sum from /i=1..k/ of /w(vi-1,vi)/
+
+The shortest path weight from vertex /u/ to /v/ is then 
+
+/delta(u,v)/ = min /{ w(p) : u --> v }/ if there is a path from u to v 
+/delta(u,v)/ = infinity otherwise. 
+
+A shortest path is any path who's path weight is equal to the shortest path weight. So there may be several
+shortest paths within the same graph.
+
+There are several variants of the shortest path problem. Above we defined the single-pair problem, but there
+is also the single-source problem (all shortest paths from one vertex to every other vertex in the graph),
+the equivalent single-destination problem, and the all-pairs problem. It turns out that there are no
+algorithms for solving the single-pair problem that are asymptotically faster than algorithms that solve
+the single-source problem. 
+
+A shortest-paths tree rooted at vertex in graph /G=(V,E)/ is a directed subgraph  where /V'/ is a subset of
+/V/ and /E'/ is a subset of /(E, V')/ is the set of vertices reachable from , /G'/ forms a rooted tree with
+root , and for all /v/ in /V'/ the unique simple path from to /v/ in /G'/ is a shortest path from to /v/ in
+/G/. The result of a single-source algorithm is a shortest-paths tree.
+
+[h4 Network Flow Algorithms]
+A flow network is a directed graph /G=(V,E)/ with a source vertex /s/ and a sink vertex /t/. Each edge has
+a positive real valued capacity function c and there is a flow function f defined over every vertex pair.
+The flow function must satisfy three contraints: 
+
+* /f(u,v) <= c(u,v)/ for all /(u,v)/ in /V/x /V/ (Capacity constraint) 
+* /f(u,v) = -f(v,u)/ for all /(u,v)/ in /V/ x /V/ (Skew symmetry)
+* sum /v/ in /V/ /f(u,v)/ = 0 for all /u/ in /V/ - /{s,t}/ (Flow conservation) 
+
+The flow of the network is the net flow entering the sink vertex t (which is equal to the net flow leaving
+the source vertex s).
+
+/|f|/ = sum /u/ in /V/ /f(u,t)/ = sum /v/ in /V/ /f(s,v)/
+
+The residual capacity of an edge is /r(u,v)/ = /c(u,v) - f(u,v)/. The edges with /r(u,v) > 0/ are residual
+edges /Ef/ which induce the residual graph /Gf = (V, Ef)/. An edge with /r(u,v) = 0/ is saturated. 
+
+The maximum flow problem is to determine the maximum possible value for |/f/| and the corresponding flow
+values for every vertex pair in the graph.  A flow network is shown in Figure 8. Vertex A is the source
+vertex and H is the target vertex. 
+
+[$../images/review_flow.gif]
+
+Edges are labeled with the flow and capacity values.  There is a long history of algorithms for solving the
+maximum flow problem, with the first algorithm due to Ford and Fulkerson. The best general purpose algorithm
+to date is the push-relabel algorithm of Goldberg which is based on the notion of a preflow introduced by
+Karzanov. 
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/tour.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/tour.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,508 @@
+[/
+ / Copyright (c) 2007 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 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
+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.
+
+[$../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.
+
+[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
+edges for this example.
+
+ #include <iostream>          // for std::cout
+ #include <utility>           // for std::pair
+ #include <algorithm>         // for std::for_each
+ #include <boost/graph/adjacency_list.hpp>
+
+ using namespace std;
+ using namespace boost;
+
+ int main(int, char*[])
+ {
+   // create a typedef for the Graph type
+   typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
+
+   // Make convenient labels for the vertices
+   enum { A, B, C, D, E, N };
+   const int num_vertices = N;
+   const char* name = "ABCDE";
+
+   // Create edges as pairs of of intengers
+   typedef pair<int, int> Edge;
+   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]);
+
+   // Declare a graph object with N vertices
+   Graph g(num_vertices);
+
+   // Add the edges to the graph
+   for (int i = 0; i < num_edges; ++i) {
+     add_edge(edge_array[i].first, edge_array[i].second, g);
+   }
+
+   // ... continue below
+   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.
+
+ 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.
+
+[h2 Accessing the Vertex Set]
+Now that we have created a graph, we can use the graph interface to access the graph data in
+different ways. First we can access all of the vertices in the graph using the `vertices()` function
+of the /VertexListGraph/ interface. This function returns a `std::pair<>` of vertex iterators (the first
+iterator points to the "beginning" of the vertices and the second iterator points "past the end").
+Dereferencing a vertex iterator gives a vertex object. The type of the vertex iterator is given by
+the graph_traits class. Note that different graph classes can have different associated vertex
+iterator types, which is why we need the `graph_traits<>` class. Given some graph type, the `graph_traits<>`
+class will provide access to the vertex_iterator type.
+
+The following example prints out the index for each of the vertices in the graph. All vertex and
+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. 
+
+
+ // ...
+ int main(int,char*[])
+ {
+   // ... continued from above
+
+   // Get the property map for vertex indices
+   typedef property_map<Graph, vertex_index_t>::type IndexMap;
+   IndexMap index = get(vertex_index, g);
+
+   cout << "vertices(g) = ";
+   typedef graph_traits<Graph>::vertex_iterator vertex_iter;
+   pair<vertex_iter, vertex_iter> vp;
+   for(vp = vertices(g); vp.first != vp.second; ++vp.first) {
+     cout << index[*vp.first] <<  " ";
+   }
+   cout << "\n";
+
+   // ...
+   return 0;
+ }
+
+The output is: 
+
+[pre
+ vertices(g) = 0 1 2 3 4
+]
+
+[h2 Accessing the Edge Set]
+The set of edges for a graph can be accessed with the edges() function of the /EdgeListGraph/ interface.
+Similar to the `vertices()` function, this returns a pair of iterators, but in this case the iterators
+are edge iterators. Dereferencing an edge iterator gives an edge object. The `source()` and `target()`
+functions return the two vertices that are connected by the edge. Instead of explicitly creating a
+`std::pair<>` for the iterators, this time we will use the `tie()` helper function. This handy function
+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*[])
+ {
+   // ... continued from above
+   cout << "edges(g) = ";
+   graph_traits<Graph>::edge_iterator ei, ei_end;
+   for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
+     cout << "(" << index[source(*ei, g)] << "," << index[target(*ei, g)] << ") ";
+   }
+   cout << "\n";
+
+   // ...
+   return 0;
+  }
+
+The output is:
+[pre
+ edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0) (3,1) (3,4) (4,0) (4,1)
+]
+
+[h2 The Adjacency Structure]
+In the next few examples we will explore the adjacency structure of the graph from the point of
+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. 
+  
+ //...
+ int main(int,char*[])
+ {
+   // ...
+   for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g));
+   return 0;
+ }
+
+We use a functor for exercise_vertex instead of just a function because the graph object will be
+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: 
+  
+ template <class Graph> struct exercise_vertex {
+   exercise_vertex(Graph& g_) : g(g_)
+   { }
+
+   // ...
+
+   Graph& g;
+ };
+
+[h3 Vertex Descriptors]
+The first thing we need to know in order to write the operator() method of the functor is the type
+for the vertex objects of the graph. The vertex type will be the parameter to the `operator()`
+method. To be precise, we do not deal with actual vertex objects, but rather with vertex descriptors.
+Many graph representations (such as adjacency lists) do not store actual vertex objects, while
+others do (e.g., pointer-linked graphs). This difference is hidden underneath the "black-box"
+of the vertex descriptor object. The vertex descriptor is something provided by each graph type
+that can be used to access information about the graph via the `out_edges()`, `in_edges()`,
+`adjacent_vertices()`, and property map functions that are described in the following sections. The
+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: 
+  
+ template <class Graph> struct exercise_vertex {
+   // ... continued from above
+
+   typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+   void operator()(const Vertex& v) const
+   {
+     // ... this is where we will "exercise" the vertex
+   }
+
+   // ...
+  };
+
+[h3 Out-Edges, In-Edges, and Edge Descriptors]
+The out-edges of a vertex are accessed with the `out_edges()` function of the /IncidenceGraph/
+interface. The out_edges() function takes two arguments: the first argument is the vertex and
+the second is the graph object. The function returns a pair of iterators which provide access
+to all of the out-edges of a vertex (similar to how the vertices() function returned a pair of
+iterators). The iterators are called out-edge iterators and dereferencing one of these iterators
+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 {
+   //... continued from above
+
+   void operator()(const Vertex& v) const
+   {
+     typedef graph_traits<Graph> GraphTraits;
+     typedef typename property_map<Graph, vertex_index_t>::type IndexMap;
+     IndexMap index = get(vertex_index, g);
+
+     cout << "out-edges: ";
+     typename GraphTraits::out_edge_iterator out_i, out_end;
+     typename GraphTraits::edge_descriptor e;
+     for(tie(out_i, out_end) = out_edges(v, g); out_i != out_end; ++out_i) {
+       e = *out_i;
+       Vertex src = source(e, g), tgt = target(e, g);
+       cout << "(" << index[src] << "," << index[targ] << ") ";
+     }
+     std::cout << "\n";
+
+     // ...
+   }
+
+   // ...
+ };
+
+For vertex 0 the output is: 
+[pre
+ out-edges: (0,1) (0,2) (0,3) (0,4)
+]
+
+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`. 
+  
+ template <class Graph> struct exercise_vertex {
+   // ... continued from above
+
+   void operator()(const Vertex& v) const
+   {
+     // ...
+     cout << "in-edges: ";
+     typedef typename graph_traits<Graph> GraphTraits;
+     typename GraphTraits::in_edge_iterator in_i, in_end;
+     for (tie(in_i, in_end) = in_edges(v,g); in_i != in_end; ++in_i) {
+       e = *in_i;
+       Vertex src = source(e, g), targ = target(e, g);
+       cout << "(" << index[src] << "," << index[targ] << ") ";
+     }
+     cout << "\n";
+     // ...
+   }
+
+   // ...
+ };
+
+For vertex 0 the output is: 
+[pr
+ in-edges: (2,0) (3,0) (4,0)
+]
+
+[h3 Adjacent Vertices]
+Given the out-edges of a vertex, the target vertices of these edges are adjacent to the source
+vertex. Sometimes an algorithm does not need to look at the edges of the graph and only cares
+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. 
+  
+ template <class Graph> struct exercise_vertex {
+   // ... continued from above
+
+   void operator()(Vertex v) const
+   {
+     //...
+     cout << "adjacent vertices: ";
+     typename graph_traits<Graph>::adjacency_iterator ai;
+     typename graph_traits<Graph>::adjacency_iterator ai_end;
+     for(tie(ai, ai_end) = adjacent_vertices(v, g); ai != ai_end; ++ai) {
+       std::cout << index[*ai] <<  " ";
+     }
+     std::cout << "\n";
+   }
+
+   //...
+ };
+
+For vertex 4 the output is: 
+[pre
+ adjacent vertices: 0 1
+]
+
+[Adding Some Color to your Graph]
+Boost.Graph attempts to be as flexible as possible in terms of accommodating how properties are
+attached to a graph. For instance, a property such as edge weight may need to be used throughout
+a graph object's lifespan and therefore it would be convenient to have the graph object also manage
+the property storage. On the other hand, a property like vertex color may only be needed for the
+duration of a single algorithm, and it would be better to have the property stored separately from
+the graph object. The first kind of property is called an internally stored property while the second
+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. 
+
+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
+Properties. Externally stored properties can be created in many different ways, although they are
+ultimately passed as separate arguments to the graph algorithms. One straightforward way to store
+properties is to create an array indexed by vertex or edge index. In the adjacency_list with `vecS`
+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. 
+
+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. 
+
+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
+for the distance. For the weight property we use the property class and specify int as the type used
+to represent weight values and edge_weight_t for the property tag (which is one of the Boost.Graph
+predefined property tags). The weight property is then used as a template argument for `adjacency_list<>`.
+The listS and vecS types are selectors that determine the data structure used inside the
+`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/). 
+
+ typedef adjacency_list<listS, vecS, directedS, 
+                        no_property,                 // no additional vertex properties
+                        property<edge_weight_t, int> // edges have integer edge weight
+                       > Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef std::pair<int,int> E;
+
+ const int num_nodes = 5;
+ E edges[] = { E(0,2), 
+               E(1,1), E(1,3), E(1,4),
+               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};
+
+ Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
+
+For the external distance property we will use a std::vector for storage. Boost.Graph algorithms treat
+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. 
+  
+ // vector for storing distance property
+ std::vector<int> d(num_vertices(G));
+
+ // get the first vertex
+ Vertex s = *(vertices(G).first);
+
+ // invoke variant 2 of Dijkstra's algorithm
+ dijkstra_shortest_paths(G, s, distance_map(&d[0]));
+
+ 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) << ") = " 
+             << d[*vi] << ;
+ std::cout << ;
+
+The output is: 
+[pre
+ distances from start vertex:
+ distance(0) = 0
+ distance(1) = 6
+ distance(2) = 1
+ distance(3) = 4
+ distance(4) = 5
+]
+
+[Extending Algorithms with Visitors]
+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. 
+
+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
+by functors, which are optional parameters to each algorithm. In Boost.Graph this role is
+fulfilled by visitors.
+
+A visitor is like a functor, but instead of having just one "apply" method, it has several.
+Each of these methods get invoked at certain well-defined points within the algorithm. The visitor
+methods are explained in detail in Section Visitor Concepts. Boost.Graph provides a number of visitors
+for some common tasks including a predecessor recording visitor. The user is encouraged to write
+his or her own visitors as a way of extending Boost.Graph. Here we will take a quick look at the
+implementation and use of the predecessor recorder. Since we will be using the
+`dijkstra_shortest_paths()` algorithm, the visitor we create must be a Dijkstra Visitor.
+
+The functionality of the record_predecessors visitor is separated into two parts. For the storage
+and access of the predecessor property, we will use a property map. The predecessor visitor will
+then only be responsible for what parent to record. To implement this, we create a
+`record_predecessors` class and template it on the predecessor property map `PredecessorMap`. Since
+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<>
+ {
+ public:
+   record_predecessors(PredecessorMap p)
+     : m_predecessor(p)
+   { }
+
+   template <class Edge, class Graph>
+   void edge_relaxed(Edge e, Graph& g) {
+     // set the parent of the target(e) to source(e)
+     put(m_predecessor, target(e, g), source(e, g));
+   }
+ protected:
+   PredecessorMap m_predecessor;
+ };
+
+The job of recording the predecessors is quite simple. When Dijkstra's algorithm relaxes an edge
+(potentially adding it to the shortest-paths tree) we record the source vertex as the predecessor
+of the target vertex. Later, if the edge is relaxed again the predecessor property will be
+overwritten by the new predecessor. Here we use the put() function associated with the
+property map to record the predecessor. The `edge_filter` of the visitor tells the algorithm when
+to invoke the `explore()` method. In this case we only want to be notified about edges in the
+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. 
+  
+ template <class PredecessorMap>
+ record_predecessors<PredecessorMap>
+ make_predecessor_recorder(PredecessorMap p) {
+   return record_predecessors<PredecessorMap>(p);
+ }
+
+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). 
+  
+ 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]). 
+                         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 << ") = " << p[*vi] << endl;
+ }
+
+The output is: 
+[pre
+ parents in the tree of shortest paths:
+ parent(0) = no parent
+ parent(1) = 4
+ parent(2) = 0
+ parent(3) = 2
+ parent(4) = 3
+]
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/tutorial.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/tutorial.qbk	2007-07-19 09:59:20 EDT (Thu, 19 Jul 2007)
@@ -0,0 +1,17 @@
+[/
+ / Copyright (c) 2007 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 Tutorial]
+
+This section contains a tutorial for the Boost.Graph library. It builds on the
+quick tour but discusses the concepts in much greater detail.
+
+[include tut_properties.qbk]
+
+[include tut_adjacency_list.qbk]
+
+[endsect]
\ No newline at end of file