[Boost-commit] svn:boost r7140

From: asutton_at_[hidden]
Date: 2007-06-25 13:32:43

Author: asutton
Date: 2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
New Revision: 7140
URL: http://svn.boost.org/trac/boost/changeset/7140

Log:
Moved some of the meta-documentation (users, pubs, etc). to the intro.
Wrote some pretty signficant chunks of the reference docs for undirected,
directed graphs.
Rewrote the undirected graph tutorial for new changes (still need to do
the directed tutorial).
Started adding the concept documentation back in.

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_visitors.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
Removed:
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/acknowledgements.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/publications.qbk
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/users.qbk
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2               |    82 ++++                                    
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk                |    51 +-                                      
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk                |    31 -                                       
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk |     2                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk       |     8                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk     |   237 ++++--------                            
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk         |    57 +++                                     
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk            |     8                                         
   sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk |   714 ++++++++++++++++++++++++++++++++++++++- 
   9 files changed, 935 insertions(+), 255 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/Jamfile.v2	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -1,13 +1,79 @@
 
-import quickbook ;
+# 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)
 
-xml graph
-	: graph.qbk
-	;
+using quickbook ;
+
+xml graph : graph.qbk ;
 
 boostbook standalone
-	: graph
-	;
+    :
+        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"
+    ;
+
+
+
+
+
+
+
+
+
+
 
-install html : ../../../../doc/html/boostbook.css ;
-install ../ : ../../../../boost.png ;

Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/acknowledgements.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/acknowledgements.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ -1,36 +0,0 @@
-[/
- / 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 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]

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_graphs.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -0,0 +1,35 @@
+[/
+ / 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 reusability of the algorithm.
+
+Figure 1: The graph concepts and refinement relationships.
+
+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.
+
+[h3 Undirected Graphs]
+
+Lots of stuff here on undirected graphs...
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_visitors.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/con_visitors.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -0,0 +1,26 @@
+[/
+ / 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]
+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:
+
+* BFS Visitor
+* DFS Visitor
+* Dijkstra Visitor
+* Bellman Ford Visitor
+* A* Visitor
+* Event Visitor
+
+[endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -0,0 +1,15 @@
+[/
+ / 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.
+
+[include con_graphs.qbk]
+[include con_visitors.qbk]
+
+[endsect]
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -1,4 +1,4 @@
- [/
+[/
  / Copyright (c) 2007 Andrew Sutton
  /
  / Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -6,45 +6,36 @@
  /]
 
 [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])
-	]
+    [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])
+    ]
 ]
 
-[/ Images ]
-[def __note__                [$images/note.png]]
-[def __alert__               [$images/caution.png]]
-[def __detail__              [$images/note.png]]
-[def __tip__                 [$images/tip.png]]
-
 [/ Contents ]
 
 [include introduction.qbk]
 
 [include history.qbk]
 
-[include users.qbk]
-
-[include publications.qbk]
-
-[include acknowledgements.qbk]
+[/ [include theory.qbk] /]
 
-[include theory.qbk]
-
-[include tour.qbk]
+[/ [include tour.qbk] /]
 
 [include guide.qbk]
 
-[include rationale.qbk]
+[include concepts.qbk]
+
+[include reference.qbk]
 
