
BoostCommit : 
From: asutton_at_[hidden]
Date: 20070723 10:48:43
Author: asutton
Date: 20070723 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 20070723 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) {
+ 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())))
+ );
+
+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
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