source: geniuswebcore/geniusweb/bidspace/pareto/PartialPareto.py@ 88

Last change on this file since 88 was 88, checked in by Bart Vastenhouw, 3 years ago

Added python SimpleRunner GUI

File size: 3.0 KB
RevLine 
[88]1from typing import List, Dict
2
3from geniusweb.bidspace.pareto.ParetoPoint import ParetoPoint
4from geniusweb.issuevalue.Bid import Bid
5from geniusweb.issuevalue.Value import Value
6from geniusweb.profile.utilityspace.LinearAdditive import LinearAdditive
7
8
9class PartialPareto:
10 '''
11 PartialPareto contains a pareto surface of partial bids. Internal-only
12 utility class for computing LinearAdditive pareto surface. Immutable.
13 '''
14
15 def __init__(self, points:List[ParetoPoint]):
16 '''
17 @param points the points to be contained in this PartialPareto
18'''
19 self._points = points
20
21 @staticmethod
22 def create(utilSpaces:List[LinearAdditive] ,
23 issues: List[str]) -> "PartialPareto":
24 '''
25 Constructor. Avoided the standard 'new' constructor as this is
26 implemented recursively (O(log(#issues))).
27
28 @param utilSpaces the {@link LinearAdditive}s
29 @param issues the issues (subset of all issues in the space) to be
30 used for this pareto
31 @return the pareto surface (non-dominated bids) when considering only the
32 given issues.
33 '''
34
35 if len(issues) == 1:
36 issue = issues[0]
37 map:Dict[str, Value] = {}
38 list:List[ParetoPoint] = []
39 for value in utilSpaces[0].getDomain().getValues(issue):
40 map[issue] = value
41 list = PartialPareto._add(list, ParetoPoint.create(Bid(map), utilSpaces))
42 return PartialPareto(list)
43 else:
44 halfway = int(len(issues) / 2)
45 return PartialPareto.create(utilSpaces, issues[0: halfway])._merge(
46 PartialPareto.create(utilSpaces, issues[halfway:]))
47
48 def getPoints(self) -> List[ParetoPoint]:
49 '''
50 @return the ParetoPoints on the (possibly partial) Pareto surface
51 '''
52 return self._points
53
54 def _merge(self, other:"PartialPareto") -> "PartialPareto":
55 '''
56 This combines two partial paretos. Here is the heart of the algorithm.
57
58 @param other another {@link PartialPareto} to be merged with this. The
59 other pareto must be composed with non-overlapping range.
60 @return merge of two partial paretos. Checks all partial1*partial2
61 combinations and only non-dominated points are kept.
62 '''
63 merge:List[ParetoPoint] = []
64 for point in self._points:
65 for otherpoint in other._points:
66 merge = PartialPareto._add(merge, point.merge(otherpoint))
67 return PartialPareto(merge)
68
69 @staticmethod
70 def _add(list:List[ParetoPoint], candidate:ParetoPoint) -> List[ParetoPoint]:
71 '''
72 Add a new ParetoPoint to a list
73
74 @param list the existing list
75 @param candidate a new {@link ParetoPoint} candidate
76 @return a new list that either ignored the candidate, or added it and
77 removed the old points that are dominated by the candidate
78 '''
79 for existing in list:
80 if candidate.isDominatedBy(existing):
81 return list
82 # if we get here, candidate is not dominated so we add it
83 # and remove existing ones now dominated
84 newlist:List[ParetoPoint] = []
85 newlist.append(candidate)
86 for existing in list:
87 if not existing.isDominatedBy(candidate):
88 newlist.append(existing)
89 return newlist
Note: See TracBrowser for help on using the repository browser.