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 >
build_graph(Graph & g,typename vertex_vector<Graph>::type & v)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
test_undirected()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
test_directed()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
main(int,char * [])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