1 // (C) Copyright 2007-2009 Andrew Sutton
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)
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>
14 #include <boost/graph/floyd_warshall_shortest.hpp>
15 #include <boost/graph/geodesic_distance.hpp>
18 using namespace boost
;
21 // number of vertices in the graph
22 static const unsigned N
= 5;
24 template < typename Graph
> struct vertex_vector
26 typedef graph_traits
< Graph
> traits
;
27 typedef vector
< typename
traits::vertex_descriptor
> type
;
30 template < typename Graph
>
31 void build_graph(Graph
& g
, typename vertex_vector
< Graph
>::type
& v
)
34 for (size_t i
= 0; i
< N
; ++i
)
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
);
47 template < typename Graph
> void test_undirected()
49 typedef typename graph_traits
< Graph
>::vertex_descriptor Vertex
;
50 typedef typename graph_traits
< Graph
>::edge_descriptor Edge
;
52 typedef exterior_vertex_property
< Graph
, double > CentralityProperty
;
53 typedef typename
CentralityProperty::container_type CentralityContainer
;
54 typedef typename
CentralityProperty::map_type CentralityMap
;
56 typedef exterior_vertex_property
< Graph
, int > DistanceProperty
;
57 typedef typename
DistanceProperty::matrix_type DistanceMatrix
;
58 typedef typename
DistanceProperty::matrix_map_type DistanceMatrixMap
;
60 typedef constant_property_map
< Edge
, int > WeightMap
;
63 vector
< Vertex
> v(N
);
66 CentralityContainer
centralities(num_vertices(g
));
67 DistanceMatrix
distances(num_vertices(g
));
69 CentralityMap
cm(centralities
, g
);
70 DistanceMatrixMap
dm(distances
, g
);
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
);
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
);
87 template < typename Graph
> void test_directed()
89 typedef typename graph_traits
< Graph
>::vertex_descriptor Vertex
;
90 typedef typename graph_traits
< Graph
>::edge_descriptor Edge
;
92 typedef exterior_vertex_property
< Graph
, double > CentralityProperty
;
93 typedef typename
CentralityProperty::container_type CentralityContainer
;
94 typedef typename
CentralityProperty::map_type CentralityMap
;
96 typedef exterior_vertex_property
< Graph
, int > DistanceProperty
;
97 typedef typename
DistanceProperty::matrix_type DistanceMatrix
;
98 typedef typename
DistanceProperty::matrix_map_type DistanceMatrixMap
;
100 typedef constant_property_map
< Edge
, int > WeightMap
;
103 vector
< Vertex
> v(N
);
106 CentralityContainer
centralities(num_vertices(g
));
107 DistanceMatrix
distances(num_vertices(g
));
109 CentralityMap
cm(centralities
, g
);
110 DistanceMatrixMap
dm(distances
, g
);
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
);
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
);
128 int main(int, char*[])
130 typedef undirected_graph
<> Graph
;
131 typedef directed_graph
<> Digraph
;
133 test_undirected
< Graph
>();
134 test_directed
< Digraph
>();