1 | //======================================================================= |
2 | // Copyright 2002 Indiana University. |
3 | // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek |
4 | // |
5 | // Distributed under the Boost Software License, Version 1.0. (See |
6 | // accompanying file LICENSE_1_0.txt or copy at |
7 | // http://www.boost.org/LICENSE_1_0.txt) |
8 | //======================================================================= |
9 | |
10 | #include <boost/config.hpp> |
11 | |
12 | #include <iostream> |
13 | #include <vector> |
14 | #include <set> |
15 | #include <utility> |
16 | #include <algorithm> |
17 | |
18 | #define VERBOSE 0 |
19 | |
20 | #include <boost/utility.hpp> |
21 | #include <boost/graph/graph_utility.hpp> |
22 | #include <boost/graph/random.hpp> |
23 | #include <boost/pending/indirect_cmp.hpp> |
24 | |
25 | #include <boost/random/mersenne_twister.hpp> |
26 | |
27 | |
28 | enum vertex_id_t { vertex_id = 500 }; |
29 | enum edge_id_t { edge_id = 501 }; |
30 | namespace boost { |
31 | BOOST_INSTALL_PROPERTY(vertex, id); |
32 | BOOST_INSTALL_PROPERTY(edge, id); |
33 | } |
34 | |
35 | |
36 | #include "graph_type.hpp" // this provides a typedef for Graph |
37 | |
38 | using namespace boost; |
39 | |
40 | /* |
41 | This program tests models of the MutableGraph concept. |
42 | */ |
43 | |
44 | using std::cout; |
45 | using std::endl; |
46 | using std::cerr; |
47 | using std::find; |
48 | |
49 | |
50 | template <class Graph, class Vertex, class ID> |
51 | bool check_vertex_cleared(Graph& g, Vertex v, ID id) |
52 | { |
53 | typename graph_traits<Graph>::vertex_iterator vi, viend; |
54 | for (boost::tie(vi,viend) = vertices(g); vi != viend; ++vi) { |
55 | typename graph_traits<Graph>::adjacency_iterator ai, aiend, found; |
56 | boost::tie(ai, aiend) = adjacent_vertices(*vi, g); |
57 | boost::indirect_cmp<ID, std::equal_to<std::size_t> > cmp(id); |
58 | |
59 | #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) && defined(__SGI_STL_PORT) |
60 | // seeing internal compiler errors when using std::find_if() |
61 | found = aiend; |
62 | for ( ; ai != aiend; ++ai) |
63 | if (cmp(*ai, v)) { |
64 | found = ai; |
65 | break; |
66 | } |
67 | #else |
68 | found = std::find_if(ai, aiend, std::bind1st(cmp,v)); |
69 | #endif |
70 | |
71 | if ( found != aiend ) { |
72 | #if VERBOSE |
73 | std::cerr << "should not have found vertex " << id[*found] << std::endl; |
74 | #endif |
75 | return false; |
76 | } |
77 | } |
78 | return true; |
79 | } |
80 | |
81 | template <class Graph, class Edge, class EdgeID> |
82 | bool check_edge_added(Graph& g, Edge e, |
83 | typename graph_traits<Graph>::vertex_descriptor a, |
84 | typename graph_traits<Graph>::vertex_descriptor b, |
85 | EdgeID edge_id, std::size_t correct_id, |
86 | bool inserted) |
87 | { |
88 | if (! (source(e, g) == a)) { |
89 | #if VERBOSE |
90 | cerr << " Failed, vertex a not source of e." << endl; |
91 | #endif |
92 | return false; |
93 | } else if (! (target(e, g) == b)) { |
94 | #if VERBOSE |
95 | cerr << " Failed, vertex b not source of e." << endl; |
96 | #endif |
97 | return false; |
98 | } else if (! is_adjacent(g, a, b)) { |
99 | #if VERBOSE |
100 | cerr << " Failed, not adj." << endl; |
101 | #endif |
102 | return false; |
103 | } else if (! in_edge_set(g,e)) { |
104 | #if VERBOSE |
105 | cerr << " Failed, not in edge set." << endl; |
106 | #endif |
107 | return false; |
108 | } else if (inserted && edge_id[e] != correct_id) { |
109 | #if VERBOSE |
110 | cerr << " Failed, invalid edge property." << endl; |
111 | #endif |
112 | return false; |
113 | } else if (!inserted && edge_id[e] != edge_id[edge(a, b, g).first]) { |
114 | #if VERBOSE |
115 | cerr << " Failed, invalid edge property." << endl; |
116 | #endif |
117 | return false; |
118 | } else if (num_edges(g) != count_edges(g)) { |
119 | #if VERBOSE |
120 | cerr << " Failed, invalid number of edges." << endl; |
121 | #endif |
122 | return false; |
123 | } |
124 | return true; |
125 | } |
126 | |
127 | |
128 | template <class Graph> |
129 | std::size_t count_edges(Graph& g) |
130 | { |
131 | std::size_t e = 0; |
132 | typename boost::graph_traits<Graph>::edge_iterator ei,ei_end; |
133 | for (boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei) |
134 | ++e; |
135 | return e; |
136 | } |
137 | |
138 | |
139 | int main(int, char* []) |
140 | { |
141 | int ret = 0; |
142 | std::size_t N = 5, E = 0; |
143 | std::size_t old_N; |
144 | |
145 | typedef ::Graph Graph; |
146 | Graph g; |
147 | typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; |
148 | typedef boost::graph_traits<Graph>::edge_descriptor Edge; |
149 | |
150 | int i, j; |
151 | std::size_t current_vertex_id = 0; |
152 | std::size_t current_edge_id = 0; |
153 | |
154 | bool is_failed = false; |
155 | |
156 | property_map<Graph, vertex_id_t>::type vertex_id_map = get(p: vertex_id, g); |
157 | |
158 | property_map<Graph, edge_id_t>::type edge_id_map = get(p: edge_id, g); |
159 | |
160 | for (std::size_t k = 0; k < N; ++k) |
161 | add_vertex(p: current_vertex_id++, g_&: g); |
162 | |
163 | // also need to test EdgeIterator graph constructor -JGS |
164 | mt19937 gen; |
165 | |
166 | for (j=0; j < 10; ++j) { |
167 | |
168 | // add_edge |
169 | #if VERBOSE |
170 | cerr << "Testing add_edge ..." << endl; |
171 | #endif |
172 | for (i=0; i < 6; ++i) { |
173 | Vertex a, b; |
174 | a = random_vertex(g, gen); |
175 | do { |
176 | b = random_vertex(g, gen); |
177 | } while ( a == b ); // don't do self edges |
178 | #if VERBOSE |
179 | cerr << "add_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] <<")" << endl; |
180 | #endif |
181 | Edge e; |
182 | bool inserted; |
183 | boost::tie(t0&: e, t1&: inserted) = add_edge(u: a, v: b, p: current_edge_id++, g_&: g); |
184 | #if VERBOSE |
185 | std::cout << "inserted: " << inserted << std::endl; |
186 | std::cout << "source(e,g)" << source(e,g) << endl; |
187 | std::cout << "target(e,g)" << target(e,g) << endl; |
188 | std::cout << "edge_id[e] = " << edge_id_map[e] << std::endl; |
189 | print_edges2(g, vertex_id_map, edge_id_map); |
190 | print_graph(g, vertex_id_map); |
191 | std::cout << "finished printing" << std::endl; |
192 | // print_in_edges(g, vertex_id_map); |
193 | #endif |
194 | if (! check_edge_added(g, e, a, b, edge_id: edge_id_map, |
195 | correct_id: current_edge_id - 1, inserted)) { |
196 | ret = -1; |
197 | break; |
198 | } |
199 | ++E; |
200 | } |
201 | |
202 | // remove_edge(u, v, g) |
203 | #if VERBOSE |
204 | cerr << "Testing remove_edge(u, v, g) ..." << endl; is_failed = false; |
205 | #endif |
206 | for (i = 0; i < 2; ++i) { |
207 | #if VERBOSE |
208 | print_edges(g, vertex_id_map); |
209 | #endif |
210 | Vertex a, b; |
211 | |
212 | Edge e = random_edge(g, gen); |
213 | boost::tie(t0&: a,t1&: b) = boost::incident(e, g); |
214 | --E; |
215 | #if VERBOSE |
216 | cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl; |
217 | #endif |
218 | remove_edge(u: a, v: b, g_&: g); |
219 | #if VERBOSE |
220 | print_graph(g, vertex_id_map); |
221 | // print_in_edges(g, vertex_id_map); |
222 | print_edges(g, vertex_id_map); |
223 | #endif |
224 | is_failed = is_failed || is_adjacent(g, a, b) || in_edge_set(g, u: a, v: b) |
225 | || num_edges(g_: g) != count_edges(g); |
226 | if (is_failed) |
227 | break; |
228 | } |
229 | if ( is_failed ) { |
230 | ret = -1; |
231 | #if VERBOSE |
232 | cerr << " Failed." << endl; |
233 | #endif |
234 | } else { |
235 | #if VERBOSE |
236 | cerr << " Passed." << endl; |
237 | #endif |
238 | } |
239 | |
240 | // remove_edge(e, g) |
241 | #if VERBOSE |
242 | cerr << "Testing remove_edge(e, g) ..." << endl; is_failed = false; |
243 | #endif |
244 | for (i = 0; i < 2; ++i) { |
245 | #if VERBOSE |
246 | print_edges(g, vertex_id_map); |
247 | #endif |
248 | Vertex a, b; |
249 | Edge e = random_edge(g, gen); |
250 | boost::tie(t0&: a,t1&: b) = boost::incident(e, g); |
251 | --E; |
252 | #if VERBOSE |
253 | cerr << "remove_edge(" << vertex_id_map[a] << "," << vertex_id_map[b] << ")" << endl; |
254 | #endif |
255 | graph_traits<Graph>::edges_size_type old_E = num_edges(g_: g); |
256 | remove_edge(e, g_&: g); |
257 | |
258 | #if VERBOSE |
259 | print_graph(g, vertex_id_map); |
260 | // print_in_edges(g, vertex_id_map); |
261 | print_edges(g, vertex_id_map); |
262 | #endif |
263 | |
264 | is_failed = is_failed || old_E != num_edges(g_: g) + 1 |
265 | || num_edges(g_: g) != count_edges(g); |
266 | if (is_failed) |
267 | break; |
268 | } |
269 | if ( is_failed ) { |
270 | ret = -1; |
271 | #if VERBOSE |
272 | cerr << " Failed." << endl; |
273 | #endif |
274 | } else { |
275 | #if VERBOSE |
276 | cerr << " Passed." << endl; |
277 | #endif |
278 | } |
279 | |
280 | // add_vertex |
281 | #if VERBOSE |
282 | cerr << "Testing add_vertex ..." << endl; is_failed = false; |
283 | #endif |
284 | old_N = num_vertices(g_: g); |
285 | graph_traits<Graph>::vertex_descriptor vid = add_vertex(g_&: g), |
286 | vidp1 = add_vertex(g_&: g); |
287 | vertex_id_map[vid] = current_vertex_id++; |
288 | vertex_id_map[vidp1] = current_vertex_id++; |
289 | |
290 | #if VERBOSE |
291 | print_vertices(g,vertex_id_map); |
292 | print_graph(g,vertex_id_map); |
293 | // print_in_edges(g,vertex_id_map); |
294 | print_edges(g,vertex_id_map); |
295 | #endif |
296 | // make sure the two added vertices are in the graph's vertex set |
297 | { |
298 | if (!in_vertex_set(g, v: vid)) { |
299 | #if VERBOSE |
300 | cerr << " Failed, " << vertex_id_map[vid] << " not in vertices(g)" << endl; |
301 | #endif |
302 | ret = -1; |
303 | break; |
304 | } |
305 | if (!in_vertex_set(g, v: vidp1)) { |
306 | #if VERBOSE |
307 | cerr << " Failed, " << vertex_id_map[vidp1] << " not in vertices(g)" << endl; |
308 | #endif |
309 | ret = -1; |
310 | break; |
311 | } |
312 | } |
313 | |
314 | // make sure the vertices do not have any out edges yet |
315 | { |
316 | graph_traits<Graph>::out_edge_iterator e, e_end; |
317 | boost::tie(t0&: e,t1&: e_end) = out_edges(u: vid,g_: g); |
318 | if (e != e_end) { |
319 | #if VERBOSE |
320 | cerr << " Failed, " << vertex_id_map[vid] |
321 | << " should not have any out-edges yet" << endl; |
322 | #endif |
323 | ret = -1; |
324 | break; |
325 | } |
326 | boost::tie(t0&: e,t1&: e_end) = out_edges(u: vidp1,g_: g); |
327 | if (e != e_end) { |
328 | #if VERBOSE |
329 | cerr << " Failed, " << vertex_id_map[vidp1] |
330 | << " should not have any out-edges yet" << endl; |
331 | #endif |
332 | ret = -1; |
333 | break; |
334 | } |
335 | } |
336 | |
337 | // make sure the vertices do not yet appear in any of the edges |
338 | { |
339 | graph_traits<Graph>::edge_iterator e, e_end; |
340 | for (boost::tie(t0&: e, t1&: e_end) = edges(g_: g); e != e_end; ++e) { |
341 | if (source(e: *e,g) == vid || target(e: *e,g) == vid) { |
342 | #if VERBOSE |
343 | cerr << " Failed, " << vertex_id_map[vid] |
344 | << " should not have any edges" << endl; |
345 | #endif |
346 | ret = -1; |
347 | break; |
348 | } |
349 | if (source(e: *e,g) == vidp1 || target(e: *e,g) == vidp1) { |
350 | #if VERBOSE |
351 | cerr << " Failed, " << vertex_id_map[vidp1] |
352 | << " should not have any edges" << endl; |
353 | #endif |
354 | ret = -1; |
355 | break; |
356 | } |
357 | } |
358 | } |
359 | // Make sure num_vertices(g) has been updated |
360 | N = num_vertices(g_: g); |
361 | if ( (N - 2) != old_N ) { |
362 | ret = -1; |
363 | #if VERBOSE |
364 | cerr << " Failed. N = " << N |
365 | << " but should be " << old_N + 2 << endl; |
366 | #endif |
367 | break; |
368 | } else { |
369 | #if VERBOSE |
370 | cerr << " Passed." << endl; |
371 | #endif |
372 | } |
373 | // add_edge again |
374 | #if VERBOSE |
375 | cerr << "Testing add_edge after add_vertex ..." << endl; is_failed = false; |
376 | #endif |
377 | |
378 | for (i=0; i<2; ++i) { |
379 | Vertex a = random_vertex(g, gen), b = random_vertex(g, gen); |
380 | while ( a == vid ) a = random_vertex(g, gen); |
381 | while ( b == vidp1 ) b = random_vertex(g, gen); |
382 | Edge e; |
383 | bool inserted; |
384 | #if VERBOSE |
385 | cerr << "add_edge(" << vertex_id_map[vid] << "," << vertex_id_map[a] <<")" << endl; |
386 | #endif |
387 | boost::tie(t0&: e,t1&: inserted) = add_edge(u: vid, v: a, p: EdgeID(current_edge_id++), g_&: g); |
388 | |
389 | if (! check_edge_added(g, e, a: vid, b: a, edge_id: edge_id_map, correct_id: current_edge_id - 1, |
390 | inserted)) { |
391 | ret = -1; |
392 | break; |
393 | } |
394 | |
395 | #if VERBOSE |
396 | cerr << "add_edge(" << vertex_id_map[b] << "," << vertex_id_map[vidp1] <<")" << endl; |
397 | #endif |
398 | // add_edge without plugin |
399 | boost::tie(t0&: e,t1&: inserted) = add_edge(u: b, v: vidp1, g_&: g); |
400 | if (inserted) |
401 | edge_id_map[e] = current_edge_id; |
402 | ++current_edge_id; |
403 | |
404 | if (! check_edge_added(g, e, a: b, b: vidp1, edge_id: edge_id_map, |
405 | correct_id: current_edge_id - 1, inserted)) { |
406 | ret = -1; |
407 | break; |
408 | } |
409 | } |
410 | |
411 | // clear_vertex |
412 | Vertex c = random_vertex(g, gen); |
413 | #if VERBOSE |
414 | cerr << "Testing clear vertex ..." << endl; is_failed = false; |
415 | print_graph(g, vertex_id_map); |
416 | // print_in_edges(g, vertex_id_map); |
417 | cerr << "clearing vertex " << vertex_id_map[c] << endl; |
418 | #endif |
419 | clear_vertex(u: c, g_&: g); |
420 | #if VERBOSE |
421 | print_graph(g, vertex_id_map); |
422 | // print_in_edges(g, vertex_id_map); |
423 | print_edges(g, vertex_id_map); |
424 | #endif |
425 | if (check_vertex_cleared(g, v: c, id: vertex_id_map) && num_edges(g_: g) == count_edges(g)) { |
426 | #if VERBOSE |
427 | cerr << " Passed." << endl; |
428 | #endif |
429 | } else { |
430 | #if VERBOSE |
431 | cerr << "**** Failed" << endl; |
432 | #endif |
433 | ret = -1; |
434 | break; |
435 | } |
436 | |
437 | #if VERBOSE |
438 | cerr << "Testing remove vertex ..." << endl; is_failed = false; |
439 | cerr << "removing vertex " << vertex_id_map[c] << endl; |
440 | #endif |
441 | |
442 | old_N = num_vertices(g_: g); |
443 | remove_vertex(u: c, g_&: g); |
444 | #if VERBOSE |
445 | print_graph(g,vertex_id_map); |
446 | // print_in_edges(g,vertex_id_map); |
447 | print_edges(g, vertex_id_map); |
448 | #endif |
449 | // can't check in_vertex_set here because the vertex_descriptor c |
450 | // is no longer valid, we'll just make sure the vertex set has |
451 | // one fewer vertex |
452 | { |
453 | graph_traits<Graph>::vertex_iterator v, v_end; |
454 | boost::tie(t0&: v, t1&: v_end) = vertices(g_: g); |
455 | for (N = 0; v != v_end; ++v) ++N; // N = std::distance(v, v_end); |
456 | if (N != old_N - 1) { |
457 | ret = -1; |
458 | #if VERBOSE |
459 | cerr << " Failed. N = " << N |
460 | << " but should be " << old_N - 1 << endl; |
461 | #endif |
462 | } |
463 | } |
464 | |
465 | N = num_vertices(g_: g); |
466 | if (N != old_N - 1) { |
467 | ret = -1; |
468 | #if VERBOSE |
469 | cerr << " Failed. N = " << N |
470 | << " but should be " << old_N - 1 << endl; |
471 | #endif |
472 | } else { |
473 | #if VERBOSE |
474 | cerr << " Passed." << endl; |
475 | #endif |
476 | } |
477 | } |
478 | if (ret == 0) |
479 | std::cout << "tests passed" << std::endl; |
480 | |
481 | return ret; |
482 | } |
483 | |