1 // Copyright 2005 The Trustees of Indiana University.
2
3 // Use, modification and distribution is subject to the Boost Software
4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 // Authors: Jeremiah Willcock
8 // Douglas Gregor
9 // Andrew Lumsdaine
10
11 // The libstdc++ debug mode makes this test run for hours...
12 #ifdef _GLIBCXX_DEBUG
13 # undef _GLIBCXX_DEBUG
14 #endif
15
16 // Test for the compressed sparse row graph type
17 #include <boost/graph/compressed_sparse_row_graph.hpp>
18 #include <boost/graph/adjacency_list.hpp>
19 #include <boost/graph/erdos_renyi_generator.hpp>
20 #include <boost/graph/graph_utility.hpp>
21 #include <boost/random/linear_congruential.hpp>
22 #include <boost/concept_check.hpp> // for ignore_unused_variable_warning
23 #include <cassert>
24 #include <iostream>
25 #include <vector>
26 #include <algorithm>
27 #include <ctime>
28 #include <boost/lexical_cast.hpp>
29 #include <boost/iterator/transform_iterator.hpp>
30 #include <boost/limits.hpp>
31 #include <string>
32 #include <boost/graph/iteration_macros.hpp>
33 #include <boost/test/minimal.hpp>
34
35 // Algorithms to test against
36 #include <boost/graph/betweenness_centrality.hpp>
37 #include <boost/graph/kruskal_min_spanning_tree.hpp>
38
39 typedef boost::adjacency_list<> GraphT;
40 typedef boost::erdos_renyi_iterator<boost::minstd_rand, GraphT> ERGen;
41
42 struct VertexData
43 {
44 int index;
45 };
46
47 struct EdgeData
48 {
49 int index_e;
50 };
51
52 typedef boost::compressed_sparse_row_graph<boost::directedS, VertexData, EdgeData>
53 CSRGraphT;
54
55 typedef boost::compressed_sparse_row_graph<boost::bidirectionalS, VertexData, EdgeData>
56 BidirCSRGraphT;
57
58 template <class G1, class VI1, class G2, class VI2, class IsomorphismMap>
assert_graphs_equal(const G1 & g1,const VI1 & vi1,const G2 & g2,const VI2 & vi2,const IsomorphismMap & iso)59 void assert_graphs_equal(const G1& g1, const VI1& vi1,
60 const G2& g2, const VI2& vi2,
61 const IsomorphismMap& iso) {
62 using boost::out_degree;
63
64 BOOST_CHECK (num_vertices(g1) == num_vertices(g2));
65 BOOST_CHECK (num_edges(g1) == num_edges(g2));
66
67 typedef typename boost::graph_traits<G1>::vertex_iterator vertiter1;
68 {
69 vertiter1 i, iend;
70 for (boost::tie(i, iend) = vertices(g1); i != iend; ++i) {
71 typename boost::graph_traits<G1>::vertex_descriptor v1 = *i;
72 typename boost::graph_traits<G2>::vertex_descriptor v2 = iso[v1];
73
74 BOOST_CHECK (vi1[v1] == vi2[v2]);
75
76 BOOST_CHECK (out_degree(v1, g1) == out_degree(v2, g2));
77 std::vector<std::size_t> edges1(out_degree(v1, g1));
78 typename boost::graph_traits<G1>::out_edge_iterator oe1, oe1end;
79 for (boost::tie(oe1, oe1end) = out_edges(v1, g1); oe1 != oe1end; ++oe1) {
80 BOOST_CHECK (source(*oe1, g1) == v1);
81 edges1.push_back(vi1[target(*oe1, g1)]);
82 }
83 std::vector<std::size_t> edges2(out_degree(v2, g2));
84 typename boost::graph_traits<G2>::out_edge_iterator oe2, oe2end;
85 for (boost::tie(oe2, oe2end) = out_edges(v2, g2); oe2 != oe2end; ++oe2) {
86 BOOST_CHECK (source(*oe2, g2) == v2);
87 edges2.push_back(vi2[target(*oe2, g2)]);
88 }
89
90 std::sort(edges1.begin(), edges1.end());
91 std::sort(edges2.begin(), edges2.end());
92 if (edges1 != edges2) {
93 std::cerr << "For vertex " << v1 << std::endl;
94 std::cerr << "edges1:";
95 for (size_t i = 0; i < edges1.size(); ++i) std::cerr << " " << edges1[i];
96 std::cerr << std::endl;
97 std::cerr << "edges2:";
98 for (size_t i = 0; i < edges2.size(); ++i) std::cerr << " " << edges2[i];
99 std::cerr << std::endl;
100 }
101 BOOST_CHECK (edges1 == edges2);
102 }
103 }
104
105 {
106 std::vector<std::pair<std::size_t, std::size_t> > all_edges1;
107 std::vector<std::pair<std::size_t, std::size_t> > all_edges2;
108 typename boost::graph_traits<G1>::edge_iterator ei1, ei1end;
109 for (boost::tie(ei1, ei1end) = edges(g1); ei1 != ei1end; ++ei1)
110 all_edges1.push_back(std::make_pair(vi1[source(*ei1, g1)],
111 vi1[target(*ei1, g1)]));
112 typename boost::graph_traits<G2>::edge_iterator ei2, ei2end;
113 for (boost::tie(ei2, ei2end) = edges(g2); ei2 != ei2end; ++ei2)
114 all_edges2.push_back(std::make_pair(vi2[source(*ei2, g2)],
115 vi2[target(*ei2, g2)]));
116 std::sort(all_edges1.begin(), all_edges1.end());
117 std::sort(all_edges2.begin(), all_edges2.end());
118 BOOST_CHECK (all_edges1 == all_edges2);
119 }
120 }
121
122 template <typename Structure>
check_consistency_one(const Structure & g)123 void check_consistency_one(const Structure& g) {
124 // Do a bunch of tests on the graph internal data
125 // Check that m_rowstart entries are valid, and that entries after
126 // m_last_source + 1 are all zero
127 BOOST_CHECK(g.m_rowstart[0] == 0);
128 for (size_t i = 0;
129 i < g.m_rowstart.size() - 1;
130 ++i) {
131 BOOST_CHECK(g.m_rowstart[i + 1] >= g.m_rowstart[i]);
132 BOOST_CHECK(g.m_rowstart[i + 1] <= g.m_rowstart.back());
133 }
134 // Check that m_column entries are within range
135 for (size_t i = 0; i < g.m_rowstart.back(); ++i) {
136 BOOST_CHECK(g.m_column[i] < g.m_rowstart.size() - 1);
137 }
138 }
139
140 template <typename Graph>
check_consistency_dispatch(const Graph & g,boost::incidence_graph_tag)141 void check_consistency_dispatch(const Graph& g,
142 boost::incidence_graph_tag) {
143 check_consistency_one(g.m_forward);
144 }
145
146 template <class G>
assert_bidir_equal_in_both_dirs(const G & g)147 void assert_bidir_equal_in_both_dirs(const G& g) {
148 BOOST_CHECK (g.m_forward.m_rowstart.size() == g.m_backward.m_rowstart.size());
149 BOOST_CHECK (g.m_forward.m_column.size() == g.m_backward.m_column.size());
150 typedef typename boost::graph_traits<G>::vertex_descriptor Vertex;
151 typedef typename boost::graph_traits<G>::edges_size_type EdgeIndex;
152 std::vector<boost::tuple<EdgeIndex, Vertex, Vertex> > edges_forward, edges_backward;
153 for (Vertex i = 0; i < g.m_forward.m_rowstart.size() - 1; ++i) {
154 for (EdgeIndex j = g.m_forward.m_rowstart[i];
155 j < g.m_forward.m_rowstart[i + 1]; ++j) {
156 edges_forward.push_back(boost::make_tuple(j, i, g.m_forward.m_column[j]));
157 }
158 }
159 for (Vertex i = 0; i < g.m_backward.m_rowstart.size() - 1; ++i) {
160 for (EdgeIndex j = g.m_backward.m_rowstart[i];
161 j < g.m_backward.m_rowstart[i + 1]; ++j) {
162 edges_backward.push_back(boost::make_tuple(g.m_backward.m_edge_properties[j], g.m_backward.m_column[j], i));
163 }
164 }
165 std::sort(edges_forward.begin(), edges_forward.end());
166 std::sort(edges_backward.begin(), edges_backward.end());
167 BOOST_CHECK (edges_forward == edges_backward);
168 }
169
170 template <typename Graph>
check_consistency_dispatch(const Graph & g,boost::bidirectional_graph_tag)171 void check_consistency_dispatch(const Graph& g,
172 boost::bidirectional_graph_tag) {
173 check_consistency_one(g.m_forward);
174 check_consistency_one(g.m_backward);
175 assert_bidir_equal_in_both_dirs(g);
176 }
177
178 template <typename Graph>
check_consistency(const Graph & g)179 void check_consistency(const Graph& g) {
180 check_consistency_dispatch(g, typename boost::graph_traits<Graph>::traversal_category());
181 }
182
183 template<typename OrigGraph>
graph_test(const OrigGraph & g)184 void graph_test(const OrigGraph& g)
185 {
186 // Check copying of a graph
187 CSRGraphT g2(g);
188 check_consistency(g2);
189 BOOST_CHECK((std::size_t)std::distance(edges(g2).first, edges(g2).second)
190 == num_edges(g2));
191 assert_graphs_equal(g, boost::identity_property_map(),
192 g2, boost::identity_property_map(),
193 boost::identity_property_map());
194
195 // Check constructing a graph from iterators
196 CSRGraphT g3(boost::edges_are_sorted,
197 boost::make_transform_iterator(edges(g2).first,
198 boost::detail::make_edge_to_index_pair(g2)),
199 boost::make_transform_iterator(edges(g2).second,
200 boost::detail::make_edge_to_index_pair(g2)),
201 num_vertices(g));
202 check_consistency(g3);
203 BOOST_CHECK((std::size_t)std::distance(edges(g3).first, edges(g3).second)
204 == num_edges(g3));
205 assert_graphs_equal(g2, boost::identity_property_map(),
206 g3, boost::identity_property_map(),
207 boost::identity_property_map());
208
209 // Check constructing a graph using in-place modification of vectors
210 {
211 std::vector<std::size_t> sources(num_edges(g2));
212 std::vector<std::size_t> targets(num_edges(g2));
213 std::size_t idx = 0;
214 // Edges actually sorted
215 BGL_FORALL_EDGES(e, g2, CSRGraphT) {
216 sources[idx] = source(e, g2);
217 targets[idx] = target(e, g2);
218 ++idx;
219 }
220 CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
221 sources,
222 targets,
223 num_vertices(g2));
224 check_consistency(g3a);
225 assert_graphs_equal(g2, boost::identity_property_map(),
226 g3a, boost::identity_property_map(),
227 boost::identity_property_map());
228 }
229 {
230 std::vector<std::size_t> sources(num_edges(g2));
231 std::vector<std::size_t> targets(num_edges(g2));
232 std::size_t idx = 0;
233 // Edges reverse-sorted
234 BGL_FORALL_EDGES(e, g2, CSRGraphT) {
235 sources[num_edges(g2) - 1 - idx] = source(e, g2);
236 targets[num_edges(g2) - 1 - idx] = target(e, g2);
237 ++idx;
238 }
239 CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
240 sources,
241 targets,
242 num_vertices(g2));
243 check_consistency(g3a);
244 assert_graphs_equal(g2, boost::identity_property_map(),
245 g3a, boost::identity_property_map(),
246 boost::identity_property_map());
247 }
248 {
249 std::vector<std::size_t> sources(num_edges(g2));
250 std::vector<std::size_t> targets(num_edges(g2));
251 std::size_t idx = 0;
252 // Edges scrambled using Fisher-Yates shuffle (Durstenfeld variant) from
253 // Wikipedia
254 BGL_FORALL_EDGES(e, g2, CSRGraphT) {
255 sources[idx] = source(e, g2);
256 targets[idx] = target(e, g2);
257 ++idx;
258 }
259 boost::minstd_rand gen(1);
260 if (num_edges(g) != 0) {
261 for (std::size_t i = num_edges(g) - 1; i > 0; --i) {
262 std::size_t scrambled = boost::uniform_int<>(0, i)(gen);
263 if (scrambled == i) continue;
264 using std::swap;
265 swap(sources[i], sources[scrambled]);
266 swap(targets[i], targets[scrambled]);
267 }
268 }
269 CSRGraphT g3a(boost::construct_inplace_from_sources_and_targets,
270 sources,
271 targets,
272 num_vertices(g2));
273 check_consistency(g3a);
274 assert_graphs_equal(g2, boost::identity_property_map(),
275 g3a, boost::identity_property_map(),
276 boost::identity_property_map());
277 }
278
279 CSRGraphT::edge_iterator ei, ei_end;
280
281 // Check edge_from_index (and implicitly the edge_index property map) for
282 // each edge in g2
283 std::size_t last_src = 0;
284 for (boost::tie(ei, ei_end) = edges(g2); ei != ei_end; ++ei) {
285 BOOST_CHECK(edge_from_index(get(boost::edge_index, g2, *ei), g2) == *ei);
286 std::size_t src = get(boost::vertex_index, g2, source(*ei, g2));
287 (void)(std::size_t)get(boost::vertex_index, g2, target(*ei, g2));
288 BOOST_CHECK(src >= last_src);
289 last_src = src;
290 }
291
292 // Check out edge iteration and vertex iteration for sortedness
293 CSRGraphT::vertex_iterator vi, vi_end;
294 std::size_t last_vertex = 0;
295 bool first_iter = true;
296 for (boost::tie(vi, vi_end) = vertices(g2); vi != vi_end; ++vi) {
297 std::size_t v = get(boost::vertex_index, g2, *vi);
298 BOOST_CHECK(first_iter || v > last_vertex);
299 last_vertex = v;
300 first_iter = false;
301
302 CSRGraphT::out_edge_iterator oei, oei_end;
303 for (boost::tie(oei, oei_end) = out_edges(*vi, g2); oei != oei_end; ++oei) {
304 BOOST_CHECK(source(*oei, g2) == *vi);
305 }
306
307 // Find a vertex for testing
308 CSRGraphT::vertex_descriptor test_vertex = vertex(num_vertices(g2) / 2, g2);
309 int edge_count = 0;
310 CSRGraphT::out_edge_iterator oei2, oei2_end;
311 for (boost::tie(oei2, oei_end) = out_edges(*vi, g2); oei2 != oei_end; ++oei2) {
312 if (target(*oei2, g2) == test_vertex)
313 ++edge_count;
314 }
315 }
316
317 // Run brandes_betweenness_centrality, which touches on a whole lot
318 // of things, including VertexListGraph and IncidenceGraph
319 using namespace boost;
320 std::vector<double> vertex_centralities(num_vertices(g3));
321 std::vector<double> edge_centralities(num_edges(g3));
322 brandes_betweenness_centrality
323 (g3,
324 make_iterator_property_map(vertex_centralities.begin(),
325 get(boost::vertex_index, g3)),
326 make_iterator_property_map(edge_centralities.begin(),
327 get(boost::edge_index, g3)));
328 // Extra qualifications for aCC
329
330 // Invert the edge centralities and use these as weights to
331 // Kruskal's MST algorithm, which will test the EdgeListGraph
332 // capabilities.
333 double max_val = (std::numeric_limits<double>::max)();
334 for (std::size_t i = 0; i < num_edges(g3); ++i)
335 edge_centralities[i] =
336 edge_centralities[i] == 0.0? max_val : 1.0 / edge_centralities[i];
337
338 typedef boost::graph_traits<CSRGraphT>::edge_descriptor edge_descriptor;
339 std::vector<edge_descriptor> mst_edges;
340 mst_edges.reserve(num_vertices(g3));
341 kruskal_minimum_spanning_tree
342 (g3, std::back_inserter(mst_edges),
343 weight_map(make_iterator_property_map(edge_centralities.begin(),
344 get(boost::edge_index, g3))));
345 }
346
graph_test(int nnodes,double density,int seed)347 void graph_test(int nnodes, double density, int seed)
348 {
349 boost::minstd_rand gen(seed);
350 std::cout << "Testing " << nnodes << " density " << density << std::endl;
351 GraphT g(ERGen(gen, nnodes, density), ERGen(), nnodes);
352 graph_test(g);
353 }
354
test_graph_properties()355 void test_graph_properties()
356 {
357 using namespace boost;
358
359 typedef compressed_sparse_row_graph<directedS,
360 no_property,
361 no_property,
362 property<graph_name_t, std::string> >
363 CSRGraphT;
364
365 CSRGraphT g;
366 BOOST_CHECK(get_property(g, graph_name) == "");
367 set_property(g, graph_name, "beep");
368 BOOST_CHECK(get_property(g, graph_name) == "beep");
369 }
370
371 struct Vertex
372 {
373 double centrality;
374 };
375
376 struct Edge
377 {
EdgeEdge378 Edge(double weight) : weight(weight), centrality(0.0) { }
379
380 double weight;
381 double centrality;
382 };
383
test_vertex_and_edge_properties()384 void test_vertex_and_edge_properties()
385 {
386 using namespace boost;
387 typedef compressed_sparse_row_graph<directedS, Vertex, Edge>
388 CSRGraphWithPropsT;
389
390 typedef std::pair<int, int> E;
391 E edges_init[6] = { E(0, 1), E(0, 3), E(1, 2), E(3, 1), E(3, 4), E(4, 2) };
392 double weights[6] = { 1.0, 1.0, 0.5, 1.0, 1.0, 0.5 };
393 double centrality[5] = { 0.0, 1.5, 0.0, 1.0, 0.5 };
394
395 CSRGraphWithPropsT g(boost::edges_are_sorted, &edges_init[0], &edges_init[0] + 6, &weights[0], 5, 6);
396 brandes_betweenness_centrality
397 (g,
398 centrality_map(get(&Vertex::centrality, g)).
399 weight_map(get(&Edge::weight, g)).
400 edge_centrality_map(get(&Edge::centrality, g)));
401
402 BGL_FORALL_VERTICES(v, g, CSRGraphWithPropsT)
403 BOOST_CHECK(g[v].centrality == centrality[v]);
404 }
405
test_main(int argc,char * argv[])406 int test_main(int argc, char* argv[])
407 {
408 // Optionally accept a seed value
409 int seed = int(std::time(0));
410 if (argc > 1) seed = boost::lexical_cast<int>(argv[1]);
411
412 std::cout << "Seed = " << seed << std::endl;
413 {
414 std::cout << "Testing empty graph" << std::endl;
415 CSRGraphT g;
416 graph_test(g);
417 }
418 // graph_test(1000, 0.05, seed);
419 // graph_test(1000, 0.0, seed);
420 // graph_test(1000, 0.1, seed);
421 graph_test(1000, 0.001, seed);
422 graph_test(1000, 0.0005, seed);
423
424 test_graph_properties();
425 test_vertex_and_edge_properties();
426
427 {
428 std::cout << "Testing CSR graph built from unsorted edges" << std::endl;
429 std::pair<int, int> unsorted_edges[] = {std::make_pair(5, 0), std::make_pair(3, 2), std::make_pair(4, 1), std::make_pair(4, 0), std::make_pair(0, 2), std::make_pair(5, 2)};
430 CSRGraphT g(boost::edges_are_unsorted, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
431
432 // Test vertex and edge bundle access
433 boost::ignore_unused_variable_warning(
434 (VertexData&)get(get(boost::vertex_bundle, g), vertex(0, g)));
435 boost::ignore_unused_variable_warning(
436 (const VertexData&)get(get(boost::vertex_bundle, (const CSRGraphT&)g), vertex(0, g)));
437 boost::ignore_unused_variable_warning(
438 (VertexData&)get(boost::vertex_bundle, g, vertex(0, g)));
439 boost::ignore_unused_variable_warning(
440 (const VertexData&)get(boost::vertex_bundle, (const CSRGraphT&)g, vertex(0, g)));
441 put(boost::vertex_bundle, g, vertex(0, g), VertexData());
442 boost::ignore_unused_variable_warning(
443 (EdgeData&)get(get(boost::edge_bundle, g), *edges(g).first));
444 boost::ignore_unused_variable_warning(
445 (const EdgeData&)get(get(boost::edge_bundle, (const CSRGraphT&)g), *edges(g).first));
446 boost::ignore_unused_variable_warning(
447 (EdgeData&)get(boost::edge_bundle, g, *edges(g).first));
448 boost::ignore_unused_variable_warning(
449 (const EdgeData&)get(boost::edge_bundle, (const CSRGraphT&)g, *edges(g).first));
450 put(boost::edge_bundle, g, *edges(g).first, EdgeData());
451
452 CSRGraphT g2(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
453 graph_test(g);
454 graph_test(g2);
455 assert_graphs_equal(g, boost::identity_property_map(),
456 g2, boost::identity_property_map(),
457 boost::identity_property_map());
458 std::cout << "Testing bidir CSR graph built from unsorted edges" << std::endl;
459 BidirCSRGraphT g2b(boost::edges_are_unsorted_multi_pass, unsorted_edges, unsorted_edges + sizeof(unsorted_edges) / sizeof(*unsorted_edges), 6);
460 graph_test(g2b);
461 assert_graphs_equal(g, boost::identity_property_map(),
462 g2b, boost::identity_property_map(),
463 boost::identity_property_map());
464 // Check in edge access
465 typedef boost::graph_traits<BidirCSRGraphT>::in_edge_iterator in_edge_iterator;
466 std::pair<in_edge_iterator, in_edge_iterator> ie(in_edges(vertex(0, g2b), g2b));
467
468 std::cout << "Testing CSR graph built using add_edges" << std::endl;
469 // Test building a graph using add_edges on unsorted lists
470 CSRGraphT g3(boost::edges_are_unsorted, unsorted_edges, unsorted_edges, 6); // Empty range
471 add_edges(unsorted_edges, unsorted_edges + 3, g3);
472 EdgeData edge_data[3];
473 add_edges(unsorted_edges + 3, unsorted_edges + 6, edge_data, edge_data + 3, g3);
474 graph_test(g3);
475 assert_graphs_equal(g, boost::identity_property_map(),
476 g3, boost::identity_property_map(),
477 boost::identity_property_map());
478 }
479
480 return 0;
481 }
482