+[/ [include bibliography.qbk] /]

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -6,42 +6,11 @@
  /]
 
 [section User's Guide]
-In order to help ease your transition to working with Boost Graph, the library
-provides two general purpose graph classes: `undirected_graph` and `directed_graph`.
-These two classes are simply abstractions over the much more configurable, but
-somewhat obstruse `adjacency_list` class. It may be important to note that these
-classes are designed to be applicable to as many problems as possible, and may
-perform poorly in some circumstances. See the section
-[link boost_graph.user_s_guide.optimizing_for_performance Optimizing for Performance]
-for details on why you would want to and how to accomplish it.
-
-Note that these examples all use /bundled properties/ - a mechanism for defining
-properties for graphs, vertices, and edges. Unfortunately, these may not work
-correctly on compilers that do not support partial template specialization. If you
-are trying to build these examples see the section on /bundled properties/ for
-translating to old-style properties.
-
-The following sections provide users guides and details for working with both
-the `undirected_graph` and `directed_graph`, the much more general `adjacency_list`
-and `adjacency_matrix` classes, the truth about properties and property maps,
-tips and tricks for optimizing, and notes on implementing new Boost.Graph
-algorithms.
 
 [include guide_undirected.qbk]
 
 [include guide_directed.qbk]
 
-[include guide_details.qbk]
-
 [include guide_adjacency_list.qbk]
 
-[h2 Optimizing for Performance]
-One of the unfortunate problems of providing general purpose classes is that they often
-fail to scale up to larger problems. Consider the Six Degrees of Kevin Bacon game. What
-happens if you want to play on, say the entire contents of the
-[@http://www.imdb.com Internet Movie Database (IMDb)]?
-Will the `undirected_graph` class be capable of building the data structure and running
-the search algorithms in reasonable time? Probably not. This section is a guide on migrating
-from a "canned" graph to a customized solution.
-
 [endsect]
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_adjacency_list.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -5,7 +5,7 @@
  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  /]
 
-[section The `adjacency_list` Class]
+[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

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_directed.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -34,16 +34,16 @@
 implement the examples described in this user's guide. Their dependencies are
 shown in figure 1. Path names have been omitted for readability.
 
-[$../images/files.png]
+[$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
+* 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
+* 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.
 
@@ -196,7 +196,7 @@
 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/reverse.png]
+[$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

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/guide_undirected.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -6,10 +6,6 @@
  /]
 
 [section Undirected Graphs]
-This section could be called "Things to do with Undirected Graphs" since its goal
-is to provide a number of concrete examples of how undirected graphs can be used
-to solve problems - and more specifically how to implement them using Boost.Graph.
-
 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.
@@ -26,24 +22,23 @@
 and yes, Kevin Bacon is actually in /Animal House/ (he plays a snotty Omega pledge
 in his film debut).
 
-[$../images/movie.png]
+[$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?). What can we do
+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
+* 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
+* 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" and was actually discussed (on air) by its inventors on MTV's "The Jon
-Stewart Show" (go figure).
+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).
@@ -57,6 +52,10 @@
 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]
@@ -99,7 +98,6 @@
 
  struct Actor
  {
-   int index;
    int distance;
    std::string name;
  };
@@ -109,27 +107,24 @@
    std::string name;
  };
 
-In this example, we are "internalizing" a number of properties for each vertex.
-Here, `Actor::index` represents the index of the vertex within the graph. Unfortunately,
-the graph class is not smart enough to automatically assign and maintain these indices
-(for a number of reasons), so we're going to have to manage this later. Likewise, the
-`Actor::distance` property records the distance from each actor to Kevin Bacon. This is
-the value that we will be computing for every actor in the data set. The `Actor::name`
-and `Movie::name` properties should be fairly self-explanatory.
+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
+/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::type, int Actor::*>::type ActorIndexMap;
- typedef boost::property_map<Graph::type, int Actor::*>::type ActorDistanceMap;
+ typedef boost::property_map<Graph, int Actor::*>::type ActorDistanceMap;
 
-The first template argument `Graph::type` defines the type of the structure that
+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 member variables
-of type `int`.
+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
@@ -151,6 +146,7 @@
 
  #include <boost/tokenizer.hpp>
 
+ // the very important actor-to-vertex mapping
  typedef std::map<std::string, Vertex> ActorMap;
 
  using namespace std;
