From 728496985428e3db5f136acebf5118cbb934bfca Mon Sep 17 00:00:00 2001
From: Sven Verdoolaege <skimo@kotnet.org>
Date: Thu, 8 Nov 2007 13:43:36 +0100
Subject: [PATCH] Polyhedron_Sample: be satisfied with a reasonable choice for
 the first direction

---
 barvinok/options.h      |  2 ++
 basis_reduction_templ.c | 24 +++++++++++++++++++++++-
 options.c               |  2 ++
 sample.c                |  6 +++++-
 4 files changed, 32 insertions(+), 2 deletions(-)

diff --git a/barvinok/options.h b/barvinok/options.h
index 5ddead0..a5dfb15 100644
--- a/barvinok/options.h
+++ b/barvinok/options.h
@@ -101,6 +101,8 @@ struct barvinok_options {
     int		verbose;
 
     int		print_stats;
+
+    int		gbr_only_first;
 };
 
 struct barvinok_options *barvinok_options_new_with_defaults();
diff --git a/basis_reduction_templ.c b/basis_reduction_templ.c
index 201f2ae..84e9cd9 100644
--- a/basis_reduction_templ.c
+++ b/basis_reduction_templ.c
@@ -15,6 +15,13 @@ static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
  * "An Implementation of the Generalized Basis Reduction Algorithm
  *  for Integer Programming" of Cook el al. to compute a reduced basis.
  * We use \epsilon = 1/4.
+ *
+ * If options->gbr_only_first is set, the user is only interested
+ * in the first direction.  In this case we stop the basis reduction when
+ *	- the width in the first direction becomes smaller than 2
+ * or
+ *	- we have moved forward all the way to the last direction
+ *	  and then back again all the way to the first direction.
  */
 Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
 				 struct barvinok_options *options)
@@ -34,6 +41,8 @@ Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
     int use_saved = 0;
     Value mu[2];
     GBR_type mu_F[2];
+    GBR_type two;
+    int end = 0;
 
     if (P->Dimension == 1)
 	return basis;
@@ -62,6 +71,9 @@ Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
     GBR_init(F_saved);
     GBR_init(mu_F[0]);
     GBR_init(mu_F[1]);
+    GBR_init(two);
+
+    GBR_set_ui(two, 2);
 
     lp = GBR_lp_init(P);
 
@@ -135,15 +147,24 @@ Matrix *Polyhedron_Reduced_Basis(Polyhedron *P,
 	GBR_set_ui(mu_F[1], 3);
 	GBR_mul(mu_F[1], mu_F[1], F_old);
 	if (GBR_lt(mu_F[0], mu_F[1])) {
+	    if (i == dim-2)
+		end = 1;
 	    Vector_Exchange(basis->p[i], basis->p[i+1], dim);
 	    if (i > 0) {
 		use_saved = 1;
 		GBR_set(F_saved, F_new);
 		GBR_lp_del_row(lp);
 		--i;
-	    } else
+	    } else {
 		GBR_set(F[0], F_new);
+		if (options->gbr_only_first && end)
+		    break;
+		if (options->gbr_only_first && GBR_lt(F[0], two))
+		    break;
+	    }
 	} else {
+	    if (options->gbr_only_first && i == 0 && end)
+		break;
 	    GBR_lp_add_row(lp, basis->p[i], dim);
 	    ++i;
 	}
@@ -174,6 +195,7 @@ unbounded:
     GBR_clear(F_saved);
     GBR_clear(mu_F[0]);
     GBR_clear(mu_F[1]);
+    GBR_clear(two);
 
     GBR_lp_delete(lp);
 
diff --git a/options.c b/options.c
index ce2957b..1dd355b 100644
--- a/options.c
+++ b/options.c
@@ -99,6 +99,8 @@ struct barvinok_options *barvinok_options_new_with_defaults()
 
     options->print_stats = 0;
 
+    options->gbr_only_first = 0;
+
     return options;
 }
 
diff --git a/sample.c b/sample.c
index 461289f..4bdf241 100644
--- a/sample.c
+++ b/sample.c
@@ -370,7 +370,11 @@ unbounded:
 	Q = P;
     } else {
 	Matrix *M, *T;
-	Matrix *basis = Polyhedron_Reduced_Basis(P, options);
+	Matrix *basis;
+
+	options->gbr_only_first = 1;
+	basis = Polyhedron_Reduced_Basis(P, options);
+	options->gbr_only_first = 0;
 
 	if (!basis)
 	    goto unbounded;
-- 
2.11.4.GIT