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