1 // (C) Copyright Andrew Sutton 2007
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)
7 //[closeness_centrality_example
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>
19 using namespace boost
;
21 // The Actor type stores the name of each vertex in the graph.
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
;
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
;
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
;
42 // Declare the weight map so that each edge returns the same value.
43 typedef constant_property_map
< Edge
, int > WeightMap
;
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
;
52 int main(int argc
, char* argv
[])
54 // Create the graph and a property map that provides access to[
57 NameMap
nm(get(&Actor::name
, g
));
59 // Read the graph from standard input.
60 read_graph(g
, nm
, cin
);
62 // Compute the distances between all pairs of vertices using
63 // the Floyd-Warshall algorithm. Note that the weight map is
64 // created so that every edge has a weight of 1.
65 DistanceMatrix
distances(num_vertices(g
));
66 DistanceMatrixMap
dm(distances
, g
);
68 floyd_warshall_all_pairs_shortest_paths(g
, dm
, weight_map(wm
));
70 // Compute the closeness centrality for graph.
71 ClosenessContainer
cents(num_vertices(g
));
72 ClosenessMap
cm(cents
, g
);
73 all_closeness_centralities(g
, dm
, cm
);
75 // Print the closeness centrality of each vertex.
76 graph_traits
< Graph
>::vertex_iterator i
, end
;
77 for (boost::tie(i
, end
) = vertices(g
); i
!= end
; ++i
)
79 cout
<< setw(12) << setiosflags(ios::left
) << g
[*i
].name
<< get(cm
, *i
)