[88] | 1 | from typing import List, Dict
|
---|
| 2 |
|
---|
| 3 | from geniusweb.bidspace.pareto.ParetoPoint import ParetoPoint
|
---|
| 4 | from geniusweb.issuevalue.Bid import Bid
|
---|
| 5 | from geniusweb.issuevalue.Value import Value
|
---|
| 6 | from geniusweb.profile.utilityspace.LinearAdditive import LinearAdditive
|
---|
| 7 |
|
---|
| 8 |
|
---|
| 9 | class 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
|
---|