1 /* Test construction of grids from polyhedron.
2 Copyright (C) 2001-2010 Roberto Bagnara <bagnara@cs.unipr.it>
3 Copyright (C) 2010-2016 BUGSENG srl (http://bugseng.com)
4
5 This file is part of the Parma Polyhedra Library (PPL).
6
7 The PPL is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 The PPL is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1307, USA.
20
21 For the most up-to-date information see the Parma Polyhedra Library
22 site: http://bugseng.com/products/ppl/ . */
23
24 #include "ppl_test.hh"
25
26 namespace {
27
28 // Grid(ph) - non-empty polyhedron
29 bool
test01()30 test01() {
31 Variable A(0);
32 Variable B(1);
33 Variable C(2);
34
35 Constraint_System cs;
36 cs.insert(B == 0);
37 cs.insert(A >= 0);
38 cs.insert(C > 0);
39
40 NNC_Polyhedron ph(cs);
41 Grid gr(ph);
42
43 Grid known_gr(3);
44 known_gr.add_constraint(B == 0);
45
46 bool ok = (gr == known_gr);
47
48 print_congruences(gr, "*** gr(ph) ***");
49
50 return ok;
51 }
52
53 // Grid(ph) - empty polyhedron
54 bool
test02()55 test02() {
56 Variable A(0);
57 Variable B(1);
58 Variable C(2);
59
60 Constraint_System cs;
61 cs.insert(B == 0);
62 cs.insert(A >= 0);
63 cs.insert(B >= 1);
64 cs.insert(C > 0);
65
66 NNC_Polyhedron ph(cs);
67 Grid gr(ph);
68
69 Grid known_gr(3, EMPTY);
70
71 bool ok = (gr == known_gr);
72
73 print_congruences(gr, "*** gr(ph) ***");
74
75 return ok;
76 }
77
78 // Grid(ph) - zero dimension universe polyhedron
79 bool
test03()80 test03() {
81
82 NNC_Polyhedron ph(0);
83 Grid gr(ph);
84
85 Grid known_gr(0);
86
87 bool ok = (gr == known_gr);
88
89 print_congruences(gr, "*** gr(ph) ***");
90
91 return ok;
92 }
93
94 // Grid(ph) - zero dimension empty polyhedron
95 bool
test04()96 test04() {
97
98 NNC_Polyhedron ph(0, EMPTY);
99 Grid gr(ph);
100
101 Grid known_gr(0, EMPTY);
102
103 bool ok = (gr == known_gr);
104
105 print_congruences(gr, "*** gr(ph) ***");
106
107 return ok;
108 }
109
110 // Grid(ph) - non-empty polyhedron constructed from generators
111 bool
test05()112 test05() {
113 Variable A(0);
114 Variable B(1);
115 Variable C(2);
116
117 Generator_System cs;
118 cs.insert(point(A + B, 3));
119 cs.insert(ray(A - C));
120 cs.insert(point());
121
122 C_Polyhedron ph(cs);
123 Grid gr(ph);
124
125 Grid known_gr(3);
126 known_gr.add_constraint(A - B + C == 0);
127
128 bool ok = (gr == known_gr);
129
130 print_congruences(gr, "*** gr(ph) ***");
131 print_generators(gr, "*** gr(ph) ***");
132
133 return ok;
134 }
135
136 /* Grid(ph) - non-empty and non-universe grid built from
137 C_polyhedron constructed from generators */
138 bool
test06()139 test06() {
140 Variable A(0);
141 Variable B(1);
142 Variable C(2);
143
144 Generator_System cs;
145 cs.insert(point(A + B, 3));
146 cs.insert(line(A - C));
147 cs.insert(point(3 * C, 2));
148
149 C_Polyhedron ph(cs);
150
151 Grid gr(ph);
152
153 print_constraints(ph, "*** ph ***");
154
155 Grid known_gr(3);
156 known_gr.add_constraint(2*A + 7*B + 2*C == 3);
157
158 bool ok = (gr == known_gr);
159
160 print_congruences(gr, "*** gr(ph) ***");
161 print_generators(gr, "*** gr(ph) ***");
162
163 print_congruences(known_gr, "*** known_gr(ph) ***");
164 print_generators(known_gr, "*** known_gr(ph) ***");
165
166 return ok;
167 }
168
169 /* Grid(ph) - universe grid built from
170 non-universe C_polyhedron constructed from generators */
171 bool
test07()172 test07() {
173 Variable A(0);
174 Variable B(1);
175 Variable C(2);
176
177 Generator_System cs;
178 cs.insert(point(A + B, 3));
179 cs.insert(point(3 * A, 2));
180 cs.insert(point(B, 7));
181 cs.insert(point(5 * C));
182
183 C_Polyhedron ph(cs);
184
185 Grid gr(ph);
186
187 print_constraints(ph, "*** ph ***");
188
189 Grid known_gr(3);
190
191 bool ok = (gr == known_gr);
192
193 print_congruences(gr, "*** gr(ph) ***");
194 print_generators(gr, "*** gr(ph) ***");
195
196 return ok;
197 }
198
199 // Grid(ph) - universe polyhedron
200 bool
test08()201 test08() {
202
203 NNC_Polyhedron ph(5);
204 Grid gr(ph);
205
206 Grid known_gr(5);
207
208 bool ok = (gr == known_gr);
209
210 print_congruences(gr, "*** gr(ph) ***");
211
212 return ok;
213 }
214
215 /* Grid(ph) - non-empty and non-universe grid built from
216 C_polyhedron constructed from generators; The complexity
217 limit allows the detection of implicit equalities from
218 any generator system*/
219 bool
test09()220 test09() {
221 Variable A(0);
222 Variable B(1);
223 Variable C(2);
224
225 Generator_System cs;
226 cs.insert(point(A + B));
227 cs.insert(line(A - C));
228 cs.insert(point(3 * C));
229
230 C_Polyhedron ph(cs);
231
232 Grid gr(ph, POLYNOMIAL_COMPLEXITY);
233
234 print_constraints(ph, "*** ph ***");
235
236 Grid known_gr(3);
237 known_gr.add_constraint(A + 2*B + C == 3);
238
239 bool ok = (gr == known_gr);
240
241 print_congruences(gr, "*** gr(ph) ***");
242 print_generators(gr, "*** gr(ph) ***");
243
244 print_congruences(known_gr, "*** known_gr(ph) ***");
245 print_generators(known_gr, "*** known_gr(ph) ***");
246
247 return ok;
248 }
249
250 /* Grid(ph) - non-empty and non-universe grid built from
251 C_polyhedron constructed from constraints; The complexity
252 is unlimited so it is able to detect the implicit equality */
253 bool
test10()254 test10() {
255 Variable A(0);
256 Variable B(1);
257
258 Constraint_System cs;
259 cs.insert(B >= 0);
260 cs.insert(B <= 0);
261 cs.insert(A >= 0);
262
263 C_Polyhedron ph(cs);
264 Grid gr(ph, ANY_COMPLEXITY);
265
266 Grid known_gr(2);
267 known_gr.add_constraint(B == 0);
268
269 bool ok = (gr == known_gr);
270
271 print_congruences(gr, "*** gr(ph) ***");
272
273 return ok;
274 }
275
276 /* Grid(ph) - non-empty and non-universe grid built from
277 C_polyhedron constructed from constraints; The complexity
278 is limited to be polynomial so it is unable to detect the
279 implicit equality */
280 bool
test11()281 test11() {
282 Variable A(0);
283 Variable B(1);
284
285 Constraint_System cs;
286 cs.insert(B >= 0);
287 cs.insert(B <= 0);
288 cs.insert(A >= 0);
289
290 C_Polyhedron ph(cs);
291 Grid gr(ph, POLYNOMIAL_COMPLEXITY);
292
293 Grid known_gr(2);
294
295 bool ok = (gr == known_gr);
296
297 print_congruences(gr, "*** gr(ph) ***");
298
299 return ok;
300 }
301
302 /* Grid(ph) - non-empty and non-universe grid built from
303 C_polyhedron constructed from constraints; The complexity
304 is limited to that of simplex so it is unable to detect the
305 implicit equality */
306 bool
test12()307 test12() {
308 Variable A(0);
309 Variable B(1);
310
311 Constraint_System cs;
312 cs.insert(B >= 0);
313 cs.insert(B <= 0);
314 cs.insert(A >= 0);
315
316 C_Polyhedron ph(cs);
317 Grid gr(ph, SIMPLEX_COMPLEXITY);
318
319 Grid known_gr(2);
320
321 bool ok = (gr == known_gr);
322
323 print_congruences(gr, "*** gr(ph) ***");
324
325 return ok;
326 }
327
328 } // namespace
329
330 BEGIN_MAIN
331 DO_TEST(test01);
332 DO_TEST(test02);
333 DO_TEST(test03);
334 DO_TEST(test04);
335 DO_TEST(test05);
336 DO_TEST(test06);
337 DO_TEST_F8(test07);
338 DO_TEST(test08);
339 DO_TEST(test09);
340 DO_TEST(test10);
341 DO_TEST(test11);
342 DO_TEST(test12);
343 END_MAIN
344