@@ -199,12 +195,12 @@
 
    if(inserted) {
      // if the vertex was inserted into the map, we need to
-     // create a new vertex in the graph
+     // 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].index = num_vertices(graph) - 1;
      g[v].name = name;
    }
    else {
@@ -241,15 +237,6 @@
 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.
 
-[warning
-Vertex indices (as used in this example) are entirely unstable if vertices are removed
-from the graph. Many graph algorithms require vertex index maps with values in the range
-\[0, `num_vertices(g)`)/. If we were to remove the first vertex in this example, the
-vertex indices would be incorrect and the program would potentially crash (accessing
-beyond `num_vertices(g)`). It is relatively trivial and inexpensive (O(`num_vertices(g)`)
-to renumber vertices just before running algorithms that require vertex index maps.
-]
-
 Our main program looks like this:
 
  int main()
@@ -264,90 +251,59 @@
 [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. To do this, we're going
-to need some help in the form of a BFS visitor.
-
- template <typename DistanceMap>
- struct ActorDistanceRecorder : public bfs_visitor<>
- {
-   ActorDistanceRecorder(DistanceMap d)
-     : distances(d)
-   {}
-
-   template <typename Edge, typename Graph>
-   void tree_edge(Edge e, const Graph& g) const
-   {
-     typedef typename Graph::vertex_descriptor Vertex;
-     Vertex
-       u = source(e, g),
-       v = target(e, g);
-     distances[v] = distances[u] + 1;
-   }
-
-   DistanceMap distances;
- };
-
-This visitor overloads the `tree_edge()` member function in order to compute the distance
-from a central vertex. In this example, the distance of a vertex from a starting vertex
-is one plus the depth of its parent in the spanning tree generated by a BFS.
-
-We're also going to provide a simple little helper function so we don't have to
-explicitly instantiate the visitor when we use it with the BFS algorithm.
-
- template <typename DistanceMap>
- ActorDistanceRecorder<DistanceMap> record_actor_distances(DistanceMap d)
- {
-   return ActorDistanceRecorder<DistanceMap>(d);
- }
-
-This leaves the question: what is a DistanceMap? To answer that, we have to complete the
-solution to the Kevin Bacon problem. Back to the `main()`...
+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()
  {
-   // ...continue from above...
-
-   ActorIndexMap indices = get(&Actor::index, graph);
-   ActorDistanceMap distances = get(&Actor::distance, graph);
+   // ...continued from above...
 
-   // find kevin (our starting point) and zero out his distance-to-self
+   // 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,
-     vertex_index_map(indices).
-     visitor(record_actor_distances(distances)));
+     visitor(
+        make_bfs_visitor(record_distances(distances, on_tree_edge()))
+        )
+   );
 
    // ...to be continued...
- }
 
-Finally, we're using the property maps that we defined so far above. The `get()` function
-essentially returns a map-like object that allows us to read and/or write the specified vertex
-or edge property. As mentioned earlier, these maps allow algorithms to reand and write both
-internal and external properties in a uniform method. Because graph algorithms cannot guess
-whether properties are internal or external, we have to pass these maps to just about every
-algorithm in this manner.
+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.
 
-We actually use the actors' distance map as it is in the distance recorder above (mostly as
-an example). We could just as easily have written the distance assignment as:
+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())))
+ );
 
-with the same effect.
-
-Finally, we can run our BFS and assign "Kevin Bacon numbers" to our actors. This is done
-by calling the `breadth_first_search()` function passing the graph, the starting vertex
-and some named parameters. The first named parameter is the vertex index map which provides
-read access to the `Actor::index` property assigned during graph construction. The second
-is an instance of our distance-recording visitor (as returned by our helper function).
-
-After finishing, each vertices distance property will be assigned. All there is left to do
+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";
@@ -401,39 +357,6 @@
  // ...
  typedef boost::property_map<Graph::type, &Vertex Actor::*>::type ActorParentMap;
 
-We are also going to change the BFS visitor that we used in the previous example.
-
- template <typename ParentMap>
- struct ActorParentRecorder : public bfs_visitor<>
- {
-   ActorParentRecorder(ParentMap d)
-    : parents(d)
-   {}
-
-   template <typename Edge, typename Graph>
-   void tree_edge(Edge e, const Graph& g) const
-   {
-     typedef typename Graph::vertex_descriptor Vertex;
-     Vertex
-       u = source(e, g),
-       v = target(e, g);
-     parents[v] = u;
-   }
-
-   ParentMap parents;
- };
-
- template <typename ParentMap>
- ActorParentRecorder<ParentMap> record_actor_parents(ParentMap d)
- {
-   return ActorParentRecorder<ParentMap>(d);
- }
-
-Despite the fact that this code is essentially cut, paste, and replace from the code
-above, there is one interesting change. Instead of assigning a distance to a vertex,
-we are setting the parent of the target to be the source. This one line allows us
-to walk the shortest paths from any actor to Kevin Bacon.
-
 The only other changes are going to be in the `main()` program.
 
  int main(int argc, char *argv[])
