|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-01 09:52:01
Author: asutton
Date: 2007-08-01 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 2007-08-01 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 2007-08-01 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 2007-08-01 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 2007-08-01 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 2007-08-01 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 size-constructible 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 worst-case 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 2007-08-01 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 2007-08-01 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
+user-defined 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 zero-value 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 built-in 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 2007-08-01 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 2007-08-01 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
+two-dimensional array-like 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 double-indexing 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 2007-08-01 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 2007-08-01 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 2007-08-01 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 2007-08-01 09:51:57 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,15 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pst-plot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+\bar{D}^{-1}\left(u\right) =
+ \frac{\left|V\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 2007-08-01 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)}}{\left|V\right|} $
+\[
+\bar{D}\left(u\right) =
+ \frac{\sum_{v \in V}{d\left(u,v\right)}}{\left|V\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 2007-08-01 09:51:57 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,20 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pst-plot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+\bar{D}\left(G\right)
+ = \frac
+ {\displaystyle\sum_{u \in V}{\bar{D}\left(u\right)}}
+ {\left|V\right|^2}
+ = \frac
+ {\displaystyle\sum_{u \in V}\sum_{v \in V}{d\left(u,v\right)}}
+ {\left|V\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 2007-08-01 09:51:57 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,20 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pst-plot}
+\usepackage{color}
+\pagestyle{empty}
+
+\begin{document}
+\[
+\bar{D}\left(G\right)
+ = \frac
+ {2\displaystyle\sum_{u \in V}{\bar{D}\left(u\right)}}
+ {\left(\left|V\right|+1\right)}
+ = \frac
+ {2\displaystyle\sum_{u \in V}\sum_{v \in V}{d\left(u,v\right)}}
+ {\left|V\right| \cdot \left(\left|V\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 2007-08-01 09:51:57 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,14 @@
+\documentclass[12pt]{article}
+
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{pst-plot}
+\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 2007-08-01 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 shortest-length 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 user-defined type by passing a dummy instance. This is useful if the
-`value_type` of `DistanceMap` is a user-defined, 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 non-numeric 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 breadth-first 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 non-trivial types, re-define 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 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())))
- );
-
-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 2007-08-01 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 breadth-first 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 self-loops 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 2007-08-01 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]
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