|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-07-30 08:32:31
Author: asutton
Date: 2007-07-30 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 2007-07-30 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 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:
-
-[$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.
-
-[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 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
-]
-
-[endsect]
\ No newline at end of file
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