Revision 8b911557
Various fixes for heuristic
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 1e6 

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 1invProb; 

67 
} 

68 
} 

69  
70 
void addFactor(const double factor) 

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*=(1factor); 

87 
if(invProb<0) std::cout << ips << "*" << (1factor) << "=" << 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/=(1factor); 

118 
if(invProb<0) std::cout << ips << "/" << (1factor) << "=" << 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(1upperBound)*(1dangerProb);


127 
if(isConflicting) lowerBound=1(1lowerBound)*(1dangerProb);


224 
upperBound.addFactor(dangerProb);


225 
if(isConflicting) lowerBound.addFactor(dangerProb);


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(lowerBoundEPSILON>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(1upperBound)/(1node>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 
bfsTree.addNode(NULL,runningEvType,pdf,isConflicting); 
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