@@ -476,16 +399,19 @@
      return -1;
    }
 
-   ActorIndexMap = get(&Actor::index, graph);
-   ActorParentMap = get(&Actor::parent, graph);
+   // get the parents map for later use.
+   ActorParentMap parents = get(&Actor::parent, g);
 
-   breadth_first_search(graph, u,
-     vertex_index_map(indices).
-     visitor(record_actor_parents(parents)));
+   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:
+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)
  {
@@ -497,10 +423,13 @@
    return v;
  }
 
-Otherwise, the code is essentially the same as above. In this case, we're passing our
-modified parent-recording visitor to the `breadth_first_search()` function. The step
-in the solution is to backtrack from the target actor to the parent, printing the
-movies that form the chain of co-starring actors.
+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(...)
  {
@@ -510,28 +439,24 @@
      string from = g[v].name;
      string to = g[p].name;
 
+     // find the edge so we can print the movie
      Edge e;
-     Graph::out_edge_iterator i, j;
-     for(tie(i, j) = out_edges(v, g); i != j; ++i) {
-       if(target(*i, g) == p) {
-         e = *i;
-         break;
-       }
-     }
+     bool found;
+     tie(e, found) = edge(v, p, g);
 
      string movie = g[e].name;
      cout << from << " starred with " << to << " in '" << movie << "'\n";
 
      v = p;
    }
- }
 
-The only "complicated" part of the backtracking is finding the edge from
-the child to the parent. Because `undirected_graph` does is not a model of an
-`adjacency_matrix`, there is no simple method that returns edge data given
-two vertices.
+   return 0;
+ }
 
-[note This problem can be simplified using the `graph_as_matrix` adapter.]
+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
@@ -541,7 +466,7 @@
 Elisabeth Shue starred with Kevin Bacon in 'Hollow Man (2000)'
 ]
 
-You now have a completely unbeatable implementation of the "Six Degrees of Kevin
+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.
 

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/introduction.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -155,7 +155,60 @@
 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. 
