-
Notifications
You must be signed in to change notification settings - Fork 0
/
FirstAlgorithmBayesianNetwork.java
469 lines (402 loc) · 15.9 KB
/
FirstAlgorithmBayesianNetwork.java
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
import java.util.ArrayList;
/**
* This class implements the simple deduction algorithm of the Bayesian Network.
* This class uses the following classes:
* readXmlFile
* Variable
* CPT
* bayesianNetwork
* @author Maya
* @version 1.0
*/
public class FirstAlgorithmBayesianNetwork {
/**
* This function finally returns the probability of the event happening.
* @param input the given query as a string
* @param bn is the Bayesian Network
* @return the probability, the number of additions, the number of multiplications
*/
public static String finalCalculation(String input, bayesianNetwork bn) {
String variable = convert(input).get(0);
int numOfOutcomesForV =0 ;
int keepRecord [] = new int [3];
double numerator = 0;
double denominator = 0;
double answerNumerator = 0;
double answerDenominator = 0;
String s = "";
// Find whether we can find directly from CPT
for (int i = 0; i < bn.getBN().size() ; i++) {
if (variable.equals(bn.getBN().get(i).getName())) {
if (bn.getBN().get(i).getParents().equals(getGiven(input, bn))) {
setWantedOutcomesForAll(input,bn,1);
s =""+ probs(bn.getBN().get(i), bn) + ",0,0";
return s;
}
}
}
//Find if probability == 0
if (isZero(input, bn)) {
s="0.00000,0,0";
return s;
}
//Find if probability == 1
if (isOne(input, bn)) {
s="1.00000,0,0";
return s;
}
for (int i = 1 ; i < createAlternatingTable(getHidden(input, bn)).length; i ++) {
setWantedOutcomesForAll(input,bn,i);
numerator =probs(bn.getBN().get(0),bn);
for (int j = 1 ; j < bn.getBN().size() ; j++) {
numerator *=probs(bn.getBN().get(j),bn);
keepRecord[2]++;
}
answerNumerator += numerator;
keepRecord[1]++;
}
for (int i = 1 ; i < createAlternatingTable(getHiddenForDenominator(input, bn)).length; i ++) {
setWantedOutcomesForDenominator2(input,bn,i);
denominator = probs(bn.getBN().get(0),bn);
for (int j = 1 ; j < bn.getBN().size() ; j++) {
denominator *=probs(bn.getBN().get(j),bn);
}
answerDenominator += denominator;
}
double answer = answerNumerator/(answerDenominator);
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if (bn.getBN().get(i).getName().equals(variable))
numOfOutcomesForV = bn.getBN().get(i).getPossibleOutcomes().size()-1;
}
for (int k = 0 ; k < numOfOutcomesForV ; k++) {
for (int i = 1 ; i < createAlternatingTable(getHidden(input, bn)).length; i ++) {
setWantedOutcomesForDenominator(input,bn,i,k);
for (int j = 1 ; j < bn.getBN().size() ; j++) {
keepRecord[2]++;
}
keepRecord[1]++;
}
}
keepRecord[1]--;
String result = String.format("%.5f", answer);
s+= "" + result + "," + keepRecord[1] +"," + keepRecord[2];
return s;
}
/**
* This function finds out if the query is already found in given
* @param input String query
* @param bn is the network
* @return whether the probability is 1
*/
public static boolean isOne(String input, bayesianNetwork bn) {
ArrayList<Variable> given = getGiven(input, bn);
ArrayList<String> queryAll = convert(input);
for (int i = 0 ; i < given.size() ; i++) {
if (given.get(i).getName().equals(queryAll.get(0)) && given.get(i).getWantedOutcome().equals(queryAll.get(1))) {
return true;
}
}
return false;
}
/**
* This function finds out if the query is already found in given
* @param input String query
* @param bn is the network
* @return whether the probability is 0
*/
public static boolean isZero(String input, bayesianNetwork bn) {
ArrayList<Variable> given = getGiven(input, bn);
ArrayList<String> queryAll = convert(input);
for (int i = 0 ; i < given.size() ; i++) {
if (given.get(i).getName().equals(queryAll.get(0)) && !given.get(i).getWantedOutcome().equals(queryAll.get(1))) {
return true;
}
}
return false;
}
/**
* This function find the wanted probability of a specific variable.
* @param v is the variable that the cpt table is going to be created around.
* @param bn is the bayesian network from which we gather our data.
* @return the probability found.
*/
public static double probs(Variable v, bayesianNetwork bn) {
String [][] cpt = v.createTruthTableByVariable(v);
ArrayList <Integer> rowNum = new ArrayList<>();
for (int i = 0; i < cpt[0].length-1 ; i++) {
if (cpt[0][i].equals(v.getName())) {
for (int j = 1; j < cpt.length ; j++) {
if (cpt[j][i].equals(v.getWantedOutcome())) {
rowNum.add(j);
}
}
}
for (int k = 0 ; k < v.getParents().size() ; k++) {
if(cpt[0][i].equals(v.getParents().get(k).getName())) {
for (int j = 1; j < cpt.length ; j++) {
if (cpt[j][i].equals(v.getParents().get(k).getWantedOutcome())) {
rowNum.add(j);
}
}
}
}
}
ArrayList<Integer> rows = new ArrayList<>();
for (int i = 0 ; i < getRowNumber(rowNum, (cpt[0].length-1)).size() ; i++ )
if (!rows.contains(getRowNumber(rowNum, (cpt[0].length-1)).get(i)))
rows.add(getRowNumber(rowNum, (cpt[0].length-1)).get(i));
double wantedProbabilitiy=0;
for (int i = 0 ; i < rows.size() ; i++) {
wantedProbabilitiy = Double.parseDouble(cpt[rows.get(i)][cpt[0].length-1]);
}
return wantedProbabilitiy;
}
/**
* This function finds the correct row to receive from the probability later
* @param rowNum
* @param numberOfcols to look at in function.
* @return a list of all rows that contain the wanted outcomes of each variables.
*/
public static ArrayList<Integer> getRowNumber(ArrayList<Integer> rowNum , int numberOfcols){
ArrayList <Integer> numbers = new ArrayList<>();
for (int i = 0 ; i < rowNum.size() ; i++) {
int count = 0;
for (int j = 0 ; j < rowNum.size() ; j++) {
if (rowNum.get(i)== rowNum.get(j))
count++;
}
if (count == numberOfcols) {
numbers.add(rowNum.get(i));
}
}
return numbers;
}
/**
* This function sets outcomes for all variables in the network.
* @param input (the query)
* @param bn Bayesian Network
* @param loopNumber as the hidden's wanted outcomes change every loop.
*/
public static void setWantedOutcomesForAll(String input, bayesianNetwork bn, int loopNumber) {
String basic = input.substring(2, input.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
//Set given wanted outcome
ArrayList<Variable> given = getGiven(input,bn);
//Set Variable wanted outcome
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if (bn.getBN().get(i).getName().equals(queryIntoArray[0])) {
bn.getBN().get(i).setWantedOutcome(queryIntoArray[1]);
}
}
//set hidden's wanted outcome
ArrayList <String> variablesquery = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i+=2)
variablesquery.add(queryIntoArray[i]);
ArrayList <Variable> hidden = new ArrayList<>();
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if (!variablesquery.contains(bn.getBN().get(i).getName())) {
hidden.add(bn.getBN().get(i));
}
}
String [][] alternating = createAlternatingTable(hidden);
for (int j = 1 ; j < alternating.length ; j++) {
for (int i = 0 ; i < hidden.size() ; i++) {
hidden.get(i).setWantedOutcome(alternating [loopNumber][i]);
}
}
}
/**
* This function only looks at the other outcomes of the variable and ignore its original wanted outcome.
* @param input is the query as the received string from the input.txt
* @param bn is out network.
* @param loopNumber as we need to iterate over the possibilities of hidden in each row.
* @param vOutcome the number of possible outcomes for the variable - the given variable in the query.
*/
public static void setWantedOutcomesForDenominator(String input, bayesianNetwork bn, int loopNumber, int vOutcome) {
String basic = input.substring(2, input.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
//Set given wanted outcome
ArrayList<Variable> given = getGiven(input,bn);
//Set Variable wanted outcome
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if (bn.getBN().get(i).getName().equals(queryIntoArray[0])) {
for (int j = 0 ; j < bn.getBN().get(i).getPossibleOutcomes().size() ; j++) {
if (bn.getBN().get(i).getPossibleOutcomes().get(j).equals(queryIntoArray[1])) {
bn.getBN().get(i).getPossibleOutcomes().remove(j);
}
bn.getBN().get(i).setWantedOutcome(bn.getBN().get(i).getPossibleOutcomes().get(vOutcome));
}
}
}
//set hidden's wanted outcome
ArrayList <Variable> hidden = getHidden(input,bn);
String [][] alternating = createAlternatingTable(hidden);
for (int j = 1 ; j < alternating.length ; j++) {
for (int i = 0 ; i < hidden.size() ; i++) {
hidden.get(i).setWantedOutcome(alternating [loopNumber][i]);
}
}
}
/**
* This function sets the wanted outcomes for the denominator, note that in the denominator we treat the variable as an hidden as its wanted outcome alternates as well.
* @param input the query as a string.
* @param bn is our network.
* @param loopNumber to rotate over our hidden possibilities in alternating table.
*/
// Set wanted outcomes for denominator
public static void setWantedOutcomesForDenominator2(String input, bayesianNetwork bn, int loopNumber) {
String basic = input.substring(2, input.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 2 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
//Set given wanted outcome
ArrayList<Variable> given = getGiven(input,bn);
//set hidden's wanted outcome
ArrayList <Variable> hidden = getHidden(input,bn);
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if (bn.getBN().get(i).getName().equals(queryIntoArray[0]))
hidden.add(bn.getBN().get(i));
}
String [][] alternating = createAlternatingTable(hidden);
// printMat(alternating);
// for (int j = 1 ; j < alternating.length ; j++) {
for (int i = 0 ; i < hidden.size() ; i++) {
hidden.get(i).setWantedOutcome(alternating [loopNumber][i]);
}
//}
}
/**
* This function creates an alternating table for the hidden variables as we have to change their wanted outcome in each loop we have to assign them different wanted outcome each time.
* @param hidden is the array list of the hidden variables - the variables that aren't in the query.
* @return a 2D array of the wanted outcomes so we can iterate through.
*/
public static String[][] createAlternatingTable(ArrayList<Variable> hidden){
int rows = 1;
for (int i = 0 ; i < hidden.size() ; i++) {
rows *= hidden.get(i).getPossibleOutcomes().size();
}
//Note that the first line is the names of variables, we should know that when accessing table to start loop from row 1.
String [][] alternating = new String [rows+1][hidden.size()];
for (int i = 0 ; i < alternating[0].length ; i++) {
alternating [0][i] = hidden.get(i).getName();
}
int divideT = 1;
for (int k = 0 ; k < hidden.size(); k++) {
alternating[0][k] = hidden.get(k).getName();
int numOutcomesT = hidden.get(k).getPossibleOutcomes().size();
int colNumT = k;
divideT *= numOutcomesT;
for (int j = 0 ; j < divideT-1 ; j ++) {
for (int i = (j)*alternating.length/divideT+1; i < (j+1)*alternating.length/divideT+1; i++) {
alternating[i][k] = hidden.get(k).getPossibleOutcomes().get(j%numOutcomesT);
}
}
for (int i = (divideT-1)*alternating.length/divideT+1; i <alternating.length ;i++) {
alternating[i][k] = hidden.get(k).getPossibleOutcomes().get(numOutcomesT-1);
}
}
return alternating;
}
/**
* This function gets all the variables that aren't in the given query, note that in this function we treat the main variable as an hidden so its wanted value is changing as well.
* @param input is the given string.
* @param bn is our network that includes all variables.
* @return an ArrayList of all the hidden variables.
*/
public static ArrayList<Variable> getHiddenForDenominator(String input , bayesianNetwork bn){
String basic = input.substring(2, input.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
ArrayList <String> variablesquery = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i+=2)
variablesquery.add(queryIntoArray[i]);
ArrayList <Variable> hidden = getHidden(input,bn);
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if(bn.getBN().get(i).getName().equals(queryIntoArray[0]))
hidden.add(bn.getBN().get(i));
}
return hidden;
}
/**
* This function gets all the variables that aren't in the given query.
* @param input is the given string.
* @param bn is our network that includes all variables.
* @return an ArrayList of all the hidden variables.
*/
public static ArrayList<Variable> getHidden(String input , bayesianNetwork bn){
String basic = input.substring(2, input.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
ArrayList <String> variablesquery = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i+=2)
variablesquery.add(queryIntoArray[i]);
ArrayList <Variable> hidden = new ArrayList<>();
for (int i = 0 ; i < bn.getBN().size() ; i++) {
if (!variablesquery.contains(bn.getBN().get(i).getName())) {
hidden.add(bn.getBN().get(i));
}
}
return hidden;
}
//Get given as an ArrayList of Variables
public static ArrayList<Variable> getGiven(String input, bayesianNetwork bn){
String basic = input.substring(2, input.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
ArrayList <String> variablesquery = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i+=2)
variablesquery.add(queryIntoArray[i]);
ArrayList<Variable> given = new ArrayList<>();
for (int i = 0 ; i < bn.getBN().size() ; i ++) {
for (int k = 0 ; k < variablesquery.size() ; k++) {
for (int j = 2; j < query.size() ; j+=2) {
if (bn.getBN().get(i).getName().equals(variablesquery.get(k)) && bn.getBN().get(i).getName().equals(query.get(j))) {
bn.getBN().get(i).setWantedOutcome(query.get(j+1));
given.add(bn.getBN().get(i));
}
}
}
}
return given;
}
// public static void getVariable(String input, bayesianNetwork bn) {
// String basic = input.substring(2, input.length()-3);
// String [] queryIntoArray = basic.split("[\\|=,]");
// for (int i = 0 ; i < bn.getBN().size() ; i++) {
// if (bn.getBN().get(i).getName().equals(queryIntoArray[0])) {
// bn.getBN().get(i).setWantedOutcome(queryIntoArray[1]);
// }
// }
// }
//Convert from String input to arrayList of all variables
public static ArrayList<String> convert(String s) {
String basic = s.substring(2, s.length()-3);
String [] queryIntoArray = basic.split("[\\|=,]");
ArrayList <String> query = new ArrayList<>();
for (int i = 0 ; i < queryIntoArray.length ; i++)
query.add(queryIntoArray[i]);
return query;
}
//Print Mat
public static void printMat(String [][] s) {
for (int i = 0 ; i < s.length ; i++) {
for (int j = 0 ; j < s[0].length ; j++) {
System.out.print(s[i][j] + ", ");
}
System.out.println(" ");
}
}
}