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 > |
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 | |
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 | |
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 | |
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 | |