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

source code of boost/libs/graph/test/csr_graph_test.cpp