|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-02 12:09:40
Author: asutton
Date: 2007-08-02 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 2007-08-02 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 2007-08-02 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 2007-08-02 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 2007-08-02 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 2007-08-02 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 non-constant
+ 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 constant-time 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 2007-08-02 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 pseudo-C++):
-
- _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 built-in 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 2007-08-02 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 2007-08-02 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 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_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
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