[88] | 1 | import threading
|
---|
| 2 | from typing import List, Set, Optional
|
---|
| 3 |
|
---|
| 4 | from geniusweb.bidspace.AllBidsList import AllBidsList
|
---|
| 5 | from geniusweb.bidspace.pareto.ParetoFrontier import ParetoFrontier
|
---|
| 6 | from geniusweb.issuevalue.Bid import Bid
|
---|
| 7 | from geniusweb.profile.PartialOrdering import PartialOrdering
|
---|
| 8 | from geniusweb.profile.Profile import Profile
|
---|
| 9 | from geniusweb.utils import val
|
---|
| 10 |
|
---|
| 11 |
|
---|
| 12 | class GenericPareto(ParetoFrontier):
|
---|
| 13 | '''
|
---|
| 14 | A set of all pareto points associated with a set of profiles. Generally
|
---|
| 15 | applicable but slow.
|
---|
| 16 | '''
|
---|
| 17 |
|
---|
| 18 | def __init__(self, profiles:List[PartialOrdering]):
|
---|
| 19 | '''
|
---|
| 20 | Constructs pareto from a general {@link PartialOrdering}. This is a
|
---|
| 21 | brute-force algorithm that will inspect (but not store) ALL bids in the
|
---|
| 22 | space, and therefore may be inapproproate depending on the size of your
|
---|
| 23 | domain. Complexity O( |bidspace|^2 |profiles| )
|
---|
| 24 |
|
---|
| 25 | @param profiles a set of at least 2 {@link PartialOrdering}s. All must be
|
---|
| 26 | defined on the same domain.
|
---|
| 27 | '''
|
---|
| 28 | if len(profiles) < 2:
|
---|
| 29 | raise ValueError("at least 2 profiles are needed")
|
---|
| 30 |
|
---|
| 31 | if None in profiles:
|
---|
| 32 | raise ValueError("Profiles must not be None")
|
---|
| 33 | domain = profiles[0].getDomain()
|
---|
| 34 | for profile in profiles:
|
---|
| 35 | if not domain == profile.getDomain():
|
---|
| 36 | raise ValueError(
|
---|
| 37 | "All profiles must be on same domain ("
|
---|
| 38 | +domain.getName() + ") but found " + str(profile));
|
---|
| 39 | self._profiles = list(profiles)
|
---|
| 40 | self._paretobids:Optional[Set[Bid]] = None
|
---|
| 41 | self._lock = threading.Lock()
|
---|
| 42 |
|
---|
| 43 | # Override
|
---|
| 44 | def getProfiles(self) -> List[Profile]:
|
---|
| 45 | return list(self._profiles)
|
---|
| 46 |
|
---|
| 47 | # Override
|
---|
| 48 | def getPoints(self) -> Set[Bid]:
|
---|
| 49 | with self._lock:
|
---|
| 50 | if self._paretobids == None:
|
---|
| 51 | self._computePareto()
|
---|
| 52 | return set(val(self._paretobids))
|
---|
| 53 |
|
---|
| 54 | # Override
|
---|
| 55 | def __repr__(self):
|
---|
| 56 | return "Pareto " + str(self.getPoints())
|
---|
| 57 |
|
---|
| 58 | def _computePareto(self):
|
---|
| 59 | '''
|
---|
| 60 | assigns {@link #paretobids}.
|
---|
| 61 | '''
|
---|
| 62 | self._paretobids:Set[Bid] = set()
|
---|
| 63 |
|
---|
| 64 | for newbid in AllBidsList(self._profiles[0].getDomain()):
|
---|
| 65 | '''
|
---|
| 66 | invariant: paretobids contains bids not dominated by other bids
|
---|
| 67 | in paretobids. That means we need (1) check if new bid is
|
---|
| 68 | dominated (2) if existing bids are dominated if we add a new bid
|
---|
| 69 | '''
|
---|
| 70 | newBidIsDominated = any(self._isDominatedBy(newbid, paretobid)
|
---|
| 71 | for paretobid in self._paretobids)
|
---|
| 72 |
|
---|
| 73 | # if new bid is not dominated, we add it and we re-check existing
|
---|
| 74 | # if they are now dominated
|
---|
| 75 | if not newBidIsDominated:
|
---|
| 76 | self._paretobids = {paretobid for paretobid in self._paretobids
|
---|
| 77 | if not self._isDominatedBy(paretobid, newbid)}
|
---|
| 78 | self._paretobids.add(newbid)
|
---|
| 79 |
|
---|
| 80 | def _isDominatedBy(self, bid1:Bid , dominantbid: Bid) -> bool:
|
---|
| 81 | '''
|
---|
| 82 | @param bid1 the bid to check
|
---|
| 83 | @param dominantbid the bid that is supposed to dominate bid1
|
---|
| 84 | @return true iff bid1 is dominated by dominant bid. "Dominated by" means
|
---|
| 85 | that the bid is preferred or equal in all profiles.
|
---|
| 86 | '''
|
---|
| 87 | return all(profile.isPreferredOrEqual(dominantbid, bid1)
|
---|
| 88 | for profile in self._profiles)
|
---|