|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-27 13:13:59
Author: asutton
Date: 2007-06-27 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 2007-06-27 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 2007-06-27 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 2007-06-27 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 2007-06-27 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 2007-06-27 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 2007-06-27 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 non-member interface.
+its associated types, member functions and non-member interface. An undirected graph
+is one in which edges have no direction - this is to say that edges can be "traveled"
+in both directions. This class provides general purpose implementation of undirected
+graphs and 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 out-edges 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 built-in internal properties for vertex
+types, and will provide semi-automated index management. Algorithms that use vertex
+indices generally assume that they are in the range \[0, `num_vertices(g)`). With
+the `undirected_graph` class vertex indices will be in this continuous range until
+a vertex is removed from the graph. This is the only operation that invalidates
+vertex indices, but the vertices will need to be renumbered using the
+`renumber_vertex_indices(g)` function.
+
+The `remove_vertex_and_renumber_indices(vi,g)` function can be used to autmoatically
+renumber indices after removing the vertex referenced by the given iterator. Because
+this function runs in linear time, it should not be used for repeated removals.
+
+[h4 Function Names for Directed and Undirected Graphs]
+Many of the operations in the Boost Graph library are named in accordance
+with the concepts of directed graphs, specifically the use of out-edges as the
+canonical adjacencty list for vertices. As a result, undirected graphs also
use the out-edge terminology to refern to its incident edges, but in-edge operations
are identical in behavior to out-edge operations.
-There are three sets of operations that have multiple names and duplicate behavior:
+There are three sets of operations that have multiple names and duplicate behaviors:
`*degree()`-computing functions, `*_edge()`-iterating accessors, and the `remove_*_edge()`
predicate-based functions. These functions are grouped together in their reference
sections.
@@ -77,37 +113,6 @@
for both directed and undirected graphs, it is better to use the `out_degree(g)`
function to access out-edges since it is guaranteed by every other graph class.
-[h4 Vertex and Edge Storage]
-The `undirected` graph class has three distinct storage compontents: one for each
-of vertices, edges, and incident-edges per vertex. Each of these storage components
-uses a `std::list`. This is important to remember when considering the performance
-of oeprations on these graphs.
-
-Note that mutating (modifying) edge operations on a graph must operate on both
-the edge list and incident edge lists. For example, adding an edge to the graph
-will insert the edge or descriptors into both the edge list and the incidence
-edge list of the edge's source and target.
-
-It is important to note that the use of the term /incident edges/ in this context
-generally refers to the /out/-edges of a vertex. Because the graph is undirected,
-every in-edge is also an out-edge, and so we use the term /incident/ to capture
-these semantics. As a result, the `out_edges(g)`, `in_edges(g)` and `incident_edges(g)`
-functions all return identical iterator ranges.
-
-[h4 Descriptor and Iterator Stability]
-With the `undirected_graph` class, descriptors and iterators remain stable after
-most operations. This is to say that removing a vertex or edge will not invalidate
-descriptors and iterators to other vertices or edges.
-
-[h4 Vertex Indexing and Stability]
-The `undirected_graph` class provides a built-in internal properties for vertex
-types, and will provide some degree of automated index management. Algorithms
-that use vertex indices generally assume that they are in the range
-\[0, `num_vertices(g)`). With the `undirected_graph` class vertex indices will
-be in this continuous range until a vertex is removed from the graph. This is
-the only operation that invalidates vertex indices, but the vertices will need
-to be renumbered using the `renumber_vertex_indices()` function.
-
[h4 Template Parameters]
There are only three parameters to the `undirected_graph` class.
[table
@@ -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 non-constant 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()`. Out-edge 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()`. In-edge 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.
]
]
[
Boost-Commit 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