
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070730 08:32:31
Author: asutton
Date: 20070730 08:32:30 EDT (Mon, 30 Jul 2007)
New Revision: 7590
URL: http://svn.boost.org/trac/boost/changeset/7590
Log:
Renamed fil
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk
 copied unchanged from r7587, /sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk 20070730 08:32:30 EDT (Mon, 30 Jul 2007)
+++ (empty file)
@@ 1,234 +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 Geodesic Distances]

 template <typename Graph, typename DistanceMap>
 double mean_geodesic(const Graph& g, DistanceMap dist)

 template <typename T, typename Graph, typename DistanceMap>
 T mean_geodesic(const Graph& g, DistanceMap dist)

 template <typename T,
 typename Graph,
 typename DistanceMap,
 typename DistanceType,
 typename Combinator>
 T mean_geodesic(
 const Graph& g,
 DistanceMap dist,
 Combinator combine,
 DistanceType zero,
 DistanceType infinity = std::numeric_limits<T>::max())



 template <typename Graph, typename DistanceMap>
 double closeness(const Graph& g, DistanceMap dist)

 template <typename T, typename Graph, typename DistanceMap>
 T closeness(const Graph& g, DistanceMap dist)

 template <typename T,
 typename Graph,
 typename DistanceMap,
 typename DistanceType,
 typename Combinator>
 T closeness(
 const Graph& g,
 DistanceMap dist,
 Combinator combine,
 DistanceType zero,
 DistanceType infinity = std::numeric_limits<T>::max())


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:

[$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.

[heading Where Defined]
`boost/graph/distance.hpp`

[heading Parameters]
[table
 [[Type] [Parameter] [Description]]
 [
 [required, in] [`const Graph& g`]
 [
 The graph object for which the measure will be computed. The
 `Graph` type is required to be a model of [BoostVertexListGraph].
 ]
 ]
 [
 [required, in] [`DistanceMap dist`]
 [
 The `dist` parameter provides the distances of the shortest paths
 from one source vertex to all others in the graph. The `DistanceMap`
 must be a model of [BoostReadWritePropertyMap], they `key_type` must
 be the `vertex_descriptor` of `Graph`.
 ]
 ]
 [
 [optional, in] [`T`]
 [
 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.
 ]
 ]
 [
 [optional, in] [`Combinator combine`]
 [
 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`.

 *Default:* `std::plus<T>()`
 ]
 ]
 [
 [optional, in] [`DistanceType zero`]
 [
 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.

 *Defaults:* `DistanceType()` (for numeric types, this is 0).
 ]
 ]
 [
 [optional, in] [`T infinity`]
 [
 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.

 *Default:* `std::numeric_limits<DistanceType>::max()`
 ]
 ]
]

[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:

 typedef undirected_graph<> Graph;
 typedef graph_traits<Graph>::vertex_descriptor Vertex;

 // 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
]

[endsect]
\ No newline at end of file
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