[Boost-commit] svn:boost r49001 - in sandbox/SOC/2008/graphs/trunk/libs/graphs/doc: . adj_list html

Subject: [Boost-commit] svn:boost r49001 - in sandbox/SOC/2008/graphs/trunk/libs/graphs/doc: . adj_list html
From: asutton_at_[hidden]
Date: 2008-09-29 10:44:47

Author: asutton
Date: 2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
New Revision: 49001
URL: http://svn.boost.org/trac/boost/changeset/49001

Log:
More work on documentation
Added:
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/concepts.qbk   (contents, props changed)
Text files modified: 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/Jamfile                 |     2                                         
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list.qbk            |   207 +++++++++++++++++                       
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list/undirected.qbk |   468 +++++++++++++++++---------------------- 
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk              |    71 +++++                                   
   sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/html/boostbook.css      |    18 +                                       
   5 files changed, 497 insertions(+), 269 deletions(-)

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/Jamfile	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/Jamfile	2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
@@ -43,7 +43,7 @@
         <xsl:param>chunk.section.depth=10
         <xsl:param>chunk.first.sections=1
         <xsl:param>toc.section.depth=10
-        <xsl:param>toc.max.depth=4
+        <xsl:param>toc.max.depth=2
         <xsl:param>generate.section.toc.level=10
 
 #         <xsl:param>boost.libraries=$(boost-root)/libs/libraries.htm

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list.qbk
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list.qbk	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list.qbk	2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
@@ -1,4 +1,9 @@
 
+[def __VertexStoreSelector__ [^VertexStoreSelector]]
+[def __EdgeStoreSelector__ [^EdgeStoreSelector]]
+[def __HasAdd__ [^HasAdd]]
+[def __HasRemove__ [^HasRemove]]
+
 [section Adjacency List]
 An adjacency list is a family of data structures that can is used to implement
 undirected, unidirectional, and bidirectional graphs. In general, an adjacency list
@@ -35,4 +40,206 @@
 [include adj_list/undirected.qbk]
 [include adj_list/directed.qbk]
 
+[section Storage Selectors]
+The vertex storage selector is responsible for determining the type of the vertex
+descriptor, a vertex key (if used), and the the vertex store itself.
+
+[*TODO] Write more about storage selectors here.
+
+[section Vertex Store Selectors]
+The selection of a vertex store determines the implementation of the vertex set
+within an adjacencly lists and how vertices are added and removed from that set
+at runtime.
+
+Vertex store selectors are almost always templates that allow parameterization over
+allocation, comparison function, or hash function. The parameters for each vertex
+store selector are specific to that implementation.
+
+[note *Implementation* Note that many of these storage selectors reference standard
+containers. However, the actual types that implement these stores are wrappers around
+those containers that expose a shared interface.]
+
+[heading Vertex Vector]
+
+ template <template <typename> class Alloc >
+ struct vertex_vector;
+
+Vertices is implemented using a `std::vector`. Vertex vectors allow vertices to be added
+in constant time but do not allow removal. If a VertexLabel is given, vertices can
+be searched in linear time. The `vertex_vector` selector has the following parameters.
+
+[table
+ [[Parameter] [Description]]
+ [[[^Alloc]]
+  [The name of an __Allocator__ template used to allocate vertices in the vertex
+   store. /Default/: `std::allocator`.]]
+]
+
+Selecting an adjacency list with `vertex_vector` will cause
+the following concept maps to be defined for the instantiated graph type.
+
+ concept_map __ConstructibleGraph__<G> { };
+
+Graphs using vertex storage are runtime-constructilbe using either __HasAddUnlabeledVertex__
+or __HasAddLabeledVertex__, depending on the choice of `VertexLabel`. Adding vertices
+to the graph is always a /O(1)/ and always add new vertices. Vertex removal is not
+supported due to the invalidation semantics of `std::vector`.
+
+[heading Vertex List]
+
+[heading Vertex Set]
+
+[heading Vertex Map]
+
+[heading Vertex Hash Set]
+Not implemented.
+
+[heading Vertex Hash Map]
+Not implemented.
+
+[heading Compressed Vertex Set]
+Not implemented.
+
+[heading Details]
+A vertex store selector is described (roughly) by the following concept. Here, the
+`VertexStoreSelector` requires the definition of associated types for a `vertex_descriptor`,
+a `vertex_key` and a metafunction that resolves the the underlying type of vertex store,
+given a vertex type.
+
+ concept VertexStoreSelector<typename Selector>
+ {
+     typename vertex_descriptor;
+     typename vertex_key = unused;
+
+     template <typename Vertex>
+     struct vertex_store { typedef ``['unspecified]`` type; };
+ };
+
+The `vertex_desciptor`...
+
+The `vertex_key` is `ununsed` (a simple empty type like `none`) unless `vertex_store<V>::type`
+models __PairAssociativeContainer__.
+
 [endsect]
+
+[section Edge Store Selectors]
+The edge selector determines the type of property and incidence store for the
+undirected_graph class. The type of container implementing the property store
+depends on the type of incident edge store.
+
+ template <...>
+ struct undirected_edge_store_selector
+ {
+     typedef ... property_descriptor;
+     typedef ... incidence_descriptor;
+
+     template <typename VertexDesc, EdgeLabel>
+     struct property_store { typedef ... type; }
+
+     template <typename VertexDesc>
+     struct incidence_store { typedef ... type; }
+ };
+
+As with the vertex storage selector, the template parameters to the edge storage
+selector are determined by the types of container being constructed. This library
+currently provides the following types of edge storage selectors:
+
+For directed graphs, we have:
+
+ template <...>
+ struct directed_edge_store_selector
+ {
+     typedef ... out_edge_descriptor;
+     typedef ... in_edge_descriptor;
+
+     template <typename VertexDesc, EdgeLabel>
+     struct out_edge_store { typedef ... type; }
+
+     template <typename VertexDesc>
+     struct in_edge_store { typedef ... type; }
+ };
+
+Or something like that... It's subject to change.
+
+[table Edge Storage Selectors
+[[Selector] [Description]]
+    [
+        [`edge_vector<PropAlloc,IncAlloc>`]
+        [The property and incident edge store are both implemented using `std::vector`s.
+         Edges can be added to the graph in constant time, but not removed.
+
+         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
+         /Default/: `std::allocator`.
+
+         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
+         /Default/: `std::allocator`.
+        ]
+    ]
+    [
+        [`edge_list<PropAlloc,IncAlloc>`]
+        [
+         The property and incident edge store are `std::list`s. Edges can be added
+         and removed in constant time.
+
+         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
+         /Default/: `std::allocator`.
+
+         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
+         /Default/: `std::allocator`.
+        ]
+    ]
+    [
+        [`edge_set<Comp,PropAlloc,IncAlloc>`]
+        [
+         The property store is implemented as a `std::list`, and the incident edge
+         store is implemented as a `std::map`, mapping the endpoint vertex descriptor
+         to the edge's property descriptor (effectively a set of edges). Edges can
+         be added and removed in time logarithmic to the degree of the endpoints.
+
+         [*[^Comp]] - The name of a __StrictWeakOrder__ used to compare the endpoints of
+         edges. /Default/: `std::less`.
+
+         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
+         /Default/: `std::allocator`.
+
+         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
+         /Default/: `std::allocator`.
+        ]
+    ]
+    [
+        [`edge_multiset<Comp,PropAlloc,IncAlloc>`]
+        [
+         The property store is implemented as a `std::list`, and the incident edge
+         store is implemented as a `std::multimap`, multimapping the endpoint vertex
+         descriptor to the edge's property descriptor (effectively a multiset of edges).
+
+        [*[^Comp]] - The name of a __StrictWeakOrder__ used to compare the endpoints of
+         edges. /Default/: `std::less`.
+
+         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
+         /Default/: `std::allocator`.
+
+         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
+         /Default/: `std::allocator`.
+        ]
+    ]
+    [[`edge_unordered_set<>`] [Not implemented.]]
+    [[`edge_unordered_multiset<>`] [Not implemented.]]
+]
+The choice of edge set essentially determines whether the graph will be a __SimpleGraph__
+or __Multigraph__. If the selector chooses a __Sequence__ or __MultipleAssociativeContainer__,
+then the graph is a __Multigraph__, meaning that it can contain multiple edges connecting
+two vertices (i.e., having the same endpoints). If the selector chooses a
+__UniqueAssociativeContainer__ then the graph will be a __SimpleGraph__, having unique
+vertices identified by a particular label.
+[endsect] [/ Edge Store Selectors /]
+
+[heading Concepts]
+
+There are a couple of concepts associated with the storage compents of :
+
+ concept __HasAdd__<
+
+
+[endsect] [/ Storage Selectors /]
+[endsect] [/ Adjacency Lists /]

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list/undirected.qbk
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list/undirected.qbk	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/adj_list/undirected.qbk	2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
@@ -1,9 +1,9 @@
 
-[def undirected_graph [^undirected_graph]]
-[def VertexLabel [^VertexLabel]]
-[def EdgeLabel [^EdgeLabel]]
-[def VertexStore [^VertexStore]]
-[def EdgeStore [^EdgeStore]]
+[def __undirected_graph__ [^undirected_graph]]
+[def __VertexLabel__ [^VertexLabel]]
+[def __EdgeLabel__ [^EdgeLabel]]
+[def __VertexStore__ [^VertexStore]]
+[def __EdgeStore__ [^EdgeStore]]
 
 [section `undirected_graph`]
 
@@ -14,250 +14,80 @@
  namespace adjacency_list {
 
      template <
-        typename VertexLabel = none,
-        typename EdgeLabel = none,
-        typename VertexStore = vertex_list<>,
-        typename EdgeStore = edge_list<>>
+        __ObjectType__ __VertexLabel__ = none,
+        __ObjectType__ __EdgeLabel__ = none,
+        __VertexStoreSelector__ __VertexStore__ = vertex_list<>,
+        __EdgeStoreSelector__ __EdgeStore__ = edge_list<>>
+    requires __MoveConstructible__<__VertexLabel__>
+          && __MoveConstructible__<__EdgeLabel__>
     undirected_graph;
 
  } } }
 
