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