blob: c22c21a4608d75c7c04b20370260cea1202a7b3b (
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;
void Tableau::addRow(ArithVar basicVar,
const std::vector<Rational>& coeffs,
const std::vector<ArithVar>& variables){
Assert(coeffs.size() == variables.size());
Assert(d_basicManager.isMember(basicVar));
//The new basic variable cannot already be a basic variable
Assert(!isActiveBasicVariable(basicVar));
d_activeBasicVars.insert(basicVar);
ReducedRowVector* row_current = new ReducedRowVector(basicVar,variables, coeffs);
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<Rational>::const_iterator coeffsIter = coeffs.begin();
vector<Rational>::const_iterator coeffsEnd = coeffs.end();
vector<ArithVar>::const_iterator varsIter = variables.begin();
for( ; coeffsIter != coeffsEnd; ++coeffsIter, ++ varsIter){
ArithVar var = *varsIter;
if(d_basicManager.isMember(var)){
if(!isActiveBasicVariable(var)){
reinjectBasic(var);
}
Assert(isActiveBasicVariable(var));
ReducedRowVector* row_var = lookup(var);
row_current->substitute(*row_var);
}
}
}
void Tableau::pivot(ArithVar x_r, ArithVar x_s){
Assert(d_basicManager.isMember(x_r));
Assert(!d_basicManager.isMember(x_s));
ReducedRowVector* row_s = lookup(x_r);
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_activeBasicVars.erase(x_r);
d_basicManager.remove(x_r);
d_activeBasicVars.insert(x_s);
d_basicManager.add(x_s);
row_s->pivot(x_s);
for(ArithVarSet::iterator basicIter = begin(), endIter = end();
basicIter != endIter; ++basicIter){
ArithVar basic = *basicIter;
if(basic == x_s) continue;
ReducedRowVector* row_k = lookup(basic);
if(row_k->has(x_s)){
d_activityMonitor[basic] += 30;
row_k->substitute(*row_s);
}
}
}
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();
}
}
}
void Tableau::updateRow(ReducedRowVector* row){
ArithVar basic = row->basic();
for(ReducedRowVector::NonZeroIterator i=row->beginNonZero(), endIter = row->endNonZero(); i != endIter; ){
ArithVar var = i->first;
++i;
if(var != basic && d_basicManager.isMember(var)){
ReducedRowVector* row_var = isActiveBasicVariable(var) ? lookup(var) : lookupEjected(var);
Assert(row_var != row);
row->substitute(*row_var);
i = row->beginNonZero();
endIter = row->endNonZero();
}
}
}
|
