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 |
|
---|
20 | using namespace boost;
|
---|
21 |
|
---|
22 | // include headers containing functions to test
|
---|
23 |
|
---|
24 | BOOST_AUTO_TEST_SUITE(Subgraph)
|
---|
25 |
|
---|
26 | BOOST_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 |
|
---|
82 | BOOST_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 | }
|
---|
182 |
|
---|
183 |
|
---|
184 | BOOST_AUTO_TEST_SUITE_END()
|
---|