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
28enum vertex_id_t { vertex_id = 500 };
29enum edge_id_t { edge_id = 501 };
30namespace 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
38using namespace boost;
39
40/*
41 This program tests models of the MutableGraph concept.
42 */
43
44using std::cout;
45using std::endl;
46using std::cerr;
47using std::find;
48
49
50template <class Graph, class Vertex, class ID>
51bool 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
81template <class Graph, class Edge, class EdgeID>
82bool 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
128template <class Graph>
129std::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
139int 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

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