2 #include <barvinok/barvinok.h>
3 #include <barvinok/util.h>
4 #include "genfun_constructor.h"
5 #include "remove_equalities.h"
7 /* Check whether all rays point in the positive directions
10 static bool Polyhedron_has_positive_rays(Polyhedron
*P
, unsigned nparam
)
13 for (r
= 0; r
< P
->NbRays
; ++r
)
14 if (value_zero_p(P
->Ray
[r
][P
->Dimension
+1])) {
16 for (i
= P
->Dimension
- nparam
; i
< P
->Dimension
; ++i
)
17 if (value_neg_p(P
->Ray
[r
][i
+1]))
24 * remove equalities that require a "compression" of the parameters
26 static Polyhedron
*remove_more_equalities(Polyhedron
*P
, unsigned nparam
,
27 Matrix
**CP
, unsigned MaxRays
)
30 remove_all_equalities(&P
, NULL
, CP
, NULL
, nparam
, MaxRays
);
37 static gen_fun
*series(Polyhedron
*P
, unsigned nparam
, barvinok_options
*options
)
44 return new gen_fun(Empty_Polyhedron(nparam
));
47 assert(!Polyhedron_is_unbounded(P
, nparam
, options
->MaxRays
));
48 assert(P
->NbBid
== 0);
49 assert(Polyhedron_has_revlex_positive_rays(P
, nparam
));
51 P
= remove_more_equalities(P
, nparam
, &CP
, options
->MaxRays
);
52 assert(emptyQ2(P
) || P
->NbEq
== 0);
54 nparam
= CP
->NbColumns
-1;
59 barvinok_count_with_options(P
, &c
, options
);
63 POL_ENSURE_VERTICES(P
);
65 gf
= series(Polyhedron_Copy(P
), nparam
, options
);
68 red
= gf_base::create(Polyhedron_Project(P
, nparam
),
69 P
->Dimension
, nparam
, options
);
70 red
->start_gf(P
, options
);
83 gen_fun
* barvinok_series_with_options(Polyhedron
*P
, Polyhedron
* C
,
84 barvinok_options
*options
)
87 unsigned nparam
= C
->Dimension
;
90 CA
= align_context(C
, P
->Dimension
, options
->MaxRays
);
91 P
= DomainIntersection(P
, CA
, options
->MaxRays
);
94 gf
= series(P
, nparam
, options
);
99 gen_fun
* barvinok_series(Polyhedron
*P
, Polyhedron
* C
, unsigned MaxRays
)
102 barvinok_options
*options
= barvinok_options_new_with_defaults();
103 options
->MaxRays
= MaxRays
;
104 gf
= barvinok_series_with_options(P
, C
, options
);
105 barvinok_options_free(options
);
109 static Polyhedron
*skew_into_positive_orthant(Polyhedron
*D
, unsigned nparam
,
115 for (Polyhedron
*P
= D
; P
; P
= P
->next
) {
116 POL_ENSURE_VERTICES(P
);
117 assert(!Polyhedron_is_unbounded(P
, nparam
, MaxRays
));
118 assert(P
->NbBid
== 0);
119 assert(Polyhedron_has_positive_rays(P
, nparam
));
121 for (int r
= 0; r
< P
->NbRays
; ++r
) {
122 if (value_notzero_p(P
->Ray
[r
][P
->Dimension
+1]))
124 for (int i
= 0; i
< nparam
; ++i
) {
126 if (value_posz_p(P
->Ray
[r
][i
+1]))
129 M
= Matrix_Alloc(D
->Dimension
+1, D
->Dimension
+1);
130 for (int i
= 0; i
< D
->Dimension
+1; ++i
)
131 value_set_si(M
->p
[i
][i
], 1);
133 Inner_Product(P
->Ray
[r
]+1, M
->p
[i
], D
->Dimension
+1, &tmp
);
134 if (value_posz_p(tmp
))
137 for (j
= P
->Dimension
- nparam
; j
< P
->Dimension
; ++j
)
138 if (value_pos_p(P
->Ray
[r
][j
+1]))
140 assert(j
< P
->Dimension
);
141 value_pdivision(tmp
, P
->Ray
[r
][j
+1], P
->Ray
[r
][i
+1]);
142 value_subtract(M
->p
[i
][j
], M
->p
[i
][j
], tmp
);
148 D
= DomainImage(D
, M
, MaxRays
);
154 gen_fun
* barvinok_enumerate_union_series_with_options(Polyhedron
*D
, Polyhedron
* C
,
155 barvinok_options
*options
)
157 Polyhedron
*conv
, *D2
;
159 gen_fun
*gf
= NULL
, *gf2
;
160 unsigned nparam
= C
->Dimension
;
165 CA
= align_context(C
, D
->Dimension
, options
->MaxRays
);
166 D
= DomainIntersection(D
, CA
, options
->MaxRays
);
169 D2
= skew_into_positive_orthant(D
, nparam
, options
->MaxRays
);
170 for (Polyhedron
*P
= D2
; P
; P
= P
->next
) {
171 assert(P
->Dimension
== D2
->Dimension
);
174 P_gf
= series(Polyhedron_Copy(P
), P
->Dimension
, options
);
178 gf
->add_union(P_gf
, options
);
182 /* we actually only need the convex union of the parameter space
183 * but the reducer classes currently expect a polyhedron in
186 Polyhedron_Free(gf
->context
);
187 gf
->context
= DomainConvex(D2
, options
->MaxRays
);
189 gf2
= gf
->summate(D2
->Dimension
- nparam
, options
);
198 gen_fun
* barvinok_enumerate_union_series(Polyhedron
*D
, Polyhedron
* C
,
202 barvinok_options
*options
= barvinok_options_new_with_defaults();
203 options
->MaxRays
= MaxRays
;
204 gf
= barvinok_enumerate_union_series_with_options(D
, C
, options
);
205 barvinok_options_free(options
);