|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-21 14:02:36
Author: asutton
Date: 2007-08-21 14:02:35 EDT (Tue, 21 Aug 2007)
New Revision: 38829
URL: http://svn.boost.org/trac/boost/changeset/38829
Log:
Finsihed B&K docs.
Rearranged the degree_centrality stuff a bit
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk | 9 ++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/bron_kerbosch_all_cliques.qbk | 139 +++++++++++++++++++++++++++++++++----
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk | 144 ++++++++++++++++++++--------------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/tiernan_all_cycles.qbk | 5
4 files changed, 206 insertions(+), 91 deletions(-)
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-21 14:02:35 EDT (Tue, 21 Aug 2007)
@@ -78,6 +78,13 @@
boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.__tiernan_girth_and_circumference___
[^tiernan_girth_and_circumference()]]]
+[template bron_kerbosch_all_cliques[] [link
+ boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.__bron_kerbosch_all_cliques___
+ [^bron_kerbosch_all_cliques()]]]
+[template bron_kerbosch_clique_number[] [link
+ boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.__bron_kerbosch_clique_number___
+ [^bron_kerbosch_clique_number()]]]
+
[/ Measures /]
[template degree_centrality[] [link
@@ -136,3 +143,5 @@
[import ../examples/eccentricity.cpp]
[import ../examples/tiernan_print_cycles.cpp]
[import ../examples/tiernan_girth_circumference.cpp]
+[import ../examples/bron_kerbosch_print_cliques.cpp]
+[import ../examples/bron_kerbosch_clique_number.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-21 14:02:35 EDT (Tue, 21 Aug 2007)
@@ -9,24 +9,48 @@
[template ex_bron_kerbosch_printing_cliques[] [link
boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.examples.printing_cliques
Printing Cliques Example]]
+[template ex_bron_kerbosch_clique_number[] [link
+ boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.examples.clique_number
+ Clique Number Example]]
[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.
+each clique is found. A clique is formally defined as a maxiamally connected
+subgraph of a graph. This means that there are no more (and no fewer) vertices
+in the graph that are connected to all other vertices in the graph. A vertex can
+participate in many cliques. Note that the smallest clique contains two vertices
+since each vertex is connected to the other.
+
+Consider the social network (represented by an undirected graph) in Figure 1.
+
+[figure
+ images/reference/social_network.png
+ *Figure 1.* A network of friends.
+]
-For directed graphs, a /directed clique/ is similarly defined. For each pair
-of vertices /u/ and /v/ in a directed clique, there are edges /(u,v)/ and /(v,u)/
-that connect them.
+There are a number of cliques in the graph. We can easily identify the two largest:
-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.
+* Scott, Jill, and Mary
+* Frank, Howard, and Anne
+
+There are six other cliques represented by pairs of actors. Note that the Scott,
+Mary, Frank, and Laurie do not form a clique because Mary and Frank are not directly
+connected. See the [ex_bron_kerbosch_printing_cliques] for more details.
+
+The /clique number/ of a graph is defined as the size (the number of vertices) of
+the largest clique in the graph. The social network in Figure 1 has a clique number
+of 3. The [bron_kerbosch_clique_number] implements this measure. See the
+[ex_bron_kerbosch_clique_number] for an example of its use.
-The Bron-Kerbosch algorithm was originally developed for undirected graphs, but
-will work for directed graphs as well (possibly at added cost).
+The Bron-Kerbosch algorithm was originally developed to operate over adjacency
+matrices representing /undirected graphs/. The algorithm can also be applied to
+/directed graphs/ using a more restrictive definition of a connected subgraph.
+A /directed clique/ is a maximally connected subgraph in which each pair of vertices
+/u/ and /v/ are connected by the edges /(u, v)/ and /(v, u)/.
+
+Although the algorithm can be used with adjacency list-based graph classes, it
+will perform less efficiently than an adjacency matrix. Also, running this algorithm
+on a directed graph will double the performance penalty (which is generally negligible).
[section [^bron_kerbosch_all_cliques()]]
#include <boost/graph/bron_kerbosch_all_cliques.hpp>
@@ -62,24 +86,105 @@
[CliqueVisitor] class.
]
]
+ [
+ [optional, in] [`std::size_t min`]
+ [
+ The minimum size of a clique to visit.
+
+ *Default:* 2 - the size of the smallest possible clique.
+ ]
+ ]
]
-[h5 Complexity]
+[heading Complexity]
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])].
Graphs that do not meet the constant-time requirements of the [AdjacencyMatrix]
-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.
+concept will incur additional runtime costs during execution (usually by a linear
+factor). Examples of such graphs include the [undirected_graph], [directed_graph],
+and the [adjacency_list] classes.
+
+Note that using the Bron-Kerbosch algorithm on directed graphs will doubles the
+amount of time it takes to determine edge connection.
[endsect]
+[section [^bron_kerbosch_clique_number()]]
+ #include <boost/graph/bron_kerbosch_all_cliques.hpp>
+
+ template <typename Graph, typename Visitor>
+ std::size_t bron_kerbosch_clique_number(const Graph& g)
+
+The `bron_kerbosch_clique_number()` function returns the size of the largest
+clique in a graph - its clique number.
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ 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 [AdjacencyMatrix],
+ [IncidenceGraph] concept and the [VertexIndexGraph]
+ concepts[footnote Any `Graph` typen that implements the `edge()`
+ function will satisfy the expression requirements for the
+ [AdjacencyMatrix], but may incur additional overhead due non-constant
+ implementations.].
+ ]
+ ]
+]
+
+[heading Return]
+The `bron_kerbosch_clique_number()` function returns the size of the largest
+clique in the the graph `g`.
+
+[heading Complexity]
+The `bron_kerbosch_clique_number()` function has the same complexity as the
+[bron_kerbosch_all_cliques] function.
+[endsect]
[section Examples]
[heading Printing Cliques]
-Write Me!
+This example demonstrates how to find and print all the cliques in a graph.
+
+[code_bron_kerbosch_print_cliques]
+
+If given the input file `social_network.graph`, which represents the social network
+pictured in Figure 1 of the
+[link boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.overview Overview],
+the program will produce the following output:
+
+[pre
+Scott Jill Mary
+Scott Bill
+Scott Frank
+Mary Laurie
+Bill Josh
+Josh Frank
+Frank Laurie
+Frank Anne Howard
+]
+
+[heading Clique Number]
+This example demonstrates the use of the [bron_kerbosch_clique_number] example.
+
+[code_bron_kerbosch_clique_number]
+
+If given the input file `social_network.graph`, which represents the social network
+pictured in Figure 1 of the
+[link boost_graph.reference.algorithms.subgraph.bron_kerbosch_all_cliques.overview Overview],
+the program will produce the following output:
+
+[pre
+clique number: 3
+]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk 2007-08-21 14:02:35 EDT (Tue, 21 Aug 2007)
@@ -123,20 +123,13 @@
returns in constant time.
[endsect]
-[section [^all_degree_centralities()]]
- #include <boost/graph/degree_centrality.hpp>
-
- template <typename Graph, typename CentralityMap>
- void all_degree_centralities(const Graph& g, CentralityMap cent);
-
- template <typename Graph, typename CentralityMap, typename Measure>
- void all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure);
+[section [^influence()]]
+ template <typename Graph, typename Vertex>
+ typename graph_traits<Graph>::degree_size_type
+ influence(const Graph& g, Vertex v);
-The `all_degree_centralities()` computes the degree centrality for each vertex in the
-graph, assigning the values to an output property map. Optionally, a degree measure
-can be given, specializing the computation of degree centrality. See the
-[degree_centrality_measures] section for more details on the influence and
-prestige measures.
+The `influence()` function the influence of the vertex to the caller. The influence
+of a vertex is the same as its out-degree.
[heading Parameters]
[table
@@ -146,54 +139,37 @@
[
The graph object for which the degree centralities will be computed.
- *Requirements:* The `Graph` type must model the [VertexListGraph]
- and [IncidenceGraph] concepts. If the `Measure` parameter is given
- as `prestige_measure`, then the graph must be a model of the
- [BidirectionalGraph] concept.
- ]
- ]
- [
- [required, out] [`CentralityMap cent`]
- [
- The property map that contains the degree centralities of all vertices
- in a graph after calling the `degree_centrality()` function.
-
- *Requirements:* The `CentralityMap` type must be a model of the
- [WritablePropertyMap] concept. The `key_type` of the map must
- be the same as the `vertex_descriptor` of the `Graph` type. If the
- `Measure` parameter is given in the call, then the `value_type`
- of `CentralityMap` must be the same as `Measure::degree_type`.
- Otherwise, the `value_type` must be the same as the `degree_size_type`
- of the graph.
+ *Requirements:* The `Graph` type must be a model of the [IncidenceGraph]
+ concept. If the `Measure` parameter is given as `prestige_measure`,
+ then the graph must be a model of the [BidirectionalGraph] concept.
]
]
[
- [optional, in] [`Measure measure`]
+ [required, in] [`Vertex v`]
[
- The `measure` parameter allows the caller to override the default
- computation of degree centrality for a vertex.
+ The vertex descriptor for which the degree centrality is computed.
- *Requirements:* The `Measure` type must be a model of the
- [DegreeMeasure] concept. The `degree_type` of `Measure` must
- be the same as the `value_type` of the `CentralityMap` type.
+ *Requirements:* The `Vertex` type must be the same as the `vertex_descriptor`
+ of the `Graph` parameter.
]
]
]
+[heading Return Value]
+The `influence()` function returns the influence of the vertex, which is the same
+as its out-degree.
+
[heading Complexity]
-The `all_degree_centralities()` function returns in /O(n*O(M))/ where /n/ is the
-number of vertices in the graph and /M/ is a measure of a vertex. If the measure
-is not specified or is `influence_measure` or `prestige_measure`, this function
-returns in linear time.
+The `influence()` function returns in constant time.
[endsect]
-[section [^influence()]]
+[section [^prestige()]]
template <typename Graph, typename Vertex>
typename graph_traits<Graph>::degree_size_type
- influence(const Graph& g, Vertex v);
+ prestige(const Graph& g, Vertex v);
-The `influence()` function the influence of the vertex to the caller. The influence
-of a vertex is the same as its out-degree.
+The `prestige()` function the prestige of the vertex to the caller. The prestige
+of a vertex is the same as its in-degree.
[heading Parameters]
[table
@@ -220,22 +196,27 @@
]
[heading Return Value]
-The `influence()` function returns the influence of the vertex, which is the same
+The `prestige()` function returns the influence of the vertex, which is the same
as its out-degree.
[heading Complexity]
-The `influence()` function returns in constant time.
+The `prestige()` returns in constant time.
[endsect]
-[section [^all_influence_values()]]
+[section [^all_degree_centralities()]]
#include <boost/graph/degree_centrality.hpp>
template <typename Graph, typename CentralityMap>
- void all_influence_values(const Graph& g, CentralityMap cent);
+ void all_degree_centralities(const Graph& g, CentralityMap cent);
+ template <typename Graph, typename CentralityMap, typename Measure>
+ void all_degree_centralities(const Graph& g, CentralityMap cent, Measure measure);
-The `all_influence_values()` function computes the influence of each vertex in the
-graph, assigning the values to an output property map.
+The `all_degree_centralities()` computes the degree centrality for each vertex in the
+graph, assigning the values to an output property map. Optionally, a degree measure
+can be given, specializing the computation of degree centrality. See the
+[degree_centrality_measures] section for more details on the influence and
+prestige measures.
[heading Parameters]
[table
@@ -266,20 +247,35 @@
of the graph.
]
]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The `measure` parameter allows the caller to override the default
+ computation of degree centrality for a vertex.
+
+ *Requirements:* The `Measure` type must be a model of the
+ [DegreeMeasure] concept. The `degree_type` of `Measure` must
+ be the same as the `value_type` of the `CentralityMap` type.
+ ]
+ ]
]
[heading Complexity]
-The `all_influence_values()` function returns linear time with respect to the
-number of vertices in the graph.
+The `all_degree_centralities()` function returns in /O(n*O(M))/ where /n/ is the
+number of vertices in the graph and /M/ is a measure of a vertex. If the measure
+is not specified or is `influence_measure` or `prestige_measure`, this function
+returns in linear time.
[endsect]
-[section [^prestige()]]
- template <typename Graph, typename Vertex>
- typename graph_traits<Graph>::degree_size_type
- prestige(const Graph& g, Vertex v);
+[section [^all_influence_values()]]
+ #include <boost/graph/degree_centrality.hpp>
+
+ template <typename Graph, typename CentralityMap>
+ void all_influence_values(const Graph& g, CentralityMap cent);
-The `prestige()` function the prestige of the vertex to the caller. The prestige
-of a vertex is the same as its in-degree.
+
+The `all_influence_values()` function computes the influence of each vertex in the
+graph, assigning the values to an output property map.
[heading Parameters]
[table
@@ -289,28 +285,32 @@
[
The graph object for which the degree centralities will be computed.
- *Requirements:* The `Graph` type must be a model of the [IncidenceGraph]
- concept. If the `Measure` parameter is given as `prestige_measure`,
- then the graph must be a model of the [BidirectionalGraph] concept.
+ *Requirements:* The `Graph` type must model the [VertexListGraph]
+ and [IncidenceGraph] concepts. If the `Measure` parameter is given
+ as `prestige_measure`, then the graph must be a model of the
+ [BidirectionalGraph] concept.
]
]
[
- [required, in] [`Vertex v`]
+ [required, out] [`CentralityMap cent`]
[
- The vertex descriptor for which the degree centrality is computed.
+ The property map that contains the degree centralities of all vertices
+ in a graph after calling the `degree_centrality()` function.
- *Requirements:* The `Vertex` type must be the same as the `vertex_descriptor`
- of the `Graph` parameter.
+ *Requirements:* The `CentralityMap` type must be a model of the
+ [WritablePropertyMap] concept. The `key_type` of the map must
+ be the same as the `vertex_descriptor` of the `Graph` type. If the
+ `Measure` parameter is given in the call, then the `value_type`
+ of `CentralityMap` must be the same as `Measure::degree_type`.
+ Otherwise, the `value_type` must be the same as the `degree_size_type`
+ of the graph.
]
]
]
-[heading Return Value]
-The `prestige()` function returns the influence of the vertex, which is the same
-as its out-degree.
-
[heading Complexity]
-The `prestige()` returns in constant time.
+The `all_influence_values()` function returns linear time with respect to the
+number of vertices in the graph.
[endsect]
[section [^all_prestige_values()]]
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-21 14:02:35 EDT (Tue, 21 Aug 2007)
@@ -10,8 +10,8 @@
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]]
+ boost_graph.reference.algorithms.subgraph.tiernan_all_cycles.examples.girth_and_circumference
+ Girth and Circumference Example]]
[heading Overview]
This function uses the Tiernan algorithm to find all /cycles/ within a given graph,
@@ -63,6 +63,7 @@
/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.
+See the [ex_tiernan_girth_circumference] for details.
[section [^tiernan_all_cycles()]]
#include <boost/graph/tiernan_all_cycles.hpp>
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