From b8ad912dd71a50b144e6cafb4bfa7b8dcd4e8faf Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Tue, 25 Mar 2008 16:48:02 +0100 Subject: [PATCH] implement Bernoulli_sum as conversion from unweighted to weighted counting --- barvinok.cc | 41 +++++++++++++++++++++++++++++++++++++++-- bernoulli.c | 28 ---------------------------- bernoulli.h | 2 -- 3 files changed, 39 insertions(+), 32 deletions(-) diff --git a/barvinok.cc b/barvinok.cc index 7336639..e18e06c 100644 --- a/barvinok.cc +++ b/barvinok.cc @@ -40,6 +40,10 @@ using std::ostringstream; #define ALLOC(t,p) p = (t*)malloc(sizeof(*p)) +static evalue *barvinok_summate_unweighted(Polyhedron *P, Polyhedron *C, + evalue *(*summate)(evalue *, unsigned, struct barvinok_options *options), + struct barvinok_options *options); + class dpoly_n { public: Matrix *coeff; @@ -451,7 +455,8 @@ void barvinok_count_with_options(Polyhedron *P, Value* result, } if (options->summation == BV_SUM_BERNOULLI) { Polyhedron *C = Universe_Polyhedron(0); - evalue *sum = Bernoulli_sum(P, C, options); + evalue *sum = barvinok_summate_unweighted(P, C, Bernoulli_sum_evalue, + options); Polyhedron_Free(C); evalue2value(sum, result); evalue_free(sum); @@ -1438,7 +1443,7 @@ evalue* barvinok_enumerate_with_options(Polyhedron *P, Polyhedron* C, if (options->approximation_method == BV_APPROX_BERNOULLI || options->summation == BV_SUM_BERNOULLI) - eres = Bernoulli_sum(P, C, options); + eres = barvinok_summate_unweighted(P, C, Bernoulli_sum_evalue, options); else eres = enumerate(P, C, options); Domain_Free(C); @@ -1570,3 +1575,35 @@ evalue *barvinok_summate(evalue *e, int nvar, struct barvinok_options *options) else return evalue_sum(e, nvar, options->MaxRays); } + +/* Turn unweighted counting problem into "weighted" counting problem + * with weight equal to 1 and call "summate" on this weighted problem. + */ +static evalue *barvinok_summate_unweighted(Polyhedron *P, Polyhedron *C, + evalue *(*summate)(evalue *, unsigned, struct barvinok_options *options), + struct barvinok_options *options) +{ + Polyhedron *CA, *D; + evalue e; + evalue *sum; + + if (emptyQ(P) || emptyQ(C)) + return evalue_zero(); + + CA = align_context(C, P->Dimension, options->MaxRays); + D = DomainIntersection(P, CA, options->MaxRays); + Domain_Free(CA); + + if (emptyQ(D)) { + Domain_Free(D); + return evalue_zero(); + } + + value_init(e.d); + e.x.p = new_enode(partition, 2, P->Dimension); + EVALUE_SET_DOMAIN(e.x.p->arr[0], D); + evalue_set_si(&e.x.p->arr[1], 1, 1); + sum = summate(&e, P->Dimension - C->Dimension, options); + free_evalue_refs(&e); + return sum; +} diff --git a/bernoulli.c b/bernoulli.c index f1ce68a..494e968 100644 --- a/bernoulli.c +++ b/bernoulli.c @@ -1080,31 +1080,3 @@ evalue *Bernoulli_sum_evalue(evalue *e, unsigned nvar, reduce_evalue(sum); return sum; } - -evalue *Bernoulli_sum(Polyhedron *P, Polyhedron *C, - struct barvinok_options *options) -{ - Polyhedron *CA, *D; - evalue e; - evalue *sum; - - if (emptyQ(P) || emptyQ(C)) - return evalue_zero(); - - CA = align_context(C, P->Dimension, options->MaxRays); - D = DomainIntersection(P, CA, options->MaxRays); - Domain_Free(CA); - - if (emptyQ(D)) { - Domain_Free(D); - return evalue_zero(); - } - - value_init(e.d); - e.x.p = new_enode(partition, 2, P->Dimension); - EVALUE_SET_DOMAIN(e.x.p->arr[0], D); - evalue_set_si(&e.x.p->arr[1], 1, 1); - sum = Bernoulli_sum_evalue(&e, P->Dimension - C->Dimension, options); - free_evalue_refs(&e); - return sum; -} diff --git a/bernoulli.h b/bernoulli.h index 6ff0d3f..bd53fb5 100644 --- a/bernoulli.h +++ b/bernoulli.h @@ -38,8 +38,6 @@ struct poly_list *faulhaber_compute(int n); */ struct poly_list *bernoulli_compute(int n); -evalue *Bernoulli_sum(Polyhedron *P, Polyhedron *C, - struct barvinok_options *options); evalue *Bernoulli_sum_evalue(evalue *e, unsigned nvar, struct barvinok_options *options); -- 2.11.4.GIT