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>
25 struct vertex_vector
26 {
27 typedef graph_traits<Graph> traits;
28 typedef vector<typename traits::vertex_descriptor> type;
29 };
30
31 template <typename Graph>
build_graph(Graph & g,typename vertex_vector<Graph>::type & v)32 void build_graph(Graph& g, typename vertex_vector<Graph>::type& v)
33 {
34 // add vertices
35 for(size_t i = 0; i < N; ++i) {
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
48 template <typename Graph>
test_undirected()49 void test_undirected()
50 {
51 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
52 typedef typename graph_traits<Graph>::edge_descriptor Edge;
53
54 typedef exterior_vertex_property<Graph, double> CentralityProperty;
55 typedef typename CentralityProperty::container_type CentralityContainer;
56 typedef typename CentralityProperty::map_type CentralityMap;
57
58 typedef exterior_vertex_property<Graph, int> DistanceProperty;
59 typedef typename DistanceProperty::matrix_type DistanceMatrix;
60 typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
61
62 typedef constant_property_map<Edge, int> WeightMap;
63
64 Graph g;
65 vector<Vertex> v(N);
66 build_graph(g, v);
67
68 CentralityContainer centralities(num_vertices(g));
69 DistanceMatrix distances(num_vertices(g));
70
71 CentralityMap cm(centralities, g);
72 DistanceMatrixMap dm(distances, g);
73
74 WeightMap wm(1);
75
76 floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
77 double geo1 = all_mean_geodesics(g, dm, cm);
78 double geo2 = small_world_distance(g, cm);
79
80 BOOST_ASSERT(cm[v[0]] == double(5)/4);
81 BOOST_ASSERT(cm[v[1]] == double(7)/4);
82 BOOST_ASSERT(cm[v[2]] == double(7)/4);
83 BOOST_ASSERT(cm[v[3]] == double(9)/4);
84 BOOST_ASSERT(cm[v[4]] == double(6)/4);
85 BOOST_ASSERT(geo1 == double(34)/20);
86 BOOST_ASSERT(geo1 == geo2);
87 }
88
89 template <typename Graph>
test_directed()90 void test_directed()
91 {
92 typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
93 typedef typename graph_traits<Graph>::edge_descriptor Edge;
94
95 typedef exterior_vertex_property<Graph, double> CentralityProperty;
96 typedef typename CentralityProperty::container_type CentralityContainer;
97 typedef typename CentralityProperty::map_type CentralityMap;
98
99 typedef exterior_vertex_property<Graph, int> DistanceProperty;
100 typedef typename DistanceProperty::matrix_type DistanceMatrix;
101 typedef typename DistanceProperty::matrix_map_type DistanceMatrixMap;
102
103 typedef constant_property_map<Edge, int> WeightMap;
104
105 Graph g;
106 vector<Vertex> v(N);
107 build_graph(g, v);
108
109 CentralityContainer centralities(num_vertices(g));
110 DistanceMatrix distances(num_vertices(g));
111
112 CentralityMap cm(centralities, g);
113 DistanceMatrixMap dm(distances, g);
114
115 WeightMap wm(1);
116
117 floyd_warshall_all_pairs_shortest_paths(g, dm, weight_map(wm));
118 double geo1 = all_mean_geodesics(g, dm, cm);
119 double geo2 = small_world_distance(g, cm);
120
121 double inf = numeric_values<double>::infinity();
122 BOOST_ASSERT(cm[v[0]] == inf);
123 BOOST_ASSERT(cm[v[1]] == inf);
124 BOOST_ASSERT(cm[v[2]] == inf);
125 BOOST_ASSERT(cm[v[3]] == double(10)/4);
126 BOOST_ASSERT(cm[v[4]] == inf);
127 BOOST_ASSERT(geo1 == inf);
128 BOOST_ASSERT(geo1 == geo2);
129 }
130
131
132 int
main(int,char * [])133 main(int, char *[])
134 {
135 typedef undirected_graph<> Graph;
136 typedef directed_graph<> Digraph;
137
138 test_undirected<Graph>();
139 test_directed<Digraph>();
140 }
141