123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158 |
- // (C) Copyright Andrew Sutton 2007
- //
- // Use, modification and distribution are subject to the
- // Boost Software License, Version 1.0 (See accompanying file
- // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
- //[inclusive_mean_geodesic_example
- #include <iostream>
- #include <iomanip>
- #include <boost/graph/directed_graph.hpp>
- #include <boost/graph/exterior_property.hpp>
- #include <boost/graph/floyd_warshall_shortest.hpp>
- #include <boost/graph/geodesic_distance.hpp>
- #include "helper.hpp"
- using namespace std;
- using namespace boost;
- // This template structure defines the function that we will apply
- // to compute both the per-vertex mean geodesic distances and the
- // graph's mean geodesic distance.
- template <typename Graph,
- typename DistanceType,
- typename ResultType,
- typename Divides = divides<ResultType> >
- struct inclusive_average
- {
- typedef DistanceType distance_type;
- typedef ResultType result_type;
- result_type operator ()(distance_type d, const Graph& g)
- {
- if(d == numeric_values<distance_type>::infinity()) {
- return numeric_values<result_type>::infinity();
- }
- else {
- return div(result_type(d), result_type(num_vertices(g)));
- }
- }
- Divides div;
- };
- // The Page type stores the name of each vertex in the graph and
- // represents web pages that can be navigated to.
- struct WebPage
- {
- string name;
- };
- // The Link type stores an associated probability of traveling
- // from one page to another.
- struct Link
- {
- float probability;
- };
- // Declare the graph type and its vertex and edge types.
- typedef directed_graph<WebPage, Link> Graph;
- typedef graph_traits<Graph>::vertex_descriptor Vertex;
- typedef graph_traits<Graph>::edge_descriptor Edge;
- // The name map provides an abstract accessor for the names of
- // each vertex. This is used during graph creation.
- typedef property_map<Graph, string WebPage::*>::type NameMap;
- // Declare a matrix type and its corresponding property map that
- // will contain the distances between each pair of vertices.
- typedef exterior_vertex_property<Graph, float> DistanceProperty;
- typedef DistanceProperty::matrix_type DistanceMatrix;
- typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
- // Declare the weight map as an accessor into the bundled
- // edge property.
- typedef property_map<Graph, float Link::*>::type WeightMap;
- // Declare a container and its corresponding property map that
- // will contain the resulting mean geodesic distances of each
- // vertex in the graph.
- typedef exterior_vertex_property<Graph, float> GeodesicProperty;
- typedef GeodesicProperty::container_type GeodesicContainer;
- typedef GeodesicProperty::map_type GeodesicMap;
- static float exclusive_geodesics(const Graph&, DistanceMatrixMap, GeodesicMap);
- static float inclusive_geodesics(const Graph&, DistanceMatrixMap, GeodesicMap);
- int
- main(int argc, char *argv[])
- {
- // Create the graph, a name map that providse abstract access
- // to the web page names, and the weight map as an accessor to
- // the edge weights (or probabilities).
- Graph g;
- NameMap nm(get(&WebPage::name, g));
- WeightMap wm(get(&Link::probability, g));
- // Read the weighted graph from standard input.
- read_weighted_graph(g, nm, wm, cin);
- // Compute the distances between all pairs of vertices using
- // the Floyd-Warshall algorithm. The weight map was created
- // above so it could be populated when the graph was read in.
- DistanceMatrix distances(num_vertices(g));
- DistanceMatrixMap dm(distances, g);
- floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
- // Create the containers and the respective property maps that
- // will contain the mean geodesics averaged both including
- // self-loop distances and excluding them.
- GeodesicContainer exclude(num_vertices(g));
- GeodesicContainer include(num_vertices(g));
- GeodesicMap exmap(exclude, g);
- GeodesicMap inmap(include, g);
- float ex = exclusive_geodesics(g, dm, exmap);
- float in = inclusive_geodesics(g, dm, inmap);
- // Print the mean geodesic distance of each vertex and finally,
- // the graph itself.
- cout << setw(12) << setiosflags(ios::left) << "vertex";
- cout << setw(12) << setiosflags(ios::left) << "excluding";
- cout << setw(12) << setiosflags(ios::left) << "including" << endl;
- graph_traits<Graph>::vertex_iterator i, end;
- for(boost::tie(i, end) = vertices(g); i != end; ++i) {
- cout << setw(12) << setiosflags(ios::left)
- << g[*i].name
- << setw(12) << get(exmap, *i)
- << setw(12) << get(inmap, *i) << endl;
- }
- cout << "small world (excluding self-loops): " << ex << endl;
- cout << "small world (including self-loops): " << in << endl;
- return 0;
- }
- float
- exclusive_geodesics(const Graph& g, DistanceMatrixMap dm, GeodesicMap gm)
- {
- // Compute the mean geodesic distances, which excludes distances
- // of self-loops by default. Return the measure for the entire graph.
- return all_mean_geodesics(g, dm, gm);
- }
- float
- inclusive_geodesics(const Graph &g, DistanceMatrixMap dm, GeodesicMap gm)
- {
- // Create a new measure object for computing the mean geodesic
- // distance of all vertices. This measure will actually be used
- // for both averages.
- inclusive_average<Graph, float, float> m;
- // Compute the mean geodesic distance using the inclusive average
- // to account for self-loop distances. Return the measure for the
- // entire graph.
- return all_mean_geodesics(g, dm, gm, m);
- }
- //]
|