Boost logo

Boost-Commit :

From: asutton_at_[hidden]
Date: 2007-07-30 12:27:11


Author: asutton
Date: 2007-07-30 12:27:10 EDT (Mon, 30 Jul 2007)
New Revision: 7595
URL: http://svn.boost.org/trac/boost/changeset/7595

Log:
Extrapolating closeness centrality documentation framework.

Added:
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness/
   sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness/total_geodesic.qbk (contents, props changed)

Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness/total_geodesic.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness/total_geodesic.qbk 2007-07-30 12:27:10 EDT (Mon, 30 Jul 2007)
@@ -0,0 +1,105 @@
+[/
+ / 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 Total Geodesic Distance]
+
+ template <typename Graph, typename DistanceMap>
+ inline float total_geodesic_distance(const Graph& g, DistanceMap dist)
+
+ template <typename ResultType, typename Graph, typename DistanceMap>
+ inline ResultType total_geodesic_distance(const Graph& g, DistanceMap dist)
+
+ template <typename Graph, typename DistanceMatrix, typename ClosenessMap>
+ inline void
+ all_total_geodesic_distances(const Graph& g,
+ DistanceMatrix& dist,
+ ClosenessMap& close)
+
+The /total geodesic distance/ for a vertex is the sum of all geodesic
+distances (shortest paths) from a vertex /u/ to all other vertices in a graph.
+It's value is formally given as:
+
+[$images/eq/total_geodesic.png]
+
+[heading Where Defined]
+`boost/graph/closeness_centrality.qbk`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [template] [`ResultType`]
+ [
+ The `ResultType` template parmeter explitly specifies the the
+ return type of the `total_geodesic_distance()` function. If not
+ given, the return type is `float`.
+
+ *Requirements:* The return type is required to model the
+ [BoostNumericValue] concept.
+ ]
+ ]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which vertex measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostVertexListGraph] concept.
+ ]
+ ]
+ [
+ [required, in] [`DistanceMap dist`]
+ [
+ The `dist` parameter provides, given a vertex /v/, the shortest
+ distance from another vertex /u/. The distance map is computed for
+ the vertex /u/, and the distance from /u/ to itself should be 0
+ (i.e., `dist[u] == 0`).
+
+ *Requirements:* `DistanceMap` must be a model of [BoostReadablePropertyMap].
+ The `key_type` of the distance map must be the same as the `vertex_descriptor`
+ of the `Graph` parameter. The `value_type` is required to be a model of
+ [BoostNumericValue].
+ ]
+ ]
+ [
+ [required, in] [`DistanceMatrix dist`]
+ [
+ The `dist` parameter provides, given vertices /u/ and /v/, the
+ length of the shortest path between the two vertices. Note that the
+ distance between a vertex and itself should be 0 (i.e., `dist[u][u] == 0`).
+
+ *Requirements:* `DistanceMatrix` must be a model of [BoostPropertyMatrix].
+ The `key_type` of the distance matrixc must be the same as the
+ `vertex_descriptor` of the `Graph` parameter. The `value_type` is
+ required to be a model of [BoostNumericValue].
+ ]
+ ]
+ [
+ [required, out] [`ClosenessMap close`]
+ [
+ The `close` parameter stores the output of the computed closeness (or
+ distance).
+
+ *Requirements:* The type of `close` must be model the
+ [BoostPropertyMap] and [BoostWritablePropertyMap] concepts. The `key_type`
+ of the property map must be the same as the `vertex_descriptor` of
+ the `Graph` type, and the `value_type` must be a model of [BoostNumericValue].
+ ]
+ ]
+]
+
+[heading Complexity]
+The `total_geodesic_distance()` function is linear with respect to the number
+of vertices in the graph.
+
+The `all_total_geodesic_distances()` function is /O(n[super 2])/ with /n/ the
+number of vertices in the graph.
+
+[heading Example]
+Write a decent example for all of these...
+
+[endsect]
\ No newline at end of file


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