|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-06-29 12:38:38
Author: asutton
Date: 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
New Revision: 7313
URL: http://svn.boost.org/trac/boost/changeset/7313
Log:
Added (and actually wrote) most of the visitor concepts - still missing a couple
visitors. Started writing core algorithm reference.
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/a_star_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/adjacency_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/adjacency_matrix.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dfs_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/edge_list_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/mutable_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/mutable_property_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/property_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/vertex_list_graph.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitor.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bidirectional_graph.qbk | 17 ++++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/concepts.qbk | 8 ++-
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk | 7 +-
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graph.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/graphs.qbk | 47 ++++++++++--------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk | 16 ++++-
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk | 9 +--
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/graph.qbk | 41 ++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk | 1
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk | 99 +++++++++++++++++++++------------------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk | 2
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/undirected_graph.qbk | 16 +++++-
12 files changed, 173 insertions(+), 94 deletions(-)
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/a_star_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/a_star_visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,72 @@
+[/
+ / 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 Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::vertex_descriptor`]
+ [
+ A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+ descriptors are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_descriptor`]
+ [
+ An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+ are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::directed_category`]
+ [
+ This type shall be convertible to `directed_tag` or `undirected_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_parallel_category`]
+ [
+ This describes whether the graph class allows the insertion of parallel edges
+ (multiple edges between the same source and target vertices). The two tags are
+ `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This describes the ways in which the vertices and edge of the graph can be visited.
+ The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+ `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`graph_traits<G>::null_vertex()`]
+ [
+ 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`
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/adjacency_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/adjacency_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,69 @@
+[/
+ / 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 Adjacency Graph]
+The AdjacencyGraph concept provides and interface for efficient access of the adjacent vertices
+to a vertex in a graph. This is quite similar to the IncidenceGraph concept (the target of an
+out-edge is an adjacent vertex). Both concepts are provided because in some contexts there is only
+concern for the vertices, whereas in other contexts the edges are also important.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `adjacency_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::adjacency_iterator`]
+ [
+ An adjacency iterator for a vertex v provides access to the vertices adjacent to v.
+ As such, the value type of an adjacency iterator is the vertex descriptor type of its
+ graph. An adjacency iterator must meet the requirements of [BoostMultiPassInputIterator].
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`adjacent_vertices(v,g)`]
+ [
+ Returns an iterator-range providing access to the vertices adjacent to vertex `v` in
+ the graph `g`.
+
+ *Returns* `std::pair<adjacency_iterator, adjacency_iterator>`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `adjacent_vertices(v,g)` function must return in constant time.
+
+[h4 Design Rationale]
+The AdjacencyGraph concept is somewhat frivolous since [BoostIncidenceGraph] really covers the same
+functionality (and more). The AdjacencyGraph concept exists because there are situations when
+`adjacent_vertices()` is more convenient to use than `out_edges()`. If you are constructing a graph
+class and do not want to put in the extra work of creating an adjacency iterator, have no fear. There
+is an adaptor class named `adjacency_iterator` that you can use to create an adjacency iterator out
+of an out-edge iterator.
+
+[h4 Notes]
+The case of a /multigraph/ (where multiple edges can connect the same two vertices) brings up an issue
+as to whether the iterators returned by the `adjacent_vertices()` function access a range that includes
+each adjacent vertex once, or whether it should match the behavior of the `out_edges()` function, and
+access a range that may include an adjacent vertex more than once. For now the behavior is defined to
+match that of `out_edges()`, though this decision may need to be reviewed in light of more experience
+with graph algorithm implementations.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/adjacency_matrix.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/adjacency_matrix.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,50 @@
+[/
+ / 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 Adjacency Matrix]
+The AdjacencyMatrix concept refines `Graph` concept and adds the requirement for efficient access
+to any edge in the graph given the source and target vertices. No Boost.Graph algorithms currently
+use this concept. However there are algorithms not yet implemented such as Floyd-Warshall that
+would require this concept.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `adjacency_matrix_tag`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`edge(u,v,g)`]
+ [
+ Returns a pair consisting of a flag saying whether there exists an edge between `u` and
+ `v` in graph g, and consisting of the edge descriptor if the edge was found.
+
+ *Returns* `std::pair<edge_iterator, bool>`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `edge(u,v,g)` function must return in constant time.
+
+[h4 Notes]
+A number of graph classes (notably [boost_undirected_graph], [boost_directed_graph] and
+[boost_adjacency_list]) provide non-constant time implementations of this interface. Although
+the function exists, none of these classes are documented as modeling this concept.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bellman_ford_visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,72 @@
+[/
+ / 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 Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::vertex_descriptor`]
+ [
+ A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+ descriptors are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_descriptor`]
+ [
+ An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+ are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::directed_category`]
+ [
+ This type shall be convertible to `directed_tag` or `undirected_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_parallel_category`]
+ [
+ This describes whether the graph class allows the insertion of parallel edges
+ (multiple edges between the same source and target vertices). The two tags are
+ `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This describes the ways in which the vertices and edge of the graph can be visited.
+ The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+ `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`graph_traits<G>::null_vertex()`]
+ [
+ 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`
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/bfs_visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,105 @@
+[/
+ / 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 Breadth-First Search Visitor]
+This concept defines the visitor interface for [booost_breadth_first_search] algorithm. Users
+can define a class with the BFS Visitor interface and pass and object of the class to
+[boost_breadth_first_search], thereby augmenting the actions taken during the graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis.initialize_vertex(v,g)`]
+ [
+ This is invoked on every vertex of the graph before the start of the graph search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.discover_vertex(v,g)`]
+ [
+ This is invoked when a vertex is encountered for the first time.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_vertex(v,g)`]
+ [
+ This is invoked on a vertex as it is popped from the queue. This happens immediately
+ before `examine_edge(v,g)` s invoked on each of the out-edges of vertex `u`.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_edge(e,g)`]
+ [
+ This is invoked on every out-edge of each vertex after it is discovered.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.tree_edge(e,g)`]
+ [
+ This is invoked on each edge as it becomes a member of the eges that the form the
+ search tree.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.non_tree_edge(v,g)`]
+ [
+ This is invoked on back or cross edges for directed graphs and cross edges
+ for undirected graphs.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.gray_target(e,g)`]
+ [
+ This is invoked on the subset of non-tree-edges who's target vertex is colored gray
+ at the time of examination. The color gray indicates that the vertex is currently
+ in the queue.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.black_target(v,g)`]
+ [
+ This is invoked on the subset of non-tree edges who's target vertex is colored black
+ at the time of examination. The color black indicates that the vertex has been removed
+ from the queue.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.finish_vertex(v,g)`]
+ [
+ This is invoked on a vertex after all of its out edges have been added to the search
+ tree and all of the adjacenct vertices have been discovered, but before the out-edges
+ of the adjacent vertices have been examined.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_bfs_visitor]
+
+[endsect]
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-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -16,7 +16,7 @@
[heading Refinement Of]
[BoostIncidenceGraph]
-[heading Associated Types]
+[h4 Associated Types]
[table
[[Type] [Description]]
[
@@ -35,7 +35,7 @@
]
]
-[heading Valid Expressions]
+[h4 Valid Expressions]
[table
[[Expression] [Description]]
[
@@ -60,4 +60,17 @@
]
]
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list] with the `Directed` template parameter as `bidirectionalS` or
+`undirectedS`.
+
+[h4 Complexity Guarantees]
+The `in_edges(g)` function is required to return in constant time.
+
+The `in_degree()` and `degree()` functions must be linear in the number of in-edges (for
+directed graph) or incident edges (for undirected graphs).
+
+
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/concepts.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -14,7 +14,7 @@
[table
[[Object] [Type]]
- [[G] [A type that is a model of a Graph (or refinement)]]
+ [[G] [A type that is a model of a [BoostGraph] (or refinement thereof)]]
[[g] [An object of type G]]
[[u,v] [Objects of type `graph_traits<G>::vertex_descriptor`]]
[[e] [An object of type `graph_traits<G>::edge_descriptor`]]
@@ -22,10 +22,12 @@
[[ei] [An object of type `graph_traits<G>::edge_iterator`]]
[[vp] [An object of type `G::vertex_property_type`]]
[[ep] [An object of type `G::edge_property_type`]]
- [[Property] [A type used to specify a vertex or edge property]]
+ [[Property] [A type used to specify a vertex or edge property. Also called a /tag/.]]
[[p] [An object of type Property]]
[[Predicate] [A function that, given an argument, returns true or false]]
- [[pred] [An object of type Predicate]]
+ [[pred] [An object of type [SgiPredicate]]]
+ [[V] [A type that is a model of a [BoostVisitor] (or refinement thereof)]]
+ [[vis] [An object of type V]]
]
[include graphs.qbk]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/descriptor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -11,7 +11,7 @@
[heading Refinement Of]
[SgiDefaultConstructible], [SgiCopyConstructible], [SgiAssignable], [SgiEqualityComparable],
-[SgiLessThanComparable], and [NoConcept Hashable].
+and [SgiLessThanComparable].
[heading Associated Types]
There are no associated types of a Descriptor.
@@ -21,7 +21,8 @@
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`.
+Note that because both model the [SgiLessThanComparable] concept, they can be used as
+keys in any associative container modeling the [SgiAssociativeContainer] concepte
+(e.g., `std::map`, `std::set`, etc).
[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dfs_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dfs_visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,99 @@
+[/
+ / 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 Depth-First Search Visitor]
+This concept defines the visitor interface for [booost_depth_first_search] algorithm. Users
+can define a class with the DFS Visitor interface and pass and object of the class to
+[boost_depth_first_search], thereby augmenting the actions taken during the graph search.
+
+[h4 Refinement Of]
+[BoostVisitor]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vis.initialize_vertex(v,g)`]
+ [
+ This is invoked on every vertex of the graph before the start of the graph search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.start_vertex(v,g)`]
+ [
+ This is invoked on the source veretx once before the start of the search.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.discover_vertex(v,g)`]
+ [
+ This is invoked when a vertex is encountered for the first time.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_edge(e,g)`]
+ [
+ This is invoked on every out-edge of each vertex after it is discovered.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.tree_edge(e,g)`]
+ [
+ This is invoked on each edge as it becomes a member of the eges that the form the
+ search tree.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.back_edge(v,g)`]
+ [
+ This is invoked on the back edges of the graph. For an unidrected graph there
+ is some ambiguity between tree edges and back edges since the edge /(u,v)/
+ and /(v,u)/ are the same edge, but both `tree_edge(v,g)` and `back_edge(v,g)`
+ will be invoked. One way to resolve this ambiguity is to record the tree
+ edges and then disregard the back edges that are already marked as tree edges.
+ An easy way to record tree edges is to record predecessors at the `tree_edge`
+ event point.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.forward_or_cross_edge(e,g)`]
+ [
+ This is invoked on forward or cross edges in the graph. In an undirected graph,
+ this method is never called.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.finish_vertex(v,g)`]
+ [
+ This is invoked on a vertex after all `finish_vertex(x,g)` has been invoked for
+ all vertices in the search tree rooted at `v` (i.e., after all its children
+ have finished). If `v` is a leaf in the search tree, `finish_vertex(v,g)` is
+ called after all its out-edges have been examined.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_dfs_visitor]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/dijkstra_visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,72 @@
+[/
+ / 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 Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::vertex_descriptor`]
+ [
+ A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+ descriptors are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_descriptor`]
+ [
+ An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+ are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::directed_category`]
+ [
+ This type shall be convertible to `directed_tag` or `undirected_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_parallel_category`]
+ [
+ This describes whether the graph class allows the insertion of parallel edges
+ (multiple edges between the same source and target vertices). The two tags are
+ `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This describes the ways in which the vertices and edge of the graph can be visited.
+ The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+ `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`graph_traits<G>::null_vertex()`]
+ [
+ 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`
+ ]
+ ]
+]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/edge_list_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/edge_list_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,98 @@
+[/
+ / 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 List Graph]
+The EdgeListGraph concept refines the [BoostGraph] concept, and adds the requirement
+for efficient access to all the edges in a graph.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `edge_list_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_iterator`]
+ [
+ An edge iterator (obtained via edges(g)) provides access to all of the edges
+ in a graph. An edge iterator type must meet the requirements of
+ [BoostMultiPassInputIterator]. The value type of the edge iterator must be the
+ same as the edge descriptor of the graph.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edges_size_type`]
+ [
+ The unsigned integer type used to represent the number of edges in the graph.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`edges(g)`]
+ [
+ Returns an iterator range providing access to all the edges in the graph `g`.
+
+ *Returns* `std::pair<edge_iterator, edge_iterator>`
+ ]
+ ]
+ [
+ [`num_edges(g)`]
+ [
+ Returns the number of edges in the graph `g`.
+
+ *Returns* `edges_size_type`
+ ]
+ ]
+ [
+ [`source(e,g)`]
+ [
+ If `e` is an edge /(u,v)/ in `g`, this function returns the source vertex `u`.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+ [
+ [`target(e,g)`]
+ [
+ If `e` is an edge /(u,v)/ in `g`, this function returns the target vertex `v`.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+]
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list]
+* [boost_edge_list]
+
+[h4 Complexity Guarantees]
+The `edges(g)`, `source(e,g)`, and `target(e,g)` functions must return in constant time.
+
+[h4 Design Rationale]
+One issue in the design of this concept is whether to include the refinement from the
+[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+of a graph is orthogonal to traversing out-edges, so it would make sense to have a edgeListGraph
+concept that only includes edge traversal. However, such a concept would no longer really be a
+graph, but would just be a set, and the STL already has concepts for dealing with such things.
+However, there are many BGL algorithms that need to traverse the vertices and out-edges of a graph,
+so for convenience a concept is needed that groups these requirements together, hence the edgeListGraph
+concept.
+
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/event_visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,72 @@
+[/
+ / 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 Graph]
+The Graph concept contains a few requirements that are common to all the graph concepts.
+These include some associated types for vertex_descriptor, edge_descriptor, etc. One
+should note that a model of Graph is not required to be a model of Assignable, so algorithms
+should pass graph objects by reference (or `const` reference).
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::vertex_descriptor`]
+ [
+ A vertex descriptor corresponds to a unique vertex in a graph. A vertex descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Vertex
+ descriptors are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_descriptor`]
+ [
+ An edge descriptor corresponds to a unqie edge /(u,v)/ in a graph. An edge descriptor
+ must be DefaultConstructible, Assignable, and EqualityComparable. Edge descriptors
+ are almost always passed by value.
+ ]
+ ]
+ [
+ [`graph_traits<G>::directed_category`]
+ [
+ This type shall be convertible to `directed_tag` or `undirected_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_parallel_category`]
+ [
+ This describes whether the graph class allows the insertion of parallel edges
+ (multiple edges between the same source and target vertices). The two tags are
+ `allow_parallel_edge_tag` and `disallow_parallel_edge_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This describes the ways in which the vertices and edge of the graph can be visited.
+ The choices are `incidence_graph_tag`, `adjacency_graph_tag`, `bidirectional_graph_tag`,
+ `vertex_list_graph_tag`, `edge_list_graph_tag`, and `adjacency_matrix_tag`.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`graph_traits<G>::null_vertex()`]
+ [
+ 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`
+ ]
+ ]
+]
+
+[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-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -11,7 +11,7 @@
should note that a model of Graph is not required to be a model of Assignable, so algorithms
should pass graph objects by reference (or `const` reference).
-[heading Associated Types]
+[h4 Associated Types]
[table
[[Type] [Description]]
[
@@ -54,7 +54,7 @@
]
]
-[heading Valid Expressions]
+[h4 Valid Expressions]
[table
[[Expression] [Description]]
[
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-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -35,42 +35,42 @@
[table
[[Expression] [Return Type or Description]]
- [[[link boost_graph.concepts.graph_concepts.graph *Graph*]]]
+ [[*[BoostGraph]*]]
[[`graph_traits<G>::vertex_descriptor`] [The type for vertex representative objects.]]
[[`graph_traits<G>::edge_descriptor`] [The type for edge representative objects.]]
[[`graph_traits<G>::directed_category`] [Graph is directed or undirected?]]
[[`graph_traits<G>::edge_parallel_category`] [Graph allows parallel edges?]]
[[`graph_traits<G>::traversal_category`] [The ways in which the vertices and edges can be traversed.]]
- [[[link boost_graph.concepts.graph_concepts.incidence_graph *Incidence Graph*] refines Graph]]
+ [[*[BoostIncidenceGraph]* refines Graph]]
[[`graph_traits<G>::degree_size_type`] [The integer type for vertex degree.]]
[[`graph_traits<G>::out_edge_iterator`] [Type for iterating over out edges.]]
[[`out_edges(v,g)`] [`std::pair<out_edge_iterator, out_edge_iterator>`]]
[[`out_degree(v,g)`] [`degree_size_type`]]
[[`source(e,g)`] [`vertex_descriptor`]]
[[`target(e,g)`] [`vertex_descriptor`]]
- [[[link boost_graph.concepts.graph_concepts.bidirectional_graph *Bidirectional Graph*] refines IncidenceGraph]]
+ [[*[BoostBidirectional Graph]* refines IncidenceGraph]]
[[`graph_traits<G>::in_edge_iterator`] [Type for iterating over in edges.]]
[[`in_edges(v,g)`] [`std::pair<in_edge_iterator,in_edge_iterator>`]]
[[`in_degree(v,g)`] [`degree_size_type`]]
[[`degree(v,g)`] [`degree_size_type`]]
- [[*AdjacencyGraph* refines Graph]]
+ [[*[BoostAdjacencyGraph]* refines Graph]]
[[`graph_traits<G>::adjacency_iterator`] [Type for iterating over adjacent vertices.]]
[[`adjacent_vertices(v,g)`] [`std::pair<adjacency_iterator,adjacency_iterator>`]]
- [[*VertexListGraph* refines IncidenceGraph and AdjacencyGraph]]
+ [[*[BoostVertexListGraph]* refines Graph]]
[[`graph_traits<G>::vertex_iterator`] [Type for iterating over vertices.]]
[[`graph_traits<G>::vertices_size_type`] [Unsigned integer type for the number of vertices.]]
[[`vertices(g)`] [`std::pair<vertex_iterator,vertex_iterator>`]]
[[`num_vertices(g)`] [`vertices_size_type`]]
- [[*EdgeListGraph* refines Graph]]
+ [[*[BoostEdgeListGraph]* refines Graph]]
[[`graph_traits<G>::edge_iterator`] [Type for iterating over edges.]]
[[`graph_traits<G>::edges_size_type`] [Unsigned integer type for the number of edges.]]
[[`edges(g)`] [`std::pair<edge_iterator, edge_iterator>`]]
[[`num_edges(g)`] [`edges_size_type`]]
[[`source(e,g)`] [`vertex_descriptor`]]
[[`target(e,g)`] [`vertex_descriptor`]]
- [[*AdjacencyMatrix* refines Graph]]
+ [[*[BoostAdjacencyMatrix]* refines Graph]]
[[`edge(u,v,g)`] [`std::pair<edge_descriptor,boo>`]]
- [[*MutableGraph* refines Graph]]
+ [[*[BoostMutableGraph]* refines Graph]]
[[`add_vertex(g)`] [`vertex_descriptor`]]
[[`clear_vertex(v,g)`] [`void`]]
[[`clear_out_edges(v,g)`] [`void`]]
@@ -82,31 +82,34 @@
[[`remove_edge_if(pred,g)`] [`void`]]
[[`remove_out_edge_if(v,pred,g)`] [`void`]]
[[`remove_in_edge_if(v,pred,g)`] [`void`]]
- [[*MutablePropertyGraph* refines Graph]]
- [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
- [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
- [[*PropertyGraph* refines Graph]]
+ [[*[BoostPropertyGraph]* refines Graph]]
[[`property_map<G,Property>::type`] [Type for a mutable property map.]]
[[`property_map<G,Property>::const_type`] [Type for a non-mutable property map.]]
[[`get(p,g)`] [Function to get a property map.]]
[[`get(p,g,x)`] [Get the property value for vertex or edge `x`]]
[[`put(p,g,x,v`)] [Set the property value for vertex or edge `x` to value `v`.]]
+ [[*[BoostMutablePropertyGraph]* refines Graph]]
+ [[`add_vertex(vp,g)`] [`vertex_descriptor`]]
+ [[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
]
[include descriptor.qbk]
[include graph.qbk]
[include incidence_graph.qbk]
[include bidirectional_graph.qbk]
-
-[*TODO]
-
-There are some functions missing like `get_property()` and `put/set_property()`.
-These occur in some documentation somewhere but are in no means pervasive, complete
-or accurate.
-
-It should also be worth pointing out that we can redefine the entire concept hierarchy
-based on a) vertex or edge operations, b) directed/undirected or c) simple or multigraphs.
-Basically, there are some interesting ways to conceptualize the Boost.Graph interface.
+[include adjacency_graph.qbk]
+[include vertex_list_graph.qbk]
+[include edge_list_graph.qbk]
+[include adjacency_matrix.qbk]
+[include mutable_graph.qbk]
+[include property_graph.qbk]
+[include mutable_property_graph.qbk]
+
+[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 [boost_undirected_graph] class has some addiitonal methods
+that can also be ported.
[h3 Undirected Graphs]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/incidence_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -10,10 +10,10 @@
(for directed graphs) or incident edges (for undirected graphs) of each vertex in
the graph.
-[heading Refinement Of]
-[link boost_graph.concepts.graph_concepts.graph Graph]
+[h4 Refinement Of]
+[BootGraph]
-[heading Associated Types]
+[h4 Associated Types]
[table
[[Type] [Description]]
[
@@ -41,7 +41,7 @@
]
]
-[heading Valid Expressions]
+[h4 Valid Expressions]
[table
[[Expression] [Description]]
[
@@ -84,4 +84,12 @@
]
]
+[h4 Notes]
+For undirected graphs, the edge /(u,v)/ is the same as edge /(v,u)/, so without some extra
+guarantee an implementation would be free use any ordering for the pair of vertices in an
+out-edge. For example, if you call `out_edges(u, g)`, and `v` is one of the vertices adjacent
+to `u`, then the implementation would be free to return /(v,u)/ as an out-edge which would be
+non-intuitive and cause trouble for algorithms. Therefore, the extra requirement is added that
+the out-edge connecting `u` and `v` must be given as /(u,v)/ and not /(v,u)/.
+
[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/mutable_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/mutable_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,174 @@
+[/
+ / 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 Mutable Graph]
+A MutableGraph can be changed via the addition or removal of edges and vertices.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`add_edge(u,v,g)`]
+ [
+ Add a new vertex to the graph. The `vertex_descriptor` for the new vertex is returned.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+ [
+ [`clear_vertex(v,g)`]
+ [
+ Removes all edges incident (both in-edges and out-edges for directed graphs) to the
+ vertex `v`.
+
+ *Returns* `void`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+ *Postcondition* `u` does not appear as a source or target of any edge in `g`.
+ ]
+ ]
+ [
+ [`clear_out_edges(v,g)`]
+ [
+ Removes all edges out-edges of the vertex `v`. For undirected graphs this is functionally
+ equivalent to `clear_vertex(v,g)`.
+
+ *Returns* `void`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+ *Postcondition* `u` does not appear as a source of any edge in `g`.
+ ]
+ ]
+ [
+ [`clear_in_edges(v,g)`]
+ [
+ Removes all edges in-edges of the vertex `v`. For undirected graphs this is functionally
+ equivalent to `clear_vertex(v,g)`.
+
+ *Returns* `void`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g`.
+
+ *Postcondition* `u` does not appear as a target of any edge in `g`.
+ ]
+ ]
+ [
+ [`remove_vertex(v,g)`]
+ [
+ Remove the vertex `v` from the vertex set of the graph. Note that undefined behavior may
+ result if there are edges remaining in the graph who's target is `u`. The `clear_vertex(v,g)`
+ function should be called first to ensure the preconditions.
+
+ *Returns* `vertex_descriptor`
+
+ *Precondition* `u` is a valid `vertex_descriptor` in `g` and does not appear as the source
+ or target of any edge in `g`.
+
+ *Postcondition* `u` is not longer in the vertex set of `g`, nor is `u` a valid descriptor.
+ ]
+ ]
+ [
+ [`add_edge(u,v,g)`]
+ [
+ Inserts the edge /(u,v)/ into the graph, and returns an edge descriptor pointing to the new edge.
+ If the graph disallows parallel edges, and the edge /(u,v)/ is already in the graph, then the boolean
+ flag returned is false and the returned edge descriptor points to the already existing edge. Note
+ that for undirected graphs, /(u,v)/ is the same edge as /(v,u)/, so after a call to the function
+ `add_edge(u,v,g)`, this implies that edge /(u,v)/ will appear in the out-edges of `u` and /(u,v)/
+ (or equivalently /(v,u)/) will appear in the out-edges of `v`. Put another way, `v` will be adjacent
+ to `u` and `u` will be adjacent to `v`.
+
+ *Returns* `vertex_descriptor`
+
+ *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+ *Postcondition* The returned `edge_descriptor` points to a valid edge in `g`.
+ ]
+ ]
+ [
+ [`remove_edge(u,v,g)`]
+ [
+ Remove the edge (u,v) from the graph. If the graph allows parallel edges this remove all occurrences
+ of /(u,v)/.
+
+ *Returns* `void`
+
+ *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+ *Postcondition* The edge /(u,v)/ is no longer in the edge set of `g`.
+ ]
+ ]
+ [
+ [`remove_edge(e,g)`]
+ [
+ Remove the edge `e` from the graph.
+
+ *Returns* `void`
+
+ *Precondition* `e` is an edge in the graph.
+
+ *Postcondition* The edge `e` is no longer in the edge set of `g`.
+ ]
+ ]
+ [
+ [`remove_edge(ei,g)`]
+ [
+ Remove the edge pointed to by the edge iterator `ei` from the graph. This expression is only required
+ when `g` also models [BoostIncidenceGraph].
+
+ *Returns* `void`
+
+ *Precondition* `*ei` is an edge in the graph.
+
+ *Postcondition* The edge `*ei` is no longer in the edge set of `g`.
+ ]
+ ]
+ [
+ [`remove_edge_if(pred,g)`]
+ [
+ Remove all edges from the graph `g` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`remove_out_edge_if(v,pred,g)`]
+ [
+ Remove all out-edges of the vertex `v` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`remove_in_edge_if(v,pred,g)`]
+ [
+ Remove all in-edges of the vertex `v` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+* Vertex insertion is guaranteed to be amortized constant time.
+* Clearing avertex is /O(E + V)/.
+* Vertex removal is /O(E + V)/.
+* Edge insertion must be either amortized constant time of it can be /O(log(E/V))/ if the insertion checks
+to prevent the addition of parallel edges (which is a "feature" of some graph types).
+* Edge removal is guaranteed to be /O(E)/.
+
+[h4 Models]
+* [boost_undirected_graph]
+* [boost_directed_graph]
+* [boost_adjacency_list]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/mutable_property_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/mutable_property_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,64 @@
+[/
+ / 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 Mutable Property Graph]
+A MutablePropertyGraph is a [BoostMutableGraph] 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]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::vertex_property_type`]
+ [
+ The property type associated with vertices in the graph `G`. This type is not
+ guaranteed to be the same as the `VertexProperties` template parameter.
+ ]
+ ]
+ [
+ [`graph_traits<G>::edge_property_type`]
+ [
+ The property type associated with edges in the graph `G`. This type is not
+ guaranteed to be the same as the `EdgeProperties` template parameter.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`add_vertex(vp,g)`]
+ [
+ Add a new vertex to the graph and copy vertex properties `vp` into the property
+ for the new vertex. The `vertex_descriptor` is returned.
+
+ *Returns* `vertex_descriptor`
+ ]
+ ]
+ [
+ [`add_edge(u,v,ep,g)`]
+ [
+ Inserts the edge /(u,v)/ into the graph, and copies object `ep` into the property
+ for that edge.
+
+ *Returns* `property_traits<property_map<G,Property>::const_type>::value_type`
+
+ *Precondition* `u` and `v` are valid vertex descriptors in `g`.
+
+ *Postcondition* The returned `edge_descriptor` points to a valid edge in `g`.
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `get(p,g)` function must return in constant time.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/property_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/property_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,86 @@
+[/
+ / 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 Property Graph]
+A PropertyGraph is a graph that has some property associated with each of the vertices or edges
+in the graph. As a given graph may have several properties associated with each vertex or edge,
+a /tag/ is used to identity which property is being accessed. The graph provides a function which
+returns a property map object and also the value corresponding to a vertex or edge and its
+indicated property.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`property_map<G, Property>::type`]
+ [
+ The type of the property map for the property specified by `Property`. This type must
+ be a model of [BoostReadWritePropertyMap] with a key type the same as the graph's
+ `vertex_descriptor` or `edge_descriptor` types.
+ ]
+ ]
+ [
+ [`property_map<G, Property>::const_type`]
+ [
+ The type of the property map for the property specified by `Property`. This type must
+ be a model of [BoostReadablePropertyMap] with a key type the same as the graph\'s
+ `vertex_descriptor` or `edge_descriptor` types.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`get(p,g)`]
+ [
+ Returns the property map specified by the property identified by the tag `p`. The parameter
+ `p` is only used to convey type information and has no value.
+
+ *Returns* `property_map<G,Property>::type` if `g` is mutable and
+ `property_map<G,Property>::const_type` otherwise.
+ ]
+ ]
+ [
+ [`get(p,g,x)`]
+ [
+ Returns the property /value/ specified by the type of property tag `p` for the given
+ vertex or edge descriptor `x`. The object `p` is only used to convey type information
+ and has no value. This function is equivalent to `get(get(p,g),x)`.
+
+ *Returns* `property_traits<property_map<G,Property>::const_type>::value_type`
+ ]
+ ]
+ [
+ [`put(p,g,x,v)`]
+ [
+ Set the property /value/ specified by the type of property tag `p` for the given
+ vertex or edge descriptor `x` to the value `v`. The object `p` is only used to
+ convey type information and has no value.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`out_degree(v,g)`]
+ [
+ Returns the number of out-edges (for directed graphs) or the number of incident
+ edges (for undirected graphs) of the vertex `v`.
+
+ *Returns* `degree_size_type`.
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `get(p,g)` function must return in constant time.
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/vertex_list_graph.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/vertex_list_graph.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,75 @@
+[/
+ / 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 List Graph]
+The VertexListGraph concept refines the [BoostGraph] concept, and adds the requirement
+for efficient traversal of all the vertices in a graph.
+
+[h4 Refinement Of]
+[BoostGraph]
+
+[h4 Associated Types]
+[table
+ [[Type] [Description]]
+ [
+ [`graph_traits<G>::traversal_category`]
+ [
+ This tag type must be convertible to `vertex_list_graph_tag`.
+ ]
+ ]
+ [
+ [`graph_traits<G>::vertex_iterator`]
+ [
+ A vertex iterator (obtained via vertices(g)) provides access to all of the vertices in
+ a graph. A vertex iterator type must meet the requirements of [BoostMultiPassInputIterator].
+ The value type of the vertex iterator must be the vertex descriptor of the graph.
+ ]
+ ]
+ [
+ [`graph_traits<G>::vertices_size_type`]
+ [
+ The unsigned integer type used to represent the number of vertices in the graph.
+ ]
+ ]
+]
+
+[h4 Valid Expressions]
+[table
+ [[Expression] [Description]]
+ [
+ [`vertices(g)`]
+ [
+ Returns an iterator range providing access to all the vertices in the graph `g`.
+
+ *Returns* `std::pair<vertex_iterator, vertex_iterator>`
+ ]
+ ]
+ [
+ [`num_vertices(g)`]
+ [
+ Returns the number of vertices in the graph `g`.
+
+ *Returns* `vertices_size_type`
+ ]
+ ]
+]
+
+[h4 Complexity Guarantees]
+The `vertices(g)` function must return in constant time.
+
+[h4 Design Rationale]
+One issue in the design of this concept is whether to include the refinement from the
+[BoostIncidenceGraph] and [BoostAdjacencyGraph] concepts. The ability to traverse the vertices
+of a graph is orthogonal to traversing out-edges, so it would make sense to have a VertexListGraph
+concept that only includes vertex traversal. However, such a concept would no longer really be a
+graph, but would just be a set, and the STL already has concepts for dealing with such things.
+However, there are many BGL algorithms that need to traverse the vertices and out-edges of a graph,
+so for convenience a concept is needed that groups these requirements together, hence the VertexListGraph
+concept.
+
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitor.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitor.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,20 @@
+[/
+ / 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 Visitor]
+This concept defines the basic requirements of all visitor concepts in the Boost.Graph
+library.
+
+[h4 Refinement Of]
+[SgiCopyConstructible]
+
+[h4 Design Rationale]
+This concpet is provided primarily as a base concept for its refinements. Its sole purpose
+is to require that instances of concepts be copy-constructible, which is how they are
+passed to different graph algorithms.
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/concepts/visitors.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -16,11 +16,8 @@
algorithm has a different set of event points, which are described by the following
visitor concepts:
-* BFS Visitor
-* DFS Visitor
-* Dijkstra Visitor
-* Bellman Ford Visitor
-* A* Visitor
-* Event Visitor
+[include visitor.qbk]
+[include bfs_visitor.qbk]
+[include dfs_visitor.qbk]
[endsect]
\ No newline at end of file
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-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -23,7 +23,11 @@
]
[/ Templates /]
-[template NoConcept[x] [x]] [/ No public web documentation for this concept. /]
+[template super[x] '''<superscript>'''[x]'''</superscript>''']
+[template sub[x] '''<subscript>'''[x]'''</subscripts>''']
+
+[/ Missing documentation /]
+[template NoConcept[x] [x]]
[/ SGI Concept Documentation /]
[template SgiAssignable[] [@http://www.sgi.com/tech/stl/Assignable.html Assignable]]
@@ -32,12 +36,31 @@
[template SgiEqualityComparable[] [@http://www.sgi.com/tech/stl/EqualityComparable.html EqualityComparable]]
[template SgiLessThanComparable[] [@http://www.sgi.com/tech/stl/LessThanComparable.html LessThanComparable]]
+[template SgiContainer[] [@http://www.sgi.com/tech/stl/Container.html Container]]
+[template SgiForwardContainer[] [@http://www.sgi.com/tech/stl/ForwardContainer.html ForwardContainer]]
+[template SgiReversibleContainer[] [@http://www.sgi.com/tech/stl/ReversibleContainer.html ReversibleContainer]]
+[template SgiRandomAccessContainer[] [@http://www.sgi.com/tech/stl/RandomAccessContainer.html RandomAccessContainer]]
+
+[template SgiSequence[] [@http://www.sgi.com/tech/stl/Sequence.html Sequence]]
+[template SgiFrontInsertionSequence[] [@http://www.sgi.com/tech/stl/FrontInsertionSequence.html FrontInsertionSequence]]
+[template SgiBackInsertionSequence[] [@http://www.sgi.com/tech/stl/BackInsertionSequence.html BackInsertionSequence]]
+
[template SgiAssociativeContainer[] [@http://www.sgi.com/tech/stl/AssociativeContainer.html AssociativeContainer]]
+[template SgiSortedAssociativeContainer[] [@http://www.sgi.com/tech/stl/SortedAssociativeContainer.html SortedAssociativeContainer]]
+[template SgiHashedAssociativeContainer[] [@http://www.sgi.com/tech/stl/HashedAssociativeContainer.html HashedAssociativeContainer]]
[template SgiBidirectionalIterator[] [@http://www.sgi.com/tech/stl/BidirectionalIterator.html BidirectionalIterator]]
[template SgiRandomAccessIterator[] [@http://www.sgi.com/tech/stl/RandomAccessIterator.html RandomAccessIterator]]
+[template SgPredicate[] [@http://www.sgi.com/tech/stl/Predicate.html Predicate]]
+
+
[/ Boost Concept Documentation /]
+[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
+
+[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
+[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
+
[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]]
@@ -50,6 +73,22 @@
[template BoostPropertyGraph[] [link boost_graph.concepts.graph_concepts.property_graph PropertyGraph]]
[template BoostMutablePropertyGraph[] [link boost_graph.concepts.graph_concepts.mutable_property_graph MutablePropertyGraph]]
+[template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
+[template BoostBFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
+[template BoostDFSVisitor[] [link boost_graph.concepts.visitor_concepts.depth_first_search_visitor DepthFirstSearchVisitor]]
+
+[/ Boost Reference Documentation]
+[template boost_undirected_graph[] [link boost_graph.reference_guide.graph_types.undirected_graph `undirected_graph`]]
+[template boost_directed_graph[] [link boost_graph.reference_guide.graph_types.directed_graph `directed_graph`]]
+[template boost_adjacency_list[] [link boost_graph.reference_guide.graph_types.adjacency_list `adjacecncy_list`]]
+[template boost_edge_list[] [link boost_graph.reference_guide.graph_types.edge_list `edge_list`]]
+
+[template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor `bfs_visitor`]]
+[template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor `dfs_visitor`]]
+
+[template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search `breadth_first_search()`]]
+[template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search `depth_first_search()`]]
+
[/ Contents ]
[include introduction.qbk]
[include history.qbk]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/breadth_first_search.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,153 @@
+[/
+ / 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 Breadth-First Search]
+ template <class Graph, class P, class T, class R>
+ void
+ breadth_first_search(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+ template <class Graph, class Buffer, class Visitor, class P, class T, class R>
+ void
+ breadth_first_search(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ Buffer& q,
+ Visitor v,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+The `breadth_first_search()` function performs a breadth-first traversal \[49\] of a directed or
+undirected graph. A breadth-first traversal visits vertices that are closer to the source before
+visiting vertices that are further away. In this context "distance" is defined as the number of edges
+in the shortest path from the source vertex. The `breadth_first_search()` function can be used to
+compute the shortest path from the source to all reachable vertices and the resulting shortest-path
+distances. For more definitions related to BFS, see section Breadth-First Search.
+
+BFS uses two data structures to to implement the traversal: a color marker for each vertex and
+a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered
+adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray
+vertices. The algorithm proceeds by removing a vertex /u/ from the queue and examining each out-edge
+/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
+queue. After all of the out-edges are examined, vertex u is colored black and the process is
+repeated. Pseudo-code for the BFS algorithm is a listed below.
+
+[pre
+BFS(G, s)
+ for each vertex u in V\[G\] initialize vertex u
+ color\[u\] := WHITE
+ d\[u\] := infinity
+ p\[u\] := u
+ end for
+
+ color\[s\] := GRAY
+ d\[s\] := 0
+ ENQUEUE(Q, s) discover vertex s
+
+ while not EMPTY(Q)
+ u := DEQUEUE(Q) examine vertex u
+ for each vertex v in adj\[u\] examine edge /(u,v)/
+ if(color\[v\] = WHITE) /(u,v)/ is a tree edge
+ color\[v\] := GRAY
+ d\[v\] := d\[u\] + 1
+ p\[v\] := u
+ ENQUEUE(Q, v) discover vertex v
+ else /(u,v)/ is a non-tree edge
+ if (color\[v\] = GRAY) /(u,v)/ has a gray target
+ ...
+ else /(u,v)/ has a black target
+ ...
+ end if
+ end for
+ color\[u\] := BLACK finsih vertex u
+ end while
+ return (d, p)
+]
+
+[heading Where Defined]
+`boost/graph/breadth_first_search.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`Graph& g`]
+ [
+ A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
+ and [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [in] [`vertex_descriptor s`]
+ [
+ The source vertex where the search is started. This must be a valid vertex descriptor of
+ `g`.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`visitor(Visitor vis)`]
+ [
+ A visitor object that is inovked inside the algorithm at event points specified by the
+ [BoostBFSVisitor]. The `vis` object must be model the [BoostBFSVisitor] concept.
+
+ *Default* `bfs_visitor<null_visitor>`.
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VeretxIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [util] [`buffer(Buffer& q)`]
+ [
+ The queue used to determine the order in which vertices will be discovered.
+ If a FIFO queue is used, then the traversal will be according to the usual
+ BFS ordering. Other types of queues can be used, but the traversal order will
+ be different. For example Dijkstra's algorithm can be implemented using a
+ priority queue. The type Buffer must be a model of [NoConcept Buffer].
+
+ The `value_type` of the buffer must be the vertex_descriptor type for the graph.
+
+ *Default* `boost::queue`
+ ]
+ ]
+]
+
+[heading Complexity]
+The time complexity is /O(E + V)/.
+
+[heading Example]
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connected_components.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -6,7 +6,6 @@
/]
[section Connected Components]
-
template <class Graph, class ComponentMap, class P, class T, class R>
typename property_traits<ComponentMap>::value_type
connected_components(const Graph &g, ComponentMap c,
Added: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/depth_first_search.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -0,0 +1,153 @@
+[/
+ / 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 Depth-First Search]
+ template <class Graph, class P, class T, class R>
+ void
+ breadth_first_search(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+ template <class Graph, class Buffer, class Visitor, class P, class T, class R>
+ void
+ breadth_first_search(Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor s,
+ Buffer& q,
+ Visitor v,
+ bgl_named_params<P,T,R>& params = ``/defaults/``)
+
+The `breadth_first_search()` function performs a breadth-first traversal \[49\] of a directed or
+undirected graph. A breadth-first traversal visits vertices that are closer to the source before
+visiting vertices that are further away. In this context "distance" is defined as the number of edges
+in the shortest path from the source vertex. The `breadth_first_search()` function can be used to
+compute the shortest path from the source to all reachable vertices and the resulting shortest-path
+distances. For more definitions related to BFS, see section Breadth-First Search.
+
+BFS uses two data structures to to implement the traversal: a color marker for each vertex and
+a queue. White vertices are undiscovered while gray vertices are discovered but have undiscovered
+adjacent vertices. Black vertices are discovered and are adjacent to only other black or gray
+vertices. The algorithm proceeds by removing a vertex /u/ from the queue and examining each out-edge
+/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
+queue. After all of the out-edges are examined, vertex u is colored black and the process is
+repeated. Pseudo-code for the BFS algorithm is a listed below.
+
+[pre
+BFS(G, s)
+ for each vertex u in V\[G\] initialize vertex u
+ color\[u\] := WHITE
+ d\[u\] := infinity
+ p\[u\] := u
+ end for
+
+ color\[s\] := GRAY
+ d\[s\] := 0
+ ENQUEUE(Q, s) discover vertex s
+
+ while not EMPTY(Q)
+ u := DEQUEUE(Q) examine vertex u
+ for each vertex v in adj\[u\] examine edge /(u,v)/
+ if(color\[v\] = WHITE) /(u,v)/ is a tree edge
+ color\[v\] := GRAY
+ d\[v\] := d\[u\] + 1
+ p\[v\] := u
+ ENQUEUE(Q, v) discover vertex v
+ else /(u,v)/ is a non-tree edge
+ if (color\[v\] = GRAY) /(u,v)/ has a gray target
+ ...
+ else /(u,v)/ has a black target
+ ...
+ end if
+ end for
+ color\[u\] := BLACK finsih vertex u
+ end while
+ return (d, p)
+]
+
+[heading Where Defined]
+`boost/graph/breadth_first_search.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`Graph& g`]
+ [
+ A directed or undirected graph. The graph type must be a model of [BoostVertexListGraph]
+ and [BoostIncidenceGraph].
+ ]
+ ]
+ [
+ [in] [`vertex_descriptor s`]
+ [
+ The source vertex where the search is started. This must be a valid vertex descriptor of
+ `g`.
+ ]
+ ]
+]
+
+[heading Named Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [in] [`visitor(Visitor vis)`]
+ [
+ A visitor object that is inovked inside the algorithm at event points specified by the
+ [BoostBFSVisitor]. The `vis` object must be model the [BoostBFSVisitor] concept.
+
+ *Default* `bfs_visitor<null_visitor>`.
+ ]
+ ]
+ [
+ [in] [`vertex_index_map(VeretxIndexMap index_map)`]
+ [
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is only necessary when the default color property map is
+ used. The type VertexIndexMap must be a model of ReadablePropertyMap. The
+ value type of the map must be an integer type. The vertex descriptor type
+ of the graph needs to be usable as the key type of the map.
+
+ *Default* `get(vertex_index, g)`. Note if you use this default, make sure
+ that your graph has an interior `vertex_index` property. For example
+ `adjacency_list` with `VertexList=listS` does not have an interior
+ `vertex_index` property.
+ ]
+ ]
+ [
+ [util] [`color_map(ColorMap color)`]
+ [
+ This is used by the algorithm to keep track of its progress through the
+ graph. The type ColorMap must be a model of ReadWritePropertyMap and
+ its key type must be the graph's `vertex_descriptor` type and the value
+ type of the color map must model ColorValue.
+
+ *Default* An `iterator_property_map` create from a `std::vector` of
+ `default_color_type` of size `num_vertices(g)` and using `index_map` as
+ the index map (to access colors for a vertex).
+ ]
+ ]
+ [
+ [util] [`buffer(Buffer& q)`]
+ [
+ The queue used to determine the order in which vertices will be discovered.
+ If a FIFO queue is used, then the traversal will be according to the usual
+ BFS ordering. Other types of queues can be used, but the traversal order will
+ be different. For example Dijkstra's algorithm can be implemented using a
+ priority queue. The type Buffer must be a model of [NoConcept Buffer].
+
+ The `value_type` of the buffer must be the vertex_descriptor type for the graph.
+
+ *Default* `boost::queue`
+ ]
+ ]
+]
+
+[heading Complexity]
+The time complexity is /O(E + V)/.
+
+[heading Example]
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/distributions.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -6,31 +6,38 @@
/]
[section Degree Distributions]
- template <class Graph, class DistributionMap>
- void degree_distribution(const Graph &g, DistributionMap& dist);
+ template <class Graph, class Distribution>
+ void degree_distribution(const Graph &g, Distribution& dist);
- template <class Graph, class DistributionMap>
- void in_degree_distribution(const Graph &g, DistributionMap& dist);
+ template <class Graph, class Distribution>
+ void in_degree_distribution(const Graph &g, Distribution& dist);
- template <class Graph, class DistributionMap>
- void out_degree_distribution(const Graph &g, DistributionMap& dist);
+ template <class Graph, class Distribution>
+ void out_degree_distribution(const Graph &g, Distribution& dist);
- template <class Graph, class HistogramMap>
- void degree_histogram(const Graph &g, HistogramMap& dist);
-
- template <class Graph, class HistogramMap>
- void in_degree_histogram(const Graph &g, HistogramMap& dist);
-
- template <class Graph, class HistogramMap>
- void out_degree_histogram(const Graph &g, HistogramMap& dist);
-
-The degree distribution functions compute statistical distributions of the degrees
-of vertices in a graph. In addition to the degree distribution, different algorithms
-allow for the computation in-degree and out-degree distributions.
-
-The histogramming functions compute historgrams, associating each vertex in
-the graph with its degree in the distribution.
+ template <class Graph, class Histogram>
+ void degree_histogram(const Graph &g, Histogram& dist);
+
+ template <class Graph, class Histogram>
+ void in_degree_histogram(const Graph &g, Histogram& dist);
+
+ template <class Graph, class Histogram>
+ void out_degree_histogram(const Graph &g, Histogram& dist);
+
+The degree distribution functions compute distributions of the degrees
+of vertices in a graph. A distribution is mapping of an observable property
+to the number of occurences of that property. In this context, the observable
+property is the degree of a vertex (or in- and out- degree), which are in
+the range \[0, /max{degree(v)}/\] Where /max{degree(v)}/ is the maximum degree
+of any vertex in a graph /G/. Therefore, the output distribution is mapping
+of vertex degree to its number of occurences in a graph.
+
+This histogram functions are closely related to the degree distribution functions.
+However, instead of computing a mapping from vertex degree to the number of
+vertices, the histogram maps vertex degree to the /set of vertices/ that exhibit
+that degree. This is very useful if you want to quickly find all vertices with
+degree 0, or find the vertex with the highest degree.
[heading Where Defined]
`boost/graph/degree_distribution.hpp`
@@ -48,41 +55,40 @@
]
]
[
- [out] [`DistributionMap& dist`]
+ [out] [`Distribution& dist`]
[
The distribution parameter maps instances of degrees (numerically)
to the number of vertices in the graph that exhibit that degree.
- The distribution output parameter has a number of strict typ requirements.
- First, it must be a model of the Sequence concept, specifically providing
- a `resize()` member function. They key (or index) type of this parameter
- should be the same as `degree_size_type` of the graph. Finally, the
- `value_type` of this method should be an integer type (preferrably
- unsigned). It is recommended to use `std::vector<degree_size_type>` for
- this parameter.
+ The distribution output parameter must be a model of both [SgiSequence]
+ and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
+ distribution must be the same as `degree_size_type`. The `value_type` must
+ be integral (preferably unsigned).
]
]
[
- [out] [`HistogramMap& hist`]
+ [out] [`Histogram& hist`]
[
The histogram parameter maps instances of degrees (numerically) to the
set of vertices that exhibit that degree.
- The histogram parameter has fairly stringent type requirements due to
- its structure. First, the parameter must model the Sequence concept,
- providing a `resize()` member function. Seocnd, the key (index) of
- the type should be the same as `degree_size_type` of the graph. The
- `value_type` of this is required to model the BackInsertionSequence,
- and the `value_type` of that /must/ be the same as the `vertex_descriptor`
- of the graph parameter.
+ The histogram output parameter must be a model of both [SgiSequence]
+ and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
+ distribution must be the same as `degree_size_type`. Additionally `value_type`
+ must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).
]
]
]
-[heading Complexity]
-The complexity of this function is /O(V)/.
+[h4 Complexity]
+The time complexity of all these functions is /O(V)/.
+
+The space complexity for the distributions functisons is /O(max{degree(v)})/ where
+/max{degree(v)}/ is the maxmimum degree of all vertices in a graph /G/.
+
+The space complexity for the histogram functions is /O(V + max{degree(v)})/.
-[heading Notes]
+[h4 Notes]
Because a graph may be a multigraph, there is no determinable upper bound on the
size of the distribution or histogram parameters. As such they are required to
be dynamically resized during the execution of the algorithm.
@@ -91,17 +97,16 @@
all the requirements. For the histogram, we recommend using a `std::vector<Sequence<Vertex> >`
where `Sequence` is one of `std::list`, `std::vector`, `std::deque`, or `std::queue`. The
choice doesn't make much difference except that a `std::list` will require more allocations,
-but a `std::vector` will require more space. The `Vertex` type must be
+but a `std::vector` will require more space. Also, note that `std::list::size()` function is
+not required to run in constant-time. The `Vertex` type must be
`graph_traits<Graph>::vertex_descriptor`.
If `dist` is the name of the output distribution after a call to `degree_distribution()`
then the maximum degree is `dist.size() - 1`. The minimum degree corresponds to the index
in `dist` with the first non-zero value.
-[heading Examples]
-The first example show how to compute and print the degree distribution. Each
-element in the returned distribution corresponds to the number of instances
-of
+[h4 Examples]
+The first example show how to compute and print the degree distribution.
undirected_graph<> g;
// add vertices and edges to g
@@ -119,9 +124,9 @@
// add vertice and edges to g
typedef graph_traits<undirected_graph<> >::vertex_descriptor vertex_type;
- typedef std::list<vertex_type> vertex_list;
+ typedef std::vector<vertex_type> vertex_vector;
- std::vector<vertex_list> hist;
+ std::vector<vertex_vector> hist;
degree_histogram(g, hist);
cout << get_vertex_index(hist.back().back()) << "\n";
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk 2007-06-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -15,6 +15,8 @@
[section Algorithms]
[section Core Algorithms]
+[include breadth_first_search.qbk]
+[include depth_first_search.qbk]
[endsect]
[section Shortest Path Algorithms]
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-29 12:38:35 EDT (Fri, 29 Jun 2007)
@@ -136,7 +136,7 @@
[h5 Model Of]
[BoostIncidenceGraph], [BoostVertexListGraph], [BoostEdgeListGraph], [BoostAdjacencyGraph],
-[BoostMutableGraph], [BoostPropertyGraph], [BoostMutablePropertyGraph].
+[BoostMutableGraph], and [BoostPropertyGraph].
Additionally, the `undirected_graph` class provides a non-constant time implementation
of the [BoostAdjacencyMatrix] associated function `edge(u,v,g)`, but does not model
@@ -157,18 +157,22 @@
[`graph_traits<undirected_graph>::vertex_descriptor`]
[
The type for the vertex descriptors associated with the graph. The `vertex_descriptor`
- models the following concepts: [BoostDescriptor].
+ models the [BoostDescriptor] and [NoConcept Hashable] concepts.
]
]
[
[`graph_traits<undirected_graph>::edge_descriptor`]
[
The type for the edge descriptors associated with the graph. The `edge_descriptor`
- models the followign concepts: [BoostDescriptor].
+ models the [BoostDescriptor] and [NoConcept Hashable] concepts.
]
]
]
+Note that edge and vertex descriptors for the `unsigned_graph` can be used as keys for both
+[SgiSortedAssociativeContainer]s and [SgiHashedAssociativeContainer]s such as `std::map` and
+`std::tr1::unordered_map` respectively.
+
[h5 Iterator Types]
[table
[[Type] [Description]]
@@ -726,4 +730,10 @@
]
]
+[h4 Rationale]
+Unlike most graph classes in Boost.Graph, the `undirected_graph` does not model the
+[BoostMutablePropertyGraph] concept. The reason for this is that it is relatively
+difficult (from a usability standpoint) to easily deduce the type to be passed as a
+property when adding vertices and edges - but especially vertices.
+
[endsect]
\ No newline at end of file
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