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
24using namespace boost;
25
26void 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
97void 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
216void 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
317int main()
318{
319 simpleGraphTest();
320 addVerticesTest();
321 addEdgeTest();
322 return boost::report_errors();
323}
324

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