
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070802 12:09:40
Author: asutton
Date: 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
New Revision: 38400
URL: http://svn.boost.org/trac/boost/changeset/38400
Log:
Finished docs for cycle/clique
Did more work on the cycle/clique visitor docs
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk  42 +++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk  8 ++
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk  7 +
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk  29 ++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk  55 ++++++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk  9 +++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk  67 ++++++++++++++++++++++++++++
7 files changed, 143 insertions(+), 74 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 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 16,16 +16,38 @@
[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
[template BoostVertexListGraph[] [link boost_graph.concepts.graph_concepts.vertex_list_graph VertexListGraph]]
[template BoostEdgeListGraph[] [link boost_graph.concepts.graph_concepts.edge_list_graph EdgeListGraph]]
[template BoostAdjacencyGraph[] [link boost_graph.concepts.graph_concepts.adjacency_graph AdjacencyGraph]]
[template BoostAdjacencyMatrix[] [link boost_graph.concepts.graph_concepts.adjacency_matrix AdjacencyMatrix]]
[template BoostMutableGraph[] [link boost_graph.concepts.graph_concepts.mutable_graph MutableGraph]]
[template BoostPropertyGraph[] [link boost_graph.concepts.graph_concepts.property_graph PropertyGraph]]
[template BoostMutablePropertyGraph[] [link boost_graph.concepts.graph_concepts.mutable_property_graph MutablePropertyGraph]]
+[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph [^Graph]]]
+[template BoostIncidenceGraph[] [link
+ boost_graph.concepts.graph_concepts.incidence_graph
+ [^IncidenceGraph]]]
+[template BoostBidirectionalGraph[] [link
+ boost_graph.concepts.graph_concepts.bidirectional_graph
+ [^BidirectionalGraph]]]
+[template BoostVertexListGraph[] [link
+ boost_graph.concepts.graph_concepts.vertex_list_graph
+ [^VertexListGraph]]]
+[template BoostEdgeListGraph[] [link
+ boost_graph.concepts.graph_concepts.edge_list_graph
+ [^EdgeListGraph]]]
+[template BoostAdjacencyGraph[] [link
+ boost_graph.concepts.graph_concepts.adjacency_graph
+ [^AdjacencyGraph]]]
+[template BoostAdjacencyMatrix[] [link
+ boost_graph.concepts.graph_concepts.adjacency_matrix
+ [^AdjacencyMatrix]]]
+[template BoostMutableGraph[] [link
+ boost_graph.concepts.graph_concepts.mutable_graph
+ [^MutableGraph]]]
+[template BoostPropertyGraph[] [link
+ boost_graph.concepts.graph_concepts.property_graph
+ [^PropertyGraph]]]
+[template BoostMutablePropertyGraph[] [link
+ boost_graph.concepts.graph_concepts.mutable_property_graph
+ [^MutablePropertyGraph]]]
+
+[template BoostVertexIndexGraph[] [link
+ boost_graph.concepts.graph_concepts
+ [^VertexIndexGraph]]]
[template BoostVisitor[] [link boost_graph.concepts.visitor_concepts.visitor Visitor]]
[template BoostBFSVisitor[] [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 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 54,11 +54,11 @@
[/ Subgraph/ ]
[template boost_bron_kerbosch_visit_cliques[] [link
 boost_graph.reference_guide.algorithms.subgraph.bron_kerbosch_find_cliques
 [^bron_kerbosch_find_cliques()]]]
+ boost_graph.reference_guide.algorithms.subgraph.bron_kerbosch_all_cliques
+ [^bron_kerbosch_all_cliques()]]]
[template boost_tiernan_find_cycles[] [link
 boost_graph.reference_guide.algorithms.subgraph.tiernan_find_cycles
 [^tiernan_find_cycles()]]]
