[Boost-commit] svn:boost r7523

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]