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 | |
38 | typedef boost::adjacency_list<> GraphT; |
39 | typedef boost::erdos_renyi_iterator< boost::minstd_rand, GraphT > ERGen; |
40 | |
41 | struct VertexData |
42 | { |
43 | int index; |
44 | }; |
45 | |
46 | struct EdgeData |
47 | { |
48 | int index_e; |
49 | }; |
50 | |
51 | typedef boost::compressed_sparse_row_graph< boost::directedS, VertexData, |
52 | EdgeData > |
53 | CSRGraphT; |
54 | |
55 | typedef boost::compressed_sparse_row_graph< boost::bidirectionalS, VertexData, |
56 | EdgeData > |
57 | BidirCSRGraphT; |
58 | |
59 | template < class G1, class VI1, class G2, class VI2, class IsomorphismMap > |
60 | void 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 | |
131 | template < 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 | |
149 | template < typename Graph > |
150 | void check_consistency_dispatch(const Graph& g, boost::incidence_graph_tag) |
151 | { |
152 | check_consistency_one(g.m_forward); |
153 | } |
154 | |
155 | template < 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 | |
188 | template < typename Graph > |
189 | void 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 | |
196 | template < typename Graph > void check_consistency(const Graph& g) |
197 | { |
198 | check_consistency_dispatch( |
199 | g, typename boost::graph_traits< Graph >::traversal_category()); |
200 | } |
201 | |
202 | template < 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 | |
367 | void 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 | |
375 | void 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 | |
389 | struct Vertex |
390 | { |
391 | double centrality; |
392 | }; |
393 | |
394 | struct Edge |
395 | { |
396 | Edge(double weight) : weight(weight), centrality(0.0) {} |
397 | |
398 | double weight; |
399 | double centrality; |
400 | }; |
401 | |
402 | void 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 | |
424 | int 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 | |