From aa817a3eb970eaf50e2775686b3da900d1afe7d1 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 15 Sep 2007 17:54:43 +0200 Subject: [PATCH] topcom: fix heuristic for selecting rows to use as non-negativity constraints If one of the rows is already (the negative of) a unit vector, we put it in the right position. We then check the row again, since we may not have checked the row that was on that right position. However, we also did this when this row had already been checked, leading to the possibility that a pair of rows would endlessly be swapped. We now only reconsider the row at the current position if the row that was moved there has not already been checked. --- topcom.c | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/topcom.c b/topcom.c index badfcce..b49bd4a 100644 --- a/topcom.c +++ b/topcom.c @@ -415,6 +415,13 @@ static void SwapColumns(Value **V, int n, int i, int j) value_swap(V[r][i], V[r][j]); } +static int is_unit_row(Value *row, int pos, int len) +{ + if (!value_one_p(row[pos]) && !value_mone_p(row[pos])) + return 0; + return First_Non_Zero(row+pos+1, len-(pos+1)) == -1; +} + /* C is assumed to be the "true" context, i.e., it has been intersected * with the projection of P onto the parameter space. * Furthermore, P and C are assumed to be full-dimensional. @@ -442,12 +449,11 @@ Param_Polyhedron *TC_P2PP(Polyhedron *P, Polyhedron *C, index = First_Non_Zero(P->Constraint[d]+1, nvar); if (index != -1) { if (index != d && - (value_one_p(P->Constraint[d][1+index]) || - value_mone_p(P->Constraint[d][1+index])) && - First_Non_Zero(P->Constraint[d]+1+index+1, nvar-(index+1)) == -1) { + is_unit_row(P->Constraint[d]+1, index, nvar)) { Vector_Exchange(P->Constraint[d], P->Constraint[index], P->Dimension+2); - --d; + if (index > d) + --d; } continue; } -- 2.11.4.GIT