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