
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070730 08:38:03
Author: asutton
Date: 20070730 08:38:00 EDT (Mon, 30 Jul 2007)
New Revision: 7591
URL: http://svn.boost.org/trac/boost/changeset/7591
Log:
Removing closeness file
Removed:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk  50 ++++++++++++
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk  3 
2 files changed, 16 insertions(+), 37 deletions()
Deleted: sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk
==============================================================================
 sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness.qbk 20070730 08:38:00 EDT (Mon, 30 Jul 2007)
+++ (empty file)
@@ 1,158 +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 Closeness]

 template <typename Graph, typename DistanceMap>
 property_traits<DistanceMap>::value_type
 closeness(const Graph&g, DistanceMap dist)

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

These functions compute the /closeness/ of vertices in a graph. The /closeness/
of a vertex is defined as the reciprocal of the sum of /geodesic distances/
(shortest paths) to all other vertices in the graph as given by the formula:

[$images/eq/closeness.png]

where ['d[sub G](u,v)] is the shortest path from /u/ to /v/. It is important to
note that these functions /do not/ compute these paths or record their distances

Boost.Graph provides two shortest paths algorithms: [boost_dijkstra_shortest_paths]
and [boost_bellman_ford_shortest_paths]. Optionally, if the target graph is
an unweighted, undirected graph, shortest paths can be recorded using
[boost_breadth_first_search]. Each of these algorithms takes as an input a
vertex for which the shortest distances are being computed. The output of
each of these algorithms is a `DistanceMap`, which is (in turn) used as the
input of these functions. Note then, that these functions compute measures
of the vertex for which the `DistanceMap` was computed.

The `closeness()` functions return the closeness of the geodesic distances
between a vertex and all others in the graph. The vertex for which this is computed
is that for which `dist` was originally computed.

The default (first) variant of this function computes and returns the
closeness as a `double`. The second variant allows the average and return
type to be computed as a userdefined type by passing a dummy instance.
This is useful if the `value_type` of `DistanceMap` is a userdefined or
otherwise nontrivial.

If the graph is unconnected, then the closeness between any two vertices
is zero.

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

[heading Parameters]

[table
 [[Type] [Parameter] [Description]]
 [
 [required, in] [`const Graph& g`]
 [
 The graph object for which the measure will be computed. The
 `Graph` type is required to be a model of [BoostVertexListGraph].
 ]
 ]
 [
 [required, in] [`vertex_descriptor v`]
 [
 The target vertex to which the geodisic distance is returned. The
 source vertex is made implicit by the `DistanceMap`.
 ]
 ]
 [
 [required, in] [`DistanceMap dist`]
 [
 The `dist` parameter provides the distances of the shortest paths
 from one source vertex to all others in the graph. The `DistanceMap`
 must be a model of [BoostReadWritePropertyMap], they `key_type` must
 be the `vertex_descriptor` of `Graph`.
 ]
 ]
 [
 [required, in] [`const T& dummy`]
 [
 An unused instance of the type returned by the `mean_geodesic_distance()`
 function. If specified, the measure will be computed as an average of
 this type. This type must essentially be numeric, as it is required to
 a) support division, b) be initialized with an integer type, and c)
 have a default of 0.
 ]
 ]
]

[h5 Return Value]
The `closeness()` function returns the closeness of the vertex for which
`dist` was computed. The closeness is defined in the formula above.

[h5 Complexity]
The `closeness()` function has /O(V)/ time complexity.

[h5 Examples]
This example computes shows the construction of a simple undirected graph and
illustrates how to compute the `closeness()` for a vertex.

[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())))
 );

Computing the `closeness()` for vertex 0 is trivial.

 cout << "closeness == " << closeness(g, dist) << end;

The output of this program is roughly:

[pre
mean geodesic distance == 0.035
]


[endsect]
\ 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 20070730 08:38:00 EDT (Mon, 30 Jul 2007)
@@ 5,45 +5,25 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
/]
[section Geodesic Distances]
+[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 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,
+ template <typename Graph,
typename DistanceMap,
 typename DistanceType,
+ typename Measure,
typename Combinator>
 T closeness(
 const Graph& g,
 DistanceMap dist,
 Combinator combine,
 DistanceType zero,
 DistanceType infinity = std::numeric_limits<T>::max())
+ 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
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 20070730 08:38:00 EDT (Mon, 30 Jul 2007)
@@ 67,8 +67,7 @@
[section Graph Measures]
[include distributions.qbk]
[include geodesic.qbk]
[include closeness.qbk]
+[include closeness_centrality.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