From 0603c0fd3e15ff738205cb09a2337bb64e52682b Mon Sep 17 00:00:00 2001
From: skimo <skimo>
Date: Wed, 6 Oct 2004 11:59:53 +0000
Subject: [PATCH] small tool for removing redundant equalities

---
 Makefile.am                   |  2 +-
 remove_redundant_equalities.c | 53 +++++++++++++++++++++++++++++++++++++++++++
 util.c                        | 19 ++++++++++++----
 3 files changed, 69 insertions(+), 5 deletions(-)
 create mode 100644 remove_redundant_equalities.c

diff --git a/Makefile.am b/Makefile.am
index e44313b..c059c6c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -1,7 +1,7 @@
 lib_LTLIBRARIES = libbarvinok.la
 noinst_PROGRAMS = test barvinok_count randomtest barvinok_enumerate \
 		  verif_ehrhart barvinok_enumerate_e verif_ehrhart_e \
-		  barvinok_series \
+		  barvinok_series remove_redundant_equalities \
 		  @bv_extra_programs@
 EXTRA_PROGRAMS = piptest
 pkginclude_HEADERS = barvinok.h util.h ev_operations.h
diff --git a/remove_redundant_equalities.c b/remove_redundant_equalities.c
new file mode 100644
index 0000000..5712fa3
--- /dev/null
+++ b/remove_redundant_equalities.c
@@ -0,0 +1,53 @@
+#include <polylib/polylibgmp.h>
+#include <ev_operations.h>
+#include <util.h>
+#include "config.h"
+
+#ifdef HAVE_GROWING_CHERNIKOVA
+#define MAXRAYS    0
+#else
+#define MAXRAYS  600
+#endif
+
+void dump_polytope(Polyhedron *P)
+{
+    int i, j;
+    unsigned nr, nc;
+
+    fprintf(stdout, "%d %d\n", nr=P->NbConstraints, nc=P->Dimension+2);
+    for (i=0; i < nr; i++) {
+	for (j=0; j < nc; j++) {
+	    value_print(stdout," "P_VALUE_FMT" ", P->Constraint[i][j]);
+	}
+	fprintf(stdout, "\n");
+    }
+}
+
+int main(int argc, char **argv)
+{
+    Polyhedron *A, *C;
+    Matrix *M;
+    Enumeration *en;
+    char **param_name;
+    int i;
+
+    M = Matrix_Read();
+    A = Constraints2Polyhedron(M, MAXRAYS);
+    Matrix_Free(M);
+    M = Matrix_Read();
+    C = Constraints2Polyhedron(M, MAXRAYS);
+    Matrix_Free(M);
+    param_name = Read_ParamNames(stdin, C->Dimension);
+    A = remove_equalities_p(A, A->Dimension-C->Dimension, 0);
+    dump_polytope(A);
+    puts("");
+    dump_polytope(C);
+    puts("");
+    for (i = 0; i < C->Dimension; ++i)
+	printf("%s ", param_name[i]);
+    puts("");
+    Free_ParamNames(param_name, C->Dimension);
+    Polyhedron_Free(A);
+    Polyhedron_Free(C);
+    return 0;
+}
diff --git a/util.c b/util.c
index cc0478a..073053d 100644
--- a/util.c
+++ b/util.c
@@ -447,6 +447,9 @@ Polyhedron *remove_equalities(Polyhedron *P)
  * factor is NbEq x (nparam+2) matrix, containing stride constraints
  * on the parameters; column nparam is the constant;
  * column nparam+1 is the stride
+ *
+ * if factor is NULL, only remove equalities that don't affect
+ * the number of points
  */
 Polyhedron *remove_equalities_p(Polyhedron *P, unsigned nvar, Matrix **factor)
 {
@@ -458,9 +461,11 @@ Polyhedron *remove_equalities_p(Polyhedron *P, unsigned nvar, Matrix **factor)
     int i, j, skip;
 
     value_init(g);
-    f = Matrix_Alloc(p->NbEq, dim-nvar+2);
+    if (factor) {
+	f = Matrix_Alloc(p->NbEq, dim-nvar+2);
+	*factor = f;
+    }
     j = 0;
-    *factor = f;
     skip = 0;
     while (nvar > 0 && p->NbEq - skip > 0) {
 	assert(dim > 0);
@@ -472,10 +477,16 @@ Polyhedron *remove_equalities_p(Polyhedron *P, unsigned nvar, Matrix **factor)
 	    break;
 
 	Vector_Gcd(p->Constraint[skip]+1, dim+1, &g);
+	if (!factor && value_notone_p(g) && value_notmone_p(g)) {
+	    ++skip;
+	    continue;
+	}
 	Vector_AntiScale(p->Constraint[skip]+1, p->Constraint[skip]+1, g, dim+1);
 	Vector_Gcd(p->Constraint[skip]+1, nvar, &g);
-	Vector_Copy(p->Constraint[skip]+1+nvar, f->p[j], dim-nvar+1);
-	value_assign(f->p[j][dim-nvar+1], g);
+	if (factor) {
+	    Vector_Copy(p->Constraint[skip]+1+nvar, f->p[j], dim-nvar+1);
+	    value_assign(f->p[j][dim-nvar+1], g);
+	}
 	v = Vector_Alloc(dim);
 	Vector_AntiScale(p->Constraint[skip]+1, v->p, g, nvar);
 	Vector_Set(v->p+nvar, 0, dim-nvar);
-- 
2.11.4.GIT