+ boost_graph.reference_guide.algorithms.subgraph.tiernan_all_cycles
+ [^tiernan_all_cycles()]]]
[/ Measures /]
[template boost_degree_centrality[] [link
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/clique_visitor.qbk 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 21,8 +21,8 @@
[`vis.clique(vs,g)`]
[`void`]
[
 *Semantics:* The `clique()` member function of the visitor is invoked
 when a fully connected subgraph is identified in the graph `g`.
+ The `clique()` member function of the visitor is invoked when a fully
+ connected subgraph is identified in the graph `g`.
*Requirements:* `g` is an object whose type `G` is a refinement of the
[BoostGraph] concept.
@@ 47,8 +47,7 @@
template<Container VertexSet>
requires SameType<VertexSet::value_type, graph_type::vertex_descriptor>
 void
 T::clique(const VertexSet&, graph_type&);
+ void T::clique(const VertexSet&, graph_type&);
};
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/cycle_visitor.qbk 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 21,19 +21,18 @@
[`vis.cycle(vs,g)`]
[`void`]
[
 *Semantics:* The `cycle()` member function of the visitor is invoked
 when a cycle is identified in the graph `g`.
+ The `vis.cycle()` member function of the visitor is invoked when a
+ cycle is identified in the graph `g`. The vertices in `vs` are arranged
+ such that first vertex is connected to the second, and that is connected
+ to the third, etc. The `back()` vertex is connected to the `front()`
+ to form a cycle.
 *Requirements:* `g` is an object whose type `G` is a refinement of the
+ *Requirements:* `g` is an object whose type `G` is a model of the
[BoostGraph] concept.
 *Requirements:* `vs` is an object whose type `VS` is a refinement of the
 [SgiSequence] concept. The `value_type` of `VS` must be the `vertex_descriptor`
 of `G`.

 *Precondition:* The vertices in `vs` are arranged such that first vertex
 is connected to the second, and that is connected to the third, etc. The
 last vertex is connected to the the first.
+ *Requirements:* `vs` is an object whose type `VertexSet` is a model
+ of the [SgiContainer] concept. The `value_type` of `VS` must be the
+ the same as the `vertex_descriptor` of `G`.
]
]
]
@@ 41,12 +40,14 @@
[heading C++0x]
This concept is defined as:
 concept CycleVisitor<typename T>
+ concept CliqueVisitor<typename T>
{
 typename graph_type;
 typename vertex_set_type;
+ Graph graph_type;
 T::cycle(const vertex_set_type&, graph_type&);
+ template<Container VertexSet>
+ requires SameType<VertexSet::value_type, graph_type::vertex_descriptor>
+ void T::cycle(const VertexSet&, graph_type&);
};
+
[endsect]
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 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 5,43 +5,53 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
[section Bron Kerbosch Cliques]
+[section Bron Kerbosch All Cliques]
template <typename Graph, typename Visitor>
 void
 bron_kerbosch_find_cliques(const Graph& g, Visitor vis)
+ void bron_kerbosch_all_cliques(const Graph& g, Visitor vis)
These functions find all /cliques/ (maximal fully connected subgraphs) of the
given graph, invoking a visitor when each clique is found.
+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.
The `bron_kerbosch_visit_cliques()` function is intended for use with undirected
+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.
+
+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/.
[heading Where Defined]
`boost/graph/clique.hpp`
+`boost/graph/bron_kerbosch_all_cliques.hpp`
[heading Parameters]

