
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070723 11:04:45
Author: asutton
Date: 20070723 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 20070723 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 userdefined type by passing a dummy instance.
+This is useful if the `value_type` of `DistanceMap` is a userdefined or
+otherwise nontrivial.
+
+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 20070723 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
BoostCommit 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