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