|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-20 13:48:04
Author: asutton
Date: 2007-08-20 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 2007-08-20 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 2007-08-20 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 2007-08-20 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 Bron-Kerbosch 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 Bron-Kerbosch 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 2007-08-20 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 2007-08-20 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 2007-08-20 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 minimum-length
+cycle in the graph, and the circumference is defined as the largest-length 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 length-two 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 maximum-length path that will be visited by the algorithm.
+
+ *Default:* `std::numeric_limits<std::size_t>::max()`.
+ ]
+ ]
+ [
+ [optional, in] [`std::size_t min`]
+ [
+ The minimum-length 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 2007-08-20 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]]
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk