From: asutton_at_[hidden]
Date: 2007-07-24 14:01:04
Author: asutton
Date: 2007-07-24 14:01:02 EDT (Tue, 24 Jul 2007)
New Revision: 7523
URL: http://svn.boost.org/trac/boost/changeset/7523
Log:
Adding more reference docs
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk | 73 ++++++++++++++++++++++++++++++++-------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk | 5 +-
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 1
3 files changed, 63 insertions(+), 16 deletions(-)
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/clique.qbk 2007-07-24 14:01:02 EDT (Tue, 24 Jul 2007)
@@ -0,0 +1,68 @@
+[/
+ / 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 Clique]
+
+ struct clique_visitor
+ {
+ template <typename VertexSet>
+ void clique(VertexSet)
+ { }
+ };
+
+ template <typename Graph, typename Visitor>
+ void
+ bron_kerbosch_visit_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. See the
+
+The `bron_kerbosch_visit_cliques()` function is intended for use with 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`
+
+[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].
+ ]
+ ]
+ [
+ [required, in] [`Visitor vis`]
+ [
+ The visitor object to the algorithm. This `Visitor` class must
+ model the `CliqueVisitor` class.
+ ]
+ ]
+]
+
+[h5 Return Value]
+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.
+
+[h5 Examples]
+
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk 2007-07-24 14:01:02 EDT (Tue, 24 Jul 2007)
@@ -56,7 +56,8 @@
[
[required, in] [`const Graph& g`]
[
- The graph object for which the distribution will be computed.
+ The graph object for which the measure will be computed. The
+ `Graph` type is required to be a model of [BoostVertexListGraph].
]
]
[
@@ -87,26 +88,70 @@
]
]
-[note
-The requirements on `T` indicate a particularly interesting problem because
-division is basically [SgiMonoid] operation - which is probably one of the
-more esoteric concepts in the STL. Curiously, the `identity_element()` operation
-which is an SGI extension and apparently not part of the actual standard.
-
-The correct implemention of `detail::sum_distances()` should take a monoid
-type and use `identity_element(f)` for initializaiton and `f` for the combination.
-]
-
[h5 Return Value]
The `closeness()` function returns the closeness of the vertex for which
`dist` was computed. The closeness is defined in the formula above.
[h5 Complexity]
-The `closeness()` function has /O(n)/ time complexity.
+The `closeness()` function has /O(V)/ time complexity.
[h5 Examples]
-[note
-Write some examples...
+This example computes shows the construction of a simple undirected graph and
+illustrates how to compute the `closeness()` for a vertex.
+
+[figure
+ images/reference/geodesic.png
+ [*Figure 1.] A simple undirected, unweighted graph.
+]
+
+This graph can be constructed programmatically as:
+
+ typedef undirected_graph<> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // Instantiate the graph and vector of vertices.
+ Graph g;
+ vector<Vertex> v(10);
+
+ // Add vertices to the graph, recording their descriptors into
+ // the vertex vector.
+ for(size_t i = 0; i < 10; ++i) {
+ v[i] = add_vertex(g);
+ }
+
+ // Connect the vertices by adding edges to the graph. This builds
+ // the graph shown in Figure 1.
+ add_edge(v[0], v[1], g); add_edge(v[1], v[2], g);
+ add_edge(v[1], v[3], g); add_edge(v[2], v[4], g);
+ add_edge(v[3], v[5], g); add_edge(v[4], v[6], g);
+ add_edge(v[4], v[7], g); add_edge(v[4], v[8], g);
+ add_edge(v[5], v[8], g); add_edge(v[6], v[9], g);
+ add_edge(v[7], v[9], g); add_edge(v[8], v[9], g);
+
+ // Initialize an exterior property for recording the distances
+ // to every vertex in the graph.
+ typedef exterior_property<Graph, int> DistanceProperty;
+ typedef DistanceProperty::container_type DistanceContainer;
+ typedef DistanceProperty::map_type DistanceMap;
+ DistanceContainer distances(10);
+ DistanceMap dist(make_property_map(dists));
+
+ // Initialize the distance to-self of vertex 0 and run a breadth-first
+ // search on the graph to compute the distance of the shortest path
+ // from vertex 0 to all others.
+ dist[v[0]] = 0;
+ breadth_first_search(g, v[0],
+ visitor(make_bfs_visitor(record_distances(dist, on_tree_edge())))
+ );
+
+Computing the `closeness()` for vertex 0 is trivial.
+
+ cout << "closeness == " << closeness(g, dist) << end;
+
+The output of this program is roughly:
+
+[pre
+mean geodesic distance == 0.035
]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk 2007-07-24 14:01:02 EDT (Tue, 24 Jul 2007)
@@ -71,7 +71,8 @@
[
[required, in] [`const Graph& g`]
[
- The graph object for which the distribution will be computed.
+ The graph object for which the measure will be computed. The
+ `Graph` type is required to be a model of [BoostVertexListGraph].
]
]
[
@@ -126,7 +127,7 @@
[h5 Complexity]
The `geodesic_distance()` function has /O(1)/ time complexity.
-The `mean_geodesic_distance()` function has /O(n)/ time complexity.
+The `mean_geodesic_distance()` function has /O(V)/ time complexity.
[h5 Examples]
This example computes shows the construction of a simple undirected graph and
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-07-24 14:01:02 EDT (Tue, 24 Jul 2007)
@@ -63,6 +63,7 @@
[include distributions.qbk]
[include geodesic.qbk]
[include closeness.qbk]
+[include eccentricity.qbk]
[endsect]
[endsect]