
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070820 13:48:04
Author: asutton
Date: 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
New Revision: 38798
URL: http://svn.boost.org/trac/boost/changeset/38798
Log:
Finished tiernan docs
Started b&k docs
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk  6
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk  22 ++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk  42 +++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk  10
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk  14 
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk  294 ++++++++++++++++++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk  2
7 files changed, 312 insertions(+), 78 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 45,10 +45,12 @@
[template MutablePropertyGraph[] [link
boost_graph.concepts.graph_concepts.mutable_property_graph
[^MutablePropertyGraph]]]

[template VertexIndexGraph[] [link
 boost_graph.concepts.graph_concepts
+ boost_graph.concepts.graph_concepts.vertex_index_graph
[^VertexIndexGraph]]]
+[template EdgeIndexGraph[] [link
+ boost_graph.concepts.graph_concepts.edge_index_graph
+ [^EdgeIndexGraph]]]
[template Visitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
[template BFSVisitor[] [link boost_graph.concepts.visitor_concepts.breadth_first_search_visitor BreadthFirstSearchVisitor]]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 64,13 +64,24 @@
[template bron_kerbosch_visit_cliques[] [link
boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques
[^bron_kerbosch_all_cliques()]]]
[template tiernan_find_cycles[] [link
 boost_graph.reference.algorithms.subgraph.tiernan_all_cycles
+
+[template tiernan_all_cycles[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_all_cycles___
[^tiernan_all_cycles()]]]
+[template tiernan_girth[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_girth___
+ [^tiernan_girth()]]]
+[template tiernan_circumference[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_circumference___
+ [^tiernan_circumference()]]]
+[template tiernan_girth_and_circumference[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_girth_and_circumference___
+ [^tiernan_girth_and_circumference()]]]
+
[/ Measures /]
[template degree_centrality[] [link
 boost_graph.reference.algorithms.measures.degree_centrality.__degree_centrality__
+ boost_graph.reference.algorithms.measures.degree_centrality.__degree_centrality___
[^degree_centrality()]]]
[template all_degree_centralities[] [link
boost_graph.reference.algorithms.measures.degree_centrality.__all_degree_centralities___
@@ 103,6 +114,9 @@
[template diameter[] [link
boost_graph.reference.algorithms.measures.eccentricity.__diameter___
[^diameter()]]]
+[template radius_and_diameter[] [link
+ boost_graph.reference.algorithms.measures.eccentricity.__radius_and_diameter___
+ [^radius_and_diameter()]]]
[template exterior_vertex_property[] [link
@@ 120,3 +134,5 @@
[import ../examples/mean_geodesic.cpp]
[import ../examples/inclusive_mean_geodesic.cpp]
[import ../examples/eccentricity.cpp]
+[import ../examples/tiernan_print_cycles.cpp]
+[import ../examples/tiernan_girth_circumference.cpp]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 6,25 +6,33 @@
/]
[section Bron Kerbosch All Cliques]
+[template ex_bron_kerbosch_printing_cliques[] [link
+ boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.examples.printing_cliques
+ Printing Cliques Example]]
 template <typename Graph, typename Visitor>
 void bron_kerbosch_all_cliques(const Graph& g, Visitor vis)

+[heading Overview]
This algorithm finds all /cliques/ of the given graph, invoking a visitor when
each clique is found. A clique is a maximally connected subgraph meaning that
each pair of vertices in the clique are connected to each other.
For directed graphs, a /directed clique/ is similarly defined. For each pair
of vertices /u/ and /v/ in the directed clique, there are edges /(u,v)/ and
/(v,u)/ that connect them.
+of vertices /u/ and /v/ in a directed clique, there are edges /(u,v)/ and /(v,u)/
+that connect them.
The `bron_kerbosch_all_cliques()` algorithm was originally written for undirected
graphs, but will work for directed graphs as well at added cost. In order for a
directed clique to exist, each vertex /u/ must be connected to /v/ and /v/ must
be connected to /u/.
+The BronKerbosch algorithm was originally developed to operate over adjacency
+matrices of undirected graphs. It will, however, work equally well for directed
+graphs given the previous definition at a constant increase in cost. However,
+using this algorithm with an adjaceny list occurs significant overhead due to
+the use of edge lookups.
[heading Where Defined]
`boost/graph/bron_kerbosch_all_cliques.hpp`
+The BronKerbosch algorithm was originally developed for undirected graphs, but
+will work for directed graphs as well (possibly at added cost).
+
+[section [^bron_kerbosch_all_cliques()]]
+ #include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+ template <typename Graph, typename Visitor>
+ void bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
[heading Parameters]
[table
@@ 56,11 +64,8 @@
]
]
[h5 Return Value]
This function does not return a value.

[h5 Complexity]
This problem has a loose upper bound of ['O(2[sup n])] if one considers all possible
+This problem has a loose upper bound of ['O(2[super n])] if one considers all possible
combinations of subsets of vertices as cliques (i.e., the powerset of vertices).
The original publication, however, approximates the runtime of the algorithm as
being proportional to ['O(3.14[super n])].
@@ 69,8 +74,13 @@
concept will incur additional runtime costs during execution (usually by a small linear
factor). Examples of such graphs include the [undirected_graph],
[directed_graph], and the [adjacency_list] classes.
+[endsect]
+
[h5 Examples]
+[section Examples]
+[heading Printing Cliques]
+Write Me!
+[endsect]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 242,15 +242,15 @@
of vertices in the graph.
[endsect]
[section [^radius_diameter()]]
+[section [^radius_and_diameter()]]
#include <boost/graph/eccentricity.hpp>
template <typename Graph, typename EccentricityMap>
std::pair<typename property_traits<EccentricityMap>::value_type,
typename property_traits<EccentricityMap>::value_type>
 radius_diameter(const Graph& g, EccentricityMap ecc)
+ radius_and_diameter(const Graph& g, EccentricityMap ecc)
The `radius_diameter()` function returns both the radius and diameter of the
+The `radius_and_diameter()` function returns both the radius and diameter of the
graph as a pair such that the `first` element of the pair is the radius and the
`second` element is the diameter. These values are computed from the eccentricities
that have been previously computed using the [eccentricity] function.
@@ 282,12 +282,12 @@
]
[heading Return Value]
The `radius_diameter()` funtion returns a pair containing both the radius (`first`)
+The `radius_and_diameter()` funtion returns a pair containing both the radius (`first`)
and diameter (`second`) of the graph. The types of these values are the same as the
`value_type` of the `EccentricityMap`.
[heading Complexity]
The `radius_diameter()` returns in linear time with respect to the number of vertices
+The `radius_radius_diameter()` returns in linear time with respect to the number of vertices
in the graph.
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 34,6 +34,7 @@
[endsect]
[section Algorithms]
+
[section Fundamental]
[include breadth_first_search.qbk]
[include depth_first_search.qbk]
@@ 51,12 +52,8 @@
[endsect]
[section Subgraph]
This section contains algorithms that implement count or enumerate subgraphs.
Note that this section can be further subdivided based on the types of subgraphs
being found. For exammple, there could be a section on finding cliques and a
section on finding cycles.
[include bron_kerbosch_all_cliques.qbk]
[include tiernan_all_cycles.qbk]
+[include bron_kerbosch_all_cliques.qbk]
[endsect]
[section Maximum Flow]
@@ 74,7 +71,8 @@
[include betweenness_centrality.qbk]
[include mean_geodesic.qbk]
[include eccentricity.qbk]
[endsect]
[endsect]
+[endsect] [/Measures]
+
+[endsect] [/Algorithms]
[endsect]
\ No newline at end of file
+[endsect] [/Reference]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 6,44 +6,88 @@
/]
[section Tiernan All Cycles]
+[template ex_tiernan_printing_cycles[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.examples.printing_cycles
+ Printing Cycles Example]]
+[template ex_tiernan_girth_circumference[] [link
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.examples.printing_cycles
+ Printing Cycles Example]]
+
+[heading Overview]
+This function uses the Tiernan algorithm to find all /cycles/ within a given graph,
+invoking a visitor when each cycle is found. A cycle is a path (a sequence of
+connected vertices) within a graph, and whose tail (the last vertex in the path)
+is connected to its head (the first vertex in the path).
+
+Consider the directed graph in Figure 1.
+
+[figure
+ images/reference/prism_3_2.png
+ *Figure 1.* A directed graph.
+]
+
+This graph has 11 distinct cycles. Some of the more obvious are:
+
+* 0, 1, 2
+* 3, 4, 5
+* 0, 3
+* 1, 4
+* 2, 5
+
+For more details see the [ex_tiernan_printing_cycles].
+
+The order in which cycles are visited is determined by the algorithm. It iterates
+over each vertex in the order of its vertex indices. The algorithm identifies cycles
+by first finding long paths and determining if they form cycles. Once the paths
+have been examined, the algorithm backtracks along the path searching for alternate
+cycles. The result (as shown in the output of the [ex_tiernan_printing_cycles]) is a
+listing that visits longer cycles first in the lexicographical order of vertex
+indices. Note that the order of visitation does /not/ imply anything about the
+relative importance of the cycle within the graph.
+
+The Tiernan algorithm is designed to work on directed graphs, but works for undirected
+graphs as well. When running on undirected graphs, however, the algorithm treats each
+edge connecting two vertices /(u,v)/ as if it were two distinct edges /(u,v)/ and
+/(v,u)/. As result the algorithm will report cycles in both directions. Consider the
+following undirected graph in Figure 2.
+
+[figure
+ images/reference/triangle.png
+ *Figure 2.* An undirected triangle.
+]
+
+If the Tiernan algorithm is run on this graph, it will visit the paths 0, 1, 2 and
+0, 2, 1.
+
+There are two properties of a graph that are derived from knowing a graphs cycles:
+/girth/ and /circumference/. The girth of a graph is defined as the minimumlength
+cycle in the graph, and the circumference is defined as the largestlength cycle.
+This module provides functions for computing these values using Tiernan's algorithm.
+
+[section [^tiernan_all_cycles()]]
+ #include <boost/graph/tiernan_all_cycles.hpp>
template <typename Graph, typename Visitor>
 inline void tiernan_all_cycles(const Graph& g, Visitor vis)
+ void tiernan_all_cycles(const Graph& g, Visitor vis)
template <typename Graph, typename Visitor>
 void tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
+ void tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t max)
template <typename Graph, typename Visitor>
 void tiernan_all_cycles(const Graph& g,
 Visitor vis,
 std::size_t minlen,
 std::size_t maxlen)

These functions find all /cycles/ within of the given graph, invoking a visitor
when each cycle is found. A cycle is a path (a sequence of connected vertices)
within a graph whose tail (the last vertex in the path) is connected to its
head (the first vertex in the path).

There are three variants of this algorithm. The first will simply find and visit
all cycles in the target graph. The second variant allows the caller to specify
an upper bound on the length of cycles visited. The third variant allows the
user to specify both upper and lower bounds on the lengths of paths being visited.
The minimum cycle length must be at least two.

The `tiernan_all_cycles()` function is designed to work on directed graph, but
works for undirected graphs as well. When running on undirected graphs, however,
the algorithm treats each edge connecting two vertices /(u,v)/ as if it were
two edges /(u,v)/ and /(v,u)/. As result the algorithm will report cycles in
both directions.
+ void tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t min, std::size_t max)
+
+The `tiernan_all_cycles()` function visits all cycles in a graph. There are three
+variants of this algorithm. The first will simply find and visit all cycles in the
+target graph. The second variant allows the caller to specify an upper bound to the
+length of cycles visited, and the third variant allows the user to specify both
+upper and lower bounds on the lengths of paths being visited. The minimum cycle
+length must be at least two.
Note that the default minimum cycle length differs between directeed and undirected
+Note that the default minimum cycle length differs between directed and undirected
graphs. For directed graphs, the algorithm allows the discovery and visitation
of lengthtwo cycles. For undirected graphs, the default minimum cycle length is
three. This prevents the algorithm from visiting every pair of connected vertices
in an undirected graph.

[heading Where Defined]
`boost/graph/tiernan_all_cycles.hpp`
+in an undirected graph as a cycle.
[heading Parameters]
[table
@@ 53,9 +97,6 @@
[
The graph for which cliques are being visited.
 *Preconditions:* The indices of vertices in the graph must be
 in the range \[0, `num_vertices(g)`).

*Requirements:* The `Graph` type must be a model of the
[IncidenceGraph] and [VertexIndexGraph] concepts.
]
@@ 69,22 +110,189 @@
[CliqueVisitor] class.
]
]
+ [
+ [optional, in] [`std::size_t max`]
+ [
+ The maximumlength path that will be visited by the algorithm.
+
+ *Default:* `std::numeric_limits<std::size_t>::max()`.
+ ]
+ ]
+ [
+ [optional, in] [`std::size_t min`]
+ [
+ The minimumlength path that will be visited by the algorithm. The
+ default minimum length path is determined by the type of graph.
+
+ *Precondition:* `min >= 2`
+
+ *Default:* If `Graph` is directed, this value defaults to 2. Otherwise
+ the default value is 3.
+ ]
+ ]
+]
+
+[heading Complexity]
+This function has a (loose) upper bound of ['O(2[super n])] where /n/ is the
+number of vertices a graph. This bound is derived from the powerset of vertices
+in /g/ and does not account for the vertex of origin or directionality of edges
+connecting vertices in a path. If one considers the paths in a triangle {1, 2, 3}
+and {3, 2, 1} to be distinct cycles within a graph, then this bound can potentially
+be much greater. From a practical standpoint, it is unlikely that real graphs will
+ever approach a number of paths remotely close to this number.
+
+This function requires ['O(n[super 2])] space where /n/ is the number of vertices
+in a graph.
+[endsect]
+
+[section [^tiernan_girth()]]
+ #include <boost/graph/tiernan_all_cycles.hpp>
+
+ template <typename Graph>
+ std::size_t tiernan_girth(const Graph& g)
+
+Comptutes the girth (the minimum length cycle) of the graph `g` by visiting all
+cycles using Tiernan's algorithm. If the graph is acyclic, it has no cycles and
+an infinite girth. If computing both girth and circumference, use the
+[tiernan_girth_and_circumference] function since this computation can be fairly
+time consuming.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the girth is computed.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [IncidenceGraph] and [VertexIndexGraph] concepts.
+ ]
+ ]
+]
+
+[heading Return]
+The `tiernan_girth()` function returns the girth of the given graph.
+
+[heading Complexity]
+The `tiernan_girth()` function has the same time complexity as the [tiernan_all_cycles]
+function.
+[endsect]
+
+[section [^tiernan_circumference()]]
+ #include <boost/graph/tiernan_all_cycles.hpp>
+
+ template <typename Graph>
+ std::size_t tiernan_circumference(const Graph& g)
+
+Comptutes the circumference (the maximum length cycle) of the graph `g` by visiting all
+cycles using Tiernan's algorithm. If the graph is acyclic, it has no cycles and an
+infinite circumference. If computing both girth and circumference, use the
+[tiernan_girth_and_circumference] function since this computation can be fairly
+time consuming.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the circumference is being computed.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [IncidenceGraph] and [VertexIndexGraph] concepts.
+ ]
+ ]
]
[h5 Return Value]
This function does not return a value.
+[heading Return]
+The `tiernan_circumference()` function returns the girth of the given graph.
[h5 Complexity]
This function has a (loose) upper bound of ['O(2[sup n])] where /n/ is the
number of vertices in /g/. This bound is derived from the powerset of vertices
in /g/ and does not account for origin or directionality of edges connecting
those vertices. If you consider the paths in a triangle {1, 2, 3} and {3, 2, 1}
to be different cycles within a graph, then this bound potentially be much greater.
+[heading Complexity]
+The `tiernan_circumference()` function has the same time complexity as the
+[tiernan_all_cycles] function.
+[endsect]
+
+[section [^tiernan_girth_and_circumference()]]
+ #include <boost/graph/tiernan_all_cycles.hpp>
+
+ template <typename Graph>
+ std::pair<std::size_t, std::size_t>
+ tiernan_girth_and_circumference(const Graph& g)
+
+Comptutes the both the girth (minimum length cycle) and circumference (maximum length
+cycle) of the graph `g` by visiting all cycles using Tiernan's algorithm. If the
+graph is acyclic, it has no cycles and both girth and cicumference are infinite.
From a practical standpoint, most (i.e., nearly all) real graphs will never approach
a number of paths even remotely close to this number.
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the girth and circumference are being computed.
+
+ *Preconditions:* The indices of vertices in the graph must be
+ in the range...
+
+ *Requirements:* The `Graph` type must be a model of the
+ [IncidenceGraph] and [VertexIndexGraph] concepts.
+ ]
+ ]
+]
+
+[heading Return]
+The `tiernan_girth_and_circumference()` function returns the girth of the given graph.
+
+[heading Complexity]
+The `tiernan_girth_and_circumference()` function has the same time complexity as the
+[tiernan_all_cycles] function.
+[endsect]
+
+[section Examples]
+[heading Printing Cycles]
+This example demonstrates the construction of a cycle visitor and its use with
+the `tiernan_all_cycles()` function. This file includes the following files:
+
+* [^examples/tiernan_print_cycles.cpp]
+* [^examples/helper.hpp]
+
+[tiernan_print_cycles]
+
+If this program is given the `prism_3_2.graph` file as input, it will print all
+the cycles in the graph shown in Figure 1.
+
+[pre
+0 1 2 5 3
+0 1 2
+0 1 4 5 3
+0 1 4 5 2
+0 3 4 5 2
+0 3 4 1 2
+0 3
+1 2 5 3 4
+1 4
+2 5
+3 4 5
+]
+
+[heading Girth and Circumference]
+This example demonstrates the use of Tiernan's algorithm to compute the girth
+and circumference of a directed graph. This example includes the following files:
+
+* [^examples/tiernan_girth_circumference.cpp]
+* [^examples/helper.hpp]
+
+[tiernan_girth_circumference]
+
+If this program is given the `prism_3_2.graph` file as input, it will print the
+following output:
+
+[pre
+girth: 2
+circumference: 5
+]
[h5 Examples]
Write an example.
+[endsect]
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/sgi_concepts.qbk 20070820 13:48:03 EDT (Mon, 20 Aug 2007)
@@ 11,7 +11,7 @@
/]
[/ Missing documentation /]
[template NoConcept[x] [x]]
+[template NoConcept[x] [^[x]]]
[template SgiAssignable[] [@http://www.sgi.com/tech/stl/Assignable.html Assignable]]
[template SgiDefaultConstructible[] [@http://www.sgi.com/tech/stl/DefaultConstructible.html DefaultConstructible]]
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