Boost-Commit :

From: asutton_at_[hidden]
Date: 2007-07-23 10:48:43

Author: asutton
Date: 2007-07-23 10:48:42 EDT (Mon, 23 Jul 2007)
New Revision: 7513
URL: http://svn.boost.org/trac/boost/changeset/7513

Log:
Added an example to geodesic docs

Text files modified:
sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk | 82 +++++++++++++++++++++++++++++++++++++--
1 files changed, 76 insertions(+), 6 deletions(-)

Modified: sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/reference/geodesic.qbk 2007-07-23 10:48:42 EDT (Mon, 23 Jul 2007)
@@ -33,7 +33,7 @@
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.
+of the vertex for which `dist` was computed.

The `geodesic_distance(g,dist)` function returns the length of the shortest path
between two vertices. The source vertex is that for which the `DistanceMap`
@@ -45,12 +45,11 @@
The `mean_geodesic_distance(g,dist,T())` functions return the (arithmatic) mean
of the geodesic distances between a vertex and all others in the graph. The
vertex for which this is computed is that for which the `DistanceMap` was
-originally computed. The mean geodesic distance is often given as:
+originally computed. The mean geodesic distance is implemeted as:

[\$images/eq/mean_geodesic.png]

-where ['d[sub G](u, v)] is the geodesic distance (shortest path) from vertices
-/u/ to /v/.
+where ['d[sub G](u, v)] is the geodesic distance (shortest path) from /u/ to /v/.

The default (first) variant of this function computes and returns the
average as a `double`. The second variant allows the average and return
@@ -134,8 +133,79 @@
The `mean_geodesic_distance(g,dist)` has O(n) time complexity.

[h5 Examples]
-[note
-Write some 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) {
+ }
+
+ // Connect the vertices by adding edges to the graph. This builds
+ // the graph shown in Figure 1.
+
+ // 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;
+ 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;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ cout << "geodesic distance to v[" << get(vertex_index, g, *i) << "] == "
+ << geodesic_distance(g, *i, dist) << endl;
+ }
+ cout << "mean geodesic distance == " << mean_geodesic_distance(g, dist) << end;
+
+The output of this program is:
+
+[pre
+geodesic distance to v\[0\] == 0
+geodesic distance to v\[1\] == 1
+geodesic distance to v\[2\] == 2
+geodesic distance to v\[3\] == 2
+geodesic distance to v\[4\] == 3
+geodesic distance to v\[5\] == 3
+geodesic distance to v\[6\] == 4
+geodesic distance to v\[7\] == 4
+geodesic distance to v\[8\] == 4
+geodesic distance to v\[9\] == 5
+mean geodesic distance == 2.8
]

[endsect]
\ No newline at end of file