[table
[[Type] [Parameter] [Description]]
[
[required, in] [`const Graph& g`]
[
 The graph for which cliques are being visited. The `Graph` type must
 /approximate/ the [BoostAdjacencyMatrix] in that it must implement
 the `edge(u,v,g)` function. It is not, however, required to return
 in constant time. Note that most graph types provide this function,
 including [boost_adjacency_list], [boost_undirected_graph], and
 [boost_directed_graph].
+ 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 [BoostAdjacencyMatrix],
+ [BoostIncidenceGraph] concept and the [BoostVertexIndexGraph]
+ concepts[footnote Any `Graph` typen that implements the `edge()`
+ function will satisfy the expression requirements for the
+ [BoostAdjacencyMatrix], but may incur additional overhead due nonconstant
+ implementations.].
]
]
[
[required, in] [`Visitor vis`]
[
 The visitor object to the algorithm. This `Visitor` class must
 model the [BoostCliqueVisitor] class.
+ The visitor object to the algorithm.
+
+ *Requirements:* This `Visitor` class must model the
+ [BoostCliqueVisitor] class.
]
]
]
@@ 50,10 +60,15 @@
This function does not return a value.
[h5 Complexity]
The complexity of this function was originally approximated as being proportional to
/O(3.14[super V])/. No strict upper bound is reported. If the `Graph` type
approximates the [BoostAdjacencyMatrix] concept, then the algorithm will perform
slower by a factor of V.
+This problem has a loose upper bound of ['O(2[sup 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])].
+
+Graphs that do not meet the constanttime requirements of the [BoostAdjacencyMatrix]
+concept will incur additional runtime costs during execution (usually by a small linear
+factor). Examples of such graphs include the [boost_undirected_graph],
+[boost_directed_graph], and the [boost_adjacency_list] classes.
[h5 Examples]
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/connectivity.qbk 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
+++ (empty file)
@@ 1,202 +0,0 @@
[/
 / 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 Connectivity Measures]

 template <
 typename Graph,
 typename Components,
 typename SizeType,
 typename ComponentMap,
 typename ColorMap,
 typename VertexIndexMap
 >
 std::size_t
 connectivity(
 const Graph& _graph,
 Components& _components,
 SizeType _number = 0,
 ComponentMap _component_map = ``['nothing]``,
 ColorMap _color_map = ``['nothing]``,
 VertexIndexMap _vertex_index_map = get(vertex_index, _graph));

The `connectivity()` algorithm is a wrapper around the [boost_connected_components]
algorithm that provides convenience for working with the resultant component maps.
The parameters have, with the exeption of `_components`, the same purpose and requirements
as documented in [boost_connected_components].

The `_components` parameter will result in a sequence of "components" of the graph
where each "component" is a sequence of vertices in the graph. After returning,
the size of the `_components` parameter will be the number of connected components
in the graph and each element in that sequence will contain a sequence of one or
more vertices. Each vertex is assigned to only one component. The assignment is
determined by the `_component_map`, whether passed to the algorithm or not.
If a vertex `v` is mapped to component id `i` such that `_component_map[v] == i` then
`v` will appear in the vertex sequence given by `_components[i]`.

To help illustrate the structure and contents of the `_components` parameter,
suppose, that after running [boost_connected_components], a graph is decomposed
into two components.

[figure
 images/reference/connected_components_after.png
 [*Figure 1.] Components found after running [boost_connected_components]
]

Assume that we have stored each vertex into a vector, `v`, such that `v[i]`
denotes the ['i[super th]] vertex in the graph above. The `_component_map` used
for this decomposition associates each vertex with a component id.

 _component_map[ v[0] ] == 0;
 _component_map[ v[1] ] == 0;
 _component_map[ v[2] ] == 0;
 _component_map[ v[3] ] == 1;
 _component_map[ v[4] ] == 1;

However, the `_components` parameter associates each component with the vertices that
comprise that component. Therefore, contents of the output sequence `_components` will
be (in pseudoC++):

 _components[0] == { v[0], v[1], v[2] };
 _components[1] == { v[0], v[1], v[2] };

This function returns the number of connected components in the graph.

There are two distinct methods for calling this function: with or without the
`_component_map` parameter. If the `_component_map` /is not/ given, then the
algorithm must first compute the connected components of `_graph`. In this case,
the user may need to supply the `_vertex_index_map` or an alternate `_color_map`.
Calling the [boost_connectivity] function in this way will not provide access
to a `_component_map` for the graph.

If the _component_map /is/ given, then the algorithm assumes that connected
components have already been assigned in the `_component_map`. In this case,
`_color_map` and `_vertex_index_map` parameters are effectively ignored. Additionally
the caller may pass the `_number` parameter to the function. If /not/ passed,
the computation is required to determine the number of components in the graph
by examining the `_component_map`. Passing `_number` as the return value of
[boost_connected_components] allows this operation to be bypassed.

[note
This hasn't been tested very will for directed graphs. In fact, testing
will probably result in the creation of `strong_connecity` which forwards the
call to `strong_connected_components`.
]

[h5 Where Defined]
`boost/graph/connectivity.hpp`

[h5 Parameters]
[table
 [[Type] [Parameter] [Description]]
 [
 [required, in] [`const Graph& _graph`]
 [
 The graph object for which the distribution will be computed. If
 the `_distribution` or `_in_distribution` arguments are supplied
 when calling this function then `_graph` must be a model of
 [BoostBidirectionalGraph]. If only `_out_distribution` is supplied,
 then `_graph` must be a model of [BoostIncidenceGraph].
 ]
 ]
 [
 [required, out] [`Components& _components`]
 [
 The components parameter provides storage for the assignment of
 vertices to components. The `ComponentMap` parameter must be a
 model of [SgiRandomAccessContainer] whose index type must be convertible
 to the graphs `vertices_size_type`, and whose `value_type` must be
 a model of [SgiBackInsertionSequence]. In turn, the `value_type` of
 this [SgiBackInsertionSequence] must be the `vertex_descriptor` type
 of `_graph`.
 ]
 ]
 [
 [optional, in] [`SizeType _number`]
 [
 This is the number of components in the graph as returned by a
 prior call to [boost_connected_components]. The SizeType must
 be convertible to the `vertices_size_type` of `Graph`.

 *Default* /not given/
 ]
 ]
 [
 [optional, in] [`ComponentMap _component_map`]
 [
 The component map that represents the assignment of vertices to
 distinct components in the graph. The `ComponentMap` must be
 a model of [BoostReadablePropertyMap]. The `value_type` should be
 integral, preferably the same as `vertices_size_type` for the
 graph. The `key_type` must be the graph's `vertex_descriptor`.

 *Default* /not given/
 ]
 ]
 [
 [optional, in] [`ColorMap _color_map`]
 [
 This is used by the [boost_connected_components] algorithm to keep
 track of its progress through the graph. The type `ColorMap` must
 be a model of [BoostReadWritePropertyMap], it's `key_type` must be
 the `vertex_descriptor` type of `_graph` and its `value_type` must
 be a model of [BoostColorValue].

 *Default* /not given/
 ]
 ]
 [
 [optional, in] [`VertexIndexMap _vertex_index_map`]
 [
 This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
 This parameter is necessary only `Graph` does not have builtin vertices
 and/or a correct ordering on them.

 *Default* `get(vertex_index, g)`
 ]
 ]
]

[h5 Return Value]
This function returns the number of connected components. When the return value of
this function is equal to `1`, then the graph is a single connected component.

[h5 Complexity]
This function has time complexity /O(V)/ and space complexity /O(V)/ (since each
vertex is assigned to a component in the _components_vector).

[h5 Examples]

[note These are going to be expanded...]

When a component map is not provided:

 typedef undirected_graph<> Graph;
 typedef graph_traits<Graph>::vertex_descriptor Vertex;
 typedef vector<Vertex> Component;
 typedef vector<Component> ComponentList;

 Graph g;
 // build a graph

 ComponentList components;
 connected_components(g, components);

 size_t c = 0;
 BOOST_FOREACH(Component comp, components) {
 cout << "component: " << c++ << " : ";
 BOOST_FOREACH(Vertex v, comp) {
 cout << get(vertex_index, g, v) << " ";
 }
 cout << "\n";
 }

If the component map /is/ available...

 // write some code to that effect.

[endsect]
\ No newline at end of file
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 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 42,7 +42,6 @@
[section Connectivity]
[include connected_components.qbk]
[include strong_components.qbk]
[include connectivity.qbk]
[endsect]
[section Shortest Paths]
@@ 52,8 +51,12 @@
[endsect]
[section Subgraph]
[include bron_kerbosch_clique.qbk]
[include tiernan_cycle.qbk]
+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]
[endsect]
[section Maximum Flow]
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 20070802 12:09:39 EDT (Thu, 02 Aug 2007)
@@ 5,44 +5,68 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
[section Tiernan Cycles]
+[section Tiernan All Cycles]
template <typename Graph, typename Visitor>
 void
 tiernan_find_cycles(const Graph& g, Visitor vis)
+ inline 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)
+
+ 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.
+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_visit_cycles()` function is designed to work on directed graph, but
+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.
+Note that the default minimum cycle length differs between directeed 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_find_cycles.hpp`
+`boost/graph/tiernan_all_cycles.hpp`
[heading Parameters]

[table
[[Type] [Parameter] [Description]]
[
[required, in] [`const Graph& g`]
[
 The graph for which cliques are being visited. The `Graph` type must
 /approximate/ the [BoostAdjacencyMatrix] in that it must implement
 the `edge(u,v,g)` function. It is not, however, required to return
 in constant time. Note that most graph types provide this function,
 including [boost_adjacency_list], [boost_undirected_graph], and
 [boost_directed_graph].
+ 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
+ [BoostIncidenceGraph] and [BoostVertexIndexGraph] concepts.
]
]
[
[required, in] [`Visitor vis`]
[
 The visitor object to the algorithm. This `Visitor` class must
 model the [BoostCliqueVisitor] class.
+ The visitor object to the algorithm.
+
+ *Requirements:* This `Visitor` class must model the
+ [BoostCliqueVisitor] class.
]
]
]
@@ 51,11 +75,16 @@
This function does not return a value.
[h5 Complexity]
No complexity has been reported for this algorithm, but it is expected to
run in /O(P(g))/ where /P(g)/ is the number of distinct simple paths in the
graph /g/ (which can be very large).
+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.
[h5 Examples]
+From a practical standpoint, most (i.e., nearly all) real graphs will never approach
+a number of paths even remotely close to this number.
+[h5 Examples]
+Write an example.
[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