1 | /* This file is a boost.test unit test and provides tests the internal |
2 | * dependency graph |
3 | * |
4 | * Created on: 06.10.2015 |
5 | * Author: Stefan Hammer <s.hammer@univie.ac.at> |
6 | * License: Boost Software License, Version 1.0. (See |
7 | * accompanying file LICENSE_1_0.txt or copy at |
8 | * http://www.boost.org/LICENSE_1_0.txt) |
9 | * |
10 | * |
11 | */ |
12 | |
13 | // std lib includes |
14 | #include <iostream> |
15 | |
16 | // include boost components |
17 | #include <boost/core/lightweight_test.hpp> |
18 | #include <boost/graph/adjacency_list.hpp> |
19 | #include <boost/graph/iteration_macros.hpp> |
20 | |
21 | // include header |
22 | #include <boost/graph/subgraph.hpp> |
23 | |
24 | using namespace boost; |
25 | |
26 | void simpleGraphTest() |
27 | { |
28 | typedef subgraph< adjacency_list< vecS, vecS, directedS, no_property, |
29 | property< edge_index_t, int > > > |
30 | Graph; |
31 | |
32 | const int N = 6; |
33 | Graph G0(N); |
34 | |
35 | enum |
36 | { |
37 | A, |
38 | B, |
39 | C, |
40 | D, |
41 | E, |
42 | F |
43 | }; // for conveniently refering to vertices in G0 |
44 | |
45 | Graph& G1 = G0.create_subgraph(); |
46 | Graph& G2 = G1.create_subgraph(); |
47 | |
48 | BOOST_TEST(&G1.parent() == &G0); |
49 | BOOST_TEST(&G2.parent() == &G1); |
50 | |
51 | enum |
52 | { |
53 | A1, |
54 | B1, |
55 | C1 |
56 | }; // for conveniently refering to vertices in G1 |
57 | enum |
58 | { |
59 | A2, |
60 | B2, |
61 | C2 |
62 | }; // for conveniently refering to vertices in G2 |
63 | |
64 | add_vertex(u_global: C, g&: G1); // global vertex C becomes local A1 for G1 |
65 | add_vertex(u_global: E, g&: G1); // global vertex E becomes local B1 for G1 |
66 | add_vertex(u_global: F, g&: G1); // global vertex F becomes local C1 for G1 |
67 | |
68 | add_vertex(u_global: C, g&: G2); // global vertex C becomes local A2 for G2 |
69 | add_vertex(u_global: E, g&: G2); // global vertex E becomes local B2 for G2 |
70 | |
71 | BOOST_TEST(num_vertices(G0) == 6); |
72 | BOOST_TEST(num_vertices(G1) == 3); |
73 | std::cerr << num_vertices(g: G1) << std::endl; |
74 | BOOST_TEST(num_vertices(G2) == 2); |
75 | |
76 | // add edges to root graph |
77 | add_edge(u: A, v: B, g&: G0); |
78 | add_edge(u: B, v: C, g&: G0); |
79 | add_edge(u: B, v: D, g&: G0); |
80 | add_edge(u: E, v: F, g&: G0); |
81 | |
82 | BOOST_TEST(num_edges(G0) == 4); |
83 | BOOST_TEST(num_edges(G1) == 1); |
84 | BOOST_TEST(num_edges(G2) == 0); |
85 | |
86 | // add edges to G1 |
87 | add_edge(u: A1, v: B1, g&: G1); |
88 | BOOST_TEST(num_edges(G0) == 5); |
89 | BOOST_TEST(num_edges(G1) == 2); |
90 | BOOST_TEST(num_edges(G2) == 1); |
91 | // num_vertices stays the same |
92 | BOOST_TEST(num_vertices(G0) == 6); |
93 | BOOST_TEST(num_vertices(G1) == 3); |
94 | BOOST_TEST(num_vertices(G2) == 2); |
95 | } |
96 | |
97 | void addVerticesTest() |
98 | { |
99 | typedef subgraph< adjacency_list< vecS, vecS, directedS, no_property, |
100 | property< edge_index_t, int > > > |
101 | Graph; |
102 | typedef Graph::vertex_descriptor Vertex; |
103 | |
104 | const int N = 3; |
105 | Graph G0(N); |
106 | Graph& G1 = G0.create_subgraph(); |
107 | Graph& G2 = G1.create_subgraph(); |
108 | |
109 | BOOST_TEST(&G1.parent() == &G0); |
110 | BOOST_TEST(&G2.parent() == &G1); |
111 | |
112 | // add vertices to G2 |
113 | Vertex n1 = add_vertex(u_global: 0, g&: G2); |
114 | Vertex n2 = add_vertex(u_global: 1, g&: G2); |
115 | // check if the global vertex 2 is equal to the returned local vertex |
116 | if (G2.find_vertex(u_global: 0).second) |
117 | { |
118 | BOOST_TEST(G2.find_vertex(0).first == n1); |
119 | } |
120 | else |
121 | { |
122 | BOOST_ERROR("vertex not found!" ); |
123 | } |
124 | if (G2.find_vertex(u_global: 1).second) |
125 | { |
126 | BOOST_TEST(G2.find_vertex(1).first == n2); |
127 | } |
128 | else |
129 | { |
130 | BOOST_ERROR("vertex not found!" ); |
131 | } |
132 | // and check if this vertex is also present in G1 |
133 | if (G1.find_vertex(u_global: 0).second) |
134 | { |
135 | BOOST_TEST(G1.local_to_global(G1.find_vertex(0).first) == 0); |
136 | } |
137 | else |
138 | { |
139 | BOOST_ERROR("vertex not found!" ); |
140 | } |
141 | if (G1.find_vertex(u_global: 0).second) |
142 | { |
143 | BOOST_TEST(G1.local_to_global(G1.find_vertex(1).first) == 1); |
144 | } |
145 | else |
146 | { |
147 | BOOST_ERROR("vertex not found!" ); |
148 | } |
149 | |
150 | // num_vertices stays the same |
151 | BOOST_TEST(num_vertices(G0) == 3); |
152 | BOOST_TEST(num_vertices(G1) == 2); |
153 | BOOST_TEST(num_vertices(G2) == 2); |
154 | |
155 | // add vertices to G1 |
156 | Vertex n3 = add_vertex(u_global: 2, g&: G1); |
157 | // check if the global vertex 2 is equal to the returned local vertex |
158 | if (G1.find_vertex(u_global: 2).second) |
159 | { |
160 | BOOST_TEST(G1.find_vertex(2).first == n3); |
161 | } |
162 | else |
163 | { |
164 | BOOST_ERROR("vertex not found!" ); |
165 | } |
166 | // num_vertices stays the same |
167 | BOOST_TEST(num_vertices(G0) == 3); |
168 | BOOST_TEST(num_vertices(G1) == 3); |
169 | BOOST_TEST(num_vertices(G2) == 2); |
170 | |
171 | // add vertices to G1 |
172 | Vertex n4 = add_vertex(g&: G1); |
173 | |
174 | // check if the new local vertex is also in the global graph |
175 | BOOST_TEST(G0.find_vertex(G1.local_to_global(n4)).second); |
176 | // check if the new local vertex is not in the subgraphs |
177 | BOOST_TEST(!G2.find_vertex(n4).second); |
178 | |
179 | // num_vertices stays the same |
180 | BOOST_TEST(num_vertices(G0) == 4); |
181 | BOOST_TEST(num_vertices(G1) == 4); |
182 | BOOST_TEST(num_vertices(G2) == 2); |
183 | |
184 | // add vertices to G0 |
185 | Vertex n5 = add_vertex(g&: G0); |
186 | |
187 | // check if the new local vertex is not in the subgraphs |
188 | BOOST_TEST(!G1.find_vertex(n5).second); |
189 | BOOST_TEST(!G2.find_vertex(n5).second); |
190 | |
191 | // num_vertices stays the same |
192 | BOOST_TEST(num_vertices(G0) == 5); |
193 | BOOST_TEST(num_vertices(G1) == 4); |
194 | BOOST_TEST(num_vertices(G2) == 2); |
195 | |
196 | typedef std::map< graph_traits< Graph::graph_type >::vertex_descriptor, |
197 | graph_traits< Graph::graph_type >::vertex_descriptor >::iterator v_itr; |
198 | |
199 | std::cerr << "All G0 vertices: " << std::endl; |
200 | for (v_itr v = G0.m_local_vertex.begin(); v != G0.m_local_vertex.end(); ++v) |
201 | { |
202 | std::cerr << G0.local_to_global(u_local: v->first) << std::endl; |
203 | } |
204 | std::cerr << "All G1 vertices: " << std::endl; |
205 | for (v_itr v = G1.m_local_vertex.begin(); v != G1.m_local_vertex.end(); ++v) |
206 | { |
207 | std::cerr << G1.local_to_global(u_local: v->first) << std::endl; |
208 | } |
209 | std::cerr << "All G2 vertices: " << std::endl; |
210 | for (v_itr v = G2.m_local_vertex.begin(); v != G2.m_local_vertex.end(); ++v) |
211 | { |
212 | std::cerr << G2.local_to_global(u_local: v->first) << std::endl; |
213 | } |
214 | } |
215 | |
216 | void addEdgeTest() |
217 | { |
218 | typedef subgraph< adjacency_list< vecS, vecS, directedS, no_property, |
219 | property< edge_index_t, int > > > |
220 | Graph; |
221 | typedef Graph::vertex_descriptor Vertex; |
222 | |
223 | const int N = 3; |
224 | Graph G0(N); |
225 | Graph& G1 = G0.create_subgraph(); |
226 | Graph& G2 = G1.create_subgraph(); |
227 | |
228 | BOOST_TEST(&G1.parent() == &G0); |
229 | BOOST_TEST(&G2.parent() == &G1); |
230 | |
231 | // add vertices |
232 | add_vertex(u_global: 0, g&: G2); |
233 | add_vertex(u_global: 1, g&: G2); |
234 | BOOST_TEST(num_vertices(G1) == 2); |
235 | BOOST_TEST(num_vertices(G2) == 2); |
236 | |
237 | // add edge to G0 which needs propagation |
238 | add_edge(u: 0, v: 1, g&: G0); |
239 | |
240 | BOOST_TEST(num_edges(G0) == 1); |
241 | BOOST_TEST(num_edges(G1) == 1); |
242 | BOOST_TEST(num_edges(G2) == 1); |
243 | // num_vertices stays the same |
244 | BOOST_TEST(num_vertices(G0) == 3); |
245 | BOOST_TEST(num_vertices(G1) == 2); |
246 | BOOST_TEST(num_vertices(G2) == 2); |
247 | |
248 | // add edge to G0 without propagation |
249 | add_edge(u: 1, v: 2, g&: G0); |
250 | |
251 | BOOST_TEST(num_edges(G0) == 2); |
252 | BOOST_TEST(num_edges(G1) == 1); |
253 | BOOST_TEST(num_edges(G2) == 1); |
254 | // num_vertices stays the same |
255 | BOOST_TEST(num_vertices(G0) == 3); |
256 | BOOST_TEST(num_vertices(G1) == 2); |
257 | BOOST_TEST(num_vertices(G2) == 2); |
258 | |
259 | // add vertex 2 to G2/G1 with edge propagation |
260 | Vertex n = add_vertex(u_global: 2, g&: G2); |
261 | BOOST_TEST(G2.local_to_global(n) == 2); |
262 | |
263 | BOOST_TEST(num_edges(G0) == 2); |
264 | BOOST_TEST(num_edges(G1) == 2); |
265 | BOOST_TEST(num_edges(G2) == 2); |
266 | // num_vertices stays the same |
267 | BOOST_TEST(num_vertices(G0) == 3); |
268 | BOOST_TEST(num_vertices(G1) == 3); |
269 | BOOST_TEST(num_vertices(G2) == 3); |
270 | |
271 | // add edge to G2 with propagation upwards |
272 | add_edge(u: 0, v: 2, g&: G2); |
273 | |
274 | BOOST_TEST(num_edges(G0) == 3); |
275 | BOOST_TEST(num_edges(G1) == 3); |
276 | BOOST_TEST(num_edges(G2) == 3); |
277 | // num_vertices stays the same |
278 | BOOST_TEST(num_vertices(G0) == 3); |
279 | BOOST_TEST(num_vertices(G1) == 3); |
280 | BOOST_TEST(num_vertices(G2) == 3); |
281 | |
282 | typedef std::map< graph_traits< Graph::graph_type >::vertex_descriptor, |
283 | graph_traits< Graph::graph_type >::vertex_descriptor >::iterator v_itr; |
284 | |
285 | std::cerr << "All G0 vertices: " << std::endl; |
286 | for (v_itr v = G0.m_local_vertex.begin(); v != G0.m_local_vertex.end(); ++v) |
287 | { |
288 | std::cerr << G0.local_to_global(u_local: v->first) << std::endl; |
289 | } |
290 | std::cerr << "All G1 vertices: " << std::endl; |
291 | for (v_itr v = G1.m_local_vertex.begin(); v != G1.m_local_vertex.end(); ++v) |
292 | { |
293 | std::cerr << G1.local_to_global(u_local: v->first) << std::endl; |
294 | } |
295 | std::cerr << "All G2 vertices: " << std::endl; |
296 | for (v_itr v = G2.m_local_vertex.begin(); v != G2.m_local_vertex.end(); ++v) |
297 | { |
298 | std::cerr << G2.local_to_global(u_local: v->first) << std::endl; |
299 | } |
300 | std::cerr << "All G0 edges: " << std::endl; |
301 | BGL_FORALL_EDGES(e, G0, Graph) |
302 | { |
303 | std::cerr << source(e, g: G0) << "->" << target(e, g: G0) << std::endl; |
304 | } |
305 | std::cerr << "All G1 edges: " << std::endl; |
306 | BGL_FORALL_EDGES(e, G1, Graph) |
307 | { |
308 | std::cerr << source(e, g: G1) << "->" << target(e, g: G1) << std::endl; |
309 | } |
310 | std::cerr << "All G2 edges: " << std::endl; |
311 | BGL_FORALL_EDGES(e, G2, Graph) |
312 | { |
313 | std::cerr << source(e, g: G2) << "->" << target(e, g: G2) << std::endl; |
314 | } |
315 | } |
316 | |
317 | int main() |
318 | { |
319 | simpleGraphTest(); |
320 | addVerticesTest(); |
321 | addEdgeTest(); |
322 | return boost::report_errors(); |
323 | } |
324 | |