From: asutton_at_[hidden]
Date: 2007-07-18 13:41:48
Author: asutton
Date: 2007-07-18 13:41:47 EDT (Wed, 18 Jul 2007)
New Revision: 7468
URL: http://svn.boost.org/trac/boost/changeset/7468
Log:
Added some comments to the clique header (mainly bibliographic).
Continued reworking the documentation for the connectivity function.
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/clique.hpp | 73 ++++++++++++++++++++++++-----
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk | 97 +++++++++++++++++++++++++++------------
2 files changed, 125 insertions(+), 45 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/clique.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clique.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/clique.hpp 2007-07-18 13:41:47 EDT (Wed, 18 Jul 2007)
@@ -10,10 +10,55 @@
namespace boost
{
- // I'm basically reimplementing the networkX version of the
- // algorithm since it's a little more clear than the published
- // version. It also appears to operate on a non-matrix structure
- // which makes the translation a little easier.
+ // The algorithm implemented in this paper is based on the so-called
+ // Algorithm 457, published as:
+ //
+ // @article{362367,
+ // author = {Coen Bron and Joep Kerbosch},
+ // title = {Algorithm 457: finding all cliques of an undirected graph},
+ // journal = {Communications of the ACM},
+ // volume = {16},
+ // number = {9},
+ // year = {1973},
+ // issn = {0001-0782},
+ // pages = {575--577},
+ // doi = {http://doi.acm.org/10.1145/362342.362367},
+ // publisher = {ACM Press},
+ // address = {New York, NY, USA},
+ // }
+ //
+ // Sort of. This implementation is adapted from the 1st version of the
+ // algorithm and does not implement the candidate selection optimization
+ // described as published - it could, it just doesn't yet.
+ //
+ // The algorithm is given as proportional to (3.14)^(n/3) power. This is
+ // not the same as O(...), but based on time measures and approximation.
+ //
+ // Unfortunately, this implementation may be less efficient on non-
+ // AdjacencyMatrix modeled graphs due to the non-constant implementation
+ // of the edge(u,v,g) functions.
+ //
+ // TODO: It might be worthwhile to provide functionality for passing
+ // a connectivity matrix to improve the efficiency of those lookups
+ // when needed. This could simply be passed as a BooleanMatrix
+ // s.t. edge(u,v,B) returns true or false. This could easily be
+ // abstracted for adjacency matricies.
+ //
+ // The following paper is interesting for a number of reasons. First,
+ // it lists a number of other such algorithms and second, it describes
+ // a new algorithm (that does not appear to require the edge(u,v,g)
+ // function and appears fairly efficient. It is probably worth investigating.
+ //
+ // @article{DBLP:journals/tcs/TomitaTT06,
+ // author = {Etsuji Tomita and Akira Tanaka and Haruhisa Takahashi},
+ // title = {The worst-case time complexity for generating all maximal cliques and computational experiments},
+ // journal = {Theor. Comput. Sci.},
+ // volume = {363},
+ // number = {1},
+ // year = {2006},
+ // pages = {28-42}
+ // ee = {http://dx.doi.org/10.1016/j.tcs.2006.06.015}
+ // }
struct clique_visitor
{
@@ -26,20 +71,20 @@
{
template <typename Graph>
inline bool
- is_clique_connected(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- typename graph_traits<Graph>::undirected_category)
+ is_connected(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ typename graph_traits<Graph>::undirected_category)
{
return edge(u, v, g).second;
}
template <typename Graph>
inline bool
- is_clique_connected(const Graph& g,
- typename graph_traits<Graph>::vertex_descriptor u,
- typename graph_traits<Graph>::vertex_descriptor v,
- typename graph_traits<Graph>::directed_category)
+ is_connected(const Graph& g,
+ typename graph_traits<Graph>::vertex_descriptor u,
+ typename graph_traits<Graph>::vertex_descriptor v,
+ typename graph_traits<Graph>::directed_category)
{
// Note that this could alternate between using an or to determine
// full connectivity. I believe that this should produce strongly
@@ -49,7 +94,7 @@
//
// TODO: use this, the other, or allow switching based on a user-
// define strategy.
- return edge(u, v, g).second || edge(v, u, g).second;
+ return edge(u, v, g).second && edge(v, u, g).second;
}
template <typename Graph, typename Container>
@@ -62,7 +107,7 @@
typename graph_traits<Graph>::directed_category cat;
typename Container::const_iterator i, end = in.end();
for(i = in.begin(); i != end; ++i) {
- if(is_clique_connected(g, v, *i, cat)) {
+ if(is_connected(g, v, *i, cat)) {
out.push_back(*i);
}
}
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk 2007-07-18 13:41:47 EDT (Wed, 18 Jul 2007)
@@ -7,38 +7,73 @@
[section Connectivity Measures]
- size_t connectivity(
- _graph,
- _components,
- _component_map = ``['not given]``,
- _color_map = ``['not given]``,
- _vertex_index_map = get(vertex_index, _graph));
+ template <
+ typename Graph,
+ typename Components,
+ typename ComponentMap,
+ typename ColorMap,
+ typename VertexIndexMap
+ >
+ std::size_t
+ connectivity(
+ const Graph& _graph,
+ Components& _components,
+ 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 some convenience for working with resultant concept maps.
-functionality for working with connected components. The parameters have, with
-the exeption of `_components`, the same purpose and requirements as
-documented in [boost_connected_components].
-
-If specified, the `_components` argument is populated with the vertices that
-appear in each component. This is to say for example, that all vertices in the
-`_component_map` with component id 0, will be placed into the vertex set
-at index 0 of the `_components` argument.
+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.
+
+[$images/reference/connected_components_after.png]
+
+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++):
-This function returns the number of connected components in the graph. The graph
-is connected if and only if this function returns exactly 1.
+ _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`. The `_color_map`
and `_vertex_index_map` parameters are effectively ignored in this case.
[note
-First, this hasn't been tested very will for directed graphs. In fact, testing
+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`.
]
@@ -50,7 +85,7 @@
[table
[[Type] [Parameter] [Description]]
[
- [required, in] [`_graph`]
+ [required, in] [`Graph _graph`]
[
The graph object for which the distribution will be computed. If
the `_distribution` or `_in_distribution` arguments are supplied
@@ -60,10 +95,10 @@
]
]
[
- [required, out] [`_components`]
+ [required, out] [`Components _components`]
[
The components parameter provides storage for the assignment of
- vertices to components. The `_components` parameter must be a
+ 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
@@ -72,11 +107,11 @@
]
]
[
- [optional, in] [`_component_map`]
+ [optional, in] [`ComponentMap _component_map`]
[
The component map that represents the assignment of vertices to
- distinct components in the graph. The `_component_map` must be
- a model of [BoostReadablePropertyMap]. the `value_type` should be
+ 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`.
@@ -84,10 +119,10 @@
]
]
[
- [optional, in] [`_color_map`]
+ [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 of `ColorMap` must
+ 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].
@@ -96,10 +131,10 @@
]
]
[
- [optional, in] [`_vertex_index_map`]
+ [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
+ This parameter is necessary only `Graph` does not have built-in vertices
and/or a correct ordering on them.
*Default* `get(vertex_index, g)`
@@ -112,8 +147,8 @@
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.
+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]
@@ -134,7 +169,7 @@
size_t c = 0;
BOOST_FOREACH(Component comp, components) {
- cout << "component: " << c++ << ": ";
+ cout << "component: " << c++ << " : ";
BOOST_FOREACH(Vertex v, comp) {
cout << get(vertex_index, g, v) << " ";
}