## Revision 8b911557

 ID 8b91155720a5cfcd26b44d6e52b64f4de49d345d Parent 0d3d896c Child e702d896

Various fixes for heuristic

View differences:

src/sim/cheuristic.cc
27 27
#include "cheuristic.h"
28 28
#include "eventset.h"
29 29

30
#define MAX_IT 1000000
30
#define MAX_IT 100
31
#define EPSILON 1e-6
31 32

32 33
EventSet::iterator::iterator(const EventSet::iterator& b) :
33 34
index(index),
......
35 36
{
36 37
}
37 38

39
class Probability
40
{
41
private:
42
double invProb;
43
int ones;
44
#ifdef DEBUG
45
std::list<double> factors;
46
#endif
47

48
public:
49
Probability()
50
{
51
invProb=1;
52
ones=0;
53
}
54

55
operator double() const
56
{
57
if(ones>0)
58
{
59
return 1;
60
}
61
else
62
{
63
std::cout << invProb << std::endl;
64
assert(!isnan(invProb));
65
assert(invProb>=0 && invProb<=1+EPSILON);
66
return 1-invProb;
67
}
68
}
69

70
71
{
72
#ifdef DEBUG
73
assert(!isnan(factor));
74
assert(factor>=0 && factor <=1);
75
factors.push_back(factor);
76
//std::cout << this << "adding " << factor << std::endl;
77
#endif
78
if(factor==1)
79
{
80
ones++;
81
}
82
else
83
{
84
assert(invProb>=0);
85
double ips=invProb;
86
invProb*=(1-factor);
87
if(invProb<0) std::cout << ips << "*" << (1-factor) << "=" << invProb << std::endl;
88
assert(invProb>=0);
89
}
90
}
91

92
void removeFactor(const double factor)
93
{
94
#ifdef DEBUG
95
assert(!isnan(factor) && factor>=0 && factor <=1);
96
bool existed=false;
97
for(std::list<double>::iterator it=factors.begin();it!=factors.end();++it)
98
{
99
if(*it==factor)
100
{
101
factors.erase(it);
102
existed=true;
103
break;
104
}
105
}
106
assert(existed);
107
//std::cout << this << ":removing " << factor << std::endl;
108
#endif
109
if(factor==1)
110
{
111
ones--;
112
assert(ones>=0);
113
}
114
else
115
{
116
double ips=invProb;
117
invProb/=(1-factor);
118
if(invProb<0) std::cout << ips << "/" << (1-factor) << "=" << invProb << std::endl;
119
assert(invProb>=0);
120
}
121
}
122
};
123

38 124
class cNode
39 125
{
40 126
private:
......
52 138

53 139
double getProbability()
54 140
{
55
return pdf.getProbability(0);
141
double prob=pdf.getProbability(0);
142
assert(!isnan(prob));
143
assert(prob>=0);
144
assert(prob<=1);
145
return prob;
56 146
}
57 147

58 148
succList_t getSuccessors()
......
84 174
{
85 175
private:
86 176
// Lower and upper bounds for the causal violation probability:
87
double lowerBound;
88
double upperBound;
177
Probability lowerBound;
178
Probability upperBound;
89 179
typedef std::list<cNode*> nodeSet_t;
90 180
nodeSet_t bfsVisitList;
91 181

......
96 186
*/
97 187
cTree()
98 188
{
99
lowerBound=0;
100
upperBound=1;
101 189
}
102 190

103 191
~cTree()
......
108 196
}
109 197
}
110 198

199
double getLowerBound() const
200
{
201
return lowerBound;
202
}
203

204
double getUpperBound() const
205
{
206
return upperBound;
207
}
208

111 209
/**
112 210
* Adding a node into the tree.
113 211
* @param parent The parent node in the tree. If parent==NULL, the new node will
......
123 221
{
124 222
cNode* newNode=new cNode(evType,isConflicting,probabilityDistribution);
125 223
const double dangerProb=newNode->getProbability();
126
upperBound=1-(1-upperBound)*(1-dangerProb);
127
if(isConflicting) lowerBound=1-(1-lowerBound)*(1-dangerProb);
224
225
128 226
bfsVisitList.push_back(newNode);
129 227
}
130 228

229
bool checkBounds() const
230
{
231
if(isnan(lowerBound) || isnan(upperBound))
232
{
233
std::cout << "a bound is not a number! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
234
return false;
235
}
236
if(lowerBound<-EPSILON || lowerBound>1)
237
{
238
std::cout << "lower bound out of bounds! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
239
return false;
240
}
241
if(upperBound<-EPSILON || upperBound>1)
242
{
243
std::cout << "upper bound out of bounds! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
244
return false;
245
}
246
if(lowerBound-EPSILON>upperBound+EPSILON)
247
{
248
std::cout << "lower bound greater then upper bound! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
249
return false;
250
}
251
return true;
252
}
253

131 254
// Performing BFS and spanning the tree:
132 255
bool bfs(double threshold, int moduleId)
133 256
{
......
143 266
}
144 267
else
145 268
{
146
upperBound=1-(1-upperBound)/(1-node->getProbability());
269
upperBound.removeFactor(node->getProbability());
147 270
}
148 271
succList_t succs=node->getSuccessors();
149 272
for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
......
160 283
// If both bounds for the probability are below (above) the threshold,
161 284
// the probability itself is also below (above) the threshold,
162 285
// i.e. we can yield the decision without further inspecting the BFS tree.
286
assert(checkBounds());
163 287
if(lowerBound<=threshold && upperBound<=threshold) {node->releaseSuccListLock(); delete node; return true;}
164 288
if(lowerBound>=threshold && upperBound>=threshold) {node->releaseSuccListLock(); delete node; return false;}
165 289
}
166 290
node->releaseSuccListLock();
167 291
delete node;
168 292
}
293
assert(checkBounds());
169 294
if(lowerBound<=threshold && upperBound<=threshold) return true;
170 295
return false; // be pessimistic
171 296
}
......
192 317
evType_t* runningEvType=it->getEvType();
193 318
int runningEvModId=it->getEvModId();
194 319
bool isConflicting=pendingEvModId==runningEvModId;
195
pdf_t pdf(it->getArrivalTime()-pendingEv->getArrivalTime());
320
pdf_t pdf(it->getArrivalTime()-pendingEv->getArrivalTime(),1);
196 321
197 322
}
198 323

199
return bfsTree.bfs(threshold,pendingEvModId);
324
bool res=bfsTree.bfs(threshold,pendingEvModId);
325
//	std::cout << "lower bound: " << bfsTree.getLowerBound() << std::endl;
326
//	std::cout << "upper bound: " << bfsTree.getUpperBound() << std::endl;
327
return res;
200 328
}
201 329

Also available in: Unified diff