source: src/main/java/parties/feedbackmediator/partialopponentmodel/ValuePreferenceGraph.java

Last change on this file was 127, checked in by Wouter Pasman, 6 years ago

#41 ROLL BACK of rev.126 . So this version is equal to rev. 125

File size: 19.6 KB
RevLine 
[127]1package parties.feedbackmediator.partialopponentmodel;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.Iterator;
6
7import genius.core.Feedback;
8import genius.core.issue.Issue;
9import genius.core.issue.IssueDiscrete;
10import genius.core.issue.IssueInteger;
11import genius.core.issue.IssueReal;
12import genius.core.issue.Value;
13import genius.core.issue.ValueDiscrete;
14import genius.core.issue.ValueInteger;
15import genius.core.issue.ValueReal;
16
17/**
18 *
19 * @author Reyhan Aydogan
20 *
21 */
22
23public class ValuePreferenceGraph {
24
25 private HashMap<Value, ValuePreferenceNode> partialGraph;
26 private Issue issue;
27 private int lowestDepth = 1;
28 private int highestDepth = 1;
29
30 public ValuePreferenceGraph(Value initialValue) {
31
32 partialGraph = new HashMap<Value, ValuePreferenceNode>();
33 partialGraph.put(initialValue, new ValuePreferenceNode(initialValue, 1));
34 }
35
36 public boolean containsIssueValue(Value issueValue) {
37 return partialGraph.containsKey(issueValue);
38 }
39
40 public Integer getDepth(Value issueValue) {
41
42 if (!containsIssueValue(issueValue))
43 return -1;
44 else
45 return partialGraph.get(issueValue).getDepth() - lowestDepth + 1; // to
46 // ensure
47 // the
48 // lowest
49 // depth
50 // is
51 // equal
52 // to
53 // one..
54
55 }
56
57 public double getEstimatedUtility(Value issueValue) { // according to depth
58 // heuristic
59
60 return (double) getDepth(issueValue) / (highestDepth - lowestDepth + 1);
61 }
62
63 public ArrayList<Value> getAllValues() {
64
65 ArrayList<Value> values = new ArrayList<Value>();
66
67 Iterator<Value> valueIterator = partialGraph.keySet().iterator();
68
69 while (valueIterator.hasNext()) {
70 values.add(valueIterator.next());
71 }
72
73 return values;
74 }
75
76 public void updateLowHighDepths() {
77
78 Iterator<Value> valueIterator = partialGraph.keySet().iterator();
79 Value currentValue = null;
80
81 lowestDepth = highestDepth; // lowerDepth can be greater than it was
82 // before
83 while (valueIterator.hasNext()) {
84 currentValue = valueIterator.next();
85
86 if (partialGraph.get(currentValue).getDepth() < lowestDepth)
87 lowestDepth = partialGraph.get(currentValue).getDepth();
88
89 if (partialGraph.get(currentValue).getDepth() > highestDepth)
90 highestDepth = partialGraph.get(currentValue).getDepth();
91 }
92
93 }
94
95 public Value getMissingValue() {
96
97 switch (issue.getType()) {
98
99 case DISCRETE:
100 IssueDiscrete issueDiscrete = (IssueDiscrete) issue;
101 for (Value value : issueDiscrete.getValues()) {
102 if (!containsIssueValue(value))
103 return value;
104 }
105 break;
106 case INTEGER:
107 IssueInteger issueInteger = (IssueInteger) issue;
108 Value value;
109 for (int i = 0; i <= (issueInteger.getUpperBound() - issueInteger.getLowerBound()); i++) {
110 value = new ValueInteger(issueInteger.getLowerBound() + i);
111 if (!containsIssueValue(value))
112 return value;
113 }
114 break;
115
116 case REAL: // needs to be checked!
117 IssueReal issueReal = (IssueReal) issue;
118 for (int i = 0; i < issueReal.getNumberOfDiscretizationSteps(); i++) {
119 value = new ValueReal(
120 issueReal.getLowerBound() + (((double) ((issueReal.getUpperBound() - issueReal.getLowerBound()))
121 / (issueReal.getNumberOfDiscretizationSteps())) * i));
122 if (!containsIssueValue(value))
123 return value;
124 }
125 break;
126 }
127
128 return null;
129 }
130
131 private void searchCondition(Value willBeChecked, ArrayList<Value> visitedList, ArrayList<Value> selectedValues,
132 ArrayList<Value> forbiddenList) {
133
134 ArrayList<Value> checkList = new ArrayList<Value>();
135
136 // eliminate the forbidden values first
137 for (Value value : getAllComparableValues(willBeChecked)) {
138 if (!forbiddenList.contains(value))
139 checkList.add(value);
140 }
141
142 // seach
143 for (Value currentValue : checkList) {
144 if (!visitedList.contains(currentValue)) {
145
146 if (!selectedValues.contains(currentValue))
147 selectedValues.add(currentValue);
148
149 for (Value equalValue : partialGraph.get(currentValue).getEqualPreferredList()) {
150 if (!visitedList.contains(equalValue))
151 visitedList.add(equalValue);
152 }
153
154 searchCondition(currentValue, visitedList, selectedValues, forbiddenList);
155 }
156 } // for
157 }
158
159 // receiveMessage each node's depth except the given value and value list
160 private void increasePreferredValueNodeDepths(Value lessPreferredValue, Value morePreferredValue, int difference) {
161
162 ArrayList<Value> forbiddenList = getAllLessPreferredValues(lessPreferredValue);
163 for (Value less : getEqualPreferredValues(lessPreferredValue))
164 forbiddenList.add(less);
165
166 // the depth of the nodes related to morePreferredValue except forbidden
167 // list will be increaded by "difference"
168
169 ArrayList<Value> selectedValues = new ArrayList<Value>();
170
171 searchCondition(morePreferredValue, new ArrayList<Value>(), selectedValues, forbiddenList);
172
173 for (Value currentValue : selectedValues) {
174 partialGraph.get(currentValue).increaseDepth(difference);
175 }
176
177 }
178
179 // The method assumes that firstValue always exists in the system.
180 public void addPreferenceOrdering(Value firstValue, Value secondValue, Feedback feedback) {
181
182 if (firstValue.equals(secondValue)) // if the values are same, do
183 // nothing
184 return;
185
186 if (!containsIssueValue(secondValue))
187 addNewNode(firstValue, secondValue, feedback);
188 else {
189
190 ValuePreferenceNode firstValueNode = partialGraph.get(firstValue);
191 ValuePreferenceNode secondValueNode = partialGraph.get(secondValue);
192
193 if (feedback == Feedback.BETTER) {
194
195 // receiveMessage the depth of all nodes except first node and
196 // all less preferred nodes than it
197 if (firstValueNode.getDepth() >= secondValueNode.getDepth()) { // receiveMessage
198 // depth
199 increasePreferredValueNodeDepths(firstValue, secondValue,
200 firstValueNode.getDepth() - secondValueNode.getDepth() + 1);
201 }
202
203 // common part
204 secondValueNode.addLessPreferredValue(firstValue);
205 firstValueNode.addMorePreferredValue(secondValue);
206 partialGraph.put(secondValue, secondValueNode);
207
208 } else if (feedback == Feedback.WORSE) {
209 if (firstValueNode.getDepth() <= secondValueNode.getDepth()) {// receiveMessage
210 // depth
211 increasePreferredValueNodeDepths(secondValue, firstValue,
212 secondValueNode.getDepth() - firstValueNode.getDepth() + 1);
213 }
214 // common part
215 secondValueNode.addMorePreferredValue(firstValue);
216 firstValueNode.addLessPreferredValue(secondValue);
217 partialGraph.put(secondValue, secondValueNode);
218
219 } else { // SAME
220
221 if (firstValueNode.getDepth() != secondValueNode.getDepth()) {
222
223 if (firstValueNode.getDepth() < secondValueNode.getDepth()) {// second
224 // node
225 // is
226 // higher
227
228 increasePreferredValueNodeDepths(secondValue, firstValue,
229 secondValueNode.getDepth() - firstValueNode.getDepth());
230 firstValueNode.setDepth(secondValueNode.getDepth());
231 } else { // first node is higher
232 increasePreferredValueNodeDepths(firstValue, secondValue,
233 firstValueNode.getDepth() - secondValueNode.getDepth());
234 }
235
236 }
237 // common part
238 firstValueNode.addEquallyPreferredValues(secondValueNode.getEqualPreferredList());
239 firstValueNode.addLessPreferredValues(secondValueNode.getLessPreferredList());
240 firstValueNode.addMorePreferredValues(secondValueNode.getMorePreferredList());
241
242 partialGraph.put(secondValue, firstValueNode);
243
244 } // SAME
245
246 updateLowHighDepths(); // common
247 partialGraph.put(firstValue, firstValueNode);
248
249 } // else not contain
250
251 }
252
253 // FirstValue always exists in the system but newValudoes not exist for this
254 // method
255 public void addNewNode(Value firstValue, Value newValue, Feedback feedback) {
256
257 ValuePreferenceNode firstValueNode = partialGraph.get(firstValue);
258
259 if (feedback == Feedback.SAME) {
260 firstValueNode.addEquallyPreferredValue(newValue);
261 partialGraph.put(newValue, firstValueNode);
262 partialGraph.put(firstValue, firstValueNode);
263 } else {
264 ValuePreferenceNode newValueNode = new ValuePreferenceNode(newValue);
265
266 if (feedback == Feedback.BETTER) {
267 newValueNode.setDepth(firstValueNode.getDepth() + 1);
268 newValueNode.addLessPreferredValue(firstValue);
269 firstValueNode.addMorePreferredValue(newValue);
270 if (newValueNode.getDepth() > highestDepth) // receiveMessage
271 // the highest depth
272 highestDepth = newValueNode.getDepth();
273
274 } else { // WORSE
275 newValueNode.setDepth(firstValueNode.getDepth() - 1);
276 newValueNode.addMorePreferredValue(firstValue);
277 firstValueNode.addLessPreferredValue(newValue);
278 if (newValueNode.getDepth() < lowestDepth) // receiveMessage the
279 // lowest depth
280 lowestDepth = newValueNode.getDepth();
281 }
282
283 partialGraph.put(newValue, newValueNode);
284 partialGraph.put(firstValue, firstValueNode);
285 } // else
286 }
287
288 private void searchPreferredValues(Value currentValue, ArrayList<Value> preferredList) {
289
290 for (Value currentPreferred : partialGraph.get(currentValue).getMorePreferredList()) {
291
292 for (Value preferred : partialGraph.get(currentPreferred).getEqualPreferredList()) {
293
294 if (!preferredList.contains(preferred)) {
295 preferredList.add(preferred);
296 searchPreferredValues(preferred, preferredList);
297 }
298 }
299 } // for
300 }
301
302 private void searchLessPreferredValues(Value value, ArrayList<Value> lessPreferredList) {
303
304 for (Value currentLessPreferred : partialGraph.get(value).getLessPreferredList()) {
305
306 for (Value lessPreferred : partialGraph.get(currentLessPreferred).getEqualPreferredList()) {
307
308 if (!lessPreferredList.contains(lessPreferred)) {
309 lessPreferredList.add(lessPreferred);
310 searchLessPreferredValues(lessPreferred, lessPreferredList);
311 }
312 }
313 }
314 }
315
316 public ArrayList<Value> getAllMorePreferredValues(Value currentValue) {
317
318 ArrayList<Value> preferredValueList = new ArrayList<Value>();
319
320 searchPreferredValues(currentValue, preferredValueList);
321
322 return preferredValueList;
323 }
324
325 public ArrayList<Value> getAllLessPreferredValues(Value currentValue) {
326
327 ArrayList<Value> lessPreferredValueList = new ArrayList<Value>();
328
329 searchLessPreferredValues(currentValue, lessPreferredValueList);
330
331 return lessPreferredValueList;
332 }
333
334 public ArrayList<Value> getAllComparableValues(Value currentValue) {
335
336 ArrayList<Value> comparables = new ArrayList<Value>();
337 comparables.addAll(getAllLessPreferredValues(currentValue));
338 comparables.addAll(getAllMorePreferredValues(currentValue));
339 comparables.addAll(getEqualPreferredValues(currentValue));
340 return comparables;
341 }
342
343 public ArrayList<Value> getAllIncomparableValues(Value currentValue) {
344
345 ArrayList<Value> incomparables = new ArrayList<Value>();
346 ArrayList<Value> comparables = getAllComparableValues(currentValue);
347
348 for (Value value : getAllValues()) {
349
350 if (!comparables.contains(value))
351 incomparables.add(value);
352 }
353
354 return incomparables;
355 }
356
357 public Value getIncomparableValue(Value currentValue) {
358
359 ArrayList<Value> comparables = getAllComparableValues(currentValue);
360
361 for (Value value : getAllValues()) {
362 if (!comparables.contains(value))
363 return value;
364 }
365 return null;
366 }
367
368 public ArrayList<Value> getEqualPreferredValues(Value currentValue) {
369 return partialGraph.get(currentValue).getEqualPreferredList();
370 }
371
372 @Override
373 public String toString() {
374
375 Iterator<ValuePreferenceNode> nodes = partialGraph.values().iterator();
376 StringBuffer buffy = new StringBuffer("Value Preference Graph:\n");
377
378 buffy.append("Lowest Depth: ").append(lowestDepth).append("\n");
379 buffy.append("Highest Depth: ").append(highestDepth).append("\n");
380 while (nodes.hasNext()) {
381 buffy.append("\n");
382 buffy.append(nodes.next());
383 }
384 return buffy.toString();
385 }
386
387 // For test purposes....
388 public static void main(String[] args) {
389
390 /*
391 * ValuePreferenceGraph mygraph=new ValuePreferenceGraph(new
392 * ValueDiscrete("a")); mygraph.addPreferenceOrdering(new
393 * ValueDiscrete("a"), new ValueDiscrete("b"), Feedback.BETTER);
394 * mygraph.addPreferenceOrdering(new ValueDiscrete("b"), new
395 * ValueDiscrete("c"), Feedback.BETTER);
396 * mygraph.addPreferenceOrdering(new ValueDiscrete("c"), new
397 * ValueDiscrete("d"), Feedback.WORSE);
398 * mygraph.addPreferenceOrdering(new ValueDiscrete("c"), new
399 * ValueDiscrete("e"), Feedback.SAME); mygraph.addPreferenceOrdering(new
400 * ValueDiscrete("e"), new ValueDiscrete("f"), Feedback.BETTER);
401 * mygraph.addPreferenceOrdering(new ValueDiscrete("a"), new
402 * ValueDiscrete("g"), Feedback.WORSE);
403 * mygraph.addPreferenceOrdering(new ValueDiscrete("a"), new
404 * ValueDiscrete("h"), Feedback.SAME); mygraph.addPreferenceOrdering(new
405 * ValueDiscrete("h"), new ValueDiscrete("k"), Feedback.WORSE);
406 * mygraph.addPreferenceOrdering(new ValueDiscrete("f"), new
407 * ValueDiscrete("m"), Feedback.SAME);
408 *
409 * System.out.println(mygraph.toString());
410 *
411 *
412 * for (Value current: mygraph.getAllValues()) {
413 *
414 * System.out.print("\n \n Value:"+current+" \n More Preferred Values:"
415 * );
416 *
417 * for (Value preferred: mygraph.getAllMorePreferredValues(current))
418 * System.out.print(" "+preferred.toString());
419 *
420 * System.out.print("\n Less Preferred Values:");
421 *
422 * for (Value lessPreferred: mygraph.getAllLessPreferredValues(current))
423 * System.out.print(" "+lessPreferred.toString());
424 *
425 * System.out.println("\nEstimated Utility:"+mygraph.getEstimatedUtility
426 * (current));
427 *
428 * }
429 *
430 * System.out.println("");
431 *
432 * System.out.println(
433 * "*******************************************************************"
434 * );
435 * System.out.println("Comparables-a :"+mygraph.getAllComparableValues(
436 * new ValueDiscrete("a")));
437 * System.out.println("Comparables-b :"+mygraph.getAllComparableValues(
438 * new ValueDiscrete("b")));
439 * System.out.println("Comparables-c :"+mygraph.getAllComparableValues(
440 * new ValueDiscrete("c")));
441 * System.out.println("Comparables-d :"+mygraph.getAllComparableValues(
442 * new ValueDiscrete("d")));
443 * System.out.println("Comparables-e :"+mygraph.getAllComparableValues(
444 * new ValueDiscrete("e")));
445 * System.out.println("Comparables-f :"+mygraph.getAllComparableValues(
446 * new ValueDiscrete("f")));
447 * System.out.println("Comparables-g :"+mygraph.getAllComparableValues(
448 * new ValueDiscrete("g")));
449 * System.out.println("Comparables-h :"+mygraph.getAllComparableValues(
450 * new ValueDiscrete("h")));
451 * System.out.println("Comparables-k :"+mygraph.getAllComparableValues(
452 * new ValueDiscrete("k")));
453 * System.out.println("Comparables-m :"+mygraph.getAllComparableValues(
454 * new ValueDiscrete("m")));
455 *
456 *
457 * System.out.println(
458 * "*******************************************************************"
459 * ); System.out.println("InComparables-a :"+mygraph.
460 * getAllIncomparableValues(new ValueDiscrete("a")));
461 * System.out.println("InComparables-b :"+mygraph.
462 * getAllIncomparableValues(new ValueDiscrete("b")));
463 * System.out.println("InComparables-c :"+mygraph.
464 * getAllIncomparableValues(new ValueDiscrete("c")));
465 * System.out.println("InComparables-d :"+mygraph.
466 * getAllIncomparableValues(new ValueDiscrete("d")));
467 * System.out.println("InComparables-e :"+mygraph.
468 * getAllIncomparableValues(new ValueDiscrete("e")));
469 * System.out.println("InComparables-f :"+mygraph.
470 * getAllIncomparableValues(new ValueDiscrete("f")));
471 * System.out.println("InComparables-g :"+mygraph.
472 * getAllIncomparableValues(new ValueDiscrete("g")));
473 * System.out.println("InComparables-h :"+mygraph.
474 * getAllIncomparableValues(new ValueDiscrete("h")));
475 * System.out.println("InComparables-k :"+mygraph.
476 * getAllIncomparableValues(new ValueDiscrete("k")));
477 * System.out.println("InComparables-m :"+mygraph.
478 * getAllIncomparableValues(new ValueDiscrete("m")));
479 */
480
481 /*
482 * ValuePreferenceGraph mygraph=new ValuePreferenceGraph(new
483 * ValueDiscrete("a")); mygraph.addPreferenceOrdering(new
484 * ValueDiscrete("a"), new ValueDiscrete("b"), Feedback.WORSE);
485 * mygraph.addPreferenceOrdering(new ValueDiscrete("b"), new
486 * ValueDiscrete("c"), Feedback.BETTER);
487 * mygraph.addPreferenceOrdering(new ValueDiscrete("c"), new
488 * ValueDiscrete("d"), Feedback.BETTER);
489 * mygraph.addPreferenceOrdering(new ValueDiscrete("d"), new
490 * ValueDiscrete("a"), Feedback.BETTER);
491 * mygraph.addPreferenceOrdering(new ValueDiscrete("d"), new
492 * ValueDiscrete("e"), Feedback.WORSE);
493 * mygraph.addPreferenceOrdering(new ValueDiscrete("b"), new
494 * ValueDiscrete("e"), Feedback.WORSE);
495 *
496 * mygraph.addPreferenceOrdering(new ValueDiscrete("d"), new
497 * ValueDiscrete("f"), Feedback.WORSE);
498 * mygraph.addPreferenceOrdering(new ValueDiscrete("d"), new
499 * ValueDiscrete("g"), Feedback.BETTER);
500 * mygraph.addPreferenceOrdering(new ValueDiscrete("b"), new
501 * ValueDiscrete("f"), Feedback.SAME); mygraph.addPreferenceOrdering(new
502 * ValueDiscrete("d"), new ValueDiscrete("k"), Feedback.WORSE);
503 * mygraph.addPreferenceOrdering(new ValueDiscrete("c"), new
504 * ValueDiscrete("m"), Feedback.WORSE);
505 * mygraph.addPreferenceOrdering(new ValueDiscrete("m"), new
506 * ValueDiscrete("n"), Feedback.BETTER);
507 * mygraph.addPreferenceOrdering(new ValueDiscrete("k"), new
508 * ValueDiscrete("m"), Feedback.BETTER); //
509 * mygraph.addPreferenceOrdering(new ValueDiscrete("e"), new
510 * ValueDiscrete("n"), Feedback.SAME);
511 * System.out.println(mygraph.toString());
512 */
513 /*
514 * System.out.println(
515 * "*******************************************************************"
516 * ); System.out.println("InComparables-a :"+mygraph.
517 * getAllIncomparableValues(new ValueDiscrete("a")));
518 * System.out.println("InComparables-b :"+mygraph.
519 * getAllIncomparableValues(new ValueDiscrete("b")));
520 * System.out.println("InComparables-c :"+mygraph.
521 * getAllIncomparableValues(new ValueDiscrete("c")));
522 * System.out.println("InComparables-d :"+mygraph.
523 * getAllIncomparableValues(new ValueDiscrete("d")));
524 * System.out.println("InComparables-e :"+mygraph.
525 * getAllIncomparableValues(new ValueDiscrete("e")));
526 * System.out.println("InComparables-f :"+mygraph.
527 * getAllIncomparableValues(new ValueDiscrete("f")));
528 * System.out.println("InComparables-g :"+mygraph.
529 * getAllIncomparableValues(new ValueDiscrete("g")));
530 * System.out.println("InComparables-k :"+mygraph.
531 * getAllIncomparableValues(new ValueDiscrete("k")));
532 * System.out.println("InComparables-m :"+mygraph.
533 * getAllIncomparableValues(new ValueDiscrete("m")));
534 * System.out.println("InComparables-n :"+mygraph.
535 * getAllIncomparableValues(new ValueDiscrete("n")));
536 */
537
538 ValuePreferenceGraph mygraph = new ValuePreferenceGraph(new ValueDiscrete("a"));
539 mygraph.addPreferenceOrdering(new ValueDiscrete("a"), new ValueDiscrete("b"), Feedback.BETTER);
540 mygraph.addPreferenceOrdering(new ValueDiscrete("b"), new ValueDiscrete("e"), Feedback.BETTER);
541 mygraph.addPreferenceOrdering(new ValueDiscrete("e"), new ValueDiscrete("c"), Feedback.BETTER);
542
543 mygraph.addPreferenceOrdering(new ValueDiscrete("c"), new ValueDiscrete("d"), Feedback.WORSE);
544 mygraph.addPreferenceOrdering(new ValueDiscrete("a"), new ValueDiscrete("d"), Feedback.BETTER);
545
546 System.out.println(mygraph.toString());
547 }
548
549 public Issue getIssue() {
550 return issue;
551 }
552
553 public void setIssue(Issue issue) {
554 this.issue = issue;
555 }
556
557}
Note: See TracBrowser for help on using the repository browser.