-The undirected_graph data structure is an adjacency list that implements undirected
-graph and is comprised of a number of types of objects. Its basic structure is
-shown in [link fig_1 Figure 1].
+The __undirected_graph__ data structure is an adjacency list implementation of undirected
+graphs. Its basic structure is shown in [link fig_1 Figure 1].
 
 [figure fig_1 images/graph/undirected.png
     [*Figure 1. Components of an undirected graph]
 ]
 
-* The VertexStore is a container that stores vertices (VertexLabel and incident edges)
-of the graph.
-* The `PropertyStore` is a container that stores the `EdgeLabel`s of edges in graph
-and descriptors to the endpoint vertices of the edge corresponding to the property.
-The type of the `PropertyStore` is determined by the type of the VertexStore.
-* The EdgeStore is a container associated with each vertex that stores descriptors
-to the corresponding endpoint and the property associated with the edge. The EdgeStore
-is referred to the `IncidenceStore` within the graph.
-
-[note *Impementation* The reason that the `PropertyStore` references the endpoints is to provide
-constant-time access to the endpoints of an edge during edge iteration. It is
-possible to create a simpler version of the undirected_graph who's property store
-does not contain back references, but neither would it provide edge iteration.]
-
-[note *Implementation* When the edge property is none, the property store should be compressed,
-eliminating the required storage space. Property descriptors can be transacted as
-integer values (or GUID's if the graph is expected to exceed 2^32 edges. This has
-specialization has not been implemented.]
+* The /vertex store/ is a container that stores vertices (vertex labels and incident
+edges) of the graph.
+* The /property store/ is a container that stores edge labels and the edges endpoints.
+The type of the property store's implementation is determined entirely by the type of
+the vertex store.
+* The /incidence store/ is a per-vertex container that stores "edge pairs" a descriptor
+to the opposite endpoint and the edge label.
+
+[note *Impementation* The reason that the `PropertyStore` references the endpoints is
+to provide constant-time access to the endpoints of an edge during edge iteration. It
+is possible (and feasible) to create a simpler version of the __undirected_graph__ who's
+property store does not contain back references, but neither would it provide edge
+iteration.]
+
+[note *Implementation* When the edge property is none, the property store should be
+compressed, eliminating the required storage space. Property descriptors could probably
+be `typedef`'d as integer values (or GUID's if the graph is expected to exceed 2^32
+edges. This has specialization has not been implemented.]
 
-[heading Template Parameters]
-The following base requirements apply to the template parameters of the undirected_graph.
+[heading Template Parameters and Requirements]
+The following base requirements apply to the template parameters of the __undirected_graph__.
 
-[table Template Parameters
+[table
 [[Parameter] [Description]]
-[[VertexLabel] [Data associated with each vertex. This defaults to `none`. This must be Semiregular.]]
-[[EdgeLabel] [Data associated with each edge. This defaults to `none`. This must be Semiregular]]
-[[VertexStore] [The vertex store selector. This defaults to `vertex_list<>`.]]
-[[EdgeStore] [The edge store selector. This defaults to `edge_list<>`.]]
-]
-[heading Storage Selectors]
-The vertex storage selector is responsible for determining the type of the vertex
-descriptor, a vertex key (if used), and the the vertex store itself.
-
- template <...>
- struct vertex_store_selector
- {
-     typedef ... vertex_descriptor;
-     typedef ... vertex_key;
-
-     template <typename Vertex>
-     struct vertex_store { typedef ... type; };
- };
-
-The template parameters to a vertex store selector can be nearly anything. For example,
-in the default selectors, they are used to pass `allocator` types, and comparision
-or hash fucntions to the vertex store.
-
-[note Unless the `vertex_store<...>::type` results in a PairAssociativeContainer, the
-vertex_key is typically defined as `unused`.]
-
-The library currently defines the  following vertex storage selectors for undirected
-graphs:
-
-[table Vertex Storage Selectors
-[[Selector] [Description]]
-    [
-        [`vertex_vector<Alloc>`]
-        [Vertices are stored in a `std::vector`. Vertex vectors allow vertices to
-         be added in constant time but do not allow removal. If a VertexLabel is
-         given, vertices can be searched in linear time.
-
-         [*[^Alloc]] - The name of an __Allocator__ template used to allocate vertices
-         in the vertex store. /Default/: `std::allocator`.
-        ]
-    ]
-    [
-        [`vertex_list<Alloc>`]
-        [Vertices are stored in a `std::list`. Vertex lists allow vertices to be
-         added and removed in constant time, and if a VertexLable is given, searched
-         in linear time.
-
-         [*[^Alloc]] - The name of an __Allocator__ used to allocate vertex objects.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [
-        [`vertex_set<Comp,Alloc>`]
-        [Vertices are stored in a `std::set`. Vertex sets allow vertices to be added,
-         removed and found (by their VertexLabel) in logarithmic time.
-
-         [*[^Comp]] - The name of a __StrictWeakOrder__ template used to compare the labels
-         of vertices in the vertex store. /Default/: `std::less`.
-
-         [*[^Alloc]] - The name of an __Allocator__ used to allocate vertex objects.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [
-        [`vertex_map<Key,Comp,Alloc>`]
-        [Vertices are stored in a `std::map` and mapped to a key of type `Key`. Vertex
-         maps allow vertices to be added, removed and found (by their VertexLabel)
-         in logarithmic time.
-
-         [*[^Key]] - The type of key objects that are uniquely mapped to each vertex.
-         There is not default key type, it must be provided when the graph type is defined.
-
-         [*[^Comp]] - The name of a __StrictWeakOrder__ template used to compare the keys
-         of vertices in the vertex store. /Default/: `std::less`.
-
-         [*[^Alloc]] - The name of an __Allocator__ used to allocate vertex objects.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [[`vertex_multiset<>`] [Not implemented.]]
-    [[`vertex_multimap<>`] [Not implemented.]]
-    [[`vertex_unordered_set<>`] [ Not implememnted]]
-    [[`vertex_unordered_map<>`] [ Not implememnted]]
-    [[`vertex_unordered_multiset<>`] [ Not implememnted]]
-    [[`vertex_unordered_multimap<>`] [ Not implememnted]]
-]
-The choice of vertex storage selector determines the how your program can add and\/or
-remove vertices from the graph. A selector that chooses a __Sequence__ container can be
-used to implement graphs whose VertexLabel does not (necessarily) uniquely identify
-the vertex. Selectors that choose __UniqueAssociativeContainer__ containers can be used to
-associate unique labels with each vertex. In the case of __PairAssociativeContainer__
-containers, a key is mapped to each vertex in the graph. In this case, the `Key`
-parameter of the storage selector /must not be the same type/ as the VertexLabel.
-
-[note Selectors that choose __MultipleAssociativeContainer__ containers describe an
-interesting class of graphs with sets of "equivalent" vertices. I don't know of any
-obvious applications of this kind of graph, but they may be out there.]
-
-[important If the VertexStore selects an __AssociativeContainer__ then the VertexLabel
-must not be `none`.]
-
-The edge selector determines the type of property and incidence store for the
-undirected_graph class. The type of container implementing the property store
-depends on the type of incident edge store.
-
- template <...>
- struct undirected_edge_store_selector
- {
-     typedef ... property_descriptor;
-     typedef ... incidence_descriptor;
-
-     template <typename VertexDesc, EdgeLabel>
-     struct property_store { typedef ... type; }
-
-     template <typename VertexDesc>
-     struct incidence_store { typedef ... type; }
- };
-
-As with the vertex storage selector, the template parameters to the edge storage
-selector are determined by the types of container being constructed. This library
-currently provides the following types of edge storage selectors:
-
-[table Edge Storage Selectors
-[[Selector] [Description]]
-    [
-        [`edge_vector<PropAlloc,IncAlloc>`]
-        [The property and incident edge store are both implemented using `std::vector`s.
-         Edges can be added to the graph in constant time, but not removed.
-
-         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
-         /Default/: `std::allocator`.
-
-         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [
-        [`edge_list<PropAlloc,IncAlloc>`]
-        [
-         The property and incident edge store are `std::list`s. Edges can be added
-         and removed in constant time.
-
-         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
-         /Default/: `std::allocator`.
-
-         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [
-        [`edge_set<Comp,PropAlloc,IncAlloc>`]
-        [
-         The property store is implemented as a `std::list`, and the incident edge
-         store is implemented as a `std::map`, mapping the endpoint vertex descriptor
-         to the edge's property descriptor (effectively a set of edges). Edges can
-         be added and removed in time logarithmic to the degree of the endpoints.
-
-         [*[^Comp]] - The name of a __StrictWeakOrder__ used to compare the endpoints of
-         edges. /Default/: `std::less`.
-
-         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
-         /Default/: `std::allocator`.
-
-         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [
-        [`edge_multiset<Comp,PropAlloc,IncAlloc>`]
-        [
-         The property store is implemented as a `std::list`, and the incident edge
-         store is implemented as a `std::multimap`, multimapping the endpoint vertex
-         descriptor to the edge's property descriptor (effectively a multiset of edges).
-
-        [*[^Comp]] - The name of a __StrictWeakOrder__ used to compare the endpoints of
-         edges. /Default/: `std::less`.
-
-         [*[^PropAlloc]] - The name of an __Allocator__ used to allocate edge labels.
-         /Default/: `std::allocator`.
-
-         [*[^IncAlloc]] - The name of an __Allocator__ used to allocate incident edges.
-         /Default/: `std::allocator`.
-        ]
-    ]
-    [[`edge_unordered_set<>`] [Not implemented.]]
-    [[`edge_unordered_multiset<>`] [Not implemented.]]
-]
-The choice of edge set essentially determines whether the graph will be a __SimpleGraph__
-or __Multigraph__. If the selector chooses a __Sequence__ or __MultipleAssociativeContainer__,
-then the graph is a __Multigraph__, meaning that it can contain multiple edges connecting
-two vertices (i.e., having the same endpoints). If the selector chooses a
-__UniqueAssociativeContainer__ then the graph will be a __SimpleGraph__, having unique
-vertices identified by a particular label.
+[[__ObjectType__ __VertexLabel__]
+ [Data associated with each vertex. This defaults to `none`.]]
+[[__ObjectType__ __EdgeLabel__]
+ [Data associated with each edge. This defaults to `none`.]]
+[[__VertexStoreSelector__ __VertexStore__]
+ [The vertex store selector. This defaults to `vertex_list<>`.]]
+[[__EdgeStoreSelector__ __EdgeStore__]
+ [The edge store selector. This defaults to `edge_list<>`.]]
+]
+
+The default __undirected_graph__ type defines a very basic graph with unlabeled
+vertices and edges that supports efficient, runtime setup and teardown - the
+addition and removal of vertices after construction.
+
+The __VertexLabel__ and __EdgeLabel__ are required to be __MoveConstructible__,
+which is a common requirement for the types contained by standard containers.
+
+[note *Design* Are these not also required to be __DefaultConstructible__?]
 
 [heading Associated Types]
-[table Associated Types
-[[Typename] [Description]]
-[[`G::vertex_label`] [The same as VertexLabel.]]
-[[`G::edge_label`] [The same as EdgeLabel.]]
+The __undirected_graph__ defines the following associated types as part of its
+public interface.
+
+[table
+[[Type name] [Description]]
+[[`G::vertex_label`] [The same as `VertexLabel`.]]
+[[`G::edge_label`] [The same as `EdgeLabel`.]]
 [[`G::vertex_descriptor`] [The representative type of vertices.]]
 [[`G::edge_descriptor`] [The representative type of edges.]]
 [[`G::vertices_size_type`] [The unsigned integral type of the number of vertices.]]
 [[`G::edges_size_type`] [The unsigned integral type of the total number of edges.]]
-[[`G::incident_edges_size_type`] [The unsigned integral type of the number of edges incident to a vertex.]]
+[[`G::incident_edges_size_type`]
+ [The unsigned integral type of the number of edges incident to a vertex.]]
 
 [[`G::vertex_iterator`] [An iterator type for the vertices in the graph.]]
 [[`G::vertex_range`] [A range of vertex iterators.]]
@@ -268,71 +98,173 @@
 [[`G::adjacent_vertex_iterator`] [An iterator type for the vertices adjacent to a given vertex.]]
 [[`G::adjacent_vertex_range`] [A range of adjacent vertex iterators.]]
 ]
-The following section is a list of member functions of the graph.
+
+The following associated types define the types of the components selected by
+the __VertexStore__ and __EdgeStore__ template parameters. These types are provided
+only for documentary purposes. They are not (currently) part of the public interface
+of the __undirected_graph__ class.
+
+[table
+[[Type name] [Description]]
+[[`G::vertex_store`] [The type of the vertex container.]]
+[[`G::proeprty_store`] [The type of the property container.]]
+[[`G::incidence_store`] [The type of the incident edge container for each vertex.]]
+]
 
 [heading Constructors and Destructor]
 
- undirected_graph()
- undirected_graph(undirected_graph const& g)
- undirected_graph(undirected_graph&& g)
- ~undirected_graph()
+ undirected_graph::undirected_graph()
+ undirected_graph::undirected_graph(undirected_graph const& g)
+ undirected_graph::undirected_graph(undirected_graph&& g)
+ ~undirected_graph::undirected_graph()
 
 The usual cadre of constructors and descructors that make graphs __Regular__. The
 undirected graph class supports default, copy, and move construction.
 
+[table
+[[Parameters] [Description]]
+[[`undirected_graph const& g`] [The graph being copied.]]
+[[`undirected_graph&& g`] [The graph being moved.]]
+]
+
+[variablelist
+[[Complexity]
+ [Default and move construction is O(1). Copy assignment is O(V + E) for all
+  kinds of graphs.]]
+ [[Notes]
+  [After moving, the graph `g` will be empty, having been cleared during the
+   `move` operation.]]
+]
+
 [heading Operators]
 
- undirected_graph& operator=(undirected_graph const& g)
- undirected_graph& operator=(undirected_graph&& g)
+ undirected_graph& undirected_graph::operator=(undirected_graph const& g)
+ undirected_graph& undirected_graph::operator=(undirected_graph&& g)
 
 Copy or move assign the vertices and edges of the graph `g` to this graph.
 
- vertex_label& operator[](vertex_descriptor v)
- vertex_label const& operator(vertex_descriptor v) const
+[table
+[[Parameters] [Description]]
+[[`undirected_graph const& g`] [The graph being copied.]]
+[[`undirected_graph&& g`] [The graph being moved.]]
+[[`return`] [The object being assigned (i.e., `*this`).]]
+]
+
+[variablelist
+[[Complexity]
+ [Move assignment is O(1). Copy assignment is O(V + E) for all kinds of graphs.]]
+]
+
+ vertex_label&          undirected_graph::operator[](vertex_descriptor v)
+ vertex_label const&    undirected_graph::operator[](vertex_descriptor v) const
 
 Return the label associated with the given vertex. This operation is only available
 for graphs with labeled vertices.
 
- edge_label& operator[](edge_descriptor e)
- edge_label const& operator[](edge_descriptor e) const
+[table
+[[Parameters] [Description]]
+[[`vertex_descriptor v`] [The vertex whose label is being accessed.]]
+[[`return`] [The label associated with the vertex described by `v`.]]
+]
+
+[variablelist
+[[Constraints] [Only available for `__LabeledVertexGraph__<G>` or `__MappedVertexGraph__<G>`.]]
+[[Complexity] [Property access is O(1).]]
+]
+
+ edge_label&        undirected_graph::operator[](edge_descriptor e)
+ edge_label const&  undirected_graph::operator[](edge_descriptor e) const
 
 Return the label associated with the given edge. This operation is only available
 for graphs with labeled edges.
 
+[table
+[[Parameters] [Description]]
+[[`edge_descriptor e`] [The edge whose label is being accessed.]]
+[[`return`]  [The label associated with the edge described by `e`.]]
+]
+
+[variablelist
+[[Constraints] [Only available for `__LabeledEdgeGraph__<G>`.]]
+[[Complexity] [Property access is O(1).]]
+]
+
 [heading Adding Vertices]
 
  vertex_descriptor add_vertex()
 
-Add an unlabeled vertex to the graph, returning the descriptor. This operation is
-only available for graphs with unlabeled vertices or whose labels are default constructible.
+Add an unlabeled vertex to the graph, returning the descriptor.
 
-/Complexity/: For vertex stores that model a __Sequence__ or __HashedAssociativeContainer__,
- this operation is /O(1)/. For __SortedAssociativeContainer__, this operation is
-/O(lg V)/.
+[variablelist
+[[Constraints]
+ [This operation is defined only if this graph models `__UnlabeledEdgeGraph__<G>`.]]
+[[Complexity] [Unlabeled vertex addition is O(1).]]
+]
 
  vertex_descriptor add_vertex(vertex_label const& l)
 
-Add a vertex with the label `l` to the graph, returning the descriptor. This operation
-is only available for graphs with labeled vertices (but not pair associative labels).
+Add a vertex with the label `l` to the graph, returning the descriptor.
 
-/Complexity/: For vertex stores that model a __Sequence__ or __HashedAssociativeContainer__
-this is /O(1)/. For __SortedAssociativeContainer__, this is /O(lg V)/.
+[variablelist
+[[Constraints]
+ [This operation is defined only if this graph models`__LabeledEdgeGraph__<G>`.]]
+[[Specializations]
+ [If `__UniqueAssociativeContainer__<G::vertex_store>` and the graph already contains
+  a vertex associated with the label `l`, a new vertex is not added and the returned
+  descriptor references the existing vertex.]]
+[[Complexity]
+ [For `__Sequence__<G::vertex_store>` and `__HashedAssociativeContainer__<G::vertex_store>`,
+  vertex addition is O(1). For `__SortedAssociativeContainer__<G::vertex_store>`, this
+  operation is O(lg V).]]
+]
 
  vertex_descriptor add_vertex(vertex_key const& k, vertex_label const& l)
 
-Add a vertex to the map with the label `l` and associate it with the key `k`. This
-operation is only avaialable for graphs with pair associative vertex labels.
+Add a vertex to the map with the label `l` and associate it with the key `k`, returning
+the descriptor.
 
-/Complexity/: For vertex stores that model a __HashedAssociativeContainer__, this
-is /O(1)/. For __SortedAssociativeContainer__, this is /O(lg V)/.
+[variablelist
+[[Constraints] [Only available for `__LabeledEdgeGraph__<G>`.]]
+[[Specializations]
+ [If `__UniqueAssociativeContainer__<G::vertex_store>` and the graph already contains
+  a vertex associated with the key `k`, a new vertex is not added and the  returned
+  descriptor references the existing vertex.]]
+[[Complexity]
+ [For `__Sequence__<G::vertex_store>` and `__HashedAssociativeContainer__<G::vertex_store>`,
+  vertex addition is /O(1)/. For `__SortedAssociativeContainer__<G::vertex_store>`, this
+  operation is /O(lg V)/.]]
+]
 
 [heading Accessing Vertices]
 
  vertex_descriptor vertex(vertex_label const& l) const
- vertex_descriptor vertex(verte_key const& k) const
 
-Return a vertex descriptor for the vertex identified by the given vertex label or
-key.
+Return a descriptor for a vertex with the label `l`. If no such vertex exists, return
+a null descriptor.
+
+[variablelist
+[[Constraints] [Only available for `__LabeledVertexGraph__<G>`.]]
+[[Specializations]
+ [If `__HasMultiEdges__<G>`, this will return a descriptor to the first vertex found
+  with the label `l`.]]
+[[Complexity for `__HashedAssociativeContainer__<G::vertex_store>`] [O(1)]]
+]
+
+ vertex_descriptor vertex(vertex_key const& k) const
+
+Return a descriptor for a vertex associated with the key `k`. If no such vertex exists,
+return a null descriptor.
+
+[variablelist
+[[Constraints] [Only available for `__MappedVertexGraph__<G>`.]]
+[[Specializations]
+ [If `__HasMultiEdges__<G>`, this will return a descriptor to the first vertex found
+  with the key `k`.]]
+[[Complexity]
+ [For `__HashedAssociativeContainer__<G::vertex_store>`, this operations is O(1).
+  For `__SortedAssociativeContainer__<G::vertex_store>`, this operation is O(lg V).
+  For `__Sequence__<G::vertex_store>`, this operation is O(V)]]
+]
 
 [heading Removing Vertices]
 
@@ -342,7 +274,13 @@
 
 Remove the given vertex or the vertex uniquely identified by the given label or
 key. All edges incident to the vertex are removed prior to the removal of the
-vertex.
+vertex.  The label and key overloads are equivalent to `remove_vertex(vertex(x))`
+where `x` is either the label or the key.
+
+/Restrictions:/ This operation not supported by vertex stores with unstable remove
+operations (i.e., `vertex_vector`).
+
+/Complexity:/
 
 [heading Adding Edges]
 
@@ -350,6 +288,8 @@
  void add_edge(vertex_label const& p, vertex_label const& q)
  void add_edge(vertex_key const& x, vertex_key const& y)
 
+ 
+
 [heading Accessing Edges]
 
  edge_descriptor edge(vertex_descriptor u, vertex_descriptor v)
@@ -407,4 +347,14 @@
  incident_edge_iterator end_incident_edges(vertex_descriptor v) const
  incident_edge_range incident_edges(vertex_descriptor v) const
 
+[heading Miscellaneous]
+
+ undirected_graph& swap(undirected_graph&& g)
+
+Swap this graph with `g` in constant time. Return a reference to this graph.
+
+ undirected_graph& clear()
+
+Remove all edges and verties from the graph in O(V + E
+
 [endsect]

Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/concepts.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/concepts.qbk	2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
@@ -0,0 +1,980 @@
+
+[section Graph Concepts]
+
+Despite the fact that this library has only two generic data structures and only
+one generic algorithm, it is has warranted the definition of a concept hierarchy
+that describes the generic interface of all the graph kinds this library should
+support. This hierarchy is not (currently) derived from emergent patterns that
+occur frequently in generic algorithms (which is generally where concepts come
+from). It is derived from the need to document the interfaces with respect to the
+constraints and refinements that imposed upon these data structures when instantiating
+them with certain types.
+
+If the concept hierarchy seems extensive - it is. A graph (in the general sense)
+has many, many different ways of being specified and implemented, and many of these
+options are relatively independent of others. In this sense, there aren't many
+graphs that fall into broad classifications for which we can easily create concepts.
+A graph, within the context of an algorithm or documentation, is a collection of
+features that can be reduced and constrained individually. Hence the size of this
+hierarchy.
+
+[important This is a work in progress.]
+
+[section Graph]
+The __Graph__ concept describes common requirements of all kinds of graphs.
+
+ concept __Graph__<typename G>
+ {
+     __Descriptor__ vertex_descriptor;
+     __Descriptor__ edge_descriptor;
+
+     static vertex_descriptor G::null_vertex();
+     static edge_descriptor G::null_edge();
+     static edge_descriptor G::make_ends(vertex_descriptor u, vertex_descriptor v);
+     static pair<vertex_descriptor, vertex_descriptor> G::get_ends(edge_descriptor e);
+ };
+
+The `null_vertex` operation returns a null vertex for the graph. This is mostly
+provided for parity with the BGL, but isn't truly needed since default-constructed
+descriptors are guaranteed to be null.
+
+The `null_edge` operation returns a null edge for the graph. As with vertex descriptors,
+default-constructed edges are null, so this function is provided only for parity
+with the `null_vertex` function.
+
+The `make_ends` operation creates a descriptor over the given endpoints of the graph.
+This does not add an edge to the graph, and the endpoints can denote edges that do
+not exist in the graph. The `make_ends` function will return a null descriptor if the
+requested endpoints do not satisfy all static properties of edges in the graph such
+as loops and dangling edges.
+
+The `get_ends` function retrieves the endpoints of an edge descriptor as `pair`.
+The ordering of the vertex descriptors depends on the implementation of the graph.
+
+[note *Design* The `make_ends` function demonstrates the fact that edge descriptors
+aren't really descriptors since you can make edges that do not exist. This is still
+a useful function, however.]
+[endsect]
+
+[section Vertex Kinds]
+Vertices in graphs distiguished by their labels and the meaning of those labels
+within the graph. For example, we could talk about graphs with unlabeled vertices,
+which are generally used for small examples about graphs. Most useful examples
+tend to include some kind of name or data associated with each vertex. For example,
+this could be names of cities in a road map, or names of airports in a flight plan.
+In many cases, the labels attached to these vertices are unique within the graph.
+For example, there are no two airports named LAX.
+
+[section UnlabeledVertexGraph]
+The __UnlabeledVertexGraph__ concept describes graphs whose vertices have no labels.
+This concept does not describe any syntactic or semantic requirements, but is only
+provided to express the particular state of the vertices in `G`.
+
+ concept __UnlabeledVertexGraph__<typename G>
+ {
+     typename vertex_label;
+     requires SameType<vertex_label, none>;
+ };
+
+[note *Design:* This is included because writing `!__LabeledVertexGraph__<G>` would
+seem to also imply `!__Graph__<G>` because of the refinement. This is definitely not
+what is intended. For many concepts and constraints, we can simply say that we
+require `__UnlabeledVertexGraph__<G>`.]
+
+[note *Implementation* This is probably not the optimal means of specifying this
+since it would require that unlabeled graphs actually expose a vertex label type.
+However, it does constrain that type to be unusable...]
+[endsect]
+
+[section LabelVertexGraph]
+The __LabeledVertexGraph__ concept applies to graphs labeled vertices.
+
+ concept __LabeledVertexGraph__<typename G> : __Graph__<G>
+ {
+     __ObjectType__ vertex_label;
+     requires !SameType<vertex_label, none>;
+
+     vertex_label& operator[](G&, vertex_descriptor v);
+     vertex_label const& operator[](G const&, vertex_descriptor v);
+
+     vertex_descriptor G::vertex(vertex_label const& l) const;
+ };
+
+The `operator[]` overload provides `const` and non-`const` access to the properties
+of the vertex represented by the descriptor `v`.
+
+The `vertex` function returns the first vertex associated with the label `l`. If no such
+vertex can be found, a null descriptor is returned.
+[endsect]
+
+[section MappedVertexGraph]
+The __MappedVertexGraph__ concept applies to graphs whose vertices and vertex labels
+associated with a key. This refines the __LabeledVertexGraph__<G> concept because
+keys must be mapped to data.
+
+ concept __MappedVertexGraph__<typename G> : __Graph__<G>
+ {
+     __ObjectType__ vertex_label;
+     __ObjectType__ vertex_key;
+     requires !SameType<vertex_label, none>;
+
+     vertex_label& operator[](G&, vertex_descriptor v);
+     vertex_label const& operator[](G const&, vertex_descriptor v);
+
+     vertex_descriptor G::vertex(vertex_key const& k) const;
+     vertex_key const& G::key(vertex_descriptor v) const;
+ };
+
+The `operator[]` overload provides `const` and non-`const` access to the properties
+of the vertex represented by the descriptor `v`.
+
+The `key` operation returns the key associated with each vertex represented by the
+descriptor `v`.
+
+The `vertex` function returns the first vertex associated with the label `l`. If no such
+vertex can be found, a null descriptor is returned.
+
+[note *Design*: This concept is distinct from the __LabeledVertexGraph__ because
+the a number of other concepts will require one or the other. Writing this concept in
+terms of __LabeledVertexGraph__ makes it nearly impossible to distinguish the two
+later on.]
+[endsect]
+
+[section UniqueLabeledVertexGraph]
+The __UniqueLabeledVertexGraph__ concept refines the __LabeledVertexGraph__ concept
+by adding the requirement that each label uniquely identifies a single vertex.
+
+ concept __UniqueLabeledVertexGraph__<typename G> : __LabeledVertexGraph__<G>
+ { };
+
+The `vertex` function runs in /O(lg V)/ on average. Note that hash tables have /O(1)/
+performance on average.
+
+[note *Design:* The uniqueness of vertices is typically accomplished using ordered
+(sorted) or unordered (hashed) sets. Each of these imposes its own requirements on
+the `label` via some ordering or hashing function, but those requirements are outside
+the scope of these concepts since they are internal to the data structures. These
+interfaces could, however, be expanded to expose the vertex comparator or hash
+function and could be made part of the graph interface.]
+[endsect]
+
+[section UniqueMappedVertexGraph]
+The __UniqueMappedVertexGraph__ concept refines the __MappedVertexGraph__ concept
+by adding the requirement that each key is uniquely associated with a single vertex.
+
+ concept __UniqueMappedVertexGraph__<typename G> : __MappedVertexGraph__<G>
+ { };
+
+The `vertex` function runs in /O(lg V))/ on average. Note that hash tables have /O(1)/
+performance on average.
+
+[note *Design:* The uniqueness of vertices is typically accomplished using ordered
+(sorted) or unordered (hashed) sets. Each of these imposes its own requirements on
+the `key` via some ordering or hashing function, but those requirements are outside
+the scope of these concepts since they are internal to the data structures. These
+interfaces could, however, be expanded to expose the vertex comparator or hash
+function and could be made part of the graph interface.]
+[endsect]
+
+[section Vertex Associativity]
+These concepts are for consideration, and have not been implemented. They refine
+the mechanism by which uniqueness is guarnanteed. In general, the /Sorted/ concepts
+result in many functions vertex operatoins in logarithmic time, while the hashed
+functions operate in constant time (on average) and assuming the underlying hash
+tables have good load factors.
+
+Note that these can also be used to describe the means by which multiplicity is
+/efficiently/ guaranteed, but since I can find no examples of applications that
+use multisets of or multimaps, they are excluded.
+
+ concept __HasSortedLabels__<typename G>
+ {
+     requires __LabeledVertexGraph__<G>;
+     __StrictWeakOrder__<auto, __LabeledVertexGraph__<G>::vertex_label> vertex_compare;
+     vertex_compare vertex_compare_function(G const& g)
+ };
+
+ concept __HasSortedKeys__<typename G>
+ {
+     requires __MappedVertexGraph__<G>;
+     __StrictWeakOrder__<auto, __MappedVertexGraph__<G>::vertex_key> vertex_compare;
+     vertex_compare vertex_compare_function(G const&) const;
+ };
+
+ concept __HasHashedLabels__<typename G>
+ {
+     requires __LabeledVertexGraph__<G>;
+     __HashFunction__<auto, __LabeledVertexGraph__<G>::vertex_label> vertex_hash;
+     vertex_hash vertex_hash_function(G const& g) const;
+ };
+
+ concept __HasHashedKeys__<typename G>
+ {
+     requires __MappedVertexGraph__<G>;
+     __HashFunction__<auto, __MappedVertexGraph__<G>::vertex_key> vertex_hash;
+     vertex_hash vertex_hash_function(G const& g) const;
+ };
+
+Each of these concepts describes a mechanism by which the associativity of vertex labels or
+keys is maintained. The `vertex_compare_function` returns the __StrictWeakOrder__ used
+to compare vertex labels or keys. The `vertex_hash_function` returns the __HashFunction__
+used to generate hash keys from the same labels or keys. Any kind of graph only
+ever models one of these concepts.
+
+[warning If your hash table implementations invalidate iterators on insertion or
+multiple iterators on removal, then you should definitely /not/ use hashed storage
+schemes for your graphs.]
+[endsect]
+[endsect]
+
+[section Edge Kinds]
+Just as there are several kinds of vertices, graphs can also have different kinds
+of edges. Edges are different than vertices in that they essentially defined by their
+endpoints. Because of this, it we cannot attribute the same kinds of uniqueness or
+mapping to edges that we would for vertices.
+
+Edges can have data (a label) associated with them, or not. Common examples of
+labels for edges include distance, resistance, and flow. Edges can also be unique
+within a graph. If a unique edge has endpoints /(u, v)/, then that is the only
+edge with those endpoints. Some graphs can also disallow some kinds of edges such
+as loops.
+
+Although all edge types (in this library) behave as __Descriptors__, they also
+have semantics beyond that of simple references. Specifically, edges have either
+undirected or directed semantics (__UndirectedEdge__ and __DirectedEdge__,
+respectively). These should be legitimate concepts in their own right because every
+graph data structure can be cast as either directed or undirected based primarily
+on the semantics of their edges.
+
+[section UnlabeledEdgeGraph]
+This concept denotes graphs that do not have labeled edges.
+
+ concept __UnlabeledEdgeGraph__<typename G> : Graph<G>
+ {
+     __ObjectType__ edge_label;
+     requires SameType<edge_label, none>;
+ };
+
+[note *Design:* See the note in __UnlabeledVertexGraph__.]
+[endsect]
+
+[section LabeledEdgeGraph]
+The __LabeledEdgeGraph__ concept applies to graphs with labeled edges.
+
+ concept __LabeledEdgeGraph__ : __Graph__<G>
+ {
+     __ObjectType__ edge_label;
+     requires !SameType<edge_label, none>;
+
+     edge_label& operator[](G&, edge_descriptor);
+     edge_label const& operator[](G const&, edge_descriptor);
+ };
+
+[note This library currently precludes the unique labeling and mapping of edges
+since edge uniqueness is determined by their endpoints and not their label.]
+[endsect]
+
+[section HasUniqueEdges]
+The __HasUniqueEdges__ concept applies to graphs that allow only a single edge
+to connect two vertices. Said otherwise, the endpoints `(u, v)` will always denote
+a unique edge label (if given) if it exists in the graph.
+
+ concept __HasUniqueEdges__<typename G>
+ {
+     requires Graph<G>;
+     axiom UniquenessOfEdges(G const& g, G::edge_descriptor e, G::edge_descriptor f)
+     {
+         if(G::get_ends(e) == G::get_ends(f)) {
+             e == f;
+         }
+     }
+ };
+
+The `UniquenessOfEdges` axiom states that if the end points of two edge descriptors
+are equivalent then their labels are the same object.
+
+[note The name __HasUniqueEdges__ is preferred over its inverse `Multigraph` in
+this case because writing `!HasUniqueEdges<G>` implies that `G` is a /multigraph/,
+but writing `!Multigraph<G>` does not necessarily imply that `G` is /simple/. An
+alternative writing migth be `AllowsMultipleEdges`.]
+[endsect]
+
+[section HasMultiEdges]
+The __HasMultiEdges__ concept applies to graphs that allow any number of edges to
+connect two vertices. This concept is mostly descriptive and is essentially shorthand
+for `!__HasUniqueEdges__<G>`.
+
+ concept __HasMultiEdges__<typename G>
+ {
+     requires !__HasUniqueEdges__<G>;
+ };
+
+[endsect]
+
+[section HasLoopEdges]
+The __HasLoopEdges__ concept applies to any graph that allows loops to exist in
+the graph.
+
+ concept __HasLoopEdges__<typename G>
+ {
+     requires Graph<G>;
+     axiom ReflexivityOfEdges(G::vertex_descriptor v)
+     { G::make_ends(v, v) != G::null_edge(); }
+ };
+
+The `ReflexivityOfEdges` allows the creation of end points that create edges from
+a vertex to itself.
+
+[note This could probably be used in conjunction to describe a `SimpleGraph` as
+one requiring  `HasUniqueEdges<G> && !HasLoopEdges<G>`. This concept could also be
+named written `AllowsLoopEdges`.]
+[endsect]
+
+[section HasUndirectedEdges]
+The endpoints of an undirected edge impart no notion of directionality. Note that
+the interface required by these edge kinds is not part of the interface of the `G`.
+
+ concept __HasUndirectedEdges__<typename G>
+ {
+     requires Graph<G>;
+
+     G::vertex_descriptor first(G::edge_descriptor e);
+     G::vertex_descriptor second(G::edge_descriptor e);
+
+     axiom EndpointEquivalence(G::vertex_descriptor v, G::vertex_descriptor u)
+     { G::make_ends(u, v) == G::make_ends(v, u); }
+ };
+
+The `first` function returns the first endpoint of the edge descriptor `e`.
+
+The `second` function returns the second endpoint of the edge descriptor `e`.
+
+The `EndpointEquivalence` axiom guarantees that the endpoints `(u, v)` are the same
+as the endpoints `(v, u)`.
+
+[note *Design:* This concept can make the development and use of algorithms somewhat
+tricky. In many cases, algorithms traverse edges and notify their visitors about the
+edges being traversed. In this case, the notions of source and target are important,
+but undirected edges have no notion of directionality. The solution taken in this
+implementation is to wrap the undirected edge in a directed edge by duplicating the
+storage of one endpoint as the source.]
+[endsect]
+
+[section HasDirectedEdges]
+The endpoints of an directed edge indicate the source and target vertices of that
+edge. Note that the interface required by these edge kinds is not part of the interface
+of the `G`.
+
+ concept __HasDirectedEdges__<typename G>
+ {
+     requires Graph<G>;
+
+     G::vertex_descriptor source(G::edge_descriptor e);
+     G::vertex_descriptor target(G::edge_descriptor e);
+
+     axiom EndpointInequivalence(G>::vertex_descriptor v, Gvertex_descriptor u)
+     {
+         if(u != v) {
+             G::make_ends(u, v) != G::make_ends(v, u);
+         }
+     }
+ };
+
+The `source` function returns the source endpoint of the edge descriptor `e`.
+
+The `target` function returns the second endpoint of the edge descriptor `e`.
+
+The `EndpointInequivalence` axiom guarantees that, if `(u, v)` does not describe
+a loop, then the edge with the endpoints `(u, v)` is distinct from an edge with
+the endpoints `(v, u)`.
+[endsect]
+[endsect]
+
+[section Edge Operations]
+There are a number of different concepts related to the addition and removal
+of edges.
+
+[section HasFindEdge]
+The __HasFindEdge__ concept applies to graphs that can be queried for the existence
+of an edge by its endpoints.
+
+ concept __HasFindEdge__<typename G>
+ {
+     requires Graph<G>;
+     G::edge_descriptor G::edge(G::vertex_descriptor u, G::vertex_descriptor v);
+ };
+
+The `edge` function returns the first edge found that connects vertices `u` and `v`.
+If no such edge is found, the returned descriptor is null.
+[endsect]
+
+[section HasAddEdge]
+The __HasAddEdge__ concept is a base concept that describes any graph to which
+edges may be added after construction. The ability to dynamically add edges does
+not necessarily imply the allocation of more memory (as opposed to adding to a `list`).
+The addition of edges is best thought of as the connecting of two vertices, which
+may or may not have some data associated with it.
+
+ concept __HasAddEdge__<typename G> { };
+
+[note *Design:* There are many ways to add edges, and each specific method is
+defined by a new concept. This is a generalization of all of them.]
+[endsect]
+
+[section HasAddUnlabledEdge]
+The __HasAddUnulabledEdge__ concept applies to any graph to which edges can be added after
+construction.
+
+ concept __HasAddUnlabeledEdge__<typename G> : __HasAddEdge__<G>
+ {
+     requires __UnlabeledEdgeGraph__<G>;
+     G::edge_descriptor add_edge(G::vertex_descriptor u, G::vertex_descriptor v)
+ }
+
+This concept requires that that target graph have unlabeled edges.
+
+The `add_edge` operation will connect the vertex `u` to the vertex `v` and return
+a descriptor to the new edge.
+
+The samantics vary if `__HasUniqueEdges__<G>`. If the edge `(u, v)` denotes an existing
+edge in the graph, then no action is taken. The returned descriptor represents the
+existing edge, not a new one. See __HasAddUniqueUnlabeledEdge__ for a means of
+determining the success of edge addition.
+[endsect]
+
+[section HasAddLabeledEdge]
+The __HasAddLabeledEdge__ concept applies to any graph to which labeled edges
+can be added after construction. This concept also refines the __LabeledEdgeGraph__
+concept.
+
+ concept __HasAddLabeledEdge__<typename G> : __HasAddEdge__<G>
+ {
+     requires __LabeledEdgeGraph__<G>;
+     G::edge_descriptor G::add_edge(G::vertex_descriptor u,
+                                    G::vertex_descriptor v,
+                                    G::edge_label const& l)
+ }
+
+The `add_edge` operation adds a new edge connecting the vertex `u` to the vertex `v`,
+and assigning the label `l` to the edge. A descriptor to the new edge is returned.
+
+The samantics vary if `__HasUniqueEdges__<G>`. If the edge `(u, v)` denotes an existing
+edge in the graph, then no action is taken. The label `l` is /not/ assigned to the
+edge, and the returned descriptor represents the existing edge, not a new one. See
+__HasAddUniqueLabeledEdge__ for a means of determining the success of edge addition.
+
+The semantics vary if `!__HasLoopEdges__<G>`. If `u == v`, then no action is taken
+and the returned descriptor is null.
+[endsect]
+
+[section HasAddUniqueUnlabeledEdge]
+The __HasAddUniqueUnlabeledEdge__ concept is a refinement of __HasAddUnlabeledEdge__ that
+provides an operation that reports the success of the edge addition.
+
+ concept __HasAddUniqueUnlabeledEdge__ : __HasUniqueEdges__<G>, __HasAddUnlabeledEdge__<G>
+ {
+     std::pair<G::edge_descriptor, bool> G::insert_edge(G::vertex_descriptor u,
+                                                        G::vertex_descriptor v);
+ };
+
+The `insert_edge` operation attempts to connct the vertex `u` to the vertex `v` and
+returns a pair containing the resulting edge descriptor and a boolean value indicating
+whether or not a new edge was added to the graph. If the boolean value is `false`
+after completion, a new edge was not added, and the descriptor references an existing
+edge.
+
+The semantics vary if `!__HasLoopEdges__<G>`. If `u == v`, then the boolean value
+is false, indicating no edge addition, and edge descriptor is null.
+[endsect]
+
+[section HasAddUniqueLabeledEdge]
+The __HasAddUniqueLabeledEdge__ concept is a refinement of the __HasAddLabeledEdge__
+concept that provides a that reports the result of the edge addition.
+
+ concept __HasAddUniqueLabeledEdge__<typename G> : __HasUniqueEdges__<G>, __HasAddLabeledEdge__<G>
+ {
+     std::pair<G::edge_descriptor, bool> G::insert_edge(G::vertex_descriptor u,
+                                                        G::vertex_descriptor v,
+                                                        G::edge_label const& l);
+ };
+ 
+The `insert_edge` operation attempts to connct the vertex `u` to the vertex `v`, assiging
+the label `l` to the new edge, and returns a pair containing the resulting edge
+descriptor and a boolean value indicating whether or not a new edge was added to
+the graph. If the boolean value is `false` after completion, a new edge was not added,
+the label was not assigned, and the descriptor references an existing edge.
+
+The semantics vary if `!__HasLoopEdges__<G>`. If `u == v`, then the boolean value
+is false, indicating no edge addition, and edge descriptor is null.
+[endsect]
+
+[section HasRemoveEdge]
+The __HasRemoveEdge__ concept applies to any graph from which edges may be removed
+after construction.  This is a refinement of the __HasAddEdge__ concept because
+any graph that allows the dynamic removal of edges should also allow their addition.
+Note that the converse is not true - not all graphs that modelt the __HasAddEdge__
+concept also model the __HasRemoveEdge__ concept.
+
+ concept HasRemoveEdge<typename G> : __HasAddEdge__<G>
+ {
+     requires Graph<G>;
+     void G::remove_edge(G::edge_descriptor e);
+     void G::remove_edges(G::vertex_descriptor u, G::vertex_descriptor v);
+     void G::remove_edges(G::vertex_descriptor v);
+ };
+
+The `remove_edge` operation removes only the edge represented by the descriptor `e`.
+
+The first `remove_edges` operation removes all edges connecting with `u` and `v` as
+endpoints. If `__HasUniqueEdges__<G>`, then `remove_edges` will remove at most one edge.
+
+The second `remove_edges` operation removes all edges incident to the vertex `v`
+so that its its degreee will be 0 after completion.
+[endsect]
+[endsect]
+
+[section Vertex Operations]
+[section HasAddVertex]
+The __HasAddVertex__ applies to any graph that defines any method for adding
+vertices to a graph after constrution.
+
+ concept __HasAddVertex__<typename G> { };
+
+[note *Design:* There are many ways to add edges, and each specific method is
+defined by a new concept. This is a generalization of all of them.]
+[endsect]
+
+[section HasAddUnlabeledVertex]
+The __HasAddUnalbeledVertex__ applies to graphs that allow the addition of unlabeled
+vertices.
+
+ cocnept __HasAddUnlabeledVertex__<typename G> : __HasAddVertex__<G>
+ {
+     requires __UnlabeledVertexGraph__<G>;
+     G::vertex_descriptor G::add_vertex();
+ };
+
+The `add_vertex` operation adds a new, unlabeled vertex to the graph and returns
+a descriptor to the new vertex.
+[endsect]
+
+[section HasAddLabeledVertex]
+The __HasAddVertex__ applies to any graph that defines any method for adding
+vertices to a graph after constrution.
+
+ concept __HasAddLabeledVertex__<typename G> :  __HasAddVertex__<G>
+ {
+     reuqires __LabeledVertexGraph__<G>;
+     G::vertex_descriptor G::add_vertex(G::vertex_label const& l);
+ };
+
+The `add_vertex` operation adds a new vertex with the label `l` to the graph.
+
+The semantics vary if `__UniqueLabeledVertexGraph__<G>`. If a vertex in the graph
+is already associated with the label `l`, then a new vertex is not added, the label
+is not assigned, and the returned descriptor represents the existing vertex.
+[endsect]
+
+[section HasAddMappedVertex]
+The __HasAddVertex__ applies to any graph that defines any method for adding
+vertices to a graph after constrution.
+
+ concept __HasAddMappedVertex__<typename G> : __HasAddVertex__<G>
+ {
+     requires __MappedVertexGraph__<G>;
+     G::vertex_descriptor G::add_vertex(G::vertex_key const& k, G::vertex_label const& l);
+ };
+
+The `add_vertex` operation adds a new vertex to the graph associated with the key `k`
+and the label `l`.
+
+The semantics vary if `__UniqueMappedVertexGraph__<G>`. If a vertex in the graph
+is already associated with the key `k`, then a new vertex is not added, the label
+is not assigned, and the returned descriptor represents the existing vertex.
+[endsect]
+
+[section HasAddUniqueLabeledVertex]
+The __HasAddVertex__ applies to any graph that defines any method for adding
+vertices to a graph after constrution.
+
+ concept __HasAddUniqueLabeledVertex__<typename G> : __HasAddLabeledVertex__<G>
+ {
+      std::pair<G::vertex_descriptor, bool> G::insert_vertex(G::vertex_label const& l);
+ };
+
+Try to add the vertex to the graph, returning a descriptor a vertex and a boolean
+value that denotes the success of the operation. If the boolean value is returned
+as `false`, then a new vertex was not added and the descriptor references an existing
+vertex with the label `l`.
+[endsect]
+
+[section HasAddUniqueMappedVertex]
+The __HasAddVertex__ applies to any graph that defines any method for adding
+vertices to a graph after constrution.
+
+ concept __HasAddUniqueMappedVertex__<typename G> : __HasAddMappedVertex__<G>
+ {
+      std::pair<G::vertex_descriptor, bool> G::insert_vertex(G::vertex_key const& k,
+                                                             G::vertex_label const& l);
+ };
+
+Try to add the vertex to the graph, returning a descriptor a vertex and a boolean
+value that denotes the success of the operation. If the boolean value is returned
+as `false`, then a new vertex was not added and the descriptor references an existing
+vertex with the key `k`.
+[endsect]
+
+[section HasRemoveVertex]
+The __HasRemoveVertex__ applies to any graph that defines any method for removing
+vertices from a graph after construction. This concept refines the __HasAddVertex__
+concept. Graphs that support the dynamic removal of vertices must also support their
+addition. The converse is not necessarily true. A graph that supports vertex addition
+need not support removal.
+
+ concept __HasRemoveVertex__<typename G> : __HasAddVertex__<G>
+ {
+     requires Graph<G>;
+     void G::remove_vertex(G::vertex_descriptor v);
+ };
+
+The `remove_vertex()` operation removes the vertex `v` from the graph. All incident
+edges of `v` are removed prior to the removal of the vertex.
+[endsect]
+[endsect]
+
+[section Graph Kinds]
+This section enumerates structural requirements on kinds of graphs.
+
+The directed graph hierarchy has been re-composed to specifically name the direction
+of edges supported by the graph. This admits the ability to create graph data structures
+that support only out edges or only in edges, and (most commonly), both. This also
+allows algorithms that only operate on the in edges of graphs (there are probably a
+few) to only require that concept, rather than a fully directed graph.
+
+There are several different sub-hiearchies in this set of concepts:
+
+[table Kinds of Graphs
+[[Kind] [Related Concepts]]
+[
+    [
+        /Components/ - These concepts relate to the major components of the graph,
+        specifically access to the vertex and sets.
+    ]
+    [__VertexListGraph__, __EdgeListGraph__]
+]
+[
+    [
+        /Mutability/ - These concepts relate to the dynamic setup and teardown of graphs
+        after construction. These concepts are more taxonomic than anything since they
+        can't specify /how/ types are constructible or mutable. They are sometimes
+        useful to describe graphs that are constructible or fully mutable.
+
+        Unfortunately, these don't actually tell you you anything useful a graph
+        since they only require refinements of `Has*` concepts. These will probably
+        go away since they aren't that useful.
+    ]
+    [
+        __ConstructibleVertexGraph__, __MutableVertexGraph__, __ConstructibleEdgeGraph__,
+        __MutableEdgeGraph__, __ConstructibleGraph__, __MutableGraph__
+    ]
+]
+[
+    [
+        /Directionality/ - These concepts relate to the directionality of edges with
+        respect to graphs.
+    ]
+    [__UndirectedGraph__, __OutDirectedGraph__, __InDirectedGraph__, __DirectedGraph__]
+]
+[
+    [
+        /Incidence/ - Concepts related to the /generic/ notion of incidence of edges
+        and adjacency of vertices.
+    ]
+    [__IncidenceGraph__, __AdjacencyGraph__, __Multigraph__]
+]
+[
+    [
+        /Implementation/ - Concepts related to the data structures that implement
+        graph types. These concepts refine other graph concepts to describe efficient
+        operations, rather than just their syntactic presence.
+    ]
+    [__AdjacencyMatrix__, __IncidenceMatrix__]
+]
+]
+
+[section VertexListGraph]
+The __VertexListGraph__ describes the requirements of graphs that expose an iterable
+sequence of their vertices.
+
+ concept __VertexListGraph__<typename G> : __Graph__<G>
+ {
+     __ForwardIterator__ vertex_iterator;
+     __ForwardRange__ vertex_range;
+     __UnsignedIntegralLike__ vertices_size_type;
+
+     vertex_iterator begin_vertices() const;
+     vertex_iterator end_vertices() const;
+     vertex_range vertices() const;
+
+     vertices_size_type num_vertices() const;
+ };
+
+[endsect]
+
+[section EdgeListGraph]
+The __EdgeListGraph__ describes the requirements of graphs that expose an iterable
+sequence of their edges.
+
+ concept __EdgeListGraph__ : <typename G> : __Graph__<G>
+ {
+     __ForwardIterator__ edge_iterator;
+     __ForwardRange__ edge_range;
+     __UnsignedIntegralLike__ edges_size_type;
+
+     edge_iterator begin_edges() const;
+     edge_iterator end_edges() const;
+     edge_range edges() const;
+
+     edges_size_type num_edges() const;
+ };
+
+[endsect]
+
+[section ConstructibleVertexGraph]
+
+ concept __ConstructibleVertexGraph__<typename G> : __Graph__<G>
+ {
+     requires __HasAddVertex__<G>;
+ };
+
+[endsect]
+
+[section MutableVertexGraph]
+
+ concept __MutableVertexGraph__<typename G> : __ConstructibleVertexGraph__<G>
+ {
+     requires HasRemoveVertex<G>;
+ };
+
+[endsect]
+
+[section ConstructibleEdgeGraph]
+
+ concept __ConstructibleEdgeGraph__<typename G> : __Graph__<G>
+ {
+     requires __HasAddEdge__<G>;
+ };
+
+[endsect]
+
+[section MutableEdgeGraph]
+
+ concept __MutableEdgeGraph__<typename G> : __ConstructibleEdgeGraph__<G>
+ {
+     HasRemoveEdge<G>
+ };
+
+[endsect]
+
+[section ConstructibleGraph]
+
+ concept __ConstructibleGraph__<typename G>
+     : __ConstructibleVertexGraph__<G>, __ConstructibleEdgeGraph__<G>
+ { };
+
+[endsect]
+
+[section MutableGraph]
+
+ concept __MutableGraph__<typename G>
+    : __MutableVertexGraph__<G>, __MutableEdgeGraph__<G>
+ { }
+
+[endsect]
+
+[section UndirectedGraph]
+The __UndirectedGraph__ concept describes the requirements of undirected graphs,
+specifically, that the graph has undirected edges, and provides access to the incident
+edges of each vertex.
+
+ concept __UndirectedGraph__<typename G> : __Graph__<G>
+ {
+     requires __HasUndirectedEdges__<G>;
+
+     __ForwardIterator__ incident_edge_iterator;
+     __ForwardRange__ incident_edge_range;
+     __UnsignedIntegralLike__ incident_edges_size_type;
+
+     incident_edge_iterator G::begin_incident_edges(vertex_descriptor v) const;
+     incident_edge_iterator G::end_incident_edges(vertex_descriptor v) const;
+     incident_edge_range G::incident_edges(vertex_descriptor v) const;
+
+     incident_edges_size_type G::degree(vertex_descriptor v) const;
+ };
+
+[note *Design* This is not the same as __IncidenceGraph__. This concept describes
+requirements only for undirected graphs, whereas the __IncidenceGraph__ defines
+incidence as an abstract concept that can be satisfied differently by undirected
+and directed graphs.]
+[endsect]
+
+[section OutDirectedGraph]
+The __OutDirectedGraph__ concept defines requirements for graphs that provide
+directional access to the out-edges of a vertex.
+
+ concept __OutDirectedGraph__<typename G> : __Graph__<G>
+ {
+     requires __HasDirectedEdges__<G>;
+
+     __ForwardIterator__ out_edge_iterator;
+     __ForwardRange__ out_edge_range;
+     __UnsignedIntegralLike__ out_edges_size_type;
+
+     out_edge_iterator G::begin_out_edges(vertex_descriptor v) const;
+     out_edge_iterator G::end_out_edges(vertex_descriptor v) const;
+     out_edge_range G::out_edges(vertex_descriptor v) const;
+
+     out_edges_size_type G::out_degree(vertex_descriptor v) const;
+ };
+
+[note This replaces the `DirectedGraph` concept in the BGL, and makes it a little
+more explicit about what is being directed.]
+[endsect]
+
+[section InDirectedGraph]
+The __InDirectedGraph__ concept describes requirements for graphs that provide
+directional access to the in-edges of a vertex.
+
+ concept __InDirectedGraph__<typename G> : __Graph__<G>
+ {
+     requires __HasDirectedEdges__<G>;
+
+     __ForwardIterator__ in_edge_iterator;
+     __ForwardRange__ in_edge_range;
+     __UnsignedIntegralLike__ in_edges_size_type;
+
+     in_edge_iterator G::begin_in_edges(vertex_descriptor v) const;
+     in_edge_iterator G::end_in_edges(vertex_descriptor v) const;
+     in_edge_range G::in_edges(vertex_descriptor v) const;
+
+     in_edges_size_type G::in_degree(vertex_descriptor v) const;
+ };
+
+[note This concept does not exist by itself in the BGL, but was part of the
+`BidirectionalGraph` concept. It is conceivable that some algorithms operate only
+on the in-edges of a fully directed graph.]
+[endsect]
+
+[section DirectedGraph]
+The __DirectedGraph__ concept refines both __OutDirectedGraph__ and __InDirectedGraph__,
+providing directional access to both the in and out edges of a graph.
+
+ concept __DirectedGraph__<typename G> : __OutDirectedGraph__<G>, __InDirectedGraph__<G>
+ {
+     __UnsignedIntegralLike__ incident_edges_size_type = out_edges_size_type;
+     incident_edges_size_type G::degree(vertex_descriptor v) const;
+ };
+
+The `degree` of a vertex in a __DirectedGraph__ is the sum of the in and out degree.
+[endsect]
+
+[section IncidenceGraph]
+The __IncidenceGraph__ concept describes a generic interface for accessing the incident
+edges of a graph. Incidence is variably defined for the __UndirectedGraph__ and
+__DirectedGraph__ concepts. The former defines incidence directly, whereas the latter
+typically denotes outgoing edges as incident.
+
+ concept __IncidenceGraph__<typename G> : __Graph__<G>
+ {
+      __ForwardIterator__ incident_edge_iterator;
+      __ForwardRange__ incident_edge_range;
+      __UnsignedIntegralLike__ incident_edges_size_type;
+
+      incident_edge_iterator begin_incident_edges(G const& g, vertex_descriptor v);
+      incident_edge_interator end_incident_edges(G const& g, vertex_descriptor v);
+      incident_edge_range incident_edges(G const& g, vertex_descriptor v);
+
+      incident_edges_size_type num_incident_edges(G const& g);
+ };
+
+The `num_incident_edges` function returns the number of edges incident to vertex `v`
+of graph `g`. This number is counted along the edges considered incident by the graph.
+For an __UndirectedGraph__, this would be the same as its degree. For a __DirectedGraph__,
+however, it could be its out-degree or in-degree, depending on how the graph type
+satisfies these requirements, but not its cumulative degree.
+[endsect]
+
+[section AdjacencyGraph]
+The __AdjacencyGraph__ concept describes a generic interface for accessing the
+adjacent vertices of a graph. This is related to the __IncidenceGraph__ in that
+a vertex's adjacent vertices are the opposite endpoints of their incident edges.
+
+ concept __AdjacencyGraph__<typename G> : __IncidenceGraph__<G>
+ {
+      __ForwardIterator__ adjacent_vertex_iterator;
+      __ForwardRange__ adjacent_vertex_range;
+      __UnsignedIntegralLike__ adjacent_vertices_size_type;
+
+      adjacent_vertex_iterator begin_adjacent_vertices(G const& g, vertex_descriptor v);
+      adjacent_vertex_interator end_adjacent_vertices(G const& g, vertex_descriptor v);
+      adjacent_vertex_range adjacent_vertices(G const& g, vertex_descriptor v);
+
+      adjacent_vertices_size_type num_adjacenct_vertices(G const& g);
+ };
+
+[note *Question* If __Multigraph__<G>, how many times should a vertex `v` be considered
+adjacent to `u` if there are /n/ edges connecting them? From an implementation
+perspective, it would seem easy to say that `v` is adjacent /n/ times. From a common
+sense perspective, a vertex is either adjacent or it isn't - `v` should only be
+adjacent once. This is easier to implement with `multisets` than sequences.]
+[endsect]
+
+[section Multigraph]
+The __Multigraph__ concept defienes interface requirements for graphs that allow
+multiple edges connecting two distinct endpoints. Specifically, multigraphs must
+not have unique edges and provide a view of multiple edges connecting two vertices.
+This view is an abstraction over the incident edges of a graph, but may be implemented
+more efficiently (as in a `multiset` or `unordered_multiset`).
+
+ concept __Multigraph__<typename G> : __IncidenceGraph__<G>
+ {
+     requires HasMultiEdges<G>;
+
+     __ForwardIterator__ multi_edge_iterator;
+     __ForwardRange__ multi_edge_range;
+     __UnsignedIntegralLike__ multi_edges_size_type;
+
+     multi_edge_iterator begin_multi_edges(G const&, vertex_descriptor u, vertex_descriptor v);
+     multi_edge_iterator end_multi_edges(G const&, vertex_descriptor u, vertex_descriptor v);
+     multi_edge_range multi_edges(G const&, vertex_descriptor u, vertex_descriptor v);
+
+     multi_edges_size_type num_multi_edges(G const&, vertex_descriptor u, vertex_descriptor v);
+ };
+
+[note *Design* Ideally, this should constrain the access of multi edges to graphs
+that can provide this feature in time linear to the degree of both vertices. This
+basically restricts implementations to adjacency lists. Note that efficient implementations
+can supply supply these iterators in logarithmic or even constant time.]
+[endsect]
+
+[section AdjacencyMatrix]
+The __AdjacencyMatrix__ concept describes a refinement of a graph type that
+provides fast (constant-time) access to the edges connecting two vertices.
+
+ concept __AdjacencyMatrix__<typename G> : Graph<G>
+ {
+     requires HasEdge<G>;   // But constant time.
+ };
+
+This concept requires that the `edge` function return in constant time.
+[endsect]
+
+[section IncidenceMatrix]
+I'm not entirely sure what this does yet...
+
+ concept __IncidenceMatrix__<typename G> { };
+
+[endsect]
+[endsect]
+
+[endsect] [/ Graph Concepts /]

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/graphs.qbk	2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
@@ -17,15 +17,23 @@
 
 [include macros.qbk]
 
-[/ Concept Macros - apparently these have file scope. /]
+[/ Standard concepts /]
+[def __ObjectType__ [^ObjectType]]
 [def __DefaultConstructible__ [^DefaultConstructible]]
 [def __CopyConstructible__ [^CopyConstructible]]
+[def __MoveConstructible__ [^MoveConstructible]]
 [def __LessThanComparable__ [^LessThanComparable]]
 [def __Semiregular__ [^Semiregular]]
 [def __Regular__ [^Regular]]
+[def __EquivalenceRelation__ [^EquivalenceRelation]]
 [def __StrictWeakOrder__ [^StrictWeakOrder]]
+[def __SignedIntegralLike__ [^SignedIntegralLike]]
+[def __UnsignedIntegralLike__ [^UnsignedIntegralLike]]
+[def __HashFunction__ [^HashFunction]]
 [def __Hashable__ [^Hashable]]
 [def __Allocator__ [^Allocator]]
+
+[/ Containers /]
 [def __Container__ [^Container]]
 [def __Sequence__ [^Sequence]]
 [def __FrontInsertionSequence__ [^FrontInsertionSequence]]
@@ -38,9 +46,64 @@
 [def __UniqueAssociativeContainer__ [^UniqueAssociativeContainer]]
 [def __MultipleAssociativeContainer__ [^MultipleAssociativeContainer]]
 
-[/ Graph pseudo-concepts /]
-[def __SimpleGraph__ [^SimpleGraph]]
+[/ Iterators and Ranges /]
+[def __ForwardIterator__ [^ForwardIterator]]
+[def __BidirectionalIterator__ [^BidirectionalIterator]]
+[def __RandomAccessIterator__ [^RandomAccessIterator]]
+[def __ForwardRange__ [^ForwardRange]]
+[def __BidirectionalRange__ [^BidirectionalRange]]
+[def __RandomAccessRange__ [^RandomAccessRange]]
+
+[/ Tons and tons of graph concepts /]
+[def __Descriptor__ [link boost_graph.graph_concepts.descriptor [^Descriptor]]]
+[def __Graph__ [^Graph]]
+[def __UnlabeledVertexGraph__ [^UnlabeledVertexGraph]]
+[def __LabeledVertexGraph__ [^LabeledVertexGraph]]
+[def __MappedVertexGraph__ [^MappedVertexGraph]]
+[def __UniqueLabeledVertexGraph__ [^UniqueLabeledVertexGraph]]
+[def __UniqueMappedVertexGraph__ [^UniqueMappedVertexGraph]]
+[def __HasSortedLabels__ [^HasSortedLabels]]
+[def __HasSortedKeys__ [^HasSortedKeys]]
+[def __HasHashedLabels__ [^HasHashedLabels]]
+[def __HasHashedKeys__ [^HasHashedKeys]]
+[def __UnlabeledEdgeGraph__ [^UnlabeledEdgeGraph]]
+[def __LabeledEdgeGraph__ [^LabeledEdgeGraph]]
+[def __HasUniqueEdges__ [^HasUniqueEdges]]
+[def __HasMultiEdges__ [^HasMultiEdges]]
+[def __HasLoopEdges__ [^HasLoopEdges]]
+[def __HasUndirectedEdges__ [^HasUndirectedEdges]]
+[def __HasDirectedEdges__ [^HasDirectedEdges]]
+[def __HasFindEdge__ [^HasFindEdge]]
+[def __HasAddEdge__ [^HasAddEdge]]
+[def __HasAddUnlabeledEdge__ [^HasAddUnlabeledEdge]]
+[def __HasAddLabeledEdge__ [^HasAddLabeledEdge]]
+[def __HasAddUniqueUnlabeledEdge__ [^HasAddUniqueUnlabeledEdge]]
+[def __HasAddUniqueLabeledEdge__ [^HasAddUniqueLabeledEdge]]
+[def __HasRemoveEdge__ [^HasRemoveEdge]]
+[def __HasAddVertex__ [^HasAddVertex]]
+[def __HasAddUnlabeledVertex__ [^HasUnlabeledVertex]]
+[def __HasAddLabeledVertex__ [^HasAddLabeledVertex]]
+[def __HasAddMappedVertex__ [^HasAddMappedVertex]]
+[def __HasAddUniqueLabeledVertex__ [^HasAddUniqueLabeledVertex]]
+[def __HasAddUniqueMappedVertex__ [^HasAddUniqueMappedVertex]]
+[def __HasRemoveVertex__ [^HasRemoveVertex]]
+[def __VertexListGraph__ [^VertexListGraph]]
+[def __EdgeListGraph__ [^EdgeListGraph]]
+[def __ConstructibleVertexGraph__ [^ConstructibleVertexGraph]]
+[def __ConstructibleEdgeGraph__ [^ConstructibleEdgeGraph]]
+[def __ConstructibleGraph__ [^ConstructibleGraph]]
+[def __MutableVertexGraph__ [^MutableVertexGraph]]
+[def __MutableEdgeGraph__ [^MutableEdgeGraph]]
+[def __MutableGraph__ [^MutableGraph]]
+[def __UndirectedGraph__ [^UndirectedGraph]]
+[def __OutDirectedGraph__ [^OutDirectedGraph]]
+[def __InDirectedGraph__ [^InDirectedGraph]]
+[def __DirectedGraph__ [^DirectedGraph]]
+[def __IncidenceGraph__ [^IncidenceGraph]]
+[def __AdjacencyGraph__ [^AdjacencyGraph]]
 [def __Multigraph__ [^Multigraph]]
+[def __AdjacencyMatrix__ [^AdjancencyMatrix]]
+[def __IncidenceMatrix__ [^IncidenceMatrix]]
 
 [section Introduction]
 The goal of this Google Summer of Code project was to attempt a redesign of the
@@ -65,6 +128,8 @@
 
 [include guide.qbk]
 
+[include concepts.qbk]
+
 [section Graph Types]
 Unlike the previous version of the BGL, this library's take on graph types is that
 more is better. Rather than parameterize all structural aspects of a graph data

Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/html/boostbook.css
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/html/boostbook.css	(original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/doc/html/boostbook.css	2008-09-29 10:44:46 EDT (Mon, 29 Sep 2008)
@@ -52,6 +52,7 @@
     .programlisting,
     .screen
     {
+        background-color: #f5f5f5;  /* whitesmoke */
         font-size: 11pt;
         display: block;
         margin: 1pc 4% 0pc 4%;
@@ -75,6 +76,9 @@
         text-align: left;
         margin: 1em 0em 0.5em 0em;
         font-weight: bold;
+        border: solid;
+        padding: 0.5em;
+        background-color: #f5f5f5;
     }
 
     h1 { font: 140% }
@@ -309,6 +313,7 @@
         display: block;
         margin: 1pc 4% 0pc 4%;
         padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+        background-color: #fffff0;
     }
 
     p.blurb img
@@ -325,17 +330,18 @@
     span.term
     {
         font-weight: bold;
-        font-size: 10pt;
+        font-size: 11pt;
+        margin: 1pc 4% 0pc 4%;
     }
 
     div.variablelist table tbody tr td
     {
-        text-align: left;
+        text-align: justify;
         vertical-align: top;
         padding: 0em 2em 0em 0em;
         font-size: 10pt;
         margin: 0em 0em 0.5em 0em;
-        line-height: 1;
+        line-height: 1.25;
     }
 
     div.variablelist dl dt
@@ -345,15 +351,15 @@
 
     div.variablelist dl dd
     {
-        margin: 0em 0em 0.5em 2em;
-        font-size: 10pt;
+        margin: 0.5em 8% 0.5em 8%;
+        font-size: 11pt;
     }
 
     div.variablelist table tbody tr td p,
     div.variablelist dl dd p
     {
         margin: 0em 0em 0.5em 0em;
-        line-height: 1;
+        line-height: 1.25;
     }
 
 /*=============================================================================