]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
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> | |
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> | |
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 | |
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 | } |