blob: a857653037568b2f0d0c3f1f53b607c60b87dc42 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
/********************* */
/*! \file tableau.cpp
** \verbatim
** Original author: taking
** Major contributors: none
** Minor contributors (to current version): none
** This file is part of the CVC4 prototype.
** Copyright (c) 2009, 2010 The Analysis of Computer Systems Group (ACSys)
** Courant Institute of Mathematical Sciences
** New York University
** See the file COPYING in the top-level source directory for licensing
** information.\endverbatim
**
** \brief [[ Add one-line brief description here ]]
**
** [[ Add lengthier description here ]]
** \todo document this file
**/
#include "theory/arith/tableau.h"
using namespace CVC4;
using namespace CVC4::theory;
using namespace CVC4::theory::arith;
using namespace std;
Tableau::~Tableau(){
while(!d_basicVariables.empty()){
ArithVar curr = *(d_basicVariables.begin());
ReducedRowVector* vec = removeRow(curr);
delete vec;
}
}
void Tableau::addRow(ArithVar basicVar,
const std::vector<Rational>& coeffs,
const std::vector<ArithVar>& variables){
Assert(coeffs.size() == variables.size());
//The new basic variable cannot already be a basic variable
Assert(!d_basicVariables.isMember(basicVar));
d_basicVariables.add(basicVar);
ReducedRowVector* row_current = new ReducedRowVector(basicVar,variables, coeffs,d_rowCount, d_columnMatrix);
d_rowsTable[basicVar] = row_current;
//A variable in the row may have been made non-basic already.
//If this is the case we fake pivoting this variable
vector<ArithVar>::const_iterator varsIter = variables.begin();
vector<ArithVar>::const_iterator varsEnd = variables.end();
for( ; varsIter != varsEnd; ++varsIter){
ArithVar var = *varsIter;
if(d_basicVariables.isMember(var)){
ReducedRowVector& row_var = lookup(var);
row_current->substitute(row_var);
}
}
}
ReducedRowVector* Tableau::removeRow(ArithVar basic){
Assert(d_basicVariables.isMember(basic));
ReducedRowVector* row = d_rowsTable[basic];
d_basicVariables.remove(basic);
d_rowsTable[basic] = NULL;
return row;
}
void Tableau::pivot(ArithVar x_r, ArithVar x_s){
Assert(d_basicVariables.isMember(x_r));
Assert(!d_basicVariables.isMember(x_s));
Debug("tableau") << "Tableau::pivot(" << x_r <<", " <<x_s <<")" << endl;
ReducedRowVector* row_s = d_rowsTable[x_r];
Assert(row_s != NULL);
Assert(row_s->has(x_s));
//Swap x_r and x_s in d_activeRows
d_rowsTable[x_s] = row_s;
d_rowsTable[x_r] = NULL;
d_basicVariables.remove(x_r);
d_basicVariables.add(x_s);
row_s->pivot(x_s);
ArithVarSet::VarList copy(getColumn(x_s).getList());
vector<ArithVar>::iterator basicIter = copy.begin(), endIter = copy.end();
for(; basicIter != endIter; ++basicIter){
ArithVar basic = *basicIter;
if(basic == x_s) continue;
ReducedRowVector& row_k = lookup(basic);
Assert(row_k.has(x_s));
row_k.substitute(*row_s);
}
Assert(getColumn(x_s).size() == 1);
Assert(getRowCount(x_s) == 1);
}
void Tableau::printTableau(){
Debug("tableau") << "Tableau::d_activeRows" << endl;
typedef RowsTable::iterator table_iter;
for(table_iter rowIter = d_rowsTable.begin(), end = d_rowsTable.end();
rowIter != end; ++rowIter){
ReducedRowVector* row_k = *rowIter;
if(row_k != NULL){
row_k->printRow();
}
}
}
|
