
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070629 12:38:38
Author: asutton
Date: 20070629 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 20070629 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 20070629 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
+outedge 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 iteratorrange 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 outedge 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 20070629 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 FloydWarshall 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 nonconstant 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 20070629 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 20070629 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 BreadthFirst 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 outedges of vertex `u`.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`vis.examine_edge(e,g)`]
+ [
+ This is invoked on every outedge 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 nontreeedges 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 nontree 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 outedges
+ 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 20070629 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 inedges (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 20070629 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 20070629 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 20070629 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 DepthFirst 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 outedge 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 outedges 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 20070629 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 20070629 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 outedges, 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 outedges 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 20070629 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 20070629 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 20070629 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 nonmutable 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 VertexIndexed 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 20070629 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
+outedge. 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 outedge which would be
+nonintuitive and cause trouble for algorithms. Therefore, the extra requirement is added that
+the outedge 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 20070629 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 inedges and outedges 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 outedges 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 inedges 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 outedges of `u` and /(u,v)/
+ (or equivalently /(v,u)/) will appear in the outedges 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 outedges of the vertex `v` for which the predicate `pred` returns true.
+
+ *Returns* `void`
+ ]
+ ]
+ [
+ [`remove_in_edge_if(v,pred,g)`]
+ [
+ Remove all inedges 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 20070629 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 20070629 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 outedges (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 20070629 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 outedges, 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 outedges 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 20070629 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 copyconstructible, 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 20070629 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 20070629 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 20070629 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 BreadthFirst 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 breadthfirst traversal \[49\] of a directed or
+undirected graph. A breadthfirst 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 shortestpath
+distances. For more definitions related to BFS, see section BreadthFirst 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 outedge
+/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
+queue. After all of the outedges are examined, vertex u is colored black and the process is
+repeated. Pseudocode 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 nontree 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 20070629 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 20070629 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 DepthFirst 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 breadthfirst traversal \[49\] of a directed or
+undirected graph. A breadthfirst 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 shortestpath
+distances. For more definitions related to BFS, see section BreadthFirst 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 outedge
+/(u,v)/. If an adjacent vertex /v/ is not already discovered, it is colored gray and placed in the
+queue. After all of the outedges are examined, vertex u is colored black and the process is
+repeated. Pseudocode 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 nontree 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 20070629 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 indegree and outdegree 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 constanttime. 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 nonzero 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 20070629 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 20070629 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 nonconstant 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
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk