
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070801 09:52:01
Author: asutton
Date: 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
New Revision: 38335
URL: http://svn.boost.org/trac/boost/changeset/38335
Log:
Wrote and modified lots of documents
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/inverse_geodesic.tex (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic_directed.tex (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic_undirected.tex (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/total_geodesic.tex (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk (contents, props changed)
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/exterior_property.qbk
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness/
Properties modified:
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic.tex (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2  2
sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk  8
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk  5
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk  1
sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk  8
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/Makefile  8
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex  5
sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic.tex  5
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk  274 ++++++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk  1
10 files changed, 145 insertions(+), 172 deletions()
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/Jamfile.v2 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 21,7 +21,7 @@
# How far down sections get TOC's
<xsl:param>toc.section.depth=10
# Max depth in each TOC:
 <xsl:param>toc.max.depth=4
+ <xsl:param>toc.max.depth=3
# How far down we go with TOC's
<xsl:param>generate.section.toc.level=10
# Logo location:
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_concepts.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 17,7 +17,7 @@
[template BoostWritablePropertyMap[] [@http://www.boost.org/libs/property_map/WritablePropertyMap.html WritablePropertyMap]]
[template BoostReadWritePropertyMap[] [@http://www.boost.org/libs/property_map/ReadWritePropertyMap.html ReadWritePropertyMap]]
[template BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor Descriptor]]
+
[template BoostGraph[] [link boost_graph.concepts.graph_concepts.graph Graph]]
[template BoostIncidenceGraph[] [link boost_graph.concepts.graph_concepts.incidence_graph IncidenceGraph]]
[template BoostBidirectionalGraph[] [link boost_graph.concepts.graph_concepts.bidirectional_graph BidirectionalGraph]]
@@ 42,4 +42,8 @@
[/ A bunch of miscellaneus concepts]
[template BoostColorValue[] [link boost_graph.concepts.miscellaneous_concepts.color_value ColorValue]]
[template BoostExteriorProperty[] [link boost_graph.concepts.utility.exterior_property [^ExteriorProperty]]]
\ No newline at end of file
+[template BoostDescriptor[] [link boost_graph.concepts.graph_concepts.descriptor [^Descriptor]]]
+[template BoostNumericValue[] [link boost_graph.concepts.general_concepts.numeric_value [^NumericValue]]]
+[template BoostPropertyMap[] [link boost_graph.concepts.general_concepts.property_map [^PropertyMap]]]
+[template BoostPropertyMatrix[] [link boost_graph.concepts.general_concepts.property_matrix [^PropertyMatrix]]]
+[template BoostDistanceMeasure[] [link boost_graph.concepts.general_concepts.distance_measure [^DistanceMeasure]]]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 32,8 +32,11 @@
[/ Path algorithms /]
[template boost_dijkstra_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.dijkstra_shortest_paths [^dijkstra_shortest_paths()]]]
[template boost_bellman_ford_shortest_paths[] [link boost_graph.reference_guide.algorithms.shortest_path_algorithms.bellman_ford_shortest_paths [^bellman_ford_shortest_paths()]]]
+[template boost_floyd_warshall_all_pairs_shortest_paths[] [link boost_graph [^floyd_warshall_all_pairs_shortest_paths]]]
+
[template boost_connected_components[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
[template boost_exterior_vertex_property[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
\ No newline at end of file
+[template boost_exterior_vertex_property[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
+[template boost_exterior_edge_property[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/distance_measure.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,61 @@
+[/
+ / 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 Distance Measure]
+The [BoostDistanceMeasure] concept defines requirements for function objects
+that are used in computations of distances.
+
+[heading Notation]
+The following expressions are used within this document:
+[table
+ [[Expression] [Description]]
+ [[M] [A type modeling the [BoostDistanceMeasure] concept.]]
+ [[m] [An object of type `M`.]]
+ [[d] [An object of type `M::distance_type`.]]
+ [[g] [An object whose type models the [BoostGraph] concept.]]
+]
+
+[heading Associated Types]
+[table
+ [[Name] [Type] [Description]]
+ [
+ [Distance Type]
+ [`M::distance_type`]
+ [
+ The type used to measure distances in graphs.
+
+ *Requirements:* The `distance_type` must be a model of the
+ [BoostNumericValue] concept.
+ ]
+ ]
+ [
+ [Result Type]
+ [`M::result_type`]
+ [
+ The type being computed as the measure.
+
+ *Requirements:* The `result_type` must be a model of the
+ [BoostNumericValue] concept.
+ ]
+ ]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Function Call]
+ [`m(d, g)`]
+ [`M::result_type`]
+ [
+ Invoke the measure on the sum of distances `d`, with respect
+ to the graph `g`. This returns the result as type `result_type`.
+ ]
+ ]
+]
+
+[endsect]
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/exterior_property.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/exterior_property.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
+++ (empty file)
@@ 1,101 +0,0 @@
[/
 / 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 Exterior Property]
The `ExteriorProperty` concept defines requirements for the generic
declaration and initialization of exterior properties and their
proeprty maps for graphs. Exterior properties consist of two components:
a container that maps a descriptor to a property value and its property
map  the abstracted interface used by most Boost.Graph algorithms
for accessing vertex and edge properties.

[heading Notation]
The following expressions are used within this document:
[table
 [[Expression] [Description]]
 [[P] [An type modeling the `ExteriorProperty` concept.]]
]

[heading Associated Types]
[table
 [[Name] [Type] [Description]]
 [
 [Value Type]
 [`P::value_type`]
 [
 *Semantics:* The value type of the property map.

 *Requirements:* `value_type` must be [SgiAssignable] and
 [SgiDefaultConstructible].
 ]
 ]
 [
 [Value Type]
 [`P::key_type`]
 [
 *Semantics:* The key type of the property map. This type must be
 either an `edge_descriptor` or `vertex_descriptor`.

 *Requirements:* `key_type` must be [SgiCopyConstructible].
 ]
 ]
 [
 [Container Type]
 [`P::container_type`]
 [
 *Semantics:* The container type used to map objects of `key_type`
 to their associated property values of type `value_type`.

 *Requirements:* The container must be sizeconstructible in that
 it must have a constructor that takes a single argument: the number
 elements in the container.

 *Requirements:* The container type must implement the `operator []`
 function, taking an object of type `key_type` returning an object
 of type `value_type`.
 ]
 ]
 [
 [Property Map Type]
 [`P::map_type`]
 [
 *Semantics:* The property map type used to abstract the access
 graph properties.

 *Requirements:* `map_type` must model the [BoostReadWritePropertyMap]
 concept.
 ]
 ]
]

[heading Expressions]
[table
 [[Name] [Expression] [Result Type] [Description]]
 [
 [Property Map Initializer]
 [`make_property_map(c)`]
 [['unspecified]]
 [
 *Semantics:* The initializer function returns a value suitable for
 constructing the property map from the given container, `c`.

 *Requirements:* `c` is of type `P::container_type`.

 *Preconditions:* `c` is not empty.
 ]
 ]
]

[heading Complexity Guarantees]
The `P::container_type::operator []()` function must return, on average, in
constant time. The worstcase time is allowed to be linear with respect to
the number of keys.

[heading Models]
[boost_exterior_vertex_property]

[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/graphs.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 93,7 +93,6 @@
[[`add_edge(u,v,ep,g)`] [`std::pair<edge_descriptor,bool>`]]
]
[include descriptor.qbk]
[include graph.qbk]
[include incidence_graph.qbk]
[include bidirectional_graph.qbk]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/numeric_value.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,80 @@
+[/
+ / 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 Numeric Value]
+The [BoostNumericValue] concept describes requirements for a type to behave
+as if it were numeric. This concept is generally used by algorithms that
+typically operate on numeric types, but can be specialized to operate on
+userdefined numerics or discrete types that emulate numerics.
+
+This concept requires that its models be regular (i.e., default and copy
+constructible, assignable, and equality comparable). Additioanlly, this
+concept requires all common mathematical operators (i.e., addition, subtraction,
+multiplication and division).
+
+Finally, this concept requires that its models define appropriate values of
+zero and infinity. These are used within certain computations to represent
+infinite and zero states.
+
+[heading Refinement Of]
+[StdRegularType], [StdAddable], [StdSubtractable], [StdMulitplicable],
+[StdDivisible].
+
+[note Why is numeric not a standard concept?]
+
+[heading Notation]
+The following expressions are used within this document:
+[table
+ [[Expression] [Description]]
+ [[N] [A type modeling the [BoostNumericValue] concept.]]
+]
+
+[heading Associated Types]
+[table
+ [[Name] [Type] [Description]]
+ [
+ [Value Type]
+ [`numeric_value<N>::value_type`]
+ [
+ The underlying type of the numeric value.
+
+ *Requirements:* `N` is a [BoostNumericValue], and the `value_type`
+ and `N` must be the same type.
+ ]
+ ]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Zero Value]
+ [`numeric_value<N>::zero()`]
+ [`numeric_value<N>::value_type`]
+ [
+ Returns the zerovalue of the numeric type.
+ ]
+ ]
+ [
+ [Infinite Value]
+ [`numeric_value<N>::infinity()`]
+ [`numeric_value<N>::value_type`]
+ [
+ Returns the designated value of infinity for the numeric type.
+
+ *Notes:* Some types such as `float` and `double` have values
+ that represent infinity. For other types, this must be explicitly
+ designated. For builtin integral types this is often chosen to
+ be `std::numeric_limits<N>::max()`.
+ ]
+ ]
+]
+
+[heading Models]
+[boost_numeric_value]
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_map.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,100 @@
+[/
+ / 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 Property Map]
+The [BoostPropertyMap] concept provides additional requirements for other Boost
+property map objects. Specifically, this concept requires that property maps
+be constructed in a syntactically similar manner.
+
+[note
+Of the two most common property maps (iterator and associative), only the
+associative property map can satisfy these requirements. The only way to guarantee
+that generically cretead exterior property maps are correctly adapted to their
+underlying containers is to declare them using the [boost_exterior_vertex_property]
+or [boost_exterior_edge_property] types.
+]
+
+[heading Refinement Of]
+[BoostReadWritePropertyMap]
+
+[heading Notation]
+The following expressions are used within this document:
+[table
+ [[Expression] [Description]]
+ [[M] [A type modeling the [BoostPropertyMap] concept.]]
+ [[m] [An object of type `M`.]]
+ [[c] [An object whose type models the [SgiContainer] concept.]]
+ [[k] [A key to the property map.]]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Default Constructor]
+ [
+ `M m`
+
+ `M()`
+ ]
+ []
+ [
+ Construct a property map `m` with no underlying container.
+ This constructor is mainly used to convey type information to
+ generic functions since it cannot function without the container.
+
+ *Postconditions:* `m[k]` is invalid.
+ ]
+ ]
+ [
+ [Container Contructor]
+ [
+ `M m(c);`
+
+ `M m = c;`
+
+ `M(c)`
+ ]
+ []
+ [
+ Construct a property map `m` over the container `c`.
+ ]
+ ]
+]
+
+[heading Notes]
+This concept is imoprtant for two reasons. First, it provides a common way
+of declaring and constructing property maps, especially when using the exterior
+property declartive facilities. Second, it provides a mechanism for "slicing"
+a [BoostPropertyMatrix] using row access. The following example shows how
+both features can be used in a template function:
+
+ template<typename Graph>
+ void shortest_paths(const Graph&)
+ {
+ // Define some useful types
+ typedef typename exterior_vertex_property<Graph, int> Property;
+ typedef typename Property::matrix_type Matrix;
+ typedef typename Property::map_type Map;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ // Get the first vertex for later
+ Vertex u = *vertices(g).first;
+
+ // Construct a matrix and a map on the first row
+ Matrix matrix(num_vertices(g));
+ Map map = matrix[u]; // Note: map[v] == matrix[u][v]
+
+ // Run a shortest paths algorithm.
+ dijkstra_shortest_paths(g, matrix);
+
+ BOOST_ASSERT(matrix[u][u] == 0); // distance to self == 0
+ BOOST_ASSERT(map[u] == 0); // same as above
+ BOOST_ASSERT(matrix[u][u] == map[u]); // just making sure
+ }
+
+[endsect]
Added: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/property_matrix.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,137 @@
+[/
+ / 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 Property Matrix]
+The [BoostPropertyMatrix] concept requires types that model it to allow
+twodimensional arraylike access to its values using descriptor objects. Types
+that model this concepts are typically nested containers that use the vertex
+or edge desctipors of a graph to access the elements of the matrix.
+
+Note that the term "matrix" can be misleading since types that model this
+concept are not required to have a "square" structure. The term "matrix" applies
+to the use of doubleindexing to access its elements (i.e., m[u][v]).
+
+[note
+The two most common possible models of this type (nested vectors and unordered maps)
+cannot model this concept due to initialization requirements. The best way to
+ensure that a matrix models this type is to use the [boost_exterior_vertex_property]
+or [boost_exterior_edge_property] types.
+]
+
+[heading Notation]
+The following expressions are used within this document:
+[table
+ [[Expression] [Description]]
+ [[M] [A type modeling the [BoostPropertyMatrix] concept.]]
+ [[m] [An object of type `M`]]
+ [[n] [An unsigned integer]]
+]
+
+[heading Associated Types]
+[table
+ [[Name] [Type] [Description]]
+ [
+ [Key Type]
+ [`property_matrix_traits<M>::key_type`]
+ [
+ The type of key used to index values in the matrix.
+
+ *Requirements:* The `key_type` must be a model of a [BoostDescriptor]
+ and be the same type as either the `vertex_descriptor` or `edge_descriptor`
+ of the graph for which the matrix is declared.
+ ]
+ ]
+ [
+ [Value Type]
+ [`property_matrix_traits<M>::value_type`]
+ [
+ The type of values contained by the matrix.
+
+ *Requirements:* The `value_type` must be default construtible.
+ ]
+ ]
+ [
+ [Container Type]
+ [`property_matrix_traits<M>::container_type`]
+ [
+ The nested container that implements storage of the value type.
+
+ *Requirements:* The `container_type` is a [SgiContainer] such that
+ the `value_type` of the container is the same as the `value_type`
+ of the matrix. The container must be [NoConcept Idexable] with the
+ index type being the same as the `key_type` of the matrix.
+ ]
+ ]
+ [
+ [Matrix Type]
+ [`property_matrix_traits<M>::matrix_type`]
+ [
+ The type of the matrix.
+
+ *Requirements:* The `matrix_type` must be the same type as `M`.
+ ]
+ ]
+]
+
+[heading Expressions]
+[table
+ [[Name] [Expression] [Result Type] [Description]]
+ [
+ [Fill Contructor]
+ []
+ [
+ `M m(n)`
+
+ `M(n)`
+ ]
+ [
+ Contstruct the matrix with `n` elements. After construction,
+ accessing elements with the range defined by the square matrix
+ is guaranteed to succeed.
+
+ *Postcondition:* `m[k][k]` is valid if `k` is mapped to an element
+ within the matrix.
+ ]
+ ]
+ [
+ [Element Access]
+ [
+ `property_matrix_traits<M>::value_type&`
+ `const property_matrix_traits<M>::value_type&`
+ ]
+ [`m[u][v]`]
+ [
+ Returns the element corresponding to the pair `u`, `v` in the
+ matrix.
+
+ *Requirements:* The keys `u` and `v` must be the same as the `key_type`
+ for the matrix.
+
+ *Preconditions:* The keys `u` and `v` must be valid vertex or edge
+ descriptors of the graph to which the matrix applies.
+ ]
+ ]
+ [
+ [Row Access]
+ [
+ `property_matrix_traits<M>::container_type&`
+ `const property_matrix_traits<M>::container_type&`
+ ]
+ [`m[u]`]
+ [
+ Returns the row (or nested container) associated with the key `u`.
+
+ *Requirements:* The key `u` must be the same as the `key_type`
+ for the matrix.
+
+ *Preconditions:* The key `u` must be valid vertex or edge descriptor
+ of the graph to which the matrix applies.
+ ]
+ ]
+]
+
+[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/concepts/utility.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 5,10 +5,14 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
[section Concepts]
+[section General Concepts]
This section describes utlity graph concepts  those that do not necessarily
pertain explicitly to graphs or visitors for algorithms.
[include exterior_property.qbk]
+[include descriptor.qbk]
+[include numeric_value.qbk]
+[include property_map.qbk]
+[include property_matrix.qbk]
+[include distance_measure.qbk]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/Makefile
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/Makefile (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/Makefile 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 1,7 +1,11 @@
src = \
 closeness.tex \
 mean_geodesic.tex
+ total_geodesic.tex \
+ mean_geodesic.tex \
+ mean_geodesic_undirected.tex \
+ mean_geodesic_directed.tex \
+ inverse_geodesic.tex \
+ closeness.tex
dvi = $(src:%.tex=%.dvi)
ps = $(src:%.tex=%.ps)
png = $(src:%.tex=%.png)
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/closeness.tex 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 8,5 +8,8 @@
\pagestyle{empty}
\begin{document}
$C(u) = \frac{n}{\sum_{u \in V}{d_G\left(u,v\right)}} $
+\[
+C\left(u\right) =
+ \frac{1}{\sum_{v \in V}{d\left(u,v\right)}}
+\]
\end{document}
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/inverse_geodesic.tex
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/inverse_geodesic.tex 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,15 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pstplot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+\bar{D}^{1}\left(u\right) =
+ \frac{\leftV\right}{\sum_{v \in V}{d\left(u,v\right)}}
+\]
+\end{document}
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic.tex
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic.tex (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic.tex 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 8,5 +8,8 @@
\pagestyle{empty}
\begin{document}
$D(u) = \frac{\sum_{u \in V}{d_G\left(u,v\right)}}{\leftV\right} $
+\[
+\bar{D}\left(u\right) =
+ \frac{\sum_{v \in V}{d\left(u,v\right)}}{\leftV\right}
+\]
\end{document}
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic_directed.tex
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic_directed.tex 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,20 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pstplot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+\bar{D}\left(G\right)
+ = \frac
+ {\displaystyle\sum_{u \in V}{\bar{D}\left(u\right)}}
+ {\leftV\right^2}
+ = \frac
+ {\displaystyle\sum_{u \in V}\sum_{v \in V}{d\left(u,v\right)}}
+ {\leftV\right^2}
+\]
+\end{document}
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic_undirected.tex
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/mean_geodesic_undirected.tex 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,20 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pstplot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+\bar{D}\left(G\right)
+ = \frac
+ {2\displaystyle\sum_{u \in V}{\bar{D}\left(u\right)}}
+ {\left(\leftV\right+1\right)}
+ = \frac
+ {2\displaystyle\sum_{u \in V}\sum_{v \in V}{d\left(u,v\right)}}
+ {\leftV\right \cdot \left(\leftV\right+1\right)}
+\]
+\end{document}
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/total_geodesic.tex
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/images/eq/total_geodesic.tex 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,14 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pstplot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+D\left(u\right) = \sum_{v \in V}{d\left(u,v\right)}
+\]
+\end{document}d_G\left(u,v\right)
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 6,209 +6,161 @@
/]
[section Closeness Centrality]
This section describes the closeness centrality framework  group of functions
related to computing measures based on the geodesic distances of vertices. There
are four related measures:
* Total geodesic distance
* Mean geodesic distances
* Inverse geodesic distance
* Closeness
+ template <typename Graph, typename DistanceMatrix, typename ClosenessMap>
+ void closeness_centrality(const Graph& g,
+ DistanceMatrix& dist,
+ ClosenessMap& close)
template <typename Graph,
 typename DistanceMap,
 typename Measure,
 typename Combinator>
 inline typename Measure::result_type
 closeness_centrality(const Graph& g,
 DistanceMap dist,
 Measure measure,
 Combinator combine)


These functions compute values based on the /geodesic distance/ between
vertices. The /geodesic distance/ between vertices /u/ and /v/ is defined
as the shortestlength path between such vertices. The shortest path can
be defined in terms of the sum of edge, weights, the sum of vertex weights,
or simply the number of "hops". It is important to notethat these functions
/do not/ compute the paths or record their distances. Instead, they rely upon
a previous computation.

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 the 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 shortest paths algorithms is a `DistanceMap`, which is used as the
input to the geodesic distance functions. Note then, that these functions compute
measures of the vertex for which `dist` was computed.

The `mean_geodesic()` functions return the (arithmatic) mean of the geodesic
distances between a vertex and all others in the graph. Intuitively, this gives
the average distance from one vertex to every other. Vertices with low mean
geodesic distance are more central to the graph. The `mean_geodesic()` for
a vertex is given as:

[$images/eq/mean_geodesic.png]

The `closeness()` functions effectively return the inverse (reciprocal) of the
`mean_geodesic()` for a vertex. It is given as:
+ typename DistanceMatrix,
+ typename ClosenessMap,
+ typename Measure>
+ void closeness_centrality(const Graph& g,
+ DistanceMatrix& dist,
+ ClosenessMap& close,
+ Measure measure)
+
+
+ template <typename Graph, typename DistanceMap>
+ float vertex_closeness_centrality(const Graph& g, DistanceMap dist)
+
+ template <typename ResultType, typename Graph, typename DistanceMap>
+ ResultType vertex_closeness_centrality(const Graph& g, DistanceMap dist)
+
+ template <typename Graph, typename DistanceMap, typename Measure>
+ typename Measure::result_type
+ vertex_closeness_centrality(const Graph& g, DistanceMap dist, Measure measure)
+
+The /closeness centrality/ measure is commonly used in social network analysis to
+identify vertices (also called actors) that are "close" to all others. To phrase
+differently, actors that are "closer" to all others have a greater reach, making
+them more influential in the network. The closeness measure is defined as the inverse
+as the sum of all geodesic distances (lengths of shortest path) from one vertex
+to all others. Formally it is given as:
[$images/eq/closeness.png]
In both of these formulas, /n/ is the number of vertices in the graph `G` and
['d[sub G](u, v)] is the geodesic distance (shortest path) from /u/ to /v/. If
/v/ is not reachable from /u/, then the distance between /u/ and /v/ is infinite.
This implies that the `mean_geodesic()` for `u` is infinite and the `closeness()`
is 0.

There are three variants of these two sets of functions, allowing increasing
genericity of usage.

The first variant of this function computes and returns the average 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, but otherwise acts as a numeric
type. The third variant allows the user to specify the type, the combination
function for computing the sum, and the default values of 0 and infinity. This
is useful when the computation is performed on a discrete or nonnumeric type.
Note that in this variant, the default value of `zero` must be explicitly
passed as an argument.
+Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/.
+Note that if any vertex in the graph is unreachable from any other, then the
+graph is unconnected, and the distance between those two unonnected vertices
+is infinite. This imlplies that the closeness of every vertex in an unconnected
+(and undirected) graph is zero. This is not necessarily the case for directed
+graphs.
+
+It is also important to note the relationship between /closeness/, /farness/
+and /mean geodesic distance/. Specifcially, /farness/ is the inverse of
+/closeness/ (or the other way around) and indicates how far an actor is from
+all others in the graph. The /mean geodesic distance/ is the average /farness/
+of a vertex.
+
+This module defines a flexible framework for computing the closeness centrality
+of vertices in a graph for previously computed geodesics by providing two generic
+functions. The first function, `closeness_centrality()` computes the closeness of
+each vertex in a graph given a matrix containing the distances between vertices.
+This matrix can be computed as the output of an "all pairs shortest path" algorithm,
+or as the result of many breadth first searches (if the graph is unweighted).
+
+The second function, `vertex_closeness_centrality()` can be used to compute the
+closeness of a single vertex. This function requires a distance map that contains
+the distance from one vertex (the source) to all others in the graph. This
+distance map can be computed as the result of a "shortest paths" algorithm or
+recording distances from a breadthfirst search.
+
+This framework also allows for a specialization of the measure through the use
+of a function object. This measure defaults to the reciprocal in the equation
+above, but can be easily redefined to perform alternative computations or, in
+the case of nontrivial types, redefine the notion of reciprocal.
[heading Where Defined]
`boost/graph/distance.hpp`
+`boost/graph/closeness_centrality.hpp`
[heading Parameters]
[table
[[Type] [Parameter] [Description]]
[
 [required, in] [`const Graph& g`]
+ [template] [`ResultType`]
[
 The graph object for which the measure will be computed. The
 `Graph` type is required to be a model of [BoostVertexListGraph].
+ The `ResultType` template parmeter explitly specifies the the
+ return type of the `closeness()` function. If not
+ given, the return type is `float`.
+
+ *Requirements:* The return type is required to model the
+ [BoostNumericValue] concept.
]
]
[
 [required, in] [`DistanceMap dist`]
+ [required, in] [`const Graph& g`]
[
 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`.
+ The graph for which vertex measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostVertexListGraph] concept.
]
]
[
 [optional, in] [`T`]
+ [required, in] [`DistanceMap dist`]
[
 If used, the `T` template parameter must be explicitly given as a
 template argument when invoking these functions. The type `T` must
 be a `Regular` type (default and copy constructible, assignable).
 Additionally, it must be `Divisible` and constructible from both
 `vertices_size_type` of `Graph` and the `value_type` of `DistanceMap`.
 Numeric types satisfy these requirements.
+ 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].
]
]
[
 [optional, in] [`Combinator combine`]
+ [required, in] [`DistanceMatrix dist`]
[
 The `combine` parameter is a binary functor that is invoked to combine
 distance values in the `DistanceMap`. The argument types and return
 type of the function must be the same as the `value_type` of the
 `DistanceMap`.
+ 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`).
 *Default:* `std::plus<T>()`
+ *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].
]
]
[
 [optional, in] [`DistanceType zero`]
+ [required, out] [`ClosenessMap close`]
[
 The `zero` parameter is used as an initial value for the combination
 of distances in these computations. Distance must be the same type
 as the `value_type` of the `DistanceMap` parameter.
+ The `close` parameter stores the output of the computed closeness (or
+ distance) for each vertex in `g`.
 *Defaults:* `DistanceType()` (for numeric types, this is 0).
+ *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].
]
]
[
 [optional, in] [`T infinity`]
+ [optional, in] [`Measure measure`]
[
 The `infinity` parameter is used to indicate a value of `T` that
 acts as an infinite value in these computations. Distance must be the
 same type as the `value_type` of the `DistanceMap` parameter. Note that
 if the shortest paths are computed using [boost_dijkstra_shortest_paths],
 and the `inf` parameter is used, this must be the same value.
+ The 'measure' parameter is an instance of a closeness measure that
+ performs the final operation (the reciprocal) for this computation.
 *Default:* `std::numeric_limits<DistanceType>::max()`
+ *Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
+ concept.
]
]
]
[h5 Complexity]
The `mean_geodesic()` and `closeness()` functions are linear with respect to
`num_vertices(g)`.

[h5 Examples]
This example computes shows the construction of a simple undirected graph and
illustrates the computation of shortest distances and the use of the `geodesic_distance()`
and `mean_geodesic_distance()` functions. Consider the following graph:

[figure
 images/reference/geodesic.png
 [*Figure 1.] A simple undirected, unweighted graph.
]

This graph can be constructed programmatically as:
+[heading Return]
+The `vertex_closeness_centrality()` function returns the closeness of a vertex.
+If the source vertex is not connected to one other in the graph, this value is 0.
+
+[heading Complexity]
+The `closenesss_centrality()` function is ['O(n[super 2])] where /n/ is the
+number of vertices in the graph.
 typedef undirected_graph<> Graph;
 typedef graph_traits<Graph>::vertex_descriptor Vertex;
+The `vertex_closeness_centrality()` function is linear with respect to the number
+of vertices in the graph.
 // 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 toself of vertex 0 and run a breadthfirst
 // 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())))
 );

We can print the geodesic distance from vertex 0 to each of the other vertices, and
its mean geodesic distance.

 Graph::vertex_iterator i, end;
 cout << "mean geodesic == " << mean_geodesic(g, dist) << end;
 cout << "closeness == " << closeness(g, dist) << end;

The output of this program is:

[pre
mean geodesic == 2.8
closeness == .35
]
+[heading Example]
+Write an example.
[endsect]
\ No newline at end of file
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk
==============================================================================
 (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 0,0 +1,208 @@
+[/
+ / 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 Mean Geodesic]
+
+ template <typename Graph, typename DistanceMatrix, typename GeodesicMap>
+ void mean_geodesic(const Graph& g, DistanceMatrix& dist, GeodesicMap& geo)
+
+ template <typename Graph,
+ typename DistanceMatrix,
+ typename GeodesicMap,
+ typename Measure>
+ void mean_geodesic(const Graph& g,
+ DistanceMatrix& dist,
+ ClosenessMap& close,
+ Measure measure)
+
+
+ template <typename Graph, typename DistanceMap>
+ float vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+
+ template <typename ResultType, typename Graph, typename DistanceMap>
+ ResultType vertex_mean_geodesic(const Graph& g, DistanceMap dist)
+
+ template <typename Graph, typename DistanceMap, typename Measure>
+ typename Measure::result_type
+ vertex_mean_geodesic(const Graph& g, DistanceMap dist, Measure measure)
+
+
+ template <typename Graph, typename DistanceMatrix>
+ float graph_mean_geodesic(const Graph& g, DistanceMatrix& dist)
+
+ template <typename ResultType, typename Graph, typename DistanceMatrix>
+ ResultType graph_mean_geodesic(const Graph& g, DistanceMatrix& dist)
+
+ template <typename Graph, typename DistanceMatrix, typename Measure>
+ typename Measure::result_type
+ graph_mean_geodesic(const Graph& g, DistanceMatrix& dist, Measure measure)
+
+The /mean geodesic distance/ measure is commonly used in large network analysis
+to quantify the /small world/ phenomonon. If the mean geodesic distance is small
+in relation to the graph (e.g., 6), then all vertices are (on average) only 6
+steps or hops away from any other. The mean geodesic distance of a vertex is
+computed over the shortest paths between vertices. Formally, it is given as:
+
+[$images/eq/mean_geodesic.png]
+
+Where /d(u,v)/ is the shortest path (geodesic distance) from /u/ to /v/.
+Note that if any vertex in the graph is unreachable from any other, then the
+graph is unconnected, and the distance between those two unonnected vertices
+is infinite. This imlplies that the closeness of every vertex in an unconnected
+(and undirected) graph is also infinite. This is not necessarily the case for
+directed graphs.
+
+The mean geodesic distance for the entire graph is essentially the average of
+mean geodesic distances of every vertex in the graph. There are alternative
+means of computing this average (e.g,. in the case of simple graphs), but
+differences in the results are negligible for large graphs. If any vertex has
+infinite mean geodesic distance, then the graph also has infinite mean geodesic
+distance.
+
+It is also important to note the relationship between /mean geodesic distance/,
+/farness/, and /closeness/. The /farness/ of a vertex is the sum of its goedesic
+distances to all other vertices (mean geodesic distances * number of vertices),
+and /closeness/ is the inverse of
+
+This module defines a flexible framework for computing the mean geodesic distance
+of vertices in a graph for previously computed geodesics by providing thrtee generic
+functions. The first function, `mean_geodesic()` computes the average distance of
+each vertex in a graph from a matrix containing the distances between vertices.
+This matrix can be computed as the output of an "all pairs shortest path" algorithm,
+or as the result of many breadth first searches (if the graph is unweighted).
+
+The second function, `vertex_mean_geodesic()` can be used to compute the
+closeness of a single vertex. This function requires a distance map that contains
+the distance from one vertex (the source) to all others in the graph. This
+distance map can be computed as the result of a "shortest paths" algorithm or
+recording distances from a breadthfirst search.
+
+The third function, `graph_mean_geodesic()` computes a single mean geodesic
+distance for the graph by averaging the mean geodesic distance for each vertex
+in a distance matrix. This average is computed differently for both directed
+and undirected graphs. For undirected graphs, the mean geodesic distance is
+computed as:
+
+[$images/eq/mean_geodesic_undirected.png]
+
+Intuitively, this is the average distance over all possible edges in the graph.
+For directed graphs the mean geodesic distance is computed as:
+
+[$images/eq/mean_geodesic_directed.png]
+
+This framework also allows for a specialization of measures used to compute
+these values. This framework employs two distinct measures. The first is used
+to compute the mean geodesic distance of a single vertex. By default this simply
+divides the sum of distances by the number of vertices. The second measure is
+used to compute the mean geodesic distance for the entire graph. This provides
+the factors in the algorithms given above.
+
+Note that for small graphs, the default choice of divisors in computations may
+seem inappropriate. For example, most simple networks preclude the possibility
+of selfloops and so the average can be computed over /n/  1 vertices. However,
+for large graphs, this difference is negligible.
+
+[heading Where Defined]
+`boost/graph/closeness_centrality.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [template] [`ResultType`]
+ [
+ The `ResultType` template parmeter explitly specifies the the
+ return type of the `closeness()` 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] concepts.
+ ]
+ ]
+ [
+ [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 distance for
+ each vertex in `g`.
+
+ *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].
+ ]
+ ]
+ [
+ [optional, in] [`Measure measure`]
+ [
+ The 'measure' parameter is an instance of a measure type that performs
+ the "averaging" operation in this computation. For the `mean_geodesic()`
+ functions, this measure is responsible for computing the average distance
+ over the graph. For the `graph_mean_geodesic()` function, this measure
+ is responsible for averaging the averages.
+
+ *Requirements:* The `Measure` type must be a model of the [BoostDistanceMeasure]
+ concept.
+ ]
+ ]
+]
+
+[heading Return]
+The `vertex_mean_geodesic()` function returns the average of geodesic distances
+to other vertices from a source. If the source vertex is not connected to one other
+in the graph, this value is infinite.
+
+The `graph_mean_geodesic()` function returns the mean geodesic distance for the
+entire graph  a common measure of the small world property. If the graph is
+unconnected, the mean geodesic distance is infinite.
+
+[heading Complexity]
+The `mean_geodesic()` and `graph_mean_geodesic()` functions are ['O(n[super 2])]
+where /n/ is the number of vertices in the graph.
+
+The `vertex_mean_geodesic()` function is linear with respect to the number
+of vertices in the graph.
+
+[heading Example]
+Write an example.
+
+[endsect]
\ No newline at end of file
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 20070801 09:51:57 EDT (Wed, 01 Aug 2007)
@@ 68,6 +68,7 @@
[section Graph Measures]
[include distributions.qbk]
[include closeness_centrality.qbk]
+[include mean_geodesic.qbk]
[include eccentricity.qbk]
[endsect]
[endsect]
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