1 // (C) Copyright Andrew Sutton 2007
2 //
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
6
7 //[inclusive_mean_geodesic_example
8 #include <iostream>
9 #include <iomanip>
10
11 #include <boost/graph/directed_graph.hpp>
12 #include <boost/graph/exterior_property.hpp>
13 #include <boost/graph/floyd_warshall_shortest.hpp>
14 #include <boost/graph/geodesic_distance.hpp>
15 #include "helper.hpp"
16
17 using namespace std;
18 using namespace boost;
19
20 // This template structure defines the function that we will apply
21 // to compute both the per-vertex mean geodesic distances and the
22 // graph's mean geodesic distance.
23 template <typename Graph,
24 typename DistanceType,
25 typename ResultType,
26 typename Divides = divides<ResultType> >
27 struct inclusive_average
28 {
29 typedef DistanceType distance_type;
30 typedef ResultType result_type;
31
operator ()inclusive_average32 result_type operator ()(distance_type d, const Graph& g)
33 {
34 if(d == numeric_values<distance_type>::infinity()) {
35 return numeric_values<result_type>::infinity();
36 }
37 else {
38 return div(result_type(d), result_type(num_vertices(g)));
39 }
40 }
41 Divides div;
42 };
43
44 // The Page type stores the name of each vertex in the graph and
45 // represents web pages that can be navigated to.
46 struct WebPage
47 {
48 string name;
49 };
50
51 // The Link type stores an associated probability of traveling
52 // from one page to another.
53 struct Link
54 {
55 float probability;
56 };
57
58 // Declare the graph type and its vertex and edge types.
59 typedef directed_graph<WebPage, Link> Graph;
60 typedef graph_traits<Graph>::vertex_descriptor Vertex;
61 typedef graph_traits<Graph>::edge_descriptor Edge;
62
63 // The name map provides an abstract accessor for the names of
64 // each vertex. This is used during graph creation.
65 typedef property_map<Graph, string WebPage::*>::type NameMap;
66
67 // Declare a matrix type and its corresponding property map that
68 // will contain the distances between each pair of vertices.
69 typedef exterior_vertex_property<Graph, float> DistanceProperty;
70 typedef DistanceProperty::matrix_type DistanceMatrix;
71 typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
72
73 // Declare the weight map as an accessor into the bundled
74 // edge property.
75 typedef property_map<Graph, float Link::*>::type WeightMap;
76
77 // Declare a container and its corresponding property map that
78 // will contain the resulting mean geodesic distances of each
79 // vertex in the graph.
80 typedef exterior_vertex_property<Graph, float> GeodesicProperty;
81 typedef GeodesicProperty::container_type GeodesicContainer;
82 typedef GeodesicProperty::map_type GeodesicMap;
83
84 static float exclusive_geodesics(const Graph&, DistanceMatrixMap, GeodesicMap);
85 static float inclusive_geodesics(const Graph&, DistanceMatrixMap, GeodesicMap);
86
87 int
main(int argc,char * argv[])88 main(int argc, char *argv[])
89 {
90 // Create the graph, a name map that providse abstract access
91 // to the web page names, and the weight map as an accessor to
92 // the edge weights (or probabilities).
93 Graph g;
94 NameMap nm(get(&WebPage::name, g));
95 WeightMap wm(get(&Link::probability, g));
96
97 // Read the weighted graph from standard input.
98 read_weighted_graph(g, nm, wm, cin);
99
100 // Compute the distances between all pairs of vertices using
101 // the Floyd-Warshall algorithm. The weight map was created
102 // above so it could be populated when the graph was read in.
103 DistanceMatrix distances(num_vertices(g));
104 DistanceMatrixMap dm(distances, g);
105 floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
106
107 // Create the containers and the respective property maps that
108 // will contain the mean geodesics averaged both including
109 // self-loop distances and excluding them.
110 GeodesicContainer exclude(num_vertices(g));
111 GeodesicContainer include(num_vertices(g));
112 GeodesicMap exmap(exclude, g);
113 GeodesicMap inmap(include, g);
114
115 float ex = exclusive_geodesics(g, dm, exmap);
116 float in = inclusive_geodesics(g, dm, inmap);
117
118 // Print the mean geodesic distance of each vertex and finally,
119 // the graph itself.
120 cout << setw(12) << setiosflags(ios::left) << "vertex";
121 cout << setw(12) << setiosflags(ios::left) << "excluding";
122 cout << setw(12) << setiosflags(ios::left) << "including" << endl;
123 graph_traits<Graph>::vertex_iterator i, end;
124 for(boost::tie(i, end) = vertices(g); i != end; ++i) {
125 cout << setw(12) << setiosflags(ios::left)
126 << g[*i].name
127 << setw(12) << get(exmap, *i)
128 << setw(12) << get(inmap, *i) << endl;
129 }
130 cout << "small world (excluding self-loops): " << ex << endl;
131 cout << "small world (including self-loops): " << in << endl;
132
133 return 0;
134 }
135
136 float
exclusive_geodesics(const Graph & g,DistanceMatrixMap dm,GeodesicMap gm)137 exclusive_geodesics(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
138 {
139 // Compute the mean geodesic distances, which excludes distances
140 // of self-loops by default. Return the measure for the entire graph.
141 return all_mean_geodesics(g, dm, gm);
142 }
143
144
145 float
inclusive_geodesics(const Graph & g,DistanceMatrixMap dm,GeodesicMap gm)146 inclusive_geodesics(const Graph &g, DistanceMatrixMap dm, GeodesicMap gm)
147 {
148 // Create a new measure object for computing the mean geodesic
149 // distance of all vertices. This measure will actually be used
150 // for both averages.
151 inclusive_average<Graph, float, float> m;
152
153 // Compute the mean geodesic distance using the inclusive average
154 // to account for self-loop distances. Return the measure for the
155 // entire graph.
156 return all_mean_geodesics(g, dm, gm, m);
157 }
158 //]
159