source: geniuswebcore/geniusweb/bidspace/pareto/GenericPareto.py@ 94

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

Refactor to help reusing partiesserver.

File size: 2.9 KB
Line 
1import threading
2from typing import List, Set, Optional
3
4from geniusweb.bidspace.AllBidsList import AllBidsList
5from geniusweb.bidspace.pareto.ParetoFrontier import ParetoFrontier
6from geniusweb.issuevalue.Bid import Bid
7from geniusweb.profile.PartialOrdering import PartialOrdering
8from geniusweb.profile.Profile import Profile
9from geniusweb.utils import val
10
11
12class 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)
Note: See TracBrowser for help on using the repository browser.