1 // (C) Copyright 2007-2009 Andrew Sutton
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 #include <iostream>
8 #include <vector>
9
10 #include <boost/graph/undirected_graph.hpp>
11 #include <boost/graph/directed_graph.hpp>
12 #include <boost/graph/floyd_warshall_shortest.hpp>
13 #include <boost/graph/closeness_centrality.hpp>
14 #include <boost/graph/exterior_property.hpp>
15 #include <boost/graph/property_maps/constant_property_map.hpp>
16
17 using namespace std;
18 using namespace boost;
19
20 // number of vertices in the graph
21 static const unsigned N = 5;
22
23 template < typename Graph > struct vertex_vector
24 {
25 typedef graph_traits< Graph > traits;
26 typedef vector< typename traits::vertex_descriptor > type;
27 };
28
29 template < typename Graph >
build_graph(Graph & g,typename vertex_vector<Graph>::type & v)30 void build_graph(Graph& g, typename vertex_vector< Graph >::type& v)
31 {
32 // add vertices
33 for (size_t i = 0; i < N; ++i)
34 {
35 v[i] = add_vertex(g);
36 }
37
38 // add edges
39 add_edge(v[0], v[1], g);
40 add_edge(v[1], v[2], g);
41 add_edge(v[2], v[0], g);
42 add_edge(v[3], v[4], g);
43 add_edge(v[4], v[0], g);
44 }
45
test_undirected()46 template < typename Graph > void test_undirected()
47 {
48 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
49 typedef typename graph_traits< Graph >::edge_descriptor Edge;
50
51 typedef exterior_vertex_property< Graph, double > CentralityProperty;
52 typedef typename CentralityProperty::container_type CentralityContainer;
53 typedef typename CentralityProperty::map_type CentralityMap;
54
55 typedef exterior_vertex_property< Graph, int > DistanceProperty;
56 typedef typename DistanceProperty::matrix_type DistanceMatrix;
57 typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
58
59 typedef constant_property_map< Edge, int > WeightMap;
60
61 Graph g;
62 vector< Vertex > v(N);
63 build_graph(g, v);
64
65 CentralityContainer centralities(num_vertices(g));
66 DistanceMatrix distances(num_vertices(g));
67
68 CentralityMap cm(centralities, g);
69 DistanceMatrixMap dm(distances, g);
70
71 WeightMap wm(1);
72
73 floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
74 all_closeness_centralities(g, dm, cm);
75
76 BOOST_ASSERT(cm[v[0]] == double(1) / 5);
77 BOOST_ASSERT(cm[v[1]] == double(1) / 7);
78 BOOST_ASSERT(cm[v[2]] == double(1) / 7);
79 BOOST_ASSERT(cm[v[3]] == double(1) / 9);
80 BOOST_ASSERT(cm[v[4]] == double(1) / 6);
81 }
82
test_directed()83 template < typename Graph > void test_directed()
84 {
85 typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
86 typedef typename graph_traits< Graph >::edge_descriptor Edge;
87
88 typedef exterior_vertex_property< Graph, double > CentralityProperty;
89 typedef typename CentralityProperty::container_type CentralityContainer;
90 typedef typename CentralityProperty::map_type CentralityMap;
91
92 typedef exterior_vertex_property< Graph, int > DistanceProperty;
93 typedef typename DistanceProperty::matrix_type DistanceMatrix;
94 typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
95
96 typedef constant_property_map< Edge, int > WeightMap;
97
98 Graph g;
99 vector< Vertex > v(N);
100 build_graph(g, v);
101
102 CentralityContainer centralities(num_vertices(g));
103 DistanceMatrix distances(num_vertices(g));
104
105 CentralityMap cm(centralities, g);
106 DistanceMatrixMap dm(distances, g);
107
108 WeightMap wm(1);
109
110 floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
111 all_closeness_centralities(g, dm, cm);
112
113 BOOST_ASSERT(cm[v[0]] == double(0));
114 BOOST_ASSERT(cm[v[1]] == double(0));
115 BOOST_ASSERT(cm[v[2]] == double(0));
116 BOOST_ASSERT(cm[v[3]] == double(1) / 10);
117 BOOST_ASSERT(cm[v[4]] == double(0));
118 }
119
main(int,char * [])120 int main(int, char*[])
121 {
122 typedef undirected_graph<> Graph;
123 typedef directed_graph<> Digraph;
124
125 test_undirected< Graph >();
126 test_directed< Digraph >();
127 }
128