?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
testlib: return success when tests run successfully
[barvinok.git] / testlib.cc
bloba7d5727c62b3d13bac5d38681c9bdd576841d451
1 #include <assert.h>
2 #include <stdlib.h>
3 #include <sstream>
4 #include <barvinok/barvinok.h>
5 #include <barvinok/set.h>
6 #include <barvinok/options.h>
7 #include <barvinok/basis_reduction.h>
8 #include <barvinok/evalue.h>
9 #include <barvinok/util.h>
10 #include "conversion.h"
11 #include "evalue_read.h"
12 #include "dpoly.h"
13 #include "lattice_point.h"
14 #include "counter.h"
15 #include "bernoulli.h"
16 #include "hilbert.h"
17 #include "hull.h"
18 #include "ilp.h"
19 #include "laurent.h"
20 #include "matrix_read.h"
21 #include "remove_equalities.h"
22 #include "config.h"
23
24 using std::cout;
25 using std::cerr;
26 using std::endl;
27
28 template <typename T>
29 void set_from_string(T& v, const char *s)
30 {
31 std::istringstream str(s);
32 str >> v;
33 }
34
35 static Matrix *matrix_read_from_str(const char *s)
36 {
37 std::istringstream str(s);
38 return Matrix_Read(str);
39 }
40
41 static int test_equalities(struct barvinok_options *options)
42 {
43 Matrix *M = matrix_read_from_str(
44 "11 11\n"
45 " 0 23 0 0 -10 0 0 0 7 -44 -8 \n"
46 " 0 0 23 0 5 0 0 0 -15 114 27 \n"
47 " 0 0 0 1 0 0 0 0 0 -1 2 \n"
48 " 0 0 0 0 0 1 0 0 -1 8 0 \n"
49 " 0 0 0 0 0 0 1 0 0 -1 2 \n"
50 " 0 0 0 0 0 0 0 1 0 -1 -1 \n"
51 " 1 0 0 0 10 0 0 0 -7 44 8 \n"
52 " 1 0 0 0 -5 0 0 0 15 -114 -27 \n"
53 " 1 0 0 0 1 0 0 0 0 0 0 \n"
54 " 1 0 0 0 0 0 0 0 1 -8 0 \n"
55 " 1 0 0 0 0 0 0 0 0 1 -2 \n");
56 Polyhedron *P = Constraints2Polyhedron(M, options->MaxRays);
57 Matrix_Free(M);
58 Polyhedron *Q = P;
59 remove_all_equalities(&P, NULL, NULL, NULL, 2, options->MaxRays);
60 assert(P->NbEq == 0);
61 if (P != Q)
62 Polyhedron_Free(Q);
63 Polyhedron_Free(P);
64 return 0;
65 }
66
67 int test_evalue_read(struct barvinok_options *options)
68 {
69 unsigned nvar, nparam;
70 const char **all_vars;
71 evalue *e1, *e2;
72
73 e1 = evalue_read_from_str("(1 * aa + 2 * a)",
74 NULL, &all_vars, &nvar, &nparam, options->MaxRays);
75 Free_ParamNames(all_vars, nvar+nparam);
76 e2 = evalue_read_from_str("(3 * aa)",
77 NULL, &all_vars, &nvar, &nparam, options->MaxRays);
78 Free_ParamNames(all_vars, nvar+nparam);
79 assert(!eequal(e1, e2));
80 evalue_free(e1);
81 evalue_free(e2);
82 return 0;
83 }
84
85 static void evalue_check_disjoint(evalue *e)
86 {
87 int i, j;
88
89 if (!e)
90 return;
91 if (EVALUE_IS_ZERO(*e))
92 return;
93 for (i = 0; i < e->x.p->size/2; ++i) {
94 Polyhedron *A = EVALUE_DOMAIN(e->x.p->arr[2*i]);
95 for (j = i+1; j < e->x.p->size/2; ++j) {
96 Polyhedron *B = EVALUE_DOMAIN(e->x.p->arr[2*j]);
97 Polyhedron *I = DomainIntersection(A, B, 0);
98 assert(emptyQ(I));
99 Polyhedron_Free(I);
100 }
101 }
102 }
103
104 static int test_eadd(struct barvinok_options *options)
105 {
106 unsigned nvar, nparam;
107 const char **all_vars;
108 evalue *e1, *e2;
109
110 e1 = evalue_read_from_str(" d -1 = 0\n"
111 " h -3 >= 0\n"
112 " - h + 100 >= 0\n"
113 "\n"
114 "(1)\n",
115 "d,h", &all_vars, &nvar, &nparam,
116 options->MaxRays);
117 Free_ParamNames(all_vars, nvar+nparam);
118 e2 = evalue_read_from_str(
119 " h -3 = 0\n"
120 " d -1 >= 0\n"
121 " - d + 3 >= 0\n"
122 "\n"
123 "(0)\n"
124 " d -1 >= 0\n"
125 " - d + 3 >= 0\n"
126 " h -4 >= 0\n"
127 " - h + 100 >= 0\n"
128 "\n"
129 "(1)\n",
130 "d,h", &all_vars, &nvar, &nparam,
131 options->MaxRays);
132 Free_ParamNames(all_vars, nvar+nparam);
133 eadd(e2, e1);
134 evalue_check_disjoint(e1);
135 evalue_free(e1);
136 evalue_free(e2);
137 return 0;
138 }
139
140 int test_evalue(struct barvinok_options *options)
141 {
142 unsigned nvar, nparam;
143 const char **all_vars;
144 evalue *poly1, poly2;
145
146 poly1 = evalue_read_from_str("(1/4 * n^4 + 1/2 * n^3 + 1/4 * n^2)",
147 NULL, &all_vars, &nvar, &nparam,
148 options->MaxRays);
149 Free_ParamNames(all_vars, nvar+nparam);
150
151 value_init(poly2.d);
152 evalue_copy(&poly2, poly1);
153 evalue_negate(poly1);
154 eadd(&poly2, poly1);
155 reduce_evalue(poly1);
156 assert(EVALUE_IS_ZERO(*poly1));
157 evalue_free(poly1);
158 free_evalue_refs(&poly2);
159 return 0;
160 }
161
162 int test_substitute(struct barvinok_options *options)
163 {
164 unsigned nvar, nparam;
165 const char **all_vars;
166 const char *vars = "a,b";
167 evalue *e1, *e2;
168 evalue *subs[2];
169
170 e1 = evalue_read_from_str("[ { 1/3 * a } = 0 ] * \n"
171 " ([ { 1/5 * b + 2/5 } = 0 ] * 5) + \n"
172 "[ { 1/3 * a } != 0 ] * 42",
173 vars, &all_vars, &nvar, &nparam,
174 options->MaxRays);
175 Free_ParamNames(all_vars, nvar+nparam);
176
177 subs[0] = evalue_read_from_str("(2 * b + 5)",
178 vars, &all_vars, &nvar, &nparam,
179 options->MaxRays);
180 Free_ParamNames(all_vars, nvar+nparam);
181 subs[1] = evalue_read_from_str("(a + 1)",
182 vars, &all_vars, &nvar, &nparam,
183 options->MaxRays);
184 Free_ParamNames(all_vars, nvar+nparam);
185
186 evalue_substitute(e1, subs);
187 evalue_free(subs[0]);
188 evalue_free(subs[1]);
189 reduce_evalue(e1);
190
191 e2 = evalue_read_from_str("[ { 2/3 * b + 2/3 } = 0 ] * \n"
192 " ([ { 1/5 * a + 3/5 } = 0 ] * 5) + \n"
193 "[ { 2/3 * b + 2/3 } != 0 ] * 42",
194 vars, &all_vars, &nvar, &nparam,
195 options->MaxRays);
196 Free_ParamNames(all_vars, nvar+nparam);
197 reduce_evalue(e2);
198
199 assert(eequal(e1, e2));
200
201 evalue_free(e1);
202 evalue_free(e2);
203 return 0;
204 }
205
206 int test_specialization(struct barvinok_options *options)
207 {
208 Value v;
209 value_init(v);
210 mpq_t count;
211 mpq_init(count);
212
213 value_set_si(v, 5);
214 dpoly n(2, v);
215 assert(value_cmp_si(n.coeff->p[0], 1) == 0);
216 assert(value_cmp_si(n.coeff->p[1], 5) == 0);
217 assert(value_cmp_si(n.coeff->p[2], 10) == 0);
218
219 value_set_si(v, 1);
220 dpoly d(2, v, 1);
221 value_set_si(v, 2);
222 dpoly d2(2, v, 1);
223 d *= d2;
224 assert(value_cmp_si(d.coeff->p[0], 2) == 0);
225 assert(value_cmp_si(d.coeff->p[1], 1) == 0);
226 assert(value_cmp_si(d.coeff->p[2], 0) == 0);
227
228 n.div(d, count, 1);
229 mpq_canonicalize(count);
230 assert(value_cmp_si(mpq_numref(count), 31) == 0);
231 assert(value_cmp_si(mpq_denref(count), 8) == 0);
232
233 value_set_si(v, -2);
234 dpoly n2(2, v);
235 assert(value_cmp_si(n2.coeff->p[0], 1) == 0);
236 assert(value_cmp_si(n2.coeff->p[1], -2) == 0);
237 assert(value_cmp_si(n2.coeff->p[2], 3) == 0);
238
239 n2.div(d, count, 1);
240 mpq_canonicalize(count);
241 assert(value_cmp_si(mpq_numref(count), 6) == 0);
242 assert(value_cmp_si(mpq_denref(count), 1) == 0);
243
244 value_clear(v);
245 mpq_clear(count);
246 return 0;
247 }
248
249 int test_lattice_points(struct barvinok_options *options)
250 {
251 Param_Vertices V;
252 mat_ZZ tmp;
253 set_from_string(tmp, "[[0 0 0 0 4][0 0 0 0 4][-1 0 1 0 4]]");
254 V.Vertex = zz2matrix(tmp);
255 vec_ZZ lambda;
256 set_from_string(lambda, "[3 5 7]");
257 mat_ZZ rays;
258 set_from_string(rays, "[[0 1 0][4 0 1][0 0 -1]]");
259 term_info num;
260 evalue *point[4];
261
262 unsigned nvar, nparam;
263 const char **all_vars;
264 point[0] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
265 "( 7 * {( 1/4 * a + ( 3/4 * c + 3/4 ) ) } + -21/4 ) ) )",
266 "a,b,c", &all_vars, &nvar, &nparam, options->MaxRays);
267 Free_ParamNames(all_vars, nvar+nparam);
268 point[1] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
269 "( 7 * {( 1/4 * a + ( 3/4 * c + 1/2 ) ) } + -1/2 ) ) )",
270 "a,b,c", &all_vars, &nvar, &nparam, options->MaxRays);
271 Free_ParamNames(all_vars, nvar+nparam);
272 point[2] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
273 "( 7 * {( 1/4 * a + ( 3/4 * c + 1/4 ) ) } + 17/4 ) ) )",
274 "a,b,c", &all_vars, &nvar, &nparam, options->MaxRays);
275 Free_ParamNames(all_vars, nvar+nparam);
276 point[3] = evalue_read_from_str("( -7/4 * a + ( 7/4 * c + "
277 "( 7 * {( 1/4 * a + ( 3/4 * c + 0 ) ) } + 9 ) ) )",
278 "a,b,c", &all_vars, &nvar, &nparam, options->MaxRays);
279 Free_ParamNames(all_vars, nvar+nparam);
280
281 lattice_point(&V, rays, lambda, &num, 4, options);
282 Matrix_Free(V.Vertex);
283
284 for (int i = 0; i < 4; ++i) {
285 assert(eequal(num.E[i], point[i]));
286 evalue_free(point[i]);
287 evalue_free(num.E[i]);
288 }
289 delete [] num.E;
290 return 0;
291 }
292
293 static int test_icounter(struct barvinok_options *options)
294 {
295 icounter cnt(2);
296 vec_QQ n_coeff;
297 mat_ZZ n_power;
298 mat_ZZ d_power;
299 set_from_string(n_coeff, "[-2/1 1/1]");
300 set_from_string(n_power, "[[2 6][3 6]]");
301 d_power.SetDims(0, 2);
302 cnt.reduce(n_coeff, n_power, d_power);
303 assert(value_cmp_si(mpq_numref(cnt.count), -1) == 0);
304 assert(value_cmp_si(mpq_denref(cnt.count), 1) == 0);
305 return 0;
306 }
307
308 static int test_infinite_counter(struct barvinok_options *options)
309 {
310 Matrix *M = matrix_read_from_str("1 3\n 1 1 0\n");
311 Polyhedron *ctx = Constraints2Polyhedron(M, options->MaxRays);
312 Matrix_Free(M);
313
314 /* (1 -1/2 x^5 - 1/2 x^7)/(1-x) */
315 infinite_counter *cnt = new infinite_counter(1, 1);
316 cnt->init(ctx, 0);
317 vec_QQ n_coeff;
318 mat_ZZ n_power;
319 mat_ZZ d_power;
320 set_from_string(n_coeff, "[1/1 -1/2 -1/2]");
321 set_from_string(n_power, "[[0][5][7]]");
322 set_from_string(d_power, "[[1]]");
323 cnt->reduce(n_coeff, n_power, d_power);
324 assert(value_cmp_si(mpq_numref(cnt->count[0]), 6) == 0);
325 assert(value_cmp_si(mpq_denref(cnt->count[0]), 1) == 0);
326 assert(value_cmp_si(mpq_numref(cnt->count[1]), 0) == 0);
327 assert(value_cmp_si(mpq_denref(cnt->count[1]), 1) == 0);
328 delete cnt;
329 Polyhedron_Free(ctx);
330
331 M = matrix_read_from_str("2 4\n 1 1 0 0\n 1 0 1 0\n");
332 ctx = Constraints2Polyhedron(M, options->MaxRays);
333 Matrix_Free(M);
334
335 /* (1 - xy)/((1-x)(1-xy)) */
336 cnt = new infinite_counter(2, 3);
337 cnt->init(ctx, 0);
338 set_from_string(n_coeff, "[1/1 -1/1]");
339 set_from_string(n_power, "[[0 0][1 1]]");
340 set_from_string(d_power, "[[1 0][1 1]]");
341 cnt->reduce(n_coeff, n_power, d_power);
342 assert(value_cmp_si(mpq_numref(cnt->count[1]), 0) != 0);
343 assert(value_cmp_si(mpq_numref(cnt->count[2]), 0) == 0);
344 assert(value_cmp_si(mpq_denref(cnt->count[2]), 1) == 0);
345 assert(value_cmp_si(mpq_numref(cnt->count[3]), 0) == 0);
346 assert(value_cmp_si(mpq_denref(cnt->count[3]), 1) == 0);
347 delete cnt;
348
349 cnt = new infinite_counter(2, 2);
350 cnt->init(ctx, 0);
351 set_from_string(n_coeff, "[-1/2 1/1 -1/3]");
352 set_from_string(n_power, "[[2 6][3 6]]");
353 d_power.SetDims(0, 2);
354 cnt->reduce(n_coeff, n_power, d_power);
355 assert(value_cmp_si(mpq_numref(cnt->count[0]), 1) == 0);
356 assert(value_cmp_si(mpq_denref(cnt->count[0]), 6) == 0);
357 assert(value_cmp_si(mpq_numref(cnt->count[1]), 0) == 0);
358 assert(value_cmp_si(mpq_denref(cnt->count[1]), 1) == 0);
359 assert(value_cmp_si(mpq_numref(cnt->count[2]), 0) == 0);
360 assert(value_cmp_si(mpq_denref(cnt->count[2]), 1) == 0);
361 delete cnt;
362
363 cnt = new infinite_counter(2, 2);
364 cnt->init(ctx, 0);
365 set_from_string(n_coeff, "[1/1]");
366 set_from_string(n_power, "[[0 11]]");
367 set_from_string(d_power, "[[0 1]]");
368 cnt->reduce(n_coeff, n_power, d_power);
369 assert(value_cmp_si(mpq_numref(cnt->count[1]), 0) != 0);
370 assert(value_cmp_si(mpq_numref(cnt->count[2]), 0) == 0);
371 assert(value_cmp_si(mpq_denref(cnt->count[2]), 1) == 0);
372 delete cnt;
373
374 Polyhedron_Free(ctx);
375
376 return 0;
377 }
378
379 static int test_series(struct barvinok_options *options)
380 {
381 Matrix *M = matrix_read_from_str(
382 "12 11\n"
383 " 0 1 0 0 0 0 0 1 0 0 3 \n"
384 " 0 0 1 0 0 0 0 -1 1 0 -5 \n"
385 " 0 0 0 1 0 0 0 0 -2 -1 6 \n"
386 " 0 0 0 0 1 0 0 1 1 0 5 \n"
387 " 0 0 0 0 0 1 0 0 -1 0 0 \n"
388 " 0 0 0 0 0 0 1 -2 0 -1 -3 \n"
389 " 1 0 0 0 0 0 0 2 0 1 3 \n"
390 " 1 0 0 0 0 0 0 1 -1 0 5 \n"
391 " 1 0 0 0 0 0 0 -1 -1 0 -5 \n"
392 " 1 0 0 0 0 0 0 -1 0 0 -3 \n"
393 " 1 0 0 0 0 0 0 0 2 1 -6 \n"
394 " 1 0 0 0 0 0 0 0 1 0 0 \n");
395 Polyhedron *P = Constraints2Polyhedron(M, options->MaxRays);
396 Matrix_Free(M);
397 Polyhedron *C = Universe_Polyhedron(3);
398 gen_fun *gf = barvinok_series_with_options(P, C, options);
399 Polyhedron_Free(P);
400 Polyhedron_Free(C);
401 delete gf;
402
403 M = matrix_read_from_str(
404 "7 8\n"
405 " 0 1 1 0 0 1 0 2 \n"
406 " 0 0 0 1 0 -2 0 6 \n"
407 " 0 0 0 0 1 -1 0 -1 \n"
408 " 0 0 0 0 0 0 1 0 \n"
409 " 1 0 1 0 0 0 0 0 \n"
410 " 1 0 -1 0 0 -1 0 -2 \n"
411 " 1 0 0 0 0 1 0 -3 \n");
412 P = Constraints2Polyhedron(M, options->MaxRays);
413 Matrix_Free(M);
414 C = Universe_Polyhedron(2);
415 gf = barvinok_series_with_options(P, C, options);
416 Polyhedron_Free(P);
417 Polyhedron_Free(C);
418 delete gf;
419
420 M = matrix_read_from_str(
421 "2 3\n"
422 "1 1 0\n"
423 "1 -1 10\n");
424 P = Constraints2Polyhedron(M, options->MaxRays);
425 Matrix_Free(M);
426 C = Universe_Polyhedron(1);
427 gf = barvinok_series_with_options(P, C, options);
428 Polyhedron_Free(P);
429 Polyhedron_Free(C);
430 gen_fun *sum = gf->summate(1, options);
431 delete gf;
432 delete sum;
433
434 return 0;
435 }
436
437 int test_todd(struct barvinok_options *options)
438 {
439 tcounter t(2, options->max_index);
440 assert(value_cmp_si(t.todd.coeff->p[0], 1) == 0);
441 assert(value_cmp_si(t.todd.coeff->p[1], -3) == 0);
442 assert(value_cmp_si(t.todd.coeff->p[2], 3) == 0);
443 assert(value_cmp_si(t.todd_denom->p[0], 1) == 0);
444 assert(value_cmp_si(t.todd_denom->p[1], 6) == 0);
445 assert(value_cmp_si(t.todd_denom->p[2], 36) == 0);
446
447 vec_ZZ lambda;
448 set_from_string(lambda, "[1 -1]");
449 zz2values(lambda, t.lambda->p);
450
451 mat_ZZ rays;
452 set_from_string(rays, "[[-1 0][-1 1]]");
453
454 QQ one(1, 1);
455
456 vec_ZZ v;
457 set_from_string(v, "[2 0 1]");
458 Vector *vertex = Vector_Alloc(3);
459 zz2values(v, vertex->p);
460
461 t.handle(rays, vertex->p, one, 1, options);
462 assert(value_cmp_si(mpq_numref(t.count), 71) == 0);
463 assert(value_cmp_si(mpq_denref(t.count), 24) == 0);
464
465 set_from_string(rays, "[[0 -1][1 -1]]");
466 set_from_string(v, "[0 2 1]");
467 zz2values(v, vertex->p);
468
469 t.handle(rays, vertex->p, one, 1, options);
470 assert(value_cmp_si(mpq_numref(t.count), 71) == 0);
471 assert(value_cmp_si(mpq_denref(t.count), 12) == 0);
472
473 set_from_string(rays, "[[1 0][0 1]]");
474 set_from_string(v, "[0 0 1]");
475 zz2values(v, vertex->p);
476
477 t.handle(rays, vertex->p, one, 1, options);
478 assert(value_cmp_si(mpq_numref(t.count), 6) == 0);
479 assert(value_cmp_si(mpq_denref(t.count), 1) == 0);
480
481 Vector_Free(vertex);
482 return 0;
483 }
484
485 int test_bernoulli(struct barvinok_options *options)
486 {
487 struct bernoulli_coef *bernoulli_coef;
488 struct poly_list *faulhaber, *bernoulli;
489 bernoulli_coef = bernoulli_coef_compute(2);
490 faulhaber = faulhaber_compute(4);
491 bernoulli_coef = bernoulli_coef_compute(8);
492 assert(value_cmp_si(bernoulli_coef->num->p[6], 1) == 0);
493 assert(value_cmp_si(bernoulli_coef->den->p[6], 42) == 0);
494 assert(value_cmp_si(faulhaber->poly[3]->p[0], 0) == 0);
495 assert(value_cmp_si(faulhaber->poly[3]->p[1], 0) == 0);
496 assert(value_cmp_si(faulhaber->poly[3]->p[2], 1) == 0);
497 assert(value_cmp_si(faulhaber->poly[3]->p[3], -2) == 0);
498 assert(value_cmp_si(faulhaber->poly[3]->p[4], 1) == 0);
499 assert(value_cmp_si(faulhaber->poly[3]->p[5], 4) == 0);
500
501 bernoulli = bernoulli_compute(6);
502 assert(value_cmp_si(bernoulli->poly[6]->p[0], 1) == 0);
503 assert(value_cmp_si(bernoulli->poly[6]->p[1], 0) == 0);
504 assert(value_cmp_si(bernoulli->poly[6]->p[2], -21) == 0);
505 assert(value_cmp_si(bernoulli->poly[6]->p[3], 0) == 0);
506 assert(value_cmp_si(bernoulli->poly[6]->p[4], 105) == 0);
507 assert(value_cmp_si(bernoulli->poly[6]->p[5], -126) == 0);
508 assert(value_cmp_si(bernoulli->poly[6]->p[6], 42) == 0);
509 assert(value_cmp_si(bernoulli->poly[6]->p[7], 42) == 0);
510
511 unsigned nvar, nparam;
512 const char **all_vars;
513 evalue *base, *sum1, *sum2;
514 base = evalue_read_from_str("(1 * n + 1)", NULL, &all_vars, &nvar, &nparam,
515 options->MaxRays);
516
517 sum1 = evalue_polynomial(faulhaber->poly[3], base);
518 Free_ParamNames(all_vars, nvar+nparam);
519
520 sum2 = evalue_read_from_str("(1/4 * n^4 + 1/2 * n^3 + 1/4 * n^2)",
521 NULL, &all_vars, &nvar, &nparam,
522 options->MaxRays);
523 Free_ParamNames(all_vars, nvar+nparam);
524 assert(eequal(sum1, sum2));
525 evalue_free(base);
526 evalue_free(sum1);
527 evalue_free(sum2);
528 return 0;
529 }
530
531 int test_bernoulli_sum(struct barvinok_options *options)
532 {
533 int summation = options->summation;
534 options->summation = BV_SUM_BERNOULLI;
535
536 unsigned nvar, nparam;
537 const char **all_vars;
538 evalue *e, *sum1, *sum2;
539 e = evalue_read_from_str("i + -1 >= 0\n -i + n >= 0\n\n 1 + (-1 *i) + i^2",
540 "i", &all_vars, &nvar, &nparam,
541 options->MaxRays);
542 Free_ParamNames(all_vars, nvar+nparam);
543
544 sum1 = barvinok_summate(e, 1, options);
545 sum2 = evalue_read_from_str("n -1 >= 0\n\n (1/3 * n^3 + 2/3 * n)",
546 NULL, &all_vars, &nvar, &nparam,
547 options->MaxRays);
548 Free_ParamNames(all_vars, nvar+nparam);
549 evalue_negate(sum1);
550 eadd(sum2, sum1);
551 reduce_evalue(sum1);
552 assert(EVALUE_IS_ZERO(*sum1));
553 evalue_free(e);
554 evalue_free(sum1);
555
556 e = evalue_read_from_str("-i + -1 >= 0\n i + n >= 0\n\n 1 + i + i^2",
557 "i", &all_vars, &nvar, &nparam,
558 options->MaxRays);
559 Free_ParamNames(all_vars, nvar+nparam);
560 sum1 = barvinok_summate(e, 1, options);
561 evalue_negate(sum1);
562 eadd(sum2, sum1);
563 reduce_evalue(sum1);
564 assert(EVALUE_IS_ZERO(*sum1));
565 evalue_free(e);
566 evalue_free(sum1);
567
568 evalue_free(sum2);
569
570 e = evalue_read_from_str("i + 4 >= 0\n -i + n >= 0\n\n i",
571 "i", &all_vars, &nvar, &nparam,
572 options->MaxRays);
573 Free_ParamNames(all_vars, nvar+nparam);
574 sum1 = barvinok_summate(e, 1, options);
575 sum2 = evalue_read_from_str("n + 0 >= 0\n\n (1/2 * n^2 + 1/2 * n + (-10))\n"
576 "n + 4 >= 0\n -n -1 >= 0\n\n (1/2 * n^2 + 1/2 * n + (-10))",
577 NULL, &all_vars, &nvar, &nparam,
578 options->MaxRays);
579 Free_ParamNames(all_vars, nvar+nparam);
580 evalue_negate(sum1);
581 eadd(sum2, sum1);
582 reduce_evalue(sum1);
583 assert(EVALUE_IS_ZERO(*sum1));
584 evalue_free(e);
585 evalue_free(sum1);
586 evalue_free(sum2);
587
588 e = evalue_read_from_str("i -5 >= 0\n -i + n >= 0\n j -1 >= 0\n i -j >= 0\n"
589 "k -1 >= 0\n j -k >= 0\n\n1",
590 "i,j,k", &all_vars, &nvar, &nparam,
591 options->MaxRays);
592 Free_ParamNames(all_vars, nvar+nparam);
593 sum1 = barvinok_summate(e, 3, options);
594 sum2 = evalue_read_from_str("n -5 >= 0\n\n"
595 "1/6 * n^3 + 1/2 * n^2 + 1/3 * n + -20",
596 NULL, &all_vars, &nvar, &nparam,
597 options->MaxRays);
598 Free_ParamNames(all_vars, nvar+nparam);
599 evalue_negate(sum1);
600 eadd(sum2, sum1);
601 reduce_evalue(sum1);
602 assert(EVALUE_IS_ZERO(*sum1));
603 evalue_free(e);
604 evalue_free(sum1);
605 evalue_free(sum2);
606
607 options->summation = summation;
608 return 0;
609 }
610
611 int test_hilbert(struct barvinok_options *options)
612 {
613 #ifdef USE_ZSOLVE
614 Matrix *M = matrix_read_from_str(
615 "2 4\n"
616 " 1 4 -3 0 \n"
617 " 1 3 2 0 \n");
618 Polyhedron *P = Constraints2Polyhedron(M, options->MaxRays);
619 Matrix_Free(M);
620
621 M = Cone_Hilbert_Basis(P, options->MaxRays);
622 assert(M->NbRows == 5);
623 assert(M->NbColumns == 3);
624 Matrix_Free(M);
625
626 M = Cone_Integer_Hull(P, NULL, 0, options);
627 assert(M->NbRows == 4);
628 assert(M->NbColumns == 3);
629 Matrix_Free(M);
630
631 Polyhedron_Free(P);
632 #endif
633 return 0;
634 }
635
636 int test_ilp(struct barvinok_options *options)
637 {
638 Matrix *M = matrix_read_from_str(
639 "2 4\n"
640 " 1 4 -3 0 \n"
641 " 1 3 2 0 \n");
642 Polyhedron *P = Constraints2Polyhedron(M, options->MaxRays);
643 Matrix_Free(M);
644 Vector *obj = Vector_Alloc(2);
645 value_set_si(obj->p[0], 7);
646 value_set_si(obj->p[1], -1);
647 Value min, max;
648 value_init(min);
649 value_init(max);
650
651 value_set_si(min, 1);
652 value_set_si(max, 17);
653 Vector *opt = Polyhedron_Integer_Minimum(P, obj->p, min, max,
654 NULL, 0, options);
655 assert(opt);
656 assert(value_cmp_si(opt->p[0], 1) == 0);
657 assert(value_cmp_si(opt->p[1], 1) == 0);
658 assert(value_cmp_si(opt->p[2], 1) == 0);
659 Vector_Free(opt);
660
661 value_clear(min);
662 value_clear(max);
663 Vector_Free(obj);
664 Polyhedron_Free(P);
665 return 0;
666 }
667
668 int test_hull(struct barvinok_options *options)
669 {
670 Matrix *M = matrix_read_from_str(
671 "4 4\n"
672 "1 32 -20 7\n"
673 "1 8 -44 187\n"
674 "1 -48 -4 285\n"
675 "1 8 68 -199\n");
676 Polyhedron *P = Constraints2Polyhedron(M, options->MaxRays);
677 Matrix_Free(M);
678
679 Matrix *hull = Polyhedron_Integer_Hull(P, options);
680 Polyhedron_Free(P);
681 assert(hull->NbRows == 4);
682 M = Matrix_Alloc(hull->NbRows, 1+hull->NbColumns);
683 for (int i = 0; i < hull->NbRows; ++i) {
684 value_set_si(M->p[i][0], 1);
685 Vector_Copy(hull->p[i], M->p[i]+1, hull->NbColumns);
686 }
687 Matrix_Free(hull);
688 Polyhedron *H = Constraints2Polyhedron(M, options->MaxRays);
689 Matrix_Free(M);
690
691 M = matrix_read_from_str(
692 "4 4\n"
693 "1 2 3 1 \n"
694 "1 3 4 1 \n"
695 "1 5 3 1 \n"
696 "1 5 5 1 \n");
697 P = Constraints2Polyhedron(M, options->MaxRays);
698 Matrix_Free(M);
699 assert(PolyhedronIncludes(P, H) && PolyhedronIncludes(H, P));
700 Polyhedron_Free(P);
701 Polyhedron_Free(H);
702
703 M = matrix_read_from_str(
704 "3 4\n"
705 "1 2 6 -3 \n"
706 "1 2 -6 3 \n"
707 "1 -2 0 3 \n");
708 P = Constraints2Polyhedron(M, options->MaxRays);
709 Matrix_Free(M);
710 assert(!emptyQ(P));
711 hull = Polyhedron_Integer_Hull(P, options);
712 Polyhedron_Free(P);
713 assert(hull->NbRows == 0);
714 Matrix_Free(hull);
715 return 0;
716 }
717
718 static int test_laurent(struct barvinok_options *options)
719 {
720 unsigned nvar, nparam;
721 const char **all_vars;
722 evalue *e, *sum, *res;
723
724 e = evalue_read_from_str(" x1 >= 0\n"
725 " x2 >= 0\n"
726 " -x1 -x2 + 2 >= 0\n"
727 "\n"
728 "(N + M * x2)\n",
729 "x1,x2", &all_vars, &nvar, &nparam,
730 options->MaxRays);
731 Free_ParamNames(all_vars, nvar+nparam);
732
733 int summation = options->summation;
734 options->summation = BV_SUM_LAURENT;
735 sum = barvinok_summate(e, nvar, options);
736 options->summation = summation;
737
738 res = evalue_read_from_str("(6 * N + 4 * M)",
739 "", &all_vars, &nvar, &nparam,
740 options->MaxRays);
741 Free_ParamNames(all_vars, nvar+nparam);
742
743 assert(value_zero_p(sum->d));
744 assert(sum->x.p->type == partition);
745 assert(sum->x.p->size == 2);
746
747 assert(eequal(res, &sum->x.p->arr[1]));
748
749 evalue_free(e);
750 evalue_free(sum);
751 evalue_free(res);
752 return 0;
753 }
754
755 /* Check that Polyhedron_Reduced_Basis produces a result
756 * of the expected dimensions (without crashing).
757 */
758 static int test_basis_reduction(struct barvinok_options *options)
759 {
760 Matrix *M;
761 Polyhedron *P;
762
763 M = matrix_read_from_str(
764 "4 4\n"
765 "1 1 0 0 \n"
766 "1 0 1 0 \n"
767 "1 -1 0 1 \n"
768 "1 0 -1 1 \n");
769 P = Constraints2Polyhedron(M, options->MaxRays);
770 Matrix_Free(M);
771
772 M = Polyhedron_Reduced_Basis(P, options);
773
774 assert(M);
775 assert(M->NbRows == 2);
776 assert(M->NbColumns == 2);
777
778 Polyhedron_Free(P);
779 Matrix_Free(M);
780
781 return 0;
782 }
783
784 int main(int argc, char **argv)
785 {
786 struct barvinok_options *options = barvinok_options_new_with_defaults();
787 test_equalities(options);
788 test_evalue_read(options);
789 test_eadd(options);
790 test_evalue(options);
791 test_substitute(options);
792 test_specialization(options);
793 test_lattice_points(options);
794 test_icounter(options);
795 test_infinite_counter(options);
796 test_series(options);
797 test_todd(options);
798 test_bernoulli(options);
799 test_bernoulli_sum(options);
800 test_hilbert(options);
801 test_ilp(options);
802 test_hull(options);
803 test_laurent(options);
804 test_basis_reduction(options);
805 barvinok_options_free(options);
806
807 return EXIT_SUCCESS;
808 }
lattice point enumeration library