ceph/src/boost/libs/graph/example/closeness_centrality.cpp

   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 //[closeness_centrality_example
   8 #include <iostream>
   9 #include <iomanip>
  10
  11 #include <boost/graph/undirected_graph.hpp>
  12 #include <boost/graph/exterior_property.hpp>
  13 #include <boost/graph/floyd_warshall_shortest.hpp>
  14 #include <boost/graph/closeness_centrality.hpp>
  15 #include <boost/graph/property_maps/constant_property_map.hpp>
  16 #include "helper.hpp"
  17
  18 using namespace std;
  19 using namespace boost;
  20
  21 // The Actor type stores the name of each vertex in the graph.
  22 struct Actor
  23 {
  24     string name;
  25 };
  26
  27 // Declare the graph type and its vertex and edge types.
  28 typedef undirected_graph<Actor> Graph;
  29 typedef graph_traits<Graph>::vertex_descriptor Vertex;
  30 typedef graph_traits<Graph>::edge_descriptor Edge;
  31
  32 // The name map provides an abstract accessor for the names of
  33 // each vertex. This is used during graph creation.
  34 typedef property_map<Graph, string Actor::*>::type NameMap;
  35
  36 // Declare a matrix type and its corresponding property map that
  37 // will contain the distances between each pair of vertices.
  38 typedef exterior_vertex_property<Graph, int> DistanceProperty;
  39 typedef DistanceProperty::matrix_type DistanceMatrix;
  40 typedef DistanceProperty::matrix_map_type DistanceMatrixMap;
  41
  42 // Declare the weight map so that each edge returns the same value.
  43 typedef constant_property_map<Edge, int> WeightMap;
  44
  45 // Declare a container and its corresponding property map that
  46 // will contain the resulting closeness centralities of each
  47 // vertex in the graph.
  48 typedef boost::exterior_vertex_property<Graph, float> ClosenessProperty;
  49 typedef ClosenessProperty::container_type ClosenessContainer;
  50 typedef ClosenessProperty::map_type ClosenessMap;
  51
  52 int
  53 main(int argc, char *argv[])
  54 {
  55     // Create the graph and a property map that provides access to[
  56     // tha actor names.
  57     Graph g;
  58     NameMap nm(get(&Actor::name, g));
  59
  60     // Read the graph from standard input.
  61     read_graph(g, nm, cin);
  62
  63     // Compute the distances between all pairs of vertices using
  64     // the Floyd-Warshall algorithm. Note that the weight map is
  65     // created so that every edge has a weight of 1.
  66     DistanceMatrix distances(num_vertices(g));
  67     DistanceMatrixMap dm(distances, g);
  68     WeightMap wm(1);
  69     floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
  70
  71     // Compute the closeness centrality for graph.
  72     ClosenessContainer cents(num_vertices(g));
  73     ClosenessMap cm(cents, g);
  74     all_closeness_centralities(g, dm, cm);
  75
  76     // Print the closeness centrality of each vertex.
  77     graph_traits<Graph>::vertex_iterator i, end;
  78     for(boost::tie(i, end) = vertices(g); i != end; ++i) {
  79         cout << setw(12) << setiosflags(ios::left)
  80              << g[*i].name << get(cm, *i) << endl;
  81     }
  82
  83     return 0;
  84 }
  85 //]