|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-07-30 08:38:03
Author: asutton
Date: 2007-07-30 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 2007-07-30 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 user-defined type by passing a dummy instance.
-This is useful if the `value_type` of `DistanceMap` is a user-defined or
-otherwise non-trivial.
-
-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 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())))
- );
-
-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 2007-07-30 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 2007-07-30 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]
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