|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-20 13:46:10
Author: asutton
Date: 2007-08-20 13:46:09 EDT (Mon, 20 Aug 2007)
New Revision: 38796
URL: http://svn.boost.org/trac/boost/changeset/38796
Log:
Added bew concepts for vertex-indexed and edge-indexed graphs
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_index_graph.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_index_graph.qbk (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk | 26 +++++++++++++++++---------
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk | 4 ++--
2 files changed, 19 insertions(+), 11 deletions(-)
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_index_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/edge_index_graph.qbk 2007-08-20 13:46:09 EDT (Mon, 20 Aug 2007)
@@ -0,0 +1,102 @@
+[/
+ / 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 Edge Index Graph]
+The [EdgeIndexGraph] concept requires that a graph type `G` provide edge indices
+for each edge in the graph, and that those indices are ordered in the range
+\[0, `num_edges(g)`).
+
+Because the removal of edges causes "gaps" in the index space, graphs that model
+this concept must also provide functions that allow them to re-index the edges.
+
+[heading Refinement Of]
+[MutablePropertyGraph]
+
+[heading Associated Types]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Edge Index Type]
+ [`G::edge_index_type`]
+ [An unsigned integer type]
+ [
+ The unsigned integral type representing edge indices.
+
+ *Requirements:* `T` must model the [NoConcept UnsignedIntegral] concept.
+ ]
+ ]
+ [
+ [Edge Index Property Type]
+ [
+ `property_map<G,edge_index_t>::type`
+ ]
+ [A mutable property map]
+ [
+ The type of property map through which edge indices are readable and
+ writable.
+
+ *Requirements:* This type must be a model of the [ReadWritePropertyMap]
+ concept. The `value_type` of the `property_traits` of this type must
+ be the same as `edge_index_type`.
+ ]
+ ]
+ [
+ [Edge Index Property Type]
+ [
+ `property_map<G,edge_index_t>::const_type`
+ ]
+ [ A `const` property map]
+ [
+ The type of property map through which edge indices are readable.
+
+ *Requirements:* This type must be a model of the [ReadablePropertyMap]
+ concept. The `value_type` of the `property_traits` of this type must
+ be the same as `edge_index_type`.
+ ]
+ ]
+]
+
+[heading Requirements]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Edge Index Property]
+ [`get(edge_index,g)`]
+ [
+ `property_map<G,edge_index_t>::type` or[br]
+ `property_map<G,edge_index_t>::const_type`
+ ]
+ [
+ Returns the property map that provides read/write access to the
+ edge indices of the graph.
+ ]
+ ]
+ [
+ [Edge Index]
+ [`get(edge_index,g,v)`]
+ [`G::edge_index_type`]
+ [
+ Returns the index of the given edge within the graph. This is
+ equvalent to `get(get(edge_index, g), v)`.
+
+ *Complexity:* Amortized constant.
+ ]
+ ]
+ [
+ [Renumber Edge Indices]
+ [`renumber_edge_indices(g)`]
+ []
+ [
+ Renumbers all vertices in the graph such that each edge is in the
+ range \[0, `num_vertices(g)`).
+
+ *Complexity:* Linear in `num_vertices(g)`.
+ ]
+ ]
+]
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk 2007-08-20 13:46:09 EDT (Mon, 20 Aug 2007)
@@ -104,12 +104,12 @@
[include property_graph.qbk]
[include mutable_property_graph.qbk]
-[h3 Pseudo-Concepts]
+[heading Pseudo-Concepts]
The concepts above describe the type and functional requirements of graphs. However,
these do not directly common concepts such as "directed graph" or "multigraph". As
such, there are a number of pseudo-concepts with which we can also describe graph objects.
-[h4 Directed and Undirected Graphs]
+[heading Directed and Undirected Graphs]
The interface that Boost.Graph provides for accessing and manipulating an undirected
graph is the same as the interface for directed graphs described in the following
sections, however there are some differences in the behaviour and semantics. For example,
@@ -211,7 +211,7 @@
weight\[(v,u)\] = 3.1
]
-[h4 Multigraphs]
+[heading Multigraphs]
A /multigraph/ is a graph (either directed or undirected) that has parallel edges
between vertices. The Boost.Graph types are mostly unrestrictive about the addition
of parallel edges, meaning that it is fairly easy to actually create multigraphs
@@ -221,13 +221,21 @@
Specifically, if the EdgeList and OutEdgeList of an [adjacency_list] models an
associative container, then the graph cannont be a multigraph.
-*Document this a little better*
+[heading Indexed Graphs]
+Indexed graph provide a specific property, an index, for verticese, edges or both.
+Many algorithms require vertex or edge indices for "fast" property acces, often
+declaring exterior properties as `vector`s and using the indices as random access
+iterators to access those properties. These concepts effectively require that
+indices are accessible as interior properties of the graph.
+
+These concepts are provided to help describe interface requirements for algorithms
+that allow indices to be provided as an exterior property map. With these concepts,
+requirements (and interfaces) can be written more disticntly for algorithms that accept
+indexed graphs, and those that require adaptation through exterior properties.
-[h3 Indexed Graphs]
-Although not explicitly documented (yet), there's a concept of a Vertex-Indexed graph
-that has some valid expressions related specifically to operations on vertex index
-property of the graph. The [undirected_graph] class has some addiitonal methods
-that can also be ported.
+There are two indexed graph concepts: [VertexIndexGraph] and [EdgeIndexGraph].
+[include vertex_index_graph.qbk]
+[include edge_index_graph.qbk]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/mutable_property_graph.qbk 2007-08-20 13:46:09 EDT (Mon, 20 Aug 2007)
@@ -6,11 +6,11 @@
/]
[section Mutable Property Graph]
-A MutablePropertyGraph is a [BoostMutableGraph] with properties attached internally to the
+A MutablePropertyGraph is a [MutableGraph] with properties attached internally to the
vertices and edges. When adding vertices and edges the value of the properties can be given.
[h4 Refinement Of]
-[BoostMutableGraph] and [BoostPropertyGraph]
+[MutableGraph] and [PropertyGraph]
[h4 Associated Types]
[table
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_index_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/vertex_index_graph.qbk 2007-08-20 13:46:09 EDT (Mon, 20 Aug 2007)
@@ -0,0 +1,102 @@
+[/
+ / 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 Vertex Index Graph]
+The [VertexIndexGraph] concept requires that a graph type `G` provide vertex indices
+for each vertex in the graph, and that those indices are ordered in the range
+\[0, `num_vertices(g)`).
+
+Because the removal of vertices causes "gaps" in the index space, graphs that model
+this concept must also provide functions that allow them to re-index the vertices.
+
+[heading Refinement Of]
+[MutablePropertyGraph]
+
+[heading Associated Types]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Vertex Index Type]
+ [`G::vertex_index_type`]
+ [An unsigned integer type]
+ [
+ The unsigned integral type representing vertex indices.
+
+ *Requirements:* `T` must model the [NoConcept UnsignedIntegral] concept.
+ ]
+ ]
+ [
+ [Vertex Index Property Type]
+ [
+ `property_map<G,vertex_index_t>::type`
+ ]
+ [A mutable property map]
+ [
+ The type of property map through which vertex indices are readable and
+ writable.
+
+ *Requirements:* This type must be a model of the [ReadWritePropertyMap]
+ concept. The `value_type` of the `property_traits` of this type must
+ be the same as `vertex_index_type`.
+ ]
+ ]
+ [
+ [Vertex Index Property Type]
+ [
+ `property_map<G,vertex_index_t>::const_type`
+ ]
+ [ A `const` property map]
+ [
+ The type of property map through which vertex indices are readable.
+
+ *Requirements:* This type must be a model of the [ReadablePropertyMap]
+ concept. The `value_type` of the `property_traits` of this type must
+ be the same as `vertex_index_type`.
+ ]
+ ]
+]
+
+[heading Requirements]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Vertex Index Property]
+ [`get(vertex_index,g)`]
+ [
+ `property_map<G,vertex_index_t>::type` or[br]
+ `property_map<G,vertex_index_t>::const_type`
+ ]
+ [
+ Returns the property map that provides read/write access to the
+ vertex indices of the graph.
+ ]
+ ]
+ [
+ [Vertex Index]
+ [`get(vertex_index,g,v)`]
+ [`G::vertex_index_type`]
+ [
+ Returns the index of the given vertex within the graph. This is
+ equvalent to `get(get(vertex_index, g), v)`.
+
+ *Complexity:* Amortized constant.
+ ]
+ ]
+ [
+ [Renumber Vertex Indices]
+ [`renumber_vertex_indices(g)`]
+ []
+ [
+ Renumbers all vertices in the graph such that each vertex is in the
+ range \[0, `num_vertices(g)`).
+
+ *Complexity:* Linear in `num_vertices(g)`.
+ ]
+ ]
+]
+
+[endsect]
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