Ticket #11714: test_subgraph.2.cc

File test_subgraph.2.cc, 8.5 KB (added by Stefan Hammer <s.hammer@…>, 7 years ago)

UPDATE: Boost unit test for the issue

Line 
1/* This file is a boost.test unit test and provides tests the internal dependency graph
2 *
3 * Created on: 06.10.2015
4 * Author: Stefan Hammer <s.hammer@univie.ac.at>
5 * License: GPLv3
6 *
7 */
8
9// std lib includes
10#include <iostream>
11
12// include boost components
13#include <boost/test/unit_test.hpp>
14#include <boost/graph/adjacency_list.hpp>
15#include <boost/graph/iteration_macros.hpp>
16
17// include header
18#include <boost/graph/subgraph.hpp>
19
20using namespace boost;
21
22// include headers containing functions to test
23
24BOOST_AUTO_TEST_SUITE(Subgraph)
25
26BOOST_AUTO_TEST_CASE(simpleGraph) {
27
28 BOOST_TEST_MESSAGE("simple subgraph");
29
30 typedef subgraph< adjacency_list< vecS, vecS, directedS,
31 no_property, property< edge_index_t, int > > > Graph;
32 typedef Graph::edge_descriptor Edge;
33 typedef Graph::vertex_descriptor Vertex;
34
35 const int N = 6;
36 Graph G0(N);
37
38 enum { A, B, C, D, E, F}; // for conveniently refering to vertices in G0
39
40 Graph& G1 = G0.create_subgraph();
41 Graph& G2 = G1.create_subgraph();
42
43 BOOST_CHECK(&G1.parent() == &G0);
44 BOOST_CHECK(&G2.parent() == &G1);
45
46 enum { A1, B1, C1 }; // for conveniently refering to vertices in G1
47 enum { A2, B2, C2 }; // for conveniently refering to vertices in G2
48
49 add_vertex(C, G1); // global vertex C becomes local A1 for G1
50 add_vertex(E, G1); // global vertex E becomes local B1 for G1
51 add_vertex(F, G1); // global vertex F becomes local C1 for G1
52
53 add_vertex(C, G2); // global vertex C becomes local A2 for G2
54 add_vertex(E, G2); // global vertex E becomes local B2 for G2
55
56 BOOST_CHECK(num_vertices(G0) == 6);
57 BOOST_CHECK(num_vertices(G1) == 3);
58 std::cerr << num_vertices(G1) << std::endl;
59 BOOST_CHECK(num_vertices(G2) == 2);
60
61 // add edges to root graph
62 add_edge(A, B, G0);
63 add_edge(B, C, G0);
64 add_edge(B, D, G0);
65 add_edge(E, F, G0);
66
67 BOOST_CHECK(num_edges(G0) == 4);
68 BOOST_CHECK(num_edges(G1) == 1);
69 BOOST_CHECK(num_edges(G2) == 0);
70
71 // add edges to G1
72 add_edge(A1, B1, G1);
73 BOOST_CHECK(num_edges(G0) == 5);
74 BOOST_CHECK(num_edges(G1) == 2);
75 BOOST_CHECK(num_edges(G2) == 1);
76 // num_vertices stays the same
77 BOOST_CHECK(num_vertices(G0) == 6);
78 BOOST_CHECK(num_vertices(G1) == 3);
79 BOOST_CHECK(num_vertices(G2) == 2);
80}
81
82BOOST_AUTO_TEST_CASE(addVertices) {
83
84 BOOST_TEST_MESSAGE("subgraph add edges");
85
86 typedef subgraph< adjacency_list< vecS, vecS, directedS,
87 no_property, property< edge_index_t, int > > > Graph;
88 typedef Graph::edge_descriptor Edge;
89 typedef Graph::vertex_descriptor Vertex;
90
91 const int N = 3;
92 Graph G0(N);
93 Graph& G1 = G0.create_subgraph();
94 Graph& G2 = G1.create_subgraph();
95
96 BOOST_CHECK(&G1.parent() == &G0);
97 BOOST_CHECK(&G2.parent() == &G1);
98
99 // add vertices to G2
100 Vertex n1 = add_vertex(0, G2);
101 Vertex n2 = add_vertex(1, G2);
102 // check if the global vertex 2 is equal to the returned local vertex
103 if (G2.find_vertex(0).second) {
104 BOOST_CHECK(G2.find_vertex(0).first == n1);
105 } else {
106 BOOST_ERROR( "vertex not found!" );
107 }
108 if (G2.find_vertex(1).second) {
109 BOOST_CHECK(G2.find_vertex(1).first == n2);
110 } else {
111 BOOST_ERROR( "vertex not found!" );
112 }
113 // and check if this vertex is also present in G1
114 if (G1.find_vertex(0).second) {
115 BOOST_CHECK(G1.local_to_global(G1.find_vertex(0).first) == 0);
116 } else {
117 BOOST_ERROR( "vertex not found!" );
118 }
119 if (G1.find_vertex(0).second) {
120 BOOST_CHECK(G1.local_to_global(G1.find_vertex(1).first) == 1);
121 } else {
122 BOOST_ERROR( "vertex not found!" );
123 }
124
125 // num_vertices stays the same
126 BOOST_CHECK(num_vertices(G0) == 3);
127 BOOST_CHECK(num_vertices(G1) == 2);
128 BOOST_CHECK(num_vertices(G2) == 2);
129
130 // add vertices to G1
131 Vertex n3 = add_vertex(2, G1);
132 // check if the global vertex 2 is equal to the returned local vertex
133 if (G1.find_vertex(2).second) {
134 BOOST_CHECK(G1.find_vertex(2).first == n3);
135 } else {
136 BOOST_ERROR( "vertex not found!" );
137 }
138 // num_vertices stays the same
139 BOOST_CHECK(num_vertices(G0) == 3);
140 BOOST_CHECK(num_vertices(G1) == 3);
141 BOOST_CHECK(num_vertices(G2) == 2);
142
143 // add vertices to G1
144 Vertex n4 = add_vertex(G1);
145
146 // check if the new local vertex is also in the global graph
147 BOOST_CHECK(G0.find_vertex(G1.local_to_global(n4)).second);
148 // check if the new local vertex is not in the subgraphs
149 BOOST_CHECK(!G2.find_vertex(n4).second);
150
151 // num_vertices stays the same
152 BOOST_CHECK(num_vertices(G0) == 4);
153 BOOST_CHECK(num_vertices(G1) == 4);
154 BOOST_CHECK(num_vertices(G2) == 2);
155
156 // add vertices to G0
157 Vertex n5 = add_vertex(G0);
158
159 // check if the new local vertex is not in the subgraphs
160 BOOST_CHECK(!G1.find_vertex(n5).second);
161 BOOST_CHECK(!G2.find_vertex(n5).second);
162
163 // num_vertices stays the same
164 BOOST_CHECK(num_vertices(G0) == 5);
165 BOOST_CHECK(num_vertices(G1) == 4);
166 BOOST_CHECK(num_vertices(G2) == 2);
167
168 std::cerr << "All G0 vertices: " << std::endl;
169 BGL_FORALL_VERTICES_T(v, G0, Graph) {
170 std::cerr << G0.local_to_global(v) << std::endl;
171 }
172 std::cerr << "All G1 vertices: " << std::endl;
173 BGL_FORALL_VERTICES_T(v, G1, Graph) {
174 std::cerr << G1.local_to_global(v) << std::endl;
175 }
176 std::cerr << "All G2 vertices: " << std::endl;
177 BGL_FORALL_VERTICES_T(v, G2, Graph) {
178 std::cerr << G2.local_to_global(v) << std::endl;
179 }
180}
181
182BOOST_AUTO_TEST_CASE(addEdge) {
183
184 BOOST_TEST_MESSAGE("subgraph add edges");
185
186 typedef subgraph< adjacency_list< vecS, vecS, directedS,
187 no_property, property< edge_index_t, int > > > Graph;
188 typedef Graph::edge_descriptor Edge;
189 typedef Graph::vertex_descriptor Vertex;
190
191 const int N = 3;
192 Graph G0(N);
193 Graph& G1 = G0.create_subgraph();
194 Graph& G2 = G1.create_subgraph();
195
196 BOOST_CHECK(&G1.parent() == &G0);
197 BOOST_CHECK(&G2.parent() == &G1);
198
199 // add vertices
200 add_vertex(0, G2);
201 add_vertex(1, G2);
202 BOOST_CHECK(num_vertices(G1) == 2);
203 BOOST_CHECK(num_vertices(G2) == 2);
204
205 // add edge to G0 which needs propagation
206 add_edge(0, 1, G0);
207
208 BOOST_CHECK(num_edges(G0) == 1);
209 BOOST_CHECK(num_edges(G1) == 1);
210 BOOST_CHECK(num_edges(G2) == 1);
211 // num_vertices stays the same
212 BOOST_CHECK(num_vertices(G0) == 3);
213 BOOST_CHECK(num_vertices(G1) == 2);
214 BOOST_CHECK(num_vertices(G2) == 2);
215
216 // add edge to G0 without propagation
217 add_edge(1, 2, G0);
218
219 BOOST_CHECK(num_edges(G0) == 2);
220 BOOST_CHECK(num_edges(G1) == 1);
221 BOOST_CHECK(num_edges(G2) == 1);
222 // num_vertices stays the same
223 BOOST_CHECK(num_vertices(G0) == 3);
224 BOOST_CHECK(num_vertices(G1) == 2);
225 BOOST_CHECK(num_vertices(G2) == 2);
226
227 // add vertex 2 to G2/G1 with edge propagation
228 Vertex n = add_vertex(2, G2);
229 BOOST_CHECK(G2.local_to_global(n) == 2);
230
231 BOOST_CHECK(num_edges(G0) == 2);
232 BOOST_CHECK(num_edges(G1) == 2);
233 BOOST_CHECK(num_edges(G2) == 2);
234 // num_vertices stays the same
235 BOOST_CHECK(num_vertices(G0) == 3);
236 BOOST_CHECK(num_vertices(G1) == 3);
237 BOOST_CHECK(num_vertices(G2) == 3);
238
239 // add edge to G2 with propagation upwards
240 add_edge(0, 2, G2);
241
242 BOOST_CHECK(num_edges(G0) == 3);
243 BOOST_CHECK(num_edges(G1) == 3);
244 BOOST_CHECK(num_edges(G2) == 3);
245 // num_vertices stays the same
246 BOOST_CHECK(num_vertices(G0) == 3);
247 BOOST_CHECK(num_vertices(G1) == 3);
248 BOOST_CHECK(num_vertices(G2) == 3);
249
250 std::cerr << "All G0 vertices: " << std::endl;
251 BGL_FORALL_VERTICES_T(v, G0, Graph) {
252 std::cerr << G0.local_to_global(v) << std::endl;
253 }
254 std::cerr << "All G1 vertices: " << std::endl;
255 BGL_FORALL_VERTICES_T(v, G1, Graph) {
256 std::cerr << G1.local_to_global(v) << std::endl;
257 }
258 std::cerr << "All G2 vertices: " << std::endl;
259 BGL_FORALL_VERTICES_T(v, G2, Graph) {
260 std::cerr << G2.local_to_global(v) << std::endl;
261 }
262 std::cerr << "All G0 edges: " << std::endl;
263 BGL_FORALL_EDGES_T(e, G0, Graph) {
264 std::cerr << source(e, G0) << "->" << target(e, G0) << std::endl;
265 }
266 std::cerr << "All G1 edges: " << std::endl;
267 BGL_FORALL_EDGES_T(e, G1, Graph) {
268 std::cerr << source(e, G1) << "->" << target(e, G1) << std::endl;
269 }
270 std::cerr << "All G2 edges: " << std::endl;
271 BGL_FORALL_EDGES_T(e, G2, Graph) {
272 std::cerr << source(e, G2) << "->" << target(e, G2) << std::endl;
273 }
274}
275
276BOOST_AUTO_TEST_SUITE_END()