+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

Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/publications.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/publications.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ -1,17 +0,0 @@
-[/
- / 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 Who's Writing about Me Now?]
-
-* 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
-
-[endsect]
\ No newline at end of file

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/rationale.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -1,4 +1,4 @@
- [/
+[/
  / Copyright (c) 2007 Andrew Sutton
  /
  / Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -108,4 +108,10 @@
 needs finer-grained control he or she can easily use the remove_edge(e, g) function
 where /e/ is an edge descriptor.
 
+[h3 Property-based Add Functions]
+The `\[un\]directed_graph` classes no longer provide `add` functionst that take
+a property as an argument. These tend not to work so well with bundled properties -
+especially when we're introducing a hidden property in the undirected_graph
+class. It makes type determination really difficult.
+
 [endsect]
\ No newline at end of file

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_adjacency_list.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -0,0 +1,400 @@
+[/
+ / 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 Reference]
+
+[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` && [br] Directed = `directedS`]
+        [OEL = `vecS`]
+    ]
+    [
+        [
+            `remove_edge()`[br]
+            `remove_edge_if()`[br]
+            `remove_out_edge_if()`[br]
+            `remove_in_edge_if()`[br]
+            `clear_vertex()`
+        ]
+        [Valid]
+        [Valid]
+        [Valid]
+        [OEL = `vecS` && [br] 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` [br]
+            `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

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk	(original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/ref_undirected_graph.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
@@ -1,4 +1,4 @@
- [/
+[/
  / Copyright (c) 2007 Andrew Sutton
  /
  / Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -6,42 +6,712 @@
  /]
 
 [section Undirected Graph Reference]
+This section provides detailed information about the `undirected_graph` class,
+its associated types, member functions and non-member interface.
 
-*TODO*: I should probably document somewhere that out_edges() and in_edges()
-are equivalent for this function. Is it important? I don't know, maybe.
+[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 Duplicitous Operations]
+Many of the original operations in the Boost Graph library are named in accordance
+with the terminology for 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.
 
-[h3 Members]
-The following tables define and describe the members of the `undirected_graph`
-class.
+There are three sets of operations that have multiple names and duplicate behavior:
+`*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.
+
+[h4 Vertex and Edge Storage]
+The `undirected` graph class has three distinct storage compontents: one for each
+of vertices, edges, and incident-edges per vertex. Each of these storage components
+uses a `std::list`. This is important to remember when considering the performance
+of oeprations on these graphs.
+
+Note that mutating (modifying) edge operations on a graph must operate on both
+the edge list and incident edge lists. For example, adding an edge to the graph
+will insert the edge or descriptors into both the edge list and the incidence
+edge list of the edge's source and target.
+
+It is important to note that the use of the term /incident edges/ in this context
+generally refers to the /out/-edges of a vertex. Because the graph is undirected,
+every in-edge is also an out-edge, and so we use the term /incident/ to capture
+these semantics. As a result, the `out_edges(g)`, `in_edges(g)` and `incident_edges(g)`
+functions all return identical iterator ranges.
+
+[h4 Descriptor and Iterator Stability]
+With the `undirected_graph` class, descriptors and iterators remain stable after
+most operations. This is to say that removing a vertex or edge will not invalidate
+descriptors and iterators to other vertices or edges.
+
+[h4 Vertex Indexing and Stability]
+The `undirected_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 `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()` function.
+
+[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`]
+    ]
+]
+
+[h5 Model Of]
+VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
+
+[h5 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
-    [[Member] [Where Defined] [Description]]
+    [[Type] [Description]]
     [
-        [`vertex_descriptor`]
-        [Graph]
-        [An opaque type whose values are used to access vertices and their properties.]
+        [`graph_traits<undirected_graph>::vertex_descriptor`]
+        [
+            The type for the vertex descriptors associated with the graph.
+        ]
     ]
     [
-        [`edge_descriptor`]
-        [Graph]
-        [An opaque type whose values are used to access edges and their properties.]
+        [`graph_traits<undirected_graph>::edge_descriptor`]
+        [
+            The type for the edge descriptors associated with the graph.
+        ]
+    ]
+]
+
+[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 `BidirectionalIterator` concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::edge_iterator`]
+        [
+            The type for iterators returned by `edges()`. Edge iterators are
+            models of the `BidirectionalIterator` concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::out_edge_iterator`]
+        [
+            The type for iterators returned by `out_edges()`. Out-edge iterators
+            are models of the `BidirectionalIterator` concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::in_edge_iterator`]
+        [
+            The type for iterators returned by `in_edges()`. In-edge iterators
+            are models of the `BidirectionalIterator` concept.
+        ]
+    ]
+    [
+        [`graph_traits<undirected_graph>::adjacency_iterator`]
+        [
+            The type for iterators returned by `adjacent_vertices`. Adjacency
+            iterators are models of the `BidirectionalIterator` 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.
+        ]
     ]
     [
-        [`directed_category`]
-        [Graph]
-        [Indicates the graph has undirected edges. It's type is `undirected_tag`.]
+        [
+``
+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`.
+        ]
     ]
     [
-        [`edge_parallel_category`]
-        [Graph]
-        [...]
+        [
+``
+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 different 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.
+        ]
     ]
     [
-        [`traversal_category`]
-        [Graph]
-        [...]
+        [
+``
+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.
+        ]
     ]
 ]
 

Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 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 Reference Guide]
+
+[include ref_undirected_graph.qbk]
+[include ref_directed_graph.qbk]
+[include ref_adjacency_list.qbk]
+
+[endsect]
\ No newline at end of file

Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/users.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/users.qbk	2007-06-25 13:32:41 EDT (Mon, 25 Jun 2007)
+++ (empty file)
@@ -1,27 +0,0 @@
-[/
- / 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 Who's Using Me Now?]
-
-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]
-
-[endsect]
\ No newline at end of file