
BoostCommit : 
Subject: [Boostcommit] svn:boost r49001  in sandbox/SOC/2008/graphs/trunk/libs/graphs/doc: . adj_list html
From: asutton_at_[hidden]
Date: 20080929 10:44:47
Author: asutton
Date: 20080929 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 20080929 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=$(boostroot)/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 20080929 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 runtimeconstructilbe 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 20080929 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
constanttime 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 pervertex 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 constanttime 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 20080929 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 defaultconstructed
+descriptors are guaranteed to be null.
+
+The `null_edge` operation returns a null edge for the graph. As with vertex descriptors,
+defaultconstructed 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 recomposed 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 subhiearchies 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 outedges 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 inedges 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 inedges 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 outdegree or indegree, 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 (constanttime) 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 20080929 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 pseudoconcepts /]
[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 20080929 10:44:46 EDT (Mon, 29 Sep 2008)
@@ 52,6 +52,7 @@
.programlisting,
.screen
{
+ backgroundcolor: #f5f5f5; /* whitesmoke */
fontsize: 11pt;
display: block;
margin: 1pc 4% 0pc 4%;
@@ 75,6 +76,9 @@
textalign: left;
margin: 1em 0em 0.5em 0em;
fontweight: bold;
+ border: solid;
+ padding: 0.5em;
+ backgroundcolor: #f5f5f5;
}
h1 { font: 140% }
@@ 309,6 +313,7 @@
display: block;
margin: 1pc 4% 0pc 4%;
padding: 0.5pc 0.5pc 0.5pc 0.5pc;
+ backgroundcolor: #fffff0;
}
p.blurb img
@@ 325,17 +330,18 @@
span.term
{
fontweight: bold;
 fontsize: 10pt;
+ fontsize: 11pt;
+ margin: 1pc 4% 0pc 4%;
}
div.variablelist table tbody tr td
{
 textalign: left;
+ textalign: justify;
verticalalign: top;
padding: 0em 2em 0em 0em;
fontsize: 10pt;
margin: 0em 0em 0.5em 0em;
 lineheight: 1;
+ lineheight: 1.25;
}
div.variablelist dl dt
@@ 345,15 +351,15 @@
div.variablelist dl dd
{
 margin: 0em 0em 0.5em 2em;
 fontsize: 10pt;
+ margin: 0.5em 8% 0.5em 8%;
+ fontsize: 11pt;
}
div.variablelist table tbody tr td p,
div.variablelist dl dd p
{
margin: 0em 0em 0.5em 0em;
 lineheight: 1;
+ lineheight: 1.25;
}
/*=============================================================================
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk