1 // Copyright 2005 The Trustees of Indiana University.
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)
7 // Authors: Jeremiah Willcock
11 // The libstdc++ debug mode makes this test run for hours...
13 # undef _GLIBCXX_DEBUG
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
27 #include <boost/lexical_cast.hpp>
28 #include <boost/iterator/transform_iterator.hpp>
29 #include <boost/limits.hpp>
31 #include <boost/graph/iteration_macros.hpp>
32 #include <boost/test/minimal.hpp>
34 // Algorithms to test against
35 #include <boost/graph/betweenness_centrality.hpp>
36 #include <boost/graph/kruskal_min_spanning_tree.hpp>
38 typedef boost::adjacency_list
<> GraphT
;
39 typedef boost::erdos_renyi_iterator
<boost::minstd_rand
, GraphT
> ERGen
;
51 typedef boost::compressed_sparse_row_graph
<boost::directedS
, VertexData
, EdgeData
>
54 typedef boost::compressed_sparse_row_graph
<boost::bidirectionalS
, VertexData
, EdgeData
>
57 template <class G1
, class VI1
, class G2
, class VI2
, class IsomorphismMap
>
58 void assert_graphs_equal(const G1
& g1
, const VI1
& vi1
,
59 const G2
& g2
, const VI2
& vi2
,
60 const IsomorphismMap
& iso
) {
61 using boost::out_degree
;
63 BOOST_CHECK (num_vertices(g1
) == num_vertices(g2
));
64 BOOST_CHECK (num_edges(g1
) == num_edges(g2
));
66 typedef typename
boost::graph_traits
<G1
>::vertex_iterator vertiter1
;
69 for (boost::tie(i
, iend
) = vertices(g1
); i
!= iend
; ++i
) {
70 typename
boost::graph_traits
<G1
>::vertex_descriptor v1
= *i
;
71 typename
boost::graph_traits
<G2
>::vertex_descriptor v2
= iso
[v1
];
73 BOOST_CHECK (vi1
[v1
] == vi2
[v2
]);
75 BOOST_CHECK (out_degree(v1
, g1
) == out_degree(v2
, g2
));
76 std::vector
<std::size_t> edges1(out_degree(v1
, g1
));
77 typename
boost::graph_traits
<G1
>::out_edge_iterator oe1
, oe1end
;
78 for (boost::tie(oe1
, oe1end
) = out_edges(v1
, g1
); oe1
!= oe1end
; ++oe1
) {
79 BOOST_CHECK (source(*oe1
, g1
) == v1
);
80 edges1
.push_back(vi1
[target(*oe1
, g1
)]);
82 std::vector
<std::size_t> edges2(out_degree(v2
, g2
));
83 typename
boost::graph_traits
<G2
>::out_edge_iterator oe2
, oe2end
;
84 for (boost::tie(oe2
, oe2end
) = out_edges(v2
, g2
); oe2
!= oe2end
; ++oe2
) {
85 BOOST_CHECK (source(*oe2
, g2
) == v2
);
86 edges2
.push_back(vi2
[target(*oe2
, g2
)]);
89 std::sort(edges1
.begin(), edges1
.end());
90 std::sort(edges2
.begin(), edges2
.end());
91 if (edges1
!= edges2
) {
92 std::cerr
<< "For vertex " << v1
<< std::endl
;
93 std::cerr
<< "edges1:";
94 for (size_t i
= 0; i
< edges1
.size(); ++i
) std::cerr
<< " " << edges1
[i
];
95 std::cerr
<< std::endl
;
96 std::cerr
<< "edges2:";
97 for (size_t i
= 0; i
< edges2
.size(); ++i
) std::cerr
<< " " << edges2
[i
];
98 std::cerr
<< std::endl
;
100 BOOST_CHECK (edges1
== edges2
);
105 std::vector
<std::pair
<std::size_t, std::size_t> > all_edges1
;
106 std::vector
<std::pair
<std::size_t, std::size_t> > all_edges2
;
107 typename
boost::graph_traits
<G1
>::edge_iterator ei1
, ei1end
;
108 for (boost::tie(ei1
, ei1end
) = edges(g1
); ei1
!= ei1end
; ++ei1
)
109 all_edges1
.push_back(std::make_pair(vi1
[source(*ei1
, g1
)],
110 vi1
[target(*ei1
, g1
)]));
111 typename
boost::graph_traits
<G2
>::edge_iterator ei2
, ei2end
;
112 for (boost::tie(ei2
, ei2end
) = edges(g2
); ei2
!= ei2end
; ++ei2
)
113 all_edges2
.push_back(std::make_pair(vi2
[source(*ei2
, g2
)],
114 vi2
[target(*ei2
, g2
)]));
115 std::sort(all_edges1
.begin(), all_edges1
.end());
116 std::sort(all_edges2
.begin(), all_edges2
.end());
117 BOOST_CHECK (all_edges1
== all_edges2
);
121 template <typename Structure
>
122 void check_consistency_one(const Structure
& g
) {
123 // Do a bunch of tests on the graph internal data
124 // Check that m_rowstart entries are valid, and that entries after
125 // m_last_source + 1 are all zero
126 BOOST_CHECK(g
.m_rowstart
[0] == 0);
128 i
< g
.m_rowstart
.size() - 1;
130 BOOST_CHECK(g
.m_rowstart
[i
+ 1] >= g
.m_rowstart
[i
]);
131 BOOST_CHECK(g
.m_rowstart
[i
+ 1] <= g
.m_rowstart
.back());
133 // Check that m_column entries are within range
134 for (size_t i
= 0; i
< g
.m_rowstart
.back(); ++i
) {
135 BOOST_CHECK(g
.m_column
[i
] < g
.m_rowstart
.size() - 1);
139 template <typename Graph
>
140 void check_consistency_dispatch(const Graph
& g
,
141 boost::incidence_graph_tag
) {
142 check_consistency_one(g
.m_forward
);
146 void assert_bidir_equal_in_both_dirs(const G
& g
) {
147 BOOST_CHECK (g
.m_forward
.m_rowstart
.size() == g
.m_backward
.m_rowstart
.size());
148 BOOST_CHECK (g
.m_forward
.m_column
.size() == g
.m_backward
.m_column
.size());
149 typedef typename
boost::graph_traits
<G
>::vertex_descriptor Vertex
;
150 typedef typename
boost::graph_traits
<G
>::edges_size_type EdgeIndex
;
151 std::vector
<boost::tuple
<EdgeIndex
, Vertex
, Vertex
> > edges_forward
, edges_backward
;
152 for (Vertex i
= 0; i
< g
.m_forward
.m_rowstart
.size() - 1; ++i
) {
153 for (EdgeIndex j
= g
.m_forward
.m_rowstart
[i
];
154 j
< g
.m_forward
.m_rowstart
[i
+ 1]; ++j
) {
155 edges_forward
.push_back(boost::make_tuple(j
, i
, g
.m_forward
.m_column
[j
]));
158 for (Vertex i
= 0; i
< g
.m_backward
.m_rowstart
.size() - 1; ++i
) {
159 for (EdgeIndex j
= g
.m_backward
.m_rowstart
[i
];
160 j
< g
.m_backward
.m_rowstart
[i
+ 1]; ++j
) {
161 edges_backward
.push_back(boost::make_tuple(g
.m_backward
.m_edge_properties
[j
], g
.m_backward
.m_column
[j
], i
));
164 std::sort(edges_forward
.begin(), edges_forward
.end());
165 std::sort(edges_backward
.begin(), edges_backward
.end());
166 BOOST_CHECK (edges_forward
== edges_backward
);
169 template <typename Graph
>
170 void check_consistency_dispatch(const Graph
& g
,
171 boost::bidirectional_graph_tag
) {
172 check_consistency_one(g
.m_forward
);
173 check_consistency_one(g
.m_backward
);
174 assert_bidir_equal_in_both_dirs(g
);
177 template <typename Graph
>
178 void check_consistency(const Graph
& g
) {
179 check_consistency_dispatch(g
, typename
boost::graph_traits
<Graph
>::traversal_category());
182 template<typename OrigGraph
>
183 void graph_test(const OrigGraph
& g
)
185 // Check copying of a graph
187 check_consistency(g2
);
188 BOOST_CHECK((std::size_t)std::distance(edges(g2
).first
, edges(g2
).second
)
190 assert_graphs_equal(g
, boost::identity_property_map(),
191 g2
, boost::identity_property_map(),
192 boost::identity_property_map());
194 // Check constructing a graph from iterators
195 CSRGraphT
g3(boost::edges_are_sorted
,
196 boost::make_transform_iterator(edges(g2
).first
,
197 boost::detail::make_edge_to_index_pair(g2
)),
198 boost::make_transform_iterator(edges(g2
).second
,
199 boost::detail::make_edge_to_index_pair(g2
)),
201 check_consistency(g3
);
202 BOOST_CHECK((std::size_t)std::distance(edges(g3
).first
, edges(g3
).second
)
204 assert_graphs_equal(g2
, boost::identity_property_map(),
205 g3
, boost::identity_property_map(),
206 boost::identity_property_map());
208 // Check constructing a graph using in-place modification of vectors
210 std::vector
<std::size_t> sources(num_edges(g2
));
211 std::vector
<std::size_t> targets(num_edges(g2
));
213 // Edges actually sorted
214 BGL_FORALL_EDGES(e
, g2
, CSRGraphT
) {
215 sources
[idx
] = source(e
, g2
);
216 targets
[idx
] = target(e
, g2
);
219 CSRGraphT
g3a(boost::construct_inplace_from_sources_and_targets
,
223 check_consistency(g3a
);
224 assert_graphs_equal(g2
, boost::identity_property_map(),
225 g3a
, boost::identity_property_map(),
226 boost::identity_property_map());
229 std::vector
<std::size_t> sources(num_edges(g2
));
230 std::vector
<std::size_t> targets(num_edges(g2
));
232 // Edges reverse-sorted
233 BGL_FORALL_EDGES(e
, g2
, CSRGraphT
) {
234 sources
[num_edges(g2
) - 1 - idx
] = source(e
, g2
);
235 targets
[num_edges(g2
) - 1 - idx
] = target(e
, g2
);
238 CSRGraphT
g3a(boost::construct_inplace_from_sources_and_targets
,
242 check_consistency(g3a
);
243 assert_graphs_equal(g2
, boost::identity_property_map(),
244 g3a
, boost::identity_property_map(),
245 boost::identity_property_map());
248 std::vector
<std::size_t> sources(num_edges(g2
));
249 std::vector
<std::size_t> targets(num_edges(g2
));
251 // Edges scrambled using Fisher-Yates shuffle (Durstenfeld variant) from
253 BGL_FORALL_EDGES(e
, g2
, CSRGraphT
) {
254 sources
[idx
] = source(e
, g2
);
255 targets
[idx
] = target(e
, g2
);
258 boost::minstd_rand
gen(1);
259 if (num_edges(g
) != 0) {
260 for (std::size_t i
= num_edges(g
) - 1; i
> 0; --i
) {
261 std::size_t scrambled
= boost::uniform_int
<>(0, i
)(gen
);
262 if (scrambled
== i
) continue;
264 swap(sources
[i
], sources
[scrambled
]);
265 swap(targets
[i
], targets
[scrambled
]);
268 CSRGraphT
g3a(boost::construct_inplace_from_sources_and_targets
,
272 check_consistency(g3a
);
273 assert_graphs_equal(g2
, boost::identity_property_map(),
274 g3a
, boost::identity_property_map(),
275 boost::identity_property_map());
278 CSRGraphT::edge_iterator ei
, ei_end
;
280 // Check edge_from_index (and implicitly the edge_index property map) for
282 std::size_t last_src
= 0;
283 for (boost::tie(ei
, ei_end
) = edges(g2
); ei
!= ei_end
; ++ei
) {
284 BOOST_CHECK(edge_from_index(get(boost::edge_index
, g2
, *ei
), g2
) == *ei
);
285 std::size_t src
= get(boost::vertex_index
, g2
, source(*ei
, g2
));
286 (void)(std::size_t)get(boost::vertex_index
, g2
, target(*ei
, g2
));
287 BOOST_CHECK(src
>= last_src
);
291 // Check out edge iteration and vertex iteration for sortedness
292 CSRGraphT::vertex_iterator vi
, vi_end
;
293 std::size_t last_vertex
= 0;
294 bool first_iter
= true;
295 for (boost::tie(vi
, vi_end
) = vertices(g2
); vi
!= vi_end
; ++vi
) {
296 std::size_t v
= get(boost::vertex_index
, g2
, *vi
);
297 BOOST_CHECK(first_iter
|| v
> last_vertex
);
301 CSRGraphT::out_edge_iterator oei
, oei_end
;
302 for (boost::tie(oei
, oei_end
) = out_edges(*vi
, g2
); oei
!= oei_end
; ++oei
) {
303 BOOST_CHECK(source(*oei
, g2
) == *vi
);
306 // Find a vertex for testing
307 CSRGraphT::vertex_descriptor test_vertex
= vertex(num_vertices(g2
) / 2, g2
);
309 CSRGraphT::out_edge_iterator oei2
, oei2_end
;
310 for (boost::tie(oei2
, oei_end
) = out_edges(*vi
, g2
); oei2
!= oei_end
; ++oei2
) {
311 if (target(*oei2
, g2
) == test_vertex
)
316 // Run brandes_betweenness_centrality, which touches on a whole lot
317 // of things, including VertexListGraph and IncidenceGraph
318 using namespace boost
;
319 std::vector
<double> vertex_centralities(num_vertices(g3
));
320 std::vector
<double> edge_centralities(num_edges(g3
));
321 brandes_betweenness_centrality
323 make_iterator_property_map(vertex_centralities
.begin(),
324 get(boost::vertex_index
, g3
)),
325 make_iterator_property_map(edge_centralities
.begin(),
326 get(boost::edge_index
, g3
)));
327 // Extra qualifications for aCC
329 // Invert the edge centralities and use these as weights to
330 // Kruskal's MST algorithm, which will test the EdgeListGraph
332 double max_val
= (std::numeric_limits
<double>::max
)();
333 for (std::size_t i
= 0; i
< num_edges(g3
); ++i
)
334 edge_centralities
[i
] =
335 edge_centralities
[i
] == 0.0? max_val
: 1.0 / edge_centralities
[i
];
337 typedef boost::graph_traits
<CSRGraphT
>::edge_descriptor edge_descriptor
;
338 std::vector
<edge_descriptor
> mst_edges
;
339 mst_edges
.reserve(num_vertices(g3
));
340 kruskal_minimum_spanning_tree
341 (g3
, std::back_inserter(mst_edges
),
342 weight_map(make_iterator_property_map(edge_centralities
.begin(),
343 get(boost::edge_index
, g3
))));
346 void graph_test(int nnodes
, double density
, int seed
)
348 boost::minstd_rand
gen(seed
);
349 std::cout
<< "Testing " << nnodes
<< " density " << density
<< std::endl
;
350 GraphT
g(ERGen(gen
, nnodes
, density
), ERGen(), nnodes
);
354 void test_graph_properties()
356 using namespace boost
;
358 typedef compressed_sparse_row_graph
<directedS
,
361 property
<graph_name_t
, std::string
> >
365 BOOST_CHECK(get_property(g
, graph_name
) == "");
366 set_property(g
, graph_name
, "beep");
367 BOOST_CHECK(get_property(g
, graph_name
) == "beep");
377 Edge(double weight
) : weight(weight
), centrality(0.0) { }
383 void test_vertex_and_edge_properties()
385 using namespace boost
;
386 typedef compressed_sparse_row_graph
<directedS
, Vertex
, Edge
>
389 typedef std::pair
<int, int> E
;
390 E edges_init
[6] = { E(0, 1), E(0, 3), E(1, 2), E(3, 1), E(3, 4), E(4, 2) };
391 double weights
[6] = { 1.0, 1.0, 0.5, 1.0, 1.0, 0.5 };
392 double centrality
[5] = { 0.0, 1.5, 0.0, 1.0, 0.5 };
394 CSRGraphWithPropsT
g(boost::edges_are_sorted
, &edges_init
[0], &edges_init
[0] + 6, &weights
[0], 5, 6);
395 brandes_betweenness_centrality
397 centrality_map(get(&Vertex::centrality
, g
)).
398 weight_map(get(&Edge::weight
, g
)).
399 edge_centrality_map(get(&Edge::centrality
, g
)));
401 BGL_FORALL_VERTICES(v
, g
, CSRGraphWithPropsT
)
402 BOOST_CHECK(g
[v
].centrality
== centrality
[v
]);
405 int test_main(int argc
, char* argv
[])
407 // Optionally accept a seed value
408 int seed
= int(std::time(0));
409 if (argc
> 1) seed
= boost::lexical_cast
<int>(argv
[1]);
411 std::cout
<< "Seed = " << seed
<< std::endl
;
413 std::cout
<< "Testing empty graph" << std::endl
;
417 // graph_test(1000, 0.05, seed);
418 // graph_test(1000, 0.0, seed);
419 // graph_test(1000, 0.1, seed);
420 graph_test(1000, 0.001, seed
);
421 graph_test(1000, 0.0005, seed
);
423 test_graph_properties();
424 test_vertex_and_edge_properties();
427 std::cout
<< "Testing CSR graph built from unsorted edges" << std::endl
;
428 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)};
429 CSRGraphT
g(boost::edges_are_unsorted
, unsorted_edges
, unsorted_edges
+ sizeof(unsorted_edges
) / sizeof(*unsorted_edges
), 6);
431 // Test vertex and edge bundle access
432 boost::ignore_unused_variable_warning(
433 (VertexData
&)get(get(boost::vertex_bundle
, g
), vertex(0, g
)));
434 boost::ignore_unused_variable_warning(
435 (const VertexData
&)get(get(boost::vertex_bundle
, (const CSRGraphT
&)g
), vertex(0, g
)));
436 boost::ignore_unused_variable_warning(
437 (VertexData
&)get(boost::vertex_bundle
, g
, vertex(0, g
)));
438 boost::ignore_unused_variable_warning(
439 (const VertexData
&)get(boost::vertex_bundle
, (const CSRGraphT
&)g
, vertex(0, g
)));
440 put(boost::vertex_bundle
, g
, vertex(0, g
), VertexData());
441 boost::ignore_unused_variable_warning(
442 (EdgeData
&)get(get(boost::edge_bundle
, g
), *edges(g
).first
));
443 boost::ignore_unused_variable_warning(
444 (const EdgeData
&)get(get(boost::edge_bundle
, (const CSRGraphT
&)g
), *edges(g
).first
));
445 boost::ignore_unused_variable_warning(
446 (EdgeData
&)get(boost::edge_bundle
, g
, *edges(g
).first
));
447 boost::ignore_unused_variable_warning(
448 (const EdgeData
&)get(boost::edge_bundle
, (const CSRGraphT
&)g
, *edges(g
).first
));
449 put(boost::edge_bundle
, g
, *edges(g
).first
, EdgeData());
451 CSRGraphT
g2(boost::edges_are_unsorted_multi_pass
, unsorted_edges
, unsorted_edges
+ sizeof(unsorted_edges
) / sizeof(*unsorted_edges
), 6);
454 assert_graphs_equal(g
, boost::identity_property_map(),
455 g2
, boost::identity_property_map(),
456 boost::identity_property_map());
457 std::cout
<< "Testing bidir CSR graph built from unsorted edges" << std::endl
;
458 BidirCSRGraphT
g2b(boost::edges_are_unsorted_multi_pass
, unsorted_edges
, unsorted_edges
+ sizeof(unsorted_edges
) / sizeof(*unsorted_edges
), 6);
460 assert_graphs_equal(g
, boost::identity_property_map(),
461 g2b
, boost::identity_property_map(),
462 boost::identity_property_map());
463 // Check in edge access
464 typedef boost::graph_traits
<BidirCSRGraphT
>::in_edge_iterator in_edge_iterator
;
465 std::pair
<in_edge_iterator
, in_edge_iterator
> ie(in_edges(vertex(0, g2b
), g2b
));
466 // quiet unused variable warning
467 ie
.first
= ie
.second
;
469 std::cout
<< "Testing CSR graph built using add_edges" << std::endl
;
470 // Test building a graph using add_edges on unsorted lists
471 CSRGraphT
g3(boost::edges_are_unsorted
, unsorted_edges
, unsorted_edges
, 6); // Empty range
472 add_edges(unsorted_edges
, unsorted_edges
+ 3, g3
);
473 EdgeData edge_data
[3];
474 add_edges(unsorted_edges
+ 3, unsorted_edges
+ 6, edge_data
, edge_data
+ 3, g3
);
476 assert_graphs_equal(g
, boost::identity_property_map(),
477 g3
, boost::identity_property_map(),
478 boost::identity_property_map());