1 //=======================================================================
2 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
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 #include <boost/config.hpp>
10 #include <iostream>
11 #include <vector>
12 #include <utility>
13 #include <algorithm>
14
15 #include <boost/graph/adjacency_list.hpp>
16
17 using namespace boost;
18 using namespace std;
19
20 typedef property< vertex_color_t, default_color_type,
21 property< vertex_distance_t, int,
22 property< vertex_degree_t, int,
23 property< vertex_in_degree_t, int,
24 property< vertex_out_degree_t, int > > > > >
25 VertexProperty;
26 typedef property< edge_weight_t, int > EdgeProperty;
27 typedef adjacency_list< vecS, vecS, bidirectionalS, VertexProperty,
28 EdgeProperty >
29 Graph;
30
print(Graph & g)31 template < class Graph > void print(Graph& g)
32 {
33 typename Graph::vertex_iterator i, end;
34 typename Graph::out_edge_iterator ei, edge_end;
35 for (boost::tie(i, end) = vertices(g); i != end; ++i)
36 {
37 cout << *i << " --> ";
38 for (boost::tie(ei, edge_end) = out_edges(*i, g); ei != edge_end; ++ei)
39 cout << target(*ei, g) << " ";
40 cout << endl;
41 }
42 }
43
myrand(std::size_t N)44 std::size_t myrand(std::size_t N)
45 {
46 std::size_t ret = rand() % N;
47 // cout << "N = " << N << " rand = " << ret << endl;
48 return ret;
49 }
50
check_edge(Graph & g,std::size_t a,std::size_t b)51 template < class Graph > bool check_edge(Graph& g, std::size_t a, std::size_t b)
52 {
53 typename Graph::adjacency_iterator vi, viend, found;
54 boost::tie(vi, viend) = adjacent_vertices(vertex(a, g), g);
55
56 found = find(vi, viend, vertex(b, g));
57 if (found == viend)
58 return false;
59
60 return true;
61 }
62
main(int,char * [])63 int main(int, char*[])
64 {
65 std::size_t N = 5;
66
67 Graph g(N);
68 int i;
69
70 bool is_failed = false;
71
72 for (i = 0; i < 6; ++i)
73 {
74 std::size_t a = myrand(N), b = myrand(N);
75 while (a == b)
76 b = myrand(N);
77 cout << "edge edge (" << a << "," << b << ")" << endl;
78 // add edges
79 add_edge(a, b, g);
80 is_failed = is_failed || (!check_edge(g, a, b));
81 }
82
83 if (is_failed)
84 cerr << " Failed." << endl;
85 else
86 cerr << " Passed." << endl;
87
88 print(g);
89
90 // remove_edge
91 for (i = 0; i < 2; ++i)
92 {
93 std::size_t a = myrand(N), b = myrand(N);
94 while (a == b)
95 b = myrand(N);
96 cout << "remove edge (" << a << "," << b << ")" << endl;
97 remove_edge(a, b, g);
98 is_failed = is_failed || check_edge(g, a, b);
99 }
100 if (is_failed)
101 cerr << " Failed." << endl;
102 else
103 cerr << " Passed." << endl;
104
105 print(g);
106
107 // add_vertex
108 is_failed = false;
109 std::size_t old_N = N;
110 std::size_t vid = add_vertex(g);
111 std::size_t vidp1 = add_vertex(g);
112
113 N = num_vertices(g);
114 if ((N - 2) != old_N)
115 cerr << " Failed." << endl;
116 else
117 cerr << " Passed." << endl;
118
119 is_failed = false;
120 for (i = 0; i < 2; ++i)
121 {
122 std::size_t a = myrand(N), b = myrand(N);
123 while (a == vid)
124 a = myrand(N);
125 while (b == vidp1)
126 b = myrand(N);
127 cout << "add edge (" << vid << "," << a << ")" << endl;
128 cout << "add edge (" << vid << "," << vidp1 << ")" << endl;
129 add_edge(vid, a, g);
130 add_edge(b, vidp1, g);
131 is_failed = is_failed || !check_edge(g, vid, a);
132 is_failed = is_failed || !check_edge(g, b, vidp1);
133 }
134 if (is_failed)
135 cerr << " Failed." << endl;
136 else
137 cerr << " Passed." << endl;
138 print(g);
139
140 // clear_vertex
141 std::size_t c = myrand(N);
142 is_failed = false;
143 clear_vertex(c, g);
144
145 if (out_degree(c, g) != 0)
146 is_failed = true;
147
148 cout << "Removing vertex " << c << endl;
149 remove_vertex(c, g);
150
151 old_N = N;
152 N = num_vertices(g);
153
154 if ((N + 1) != old_N)
155 is_failed = true;
156
157 if (is_failed)
158 cerr << " Failed." << endl;
159 else
160 cerr << " Passed." << endl;
161
162 print(g);
163
164 return 0;
165 }
166