[Boost-commit] svn:boost r7514

From: asutton_at_[hidden]
Date: 2007-07-23 11:04:45

Author: asutton
Date: 2007-07-23 11:04:45 EDT (Mon, 23 Jul 2007)
New Revision: 7514
URL: http://svn.boost.org/trac/boost/changeset/7514

Log:
Added docs for closeness.
Fixing typos in geodesics.

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk
Text files modified: 
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk |    26 +++++++++++---------------              
   1 files changed, 11 insertions(+), 15 deletions(-)

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk	2007-07-23 11:04:45 EDT (Mon, 23 Jul 2007)
@@ -0,0 +1,113 @@
+[/
+ / 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 Closeness]
+
+    template <typename Graph, typename DistanceMap>
+    property_traits<DistanceMap>::value_type
+    closeness(const Graph&g, DistanceMap dist)
+
+    template <typename Graph, typename DistanceMap, typename T>
+    T
+    closeness(const Graph& g, DistanceMap dist, const T& dummy)
+
+These functions compute the /closeness/ of vertices in a graph. The /closeness/
+of a vertex is defined as the reciprocal of the sum of /geodesic distances/
+(shortest paths) to all other vertices in the graph as given by the formula:
+
+[$images/eq/closeness.png]
+
+where ['d[sub G](u,v)] is the shortest path from /u/ to /v/. It is important to
+note that these functions /do not/ compute these paths or record their distances
+
+Boost.Graph provides two shortest paths algorithms: [boost_dijkstra_shortest_paths]
+and [boost_bellman_ford_shortest_paths]. Optionally, if the target graph is
+an unweighted, undirected graph, shortest paths can be recorded using
+[boost_breadth_first_search]. Each of these algorithms takes as an input a
+vertex for which the shortest distances are being computed. The output of
+each of these algorithms is a `DistanceMap`, which is (in turn) used as the
+input of these functions. Note then, that these functions compute measures
+of the vertex for which the `DistanceMap` was computed.
+
+The `closeness()` functions return the closeness of the geodesic distances
+between a vertex and all others in the graph. The vertex for which this is computed
+is that for which `dist` was originally computed.
+
+The default (first) variant of this function computes and returns the
+closeness as a `double`. The second variant allows the average and return
+type to be computed as a user-defined type by passing a dummy instance.
+This is useful if the `value_type` of `DistanceMap` is a user-defined or
+otherwise non-trivial.
+
+If the graph is unconnected, then the closeness between any two vertices
+is zero.
+
+[heading Where Defined]
+`boost/graph/distance.hpp`
+
+[heading Parameters]
+
+[table
+    [[Type] [Parameter] [Description]]
+    [
+        [required, in] [`const Graph& g`]
+        [
+            The graph object for which the distribution will be computed.
+        ]
+    ]
+    [
+        [required, in] [`vertex_descriptor v`]
+        [
+            The target vertex to which the geodisic distance is returned. The
+            source vertex is made implicit by the `DistanceMap`.
+        ]
+    ]
+    [
+        [required, in] [`DistanceMap dist`]
+        [
+            The `dist` parameter provides the distances of the shortest paths
+            from one source vertex to all others in the graph. The `DistanceMap`
+            must be a model of [BoostReadWritePropertyMap], they `key_type` must
+            be the `vertex_descriptor` of `Graph`.
+        ]
+    ]
+    [
+        [required, in] [`const T& dummy`]
+        [
+            An unused instance of the type returned by the `mean_geodesic_distance()`
+            function. If specified, the measure will be computed as an average of
+            this type. This type must essentially be numeric, as it is required to
+            a) support division, b) be initialized with an integer type, and c)
+            have a default of 0.
+        ]
+    ]
+]
+
+[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.
+
+[h5 Examples]
+[note
+Write some examples...
+]
+
+
+[endsect]
\ No newline at end of file

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-23 11:04:45 EDT (Mon, 23 Jul 2007)
@@ -14,7 +14,7 @@
                       DistanceMap dist)
 
     template <typename Graph, typename DistanceMap>
-    inline double
+    double
     mean_geodesic_distance(const Graph& g, DistanceMap dist)
 
     template <typename Graph, typename DistanceMap, typename T>
@@ -29,23 +29,23 @@
 Boost.Graph provides two shortest paths algorithms: [boost_dijkstra_shortest_paths]
 and [boost_bellman_ford_shortest_paths]. Optionally, if the target graph is
 an unweighted, undirected graph, shortest paths can be recorded using
-[boost_breadh_first_search]. Each of these algorithms takes as an input a
+[boost_breadth_first_search]. Each of these algorithms takes as an input a
 vertex for which the shortest distances are being computed. The output of
 each of these algorithms is a `DistanceMap`, which is (in turn) used as the
 input of these functions. Note then, that these functions compute measures
 of the vertex for which `dist` was computed.
 
-The `geodesic_distance(g,dist)` function returns the length of the shortest path
+The `geodesic_distance()` function returns the length of the shortest path
 between two vertices. The source vertex is that for which the `DistanceMap`
 was computed and the target vertex, `v`, is supplied as a parameter. This
 function is an alias for:
 
     dist[v];
 
-The `mean_geodesic_distance(g,dist,T())` functions return the (arithmatic) mean
+The `mean_geodesic_distance()` functions return the (arithmatic) mean
 of the geodesic distances between a vertex and all others in the graph. The
-vertex for which this is computed is that for which the `DistanceMap` was
-originally computed. The mean geodesic distance is implemeted as:
+vertex for which this is computed is that for which `dist` originally \
+computed. The mean geodesic distance is implemeted as:
 
 [$images/eq/mean_geodesic.png]
 
@@ -71,11 +71,7 @@
     [
         [required, in] [`const Graph& g`]
         [
-            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].
+            The graph object for which the distribution will be computed.
         ]
     ]
     [
@@ -121,16 +117,16 @@
 ]
 
 [h5 Return Value]
-The `geodesic_distance(g,v,dist)` function returns the distance of the shortest
+The `geodesic_distance()` function returns the distance of the shortest
 path to `v`.
 
-The `mean_geodesic_distance(g,dist)` function returns the (arithmatic) mean of
+The `mean_geodesic_distance()` function returns the (arithmatic) mean of
 the shortest distances to all other vertices.
 
 [h5 Complexity]
-The `geodesic_distance(g,v,dist)` has O(1) time complexity.
+The `geodesic_distance()` function has /O(1)/ time complexity.
 
-The `mean_geodesic_distance(g,dist)` has O(n) time complexity.
+The `mean_geodesic_distance()` function has /O(n)/ time complexity.
 
 [h5 Examples]
 This example computes shows the construction of a simple undirected graph and