|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-01 13:35:31
Author: asutton
Date: 2007-08-01 13:35:28 EDT (Wed, 01 Aug 2007)
New Revision: 38338
URL: http://svn.boost.org/trac/boost/changeset/38338
Log:
Added docs for eccentricity, radius and diameter
Renamed algorithms in ToC for convenience.
Added and fixed a bunch of template references
Added:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/diameter.qbk (contents, props changed)
sandbox/SOC/2007/graphs/libs/graph/doc/reference/radius.qbk (contents, props changed)
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/boost_reference.qbk | 77 +++++++++++++++---
sandbox/SOC/2007/graphs/libs/graph/doc/reference/closeness_centrality.qbk | 22 ++--
sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk | 165 ++++++++++++++++-----------------------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk | 61 +++++++-------
sandbox/SOC/2007/graphs/libs/graph/doc/reference/reference.qbk | 20 ++--
6 files changed, 185 insertions(+), 164 deletions(-)
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 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -25,18 +25,65 @@
[template boost_time_stamper[] [link boost_graph.reference_guide.event_visitors.time_stamper [^time_stamper]]]
[template boost_property_writer[] [link boost_graph.reference_guide.event_visitors.property_writer [^property_writer]]]
-[/ Core algorithms /]
-[template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search [^breadth_first_search()]]]
-[template boost_depth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.depth_first_search [^depth_first_search()]]]
-
-[/ 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()]]]
-[template boost_exterior_edge_property[] [link boost_graph.reference_guide.algorithms.connectivity_algorithms.connected_components [^connected_components()]]]
\ No newline at end of file
+[/ Fundamental /]
+[template boost_breadth_first_search[] [link
+ boost_graph.reference_guide.algorithms.fundamental.breadth_first_search
+ [^breadth_first_search()]]]
+[template boost_depth_first_search[] [link
+ boost_graph.reference_guide.algorithms.fundamental.depth_first_search
+ [^depth_first_search()]]]
+
+[/ Shortest Path /]
+[template boost_dijkstra_shortest_paths[] [link
+ boost_graph.reference_guide.algorithms.shortest_paths.dijkstra_shortest_paths
+ [^dijkstra_shortest_paths()]]]
+[template boost_bellman_ford_shortest_paths[] [link
+ boost_graph.reference_guide.algorithms.shortest_paths.bellman_ford_shortest_paths
+ [^bellman_ford_shortest_paths()]]]
+[template boost_floyd_warshall_all_pairs_shortest_paths[] [link
+ boost_graph.reference_guide.algorithms.shortest_paths.floyd_warshall_all_pairs_shortest_paths
+ [^floyd_warshall_all_pairs_shortest_paths()]]]
+
+[/ Connectivity /]
+[template boost_connected_components[] [link
+ boost_graph.reference_guide.algorithms.connectivity.connected_components
+ [^connected_components()]]]
+[template boost_strong_connected_components[] [link
+ boost_graph.reference_guide.algorithms.connectivity.strongly_connected_components
+ [^strongly_connected_components]]]
+
+[/ Subgraph/ ]
+[template boost_bron_kerbosch_visit_cliques[] [link
+ boost_graph.reference_guide.algorithms.subgraph.bron_kerbosch_find_cliques
+ [^bron_kerbosch_find_cliques()]]]
+[template boost_tiernan_find_cycles[] [link
+ boost_graph.reference_guide.algorithms.subgraph.tiernan_find_cycles
+ [^tiernan_find_cycles()]]]
+
+[/ Measures /]
+[template boost_degree_centrality[] [link
+ boost_graph.reference_guide.algorithms.graph_measures.degree_centrality
+ [^degree_centrality()]]]
+[template boost_closeness_centrality[] [link
+ boost_graph.reference_guide.algorithms.graph_measures.closeness_centrality
+ [^closeness_centrality()]]]
+[template boost_mean_geodesic[] [link
+ boost_graph.reference_guide.algorithms.graph_measures.mean_geodesic
+ [^mean_geodesic()]]]
+[template boost_eccentricity[] [link
+ boost_graph.reference_guide.algorithms.graph_measures.eccentricity
+ [^eccentricity()]]]
+[template boost_graph_radius[] [link
+ boost_graph.reference_guide.algorithms.graph_measures.raidus
+ [^radius()]]]
+[template boost_graph_diameter[] [link
+ boost_graph.reference_guide.algorithms.graph_measures.diameter
+ [^diameter()]]]
+
+
+[template boost_exterior_vertex_property[] [link
+ boost_graph
+ [^exterior_vertex_property]]]
+[template boost_exterior_edge_property[] [link
+ boost_graph
+ [^exterior_edge_property]]]
\ 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 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -9,16 +9,16 @@
template <typename Graph, typename DistanceMatrix, typename ClosenessMap>
void closeness_centrality(const Graph& g,
- DistanceMatrix& dist,
- ClosenessMap& close)
+ const DistanceMatrix& dist,
+ ClosenessMap close)
template <typename Graph,
typename DistanceMatrix,
typename ClosenessMap,
typename Measure>
void closeness_centrality(const Graph& g,
- DistanceMatrix& dist,
- ClosenessMap& close,
+ const DistanceMatrix& dist,
+ ClosenessMap close,
Measure measure)
@@ -101,10 +101,10 @@
[
[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`).
+ Given a vertex `v`, the `dist` parameter provides the length of the
+ shortest path between a vertex `u` and `v`. The vertex `u` is the
+ vertex for which the distance map was initially computed. The
+ distance from /u/ to itself should be zero (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`
@@ -113,10 +113,10 @@
]
]
[
- [required, in] [`DistanceMatrix dist`]
+ [required, in] [`const DistanceMatrix& dist`]
[
- The `dist` parameter provides, given vertices /u/ and /v/, the
- length of the shortest path between the two vertices. Note that the
+ Given vertices /u/ and /v/, the `dist` parameter provides 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].
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/degree_centrality.qbk 2007-08-01 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -97,13 +97,13 @@
]
]
-[h5 Return Value]
+[heading Return Value]
The `vertex_degree_centrality()` function returns the centrality of a vertex.
If no `measure` parameter is given, the return type is the same as the
`degree_size_type` of the `Graph`. Otherwise, it is the `degree_type` of
the `Measure`.
-[h5 Complexity]
+[heading Complexity]
The default measure is a constant-time function. Replacing the default measure
with a non-constant-time function will affect the complexity of the computations.
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/diameter.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/diameter.qbk 2007-08-01 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,62 @@
+[/
+ / 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 Diameter]
+
+ template <typename Graph, typename EccentricityMap>
+ typename property_traits<EccentricityMap>::value_type
+ graph_diameter(const Graph& g, EccentricityMap ecc)
+
+The /diameter/ of a graph is the maximum /eccentricty/ of any vertex in the
+graph. This computes and returns that value using previously computed
+eccentricity values. Eccentricity values are typically computed using the
+[boost_eccentricity] functions.
+
+The diameter of a graph is also used to establish the graph's /periphery/ - the
+set of vertices having the same eccentricity as the graph diameter. This subset
+can be computed using the [boost_graph_periphery] functions.
+
+[heading Where Defined]
+`boost/graph/diameter.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the eccentricity measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostVertexListGraph] concepts.
+ ]
+ ]
+ [
+ [required, in] [`EccentricityMap ecc`]
+ [
+ The `ecc` property map associates an eccentricity value with every
+ vertex in the graph.
+
+ *Requirements:* `EccentricityMap` 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` must model the [SgiLessThanComparable]
+ concept.
+ ]
+ ]
+]
+
+[heading Return Value]
+The `graph_diameter()` function returns the radius of the given graph with respect
+to the given eccentricity values.
+
+[heading Complexity]
+The `graph_diameter()` function is linear.
+
+[heading Examples]
+Write an example.
+
+[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/eccentricity.qbk 2007-08-01 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -8,133 +8,102 @@
[section Eccentricity]
template <typename Graph, typename DistanceMap>
- property_traits<DistanceMap>::value_type
- eccentricity(const Graph&g, DistanceMap dist)
+ typename property_traits<DistanceMap>::value_type
+ vertex_eccentricity(const Graph& g, GeodesicMap dist)
-This function computes the /eccentricity/ of a vertex in a graph. The eccentricity
-of a vertex is defined as the maximum geodesic distance (shortest paths) to any
-other vertex in the graph. 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.
+ template <typename Graph, typename DistanceMatrix, typename EccentricityMap>
+ void eccentricity(const Graph& g, const DistanceMatrix& dist, EccentricityMap ecc)
-If the graph is unconnected, then the eccentricity of any vertex will be
-infinite.
+The /eccentricity/ of a vertex is the maximum geodesic distance to any other
+vertex in the graph. Intuitively, Vertices with low eccentricity can reach all
+other vertices in the graph more quickly than vertices with high eccentricity.
+Eccentricity values are used to help compute the [boost_graph_radius] and
+[boost_graph_diameter]. These values can be used in turn, to identify the
+[boost_gaph_center] and [boost_graph_periperhy] subgraphs.
+
+Note that for any vertex in a graph that is not connected to another, its
+eccentricity is defined to be infinite.
+
+This module provide two generic functions. The first function, `eccentricity()`
+computes this values for all vertices in the graph given a matrix that provides
+the shortest paths between all pairs of vertices. This matrix can be computed
+as the output of an all-pairs shortest paths algorithm (e.g.,
+[boost_floyd_warshall_all_pairs_shortest_paths]) or repeated application of a
+breadth-first search. The output of this function is stored in a property map.
+
+The second function, `vertex_eccentricity()` computes the eccentricty of a
+single vertex given the shortest paths to every other vertex in the graph. The
+distance map can be computed using a shortest paths algorithms (e.g.,
+[boost_dijkstra_shortest_paths] or a breadth-first search. The output of this
+function is returned to the caller.
[heading Where Defined]
-`boost/graph/distance.hpp`
+`boost/graph/eccentricity.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].
+ The graph for which the eccentricity measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostVertexListGraph] concepts.
]
]
[
- [required, in] [`vertex_descriptor v`]
+ [required, in] [`DistanceMap dist`]
[
- The target vertex to which the geodisic distance is returned. The
- source vertex is made implicit by the `DistanceMap`.
+ Given a vertex `v`, the `dist` parameter provides the length of the
+ shortest path between a vertex `u` and `v`. The vertex `u` is the
+ vertex for which the distance map was initially computed. The
+ distance from /u/ to itself should be zero (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] [`DistanceMap dist`]
+ [required, in] [`const DistanceMatrix& 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`.
+ Given vertices /u/ and /v/, the `dist` parameter provides 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, in] [`const T& dummy`]
+ [required, out] [`EccentricityMap ecc`]
[
- 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.
+ The `ecc` parameter stores the computed results of the `eccentricity()`
+ function for each vertex in the graph.
+
+ *Requirements:* The `EccentricityMap` type must be a model of the
+ [BoostReadablePropertyMap] type. The `key_type` of the property map
+ must be the `vertex_descriptor` of the `Graph`. The `value_type`
+ must be the same as the `value_type` of the distance matrix.
]
]
]
-[h5 Return Value]
-The `eccentricity()` function returns the closeness of the vertex for which
-`dist` was computed.
-
-[h5 Complexity]
-The `eccentricity()` 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 `eccentricity()` 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())))
- );
+[heading Return Value]
+The `vertex_eccentricity()` function returns the eccentricity of the vertex.
+If the graph is unconnected, this returns the infinite value of the distance
+map's `value_type`.
-Computing the `eccentricity()` for vertex 0 is trivial.
+[heading Complexity]
+The `eccentricity()` function has /O(n^2)/ time complexity.
- cout << "eccentricity == " << eccentricity(g, dist) << end;
-
-The output of this program is:
-
-[pre
-mean geodesic distance == 5
-]
+The `vertex_eccentricity()` is linear.
+[heading Examples]
+Write an example.
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/mean_geodesic.qbk 2007-08-01 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -8,15 +8,15 @@
[section Mean Geodesic]
template <typename Graph, typename DistanceMatrix, typename GeodesicMap>
- void mean_geodesic(const Graph& g, DistanceMatrix& dist, GeodesicMap& geo)
+ void mean_geodesic(const Graph& g, const DistanceMatrix& dist, GeodesicMap geo)
template <typename Graph,
typename DistanceMatrix,
typename GeodesicMap,
typename Measure>
void mean_geodesic(const Graph& g,
- DistanceMatrix& dist,
- ClosenessMap& close,
+ const DistanceMatrix& dist,
+ ClosenessMap close,
Measure measure)
@@ -31,15 +31,14 @@
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 Graph, typename GeodesicMap, typename Measure>
+ typename Measure::result_type
+ graph_mean_geodesic(const Graph& g, GeodesicMap geo, Measure measure)
- template <typename ResultType, typename Graph, typename DistanceMatrix>
- ResultType graph_mean_geodesic(const Graph& g, DistanceMatrix& dist)
+ template <typename Graph, typename GeodesicMap>
+ typename property_traits<GeodesicMap>::value_type
+ graph_mean_geodesic(const Graph& g, GeodesicMap geo)
- 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
@@ -82,10 +81,10 @@
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:
+distance for the graph by averaging the mean geodesic distances of each vertex
+in the geodesic distance map. 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]
@@ -135,10 +134,10 @@
[
[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`).
+ Given a vertex `v`, the `dist` parameter provides the length of the
+ shortest path between a vertex `u` and `v`. The vertex `u` is the
+ vertex for which the distance map was initially computed. The
+ distance from /u/ to itself should be zero (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`
@@ -147,10 +146,10 @@
]
]
[
- [required, in] [`DistanceMatrix dist`]
+ [required, in] [`const DistanceMatrix dist`]
[
- The `dist` parameter provides, given vertices /u/ and /v/, the
- length of the shortest path between the two vertices. Note that the
+ Given vertices /u/ and /v/, the `dist` parameter provides 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].
@@ -160,15 +159,19 @@
]
]
[
- [required, out] [`ClosenessMap close`]
+ [required, both] [`GeodesicMap geo`]
[
- 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].
+ When used with the `mean_geodesic()` function, the `geo` parameter stores
+ the computed mean geodesic distances for each vertex pair in the matrix.
+ When used with the `graph_mean_geodesic()` function, the parameter provides
+ the input required to compute the mean distance for the graph.
+
+ *Requirements:* As an input parameter, the `GeodesicMap` type is required
+ to model the [BoostReadablePropertyMap] concept. As an output parameter,
+ it is required to model the [BoostWritablePropertyMap] concept. The
+ `key_type` of this parameter must be the `vertex_descriptor` of the
+ `Graph`, and the `value_type` must be a model of the [BoostNumericValue]
+ concept.
]
]
[
Added: sandbox/SOC/2007/graphs/libs/graph/doc/reference/radius.qbk
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/radius.qbk 2007-08-01 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -0,0 +1,62 @@
+[/
+ / 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 Radius]
+
+ template <typename Graph, typename EccentricityMap>
+ typename property_traits<EccentricityMap>::value_type
+ graph_radius(const Graph& g, EccentricityMap ecc)
+
+The /radius/ of a graph is the minimum /eccentricty/ of any vertex in the
+graph. This computes and returns that value using previously computed
+eccentricity values. Eccentricity values are typically computed using the
+[boost_eccentricity] functions.
+
+The radius of a graph is also used to establish the graph's /center/ - the
+set of vertices having the same eccentricity as the graph radius. This subset
+can be computed using the [boost_graph_center] functions.
+
+[heading Where Defined]
+`boost/graph/radius.hpp`
+
+[heading Parameters]
+[table
+ [[Type] [Parameter] [Description]]
+ [
+ [required, in] [`const Graph& g`]
+ [
+ The graph for which the eccentricity measures are being comptued.
+
+ *Requirements:* The `Graph` type must be a model of the
+ [BoostVertexListGraph] concepts.
+ ]
+ ]
+ [
+ [required, in] [`EccentricityMap ecc`]
+ [
+ The `ecc` property map associates an eccentricity value with every
+ vertex in the graph.
+
+ *Requirements:* `EccentricityMap` 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` must model the [SgiLessThanComparable]
+ concept.
+ ]
+ ]
+]
+
+[heading Return Value]
+The `graph_radius()` function returns the radius of the given graph with respect
+to the given eccentricity values.
+
+[heading Complexity]
+The `graph_radius()` function is linear.
+
+[heading Examples]
+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 13:35:28 EDT (Wed, 01 Aug 2007)
@@ -34,42 +34,44 @@
[endsect]
[section Algorithms]
-[section Core Algorithms]
+[section Fundamental]
[include breadth_first_search.qbk]
[include depth_first_search.qbk]
[endsect]
-[section Shortest Path Algorithms]
+[section Shortest Paths]
[endsect]
-[section Minimum Spanning Tree Algorithms]
+[section Minimum Spanning Tree]
[endsect]
-[section Connectivity Algorithms]
+[section Connectivity]
[include connected_components.qbk]
[include strong_components.qbk]
[include connectivity.qbk]
[endsect]
-[section Subgraph Finding Algorithms]
+[section Subgraph Finding]
[include clique.qbk]
[include cycle.qbk]
[endsect]
-[section Maximum Flow Algorithms]
+[section Maximum Flow]
[endsect]
-[section Sparse Matrix Ordering Algorithms]
+[section Sparse Matrix Ordering]
[endsect]
-[section Layout Algorithms]
+[section Layout]
[endsect]
-[section Graph Measures]
+[section Measures]
[include degree_centrality.qbk]
[include closeness_centrality.qbk]
[include mean_geodesic.qbk]
[include eccentricity.qbk]
+[include radius.qbk]
+[include diameter.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