
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070627 13:13:59
Author: asutton
Date: 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
New Revision: 7201
URL: http://svn.boost.org/trac/boost/changeset/7201
Log:
Added a new Descriptor concept to explicitly denote the valid operations
and uses of it.
Added a bunch of templates for referencing concept documentation.
Updated docs as per comments w/Jeremy Siek.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk  2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk  26 +++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk  105 ++++++++++++++++++++++
5 files changed, 89 insertions(+), 48 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
@@ 14,7 +14,7 @@
the vertex.
[heading Refinement Of]
[link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]
+[BoostIncidenceGraph]
[heading Associated Types]
[table
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
@@ 0,0 +1,27 @@
+[/
+ / Copyright (c) 2007 Andrew Sutton
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[section Descriptor]
+The Descriptor concept describes requirements common to vertex and edge descriptors of
+all graph types.
+
+[heading Refinement Of]
+[SgiDefaultConstructible], [SgiCopyConstructible], [SgiAssignable], [SgiEqualityComparable],
+[SgiLessThanComparable], and [NoConcept Hashable].
+
+[heading Associated Types]
+There are no associated types of a Descriptor.
+
+[heading Valid Expressions]
+Beyond the requirements of the refined concepts, the descriptor does not require any
+additional valid expressions.
+
+[heading Notes]
+Note that because both vertex and edge descriptors model the [SgiLessThanComparable] concept,
+they can be used in [SgiAssociativeContainer]s like `std::map` and `std::tr1::unordered_map`.
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
@@ 63,6 +63,8 @@
Returns a special `vertex_descriptor` which does not refer to any vertex for graphs
of type `G`. Note that default initialization of `vertex_descriptors` are /not/
guaranteed to be equal to then `null_vertex()`.
+
+ *Returns* `vertex_descriptor`
]
]
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
@@ 93,8 +93,10 @@
[[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
]
+[include descriptor.qbk]
[include graph.qbk]
[include incidence_graph.qbk]
+[include bidirectional_graph.qbk]
[*TODO]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
@@ 23,6 +23,32 @@
]
[/ Templates /]
+[template NoConcept[x] [x]] [/ No public web documentation for this concept. /]
+
+[/ SGI Concept Documentation /]
+[template SgiAssignable[] [@http://www.sgi.com/tech/stl/Assignable.html Assignable]]
+[template SgiDefaultConstructible[] [@http://www.sgi.com/tech/stl/DefaultConstructible.html DefaultConstructible]]
+[template SgiCopyConstructible[] [@http://www.sgi.com/tech/stl/CopyConstructible.html CopyConstructible]]
+[template SgiEqualityComparable[] [@http://www.sgi.com/tech/stl/EqualityComparable.html EqualityComparable]]
+[template SgiLessThanComparable[] [@http://www.sgi.com/tech/stl/LessThanComparable.html LessThanComparable]]
+
+[template SgiAssociativeContainer[] [@http://www.sgi.com/tech/stl/AssociativeContainer.html AssociativeContainer]]
+
+[template SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html BidirectionalIterator]]
+[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html RandomAccessIterator]]
+
+[/ Boost Concept Documentation /]
+[template BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor Descriptor]]
+[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
+[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
+[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
+[template BoostVertexListGraph[] [link boost_graph.concepts.graph_concepts.vertex_list_graph VertexListGraph]]
+[template BoostEdgeListGraph[] [link boost_graph.concepts.graph_concepts.edge_list_graph EdgeListGraph]]
+[template BoostAdjacencyGraph[] [link boost_graph.concepts.graph_concepts.adjacency_graph AdjacencyGraph]]
+[template BoostAdjacencyMatrix[] [link boost_graph.concepts.graph_concepts.adjacency_matrix AdjacencyMatrix]]
+[template BoostMutableGraph[] [link boost_graph.concepts.graph_concepts.mutable_graph MutableGraph]]
+[template BoostPropertyGraph[] [link boost_graph.concepts.graph_concepts.property_graph PropertyGraph]]
+[template BoostMutablePropertyGraph[] [link boost_graph.concepts.graph_concepts.mutable_property_graph MutablePropertyGraph]]
[/ Contents ]
[include introduction.qbk]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk 20070627 13:13:58 EDT (Wed, 27 Jun 2007)
@@ 7,11 +7,15 @@
[section Undirected Graph]
This section provides detailed information about the `undirected_graph` class,
its associated types, member functions and nonmember interface.
+its associated types, member functions and nonmember interface. An undirected graph
+is one in which edges have no direction  this is to say that edges can be "traveled"
+in both directions. This class provides general purpose implementation of undirected
+graphs and that can be used with algorithms in the Boost Graph Library.
[h4 Notation]
The following notation is used in this documentation. The following type names
are generally meant to mean the following:
+
[table
[[Used Type] [Actual Type]]
[
@@ 54,14 +58,46 @@
[[`v`] [The value of a property (usually a template parameter)]]
]
[h4 Duplicitous Operations]
Many of the original operations in the Boost Graph library are named in accordance
with the terminology for directed graphs, specifically the use of outedges as
the canonical adjacencty list for vertices. As a result, undirected graphs also
+[h4 Descriptor and Iterator Stability]
+With the `undirected_graph` class, descriptors and iterators remain stable after
+all operations except descriptors and iterators referencing the vertices and edges
+that have been removed. Removing a vertex or edge will not invalidate descriptors
+and iterators to other vertices or edges.
+
+For example, consider the following code:
+
+ undirected_graph<> g;
+ undirected_graph<>::vertex_descriptor u = add_vertex(g);
+ undirected_graph<>::vertex_descriptor v = add_vertex(g);
+ undirected_graph<>::vertex_descriptor w = add_vertex(g);
+ remove_vertex(u);
+ add_edge(v, w, g);
+
+After running this program, the descriptor `u` will be invalid but `v` and `w` will
+still be valid so the call to `add_edge(v,w,g)` is also valid. Note that this
+property does not hold for all graph types.
+
+[h4 Vertex Indexing and Stability]
+The `undirected_graph` class provides a builtin internal properties for vertex
+types, and will provide semiautomated index management. Algorithms that use vertex
+indices generally assume that they are in the range \[0, `num_vertices(g)`). With
+the `undirected_graph` class vertex indices will be in this continuous range until
+a vertex is removed from the graph. This is the only operation that invalidates
+vertex indices, but the vertices will need to be renumbered using the
+`renumber_vertex_indices(g)` function.
+
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
+[h4 Function Names for Directed and Undirected Graphs]
+Many of the operations in the Boost Graph library are named in accordance
+with the concepts of directed graphs, specifically the use of outedges as the
+canonical adjacencty list for vertices. As a result, undirected graphs also
use the outedge terminology to refern to its incident edges, but inedge operations
are identical in behavior to outedge operations.
There are three sets of operations that have multiple names and duplicate behavior:
+There are three sets of operations that have multiple names and duplicate behaviors:
`*degree()`computing functions, `*_edge()`iterating accessors, and the `remove_*_edge()`
predicatebased functions. These functions are grouped together in their reference
sections.
@@ 77,37 +113,6 @@
for both directed and undirected graphs, it is better to use the `out_degree(g)`
function to access outedges since it is guaranteed by every other graph class.
[h4 Vertex and Edge Storage]
The `undirected` graph class has three distinct storage compontents: one for each
of vertices, edges, and incidentedges per vertex. Each of these storage components
uses a `std::list`. This is important to remember when considering the performance
of oeprations on these graphs.

Note that mutating (modifying) edge operations on a graph must operate on both
the edge list and incident edge lists. For example, adding an edge to the graph
will insert the edge or descriptors into both the edge list and the incidence
edge list of the edge's source and target.

It is important to note that the use of the term /incident edges/ in this context
generally refers to the /out/edges of a vertex. Because the graph is undirected,
every inedge is also an outedge, and so we use the term /incident/ to capture
these semantics. As a result, the `out_edges(g)`, `in_edges(g)` and `incident_edges(g)`
functions all return identical iterator ranges.

[h4 Descriptor and Iterator Stability]
With the `undirected_graph` class, descriptors and iterators remain stable after
most operations. This is to say that removing a vertex or edge will not invalidate
descriptors and iterators to other vertices or edges.

[h4 Vertex Indexing and Stability]
The `undirected_graph` class provides a builtin internal properties for vertex
types, and will provide some degree of automated index management. Algorithms
that use vertex indices generally assume that they are in the range
\[0, `num_vertices(g)`). With the `undirected_graph` class vertex indices will
be in this continuous range until a vertex is removed from the graph. This is
the only operation that invalidates vertex indices, but the vertices will need
to be renumbered using the `renumber_vertex_indices()` function.

[h4 Template Parameters]
There are only three parameters to the `undirected_graph` class.
[table
@@ 130,7 +135,12 @@
]
[h5 Model Of]
VertexAndEdgeListGraph, MutablePropertyGraph, CopyConstructible, Assignable, and Serializable.
+[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
+[BoostMutableGraph], [BoostPropertyGraph], [BoostMutablePropertyGraph].
+
+Additionally, the `undirected_graph` class provides a nonconstant time implementation
+of the [BoostAdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
+the concept.
[h5 Where Defined]
`boost/graph/undirected_graph.hpp`
@@ 146,13 +156,15 @@
[
[`graph_traits<undirected_graph>::vertex_descriptor`]
[
 The type for the vertex descriptors associated with the graph.
+ The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
+ models the following concepts: [BoostDescriptor].
]
]
[
[`graph_traits<undirected_graph>::edge_descriptor`]
[
 The type for the edge descriptors associated with the graph.
+ The type for the edge descriptors associated with the graph. The `edge_descriptor`
+ models the followign concepts: [BoostDescriptor].
]
]
]
@@ 164,35 +176,35 @@
[`graph_traits<undirected_graph>::vertex_iterator`]
[
The type for iterators returned by `vertices()`. Verex iterators are
 models of the `BidirectionalIterator` concept.
+ models of the [SgiBidirectionalIterator] concept.
]
]
[
[`graph_traits<undirected_graph>::edge_iterator`]
[
The type for iterators returned by `edges()`. Edge iterators are
 models of the `BidirectionalIterator` concept.
+ models of the [SgiBidirectionalIterator] concept.
]
]
[
[`graph_traits<undirected_graph>::out_edge_iterator`]
[
The type for iterators returned by `out_edges()`. Outedge iterators
 are models of the `BidirectionalIterator` concept.
+ are models of the [SgiBidirectionalIterator] concept.
]
]
[
[`graph_traits<undirected_graph>::in_edge_iterator`]
[
The type for iterators returned by `in_edges()`. Inedge iterators
 are models of the `BidirectionalIterator` concept.
+ are models of the [SgiBidirectionalIterator] concept.
]
]
[
[`graph_traits<undirected_graph>::adjacency_iterator`]
[
The type for iterators returned by `adjacent_vertices`. Adjacency
 iterators are models of the `BidirectionalIterator` concept.
+ iterators are models of the [SgiBidirectionalIterator] concept.
]
]
]
@@ 519,8 +531,7 @@
[
Renumbers all interior vertex indices such that each vertex has an index
in the range \[0, `num_vertices(g)`). Generally, this function needs to
 be called after removing vertices and before invoking different graph
 algorithms.
+ be called after removing vertices and before invoking graph algorithms.
]
]
[
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