source: voting/src/main/java/geniusweb/voting/CollectedVotes.java@ 52

Last change on this file since 52 was 52, checked in by ruud, 14 months ago

Fixed small issues in domaineditor.
File size: 10.7 KB
Line 
1package geniusweb.voting;
2
3import java.util.Collections;
4import java.util.Comparator;
5import java.util.HashMap;
6import java.util.HashSet;
7import java.util.Map;
8import java.util.PriorityQueue;
9import java.util.Set;
10import java.util.stream.Collectors;
11
12import geniusweb.actions.PartyId;
13import geniusweb.actions.Vote;
14import geniusweb.actions.Votes;
15import geniusweb.issuevalue.Bid;
16import tudelft.utilities.immutablelist.FixedList;
17import tudelft.utilities.immutablelist.ImmutableList;
18import tudelft.utilities.immutablelist.PowerSet;
19
20/**
21 * Utility class. Typically contains all the votes collected from 1 round. Can
22 * find the best combinations of votes, eg to get the maximum consensus group
23 */
24public class CollectedVotes {
25 private final Map<PartyId, Votes> allvotes;
26 private final Map<PartyId, Integer> powers;
27
28 // caching
29 private transient Map<Bid, Set<Vote>> allBids = null;
30
31 /**
32 *
33 * @param votesMap the {@link Votes} done for each party
34 * @param power the power of each party. The power is an integer number.
35 * In the voting process, the party powers add up to form
36 * the total voting power. This set may contain parties that
37 * are not in newmap.
38 */
39 public CollectedVotes(Map<PartyId, Votes> votesMap,
40 Map<PartyId, Integer> power) {
41 this.allvotes = new HashMap<>(votesMap);
42 this.powers = new HashMap<>(power);
43 if (!powers.keySet().containsAll(allvotes.keySet())) {
44 throw new IllegalArgumentException(
45 "All voting parties must have a power");
46 }
47 }
48
49 /**
50 * @param votes additional set of votes for a new party that did not yet
51 * vote.
52 * @param power powers for the new party, can be null if power already set
53 * previously.
54 * @return new CollectedVotes with the new votes added.
55 */
56 public CollectedVotes with(Votes votes, Integer power) {
57 PartyId actor = votes.getActor();
58 if (allvotes.containsKey(actor))
59 throw new IllegalArgumentException(
60 "Party " + actor + " already voted");
61
62 Map<PartyId, Integer> newpowers = new HashMap<>(powers);
63 if (!powers.containsKey(actor)) {
64 if (power == null)
65 throw new IllegalArgumentException(
66 "Power must be set for new actor " + actor);
67 newpowers.put(actor, power);
68 }
69
70 Map<PartyId, Votes> newmap = new HashMap<>(allvotes);
71 newmap.put(actor, votes);
72 return new CollectedVotes(newmap, newpowers);
73 }
74
75 /**
76 * @return all the votes placed so far
77 */
78 public Map<PartyId, Votes> getVotes() {
79 return Collections.unmodifiableMap(allvotes);
80 }
81
82 /**
83 * @return the powers of all parties
84 */
85 public Map<PartyId, Integer> getPowers() {
86 return Collections.unmodifiableMap(powers);
87 }
88
89 /**
90 * @return a map containing for each {@link Bid}s a subset of
91 * {@link PartyId}s that placed a satisfied vote for that bid, such
92 * that the subset has maximum power. Maximum power means that there
93 * is no other subset of satisfied votes for that bid with more
94 * group power. There may be other subsets of equal power for the
95 * bid. If there are no concensus possibilities at all for a bid,
96 * the bid is not placed in the map.
97 */
98 public Map<Bid, Set<PartyId>> getMaxAgreements() {
99 Map<Bid, Set<PartyId>> agreements = new HashMap<>();
100 Map<Bid, Set<Vote>> allbidsmap = getAllBids();
101 for (Bid bid : allbidsmap.keySet()) {
102 Set<PartyId> max = getMaxPowerGroup(allbidsmap.get(bid));
103 if (!max.isEmpty())
104 agreements.put(bid, max);
105 }
106 return agreements;
107 }
108
109 /**
110 * @return all bids that were voted on and the votes for that bid. This
111 * basically reverses keys and values in {@link #allvotes}
112 */
113 public Map<Bid, Set<Vote>> getAllBids() {
114 if (allBids == null)
115 allBids = getAllBids1();
116 return allBids;
117 }
118
119 /**
120 *
121 * @param parties the parties to be removed
122 * @return new CollectedVotes without given parties
123 */
124 public CollectedVotes without(Set<PartyId> parties) {
125 Map<PartyId, Votes> newvotes = new HashMap<>(allvotes);
126 newvotes.keySet().removeAll(parties);
127 Map<PartyId, Integer> newpower = new HashMap<>(powers);
128 newpower.keySet().removeAll(parties);
129 return new CollectedVotes(newvotes, newpower);
130 }
131
132 /**
133 *
134 * @param parties a list of parties
135 * @return total voting power of the parties
136 */
137 public Integer getTotalPower(Set<PartyId> parties) {
138 return parties.stream().map(p -> powers.get(p)).reduce(0, Integer::sum);
139 }
140
141 /**
142 * Breath-first optimized search, similar as {@link #getMaxPowerGroup(Set)}
143 * but more efficient on average (remains to be proven). Notice that this
144 * algorithm may be more expensive particularly if there is no consensus at
145 * all, because of the added overhead of the breath-first search
146 *
147 * @param allvotes a list of all votes for a particular bid.
148 * @return a consensus-group with maximum power, so there is no other
149 * consensus group that has more power (but there may be other
150 * groups with same power). returns empty set if no consensus found
151 */
152 protected Set<PartyId> getMaxPowerGroupBreathFirst(Set<Vote> allvotes) {
153 /**
154 * queue that keeps the options for the breath-first search sorted from
155 * highest to lowest power of the voters.
156 */
157 PriorityQueue<Set<Vote>> queue = new PriorityQueue<>(
158 new Comparator<Set<Vote>>() {
159 @Override
160 public int compare(Set<Vote> vs1, Set<Vote> vs2) {
161 Set<PartyId> parties1 = vs1.stream()
162 .map(vote -> vote.getActor())
163 .collect(Collectors.toSet());
164 Set<PartyId> parties2 = vs2.stream()
165 .map(vote -> vote.getActor())
166 .collect(Collectors.toSet());
167 return getTotalPower(parties1)
168 .compareTo(getTotalPower(parties2));
169 }
170 });
171 queue.add(allvotes);
172
173 while (!queue.isEmpty()) {
174 // try one with the highest power
175 Set<Vote> vs = queue.poll();
176 if (isViable(vs))
177 return getParties(vs);
178 if (vs.size() > 1) {
179 // vote can be splitted. push all new subsets
180 for (Vote vote : vs) {
181 Set<Vote> subvotes = new HashSet<>(vs);
182 subvotes.remove(vote);
183 // avoid duplicate work. Since this has a removed party,
184 // and assuming power of each party >=1,
185 // we can not already have checked subvotes
186 if (!queue.contains(subvotes))
187 queue.add(subvotes);
188 }
189 }
190
191 }
192 return Collections.emptySet();
193 }
194
195 /**
196 *
197 * @param votes a list of all votes for a particular bid. The parties that
198 * placed the votes are called 'voters'
199 * @return a consensus-group with maximum power, so there is no other
200 * consensus group that has more power (but there may be other
201 * groups with same power). returns empty set if no consensus found
202 */
203 protected Set<PartyId> getMaxPowerGroup(Set<Vote> votes) {
204 Set<PartyId> maxgroup = Collections.emptySet();
205 Integer maxpower = 0;
206
207 for (Set<PartyId> parties : getConsensusGroups(votes)) {
208 Integer power = getTotalPower(parties);
209 if (power > maxpower) {
210 maxgroup = parties;
211 maxpower = power;
212 }
213 }
214 return maxgroup;
215 }
216
217 /**
218 *
219 * @param votes a set of {@link Votes} for one single {@link Bid}. It is
220 * assumed all votes are by different parties.
221 * @return all subsets sets of parties that create a viable consensus vote.
222 * A viable consensus voteset VS is a subset of the votes, such that
223 * <ol>
224 * <li>|VS| &ge; 2
225 * <li>TP = The sum of the powers of the parties in VS
226 * <li>forall v in VS: v_minpower &le; TP &le; v_maxpower
227 * </ol>
228 * Notice that this algorithm works in exponential space
229 * (=expensive) and not suited for large numbers of parties. Should
230 * work fine for up to 10 parties.
231 */
232 protected Set<Set<PartyId>> getConsensusGroups(Set<Vote> votes) {
233 Set<Set<PartyId>> groups = new HashSet<>();
234
235 PowerSet<Vote> allVotePermutations = new PowerSet<Vote>(
236 new FixedList<Vote>(votes));
237 // check each possible subset.
238 // TODO stream this
239 for (ImmutableList<Vote> voteList : allVotePermutations) {
240 if (isViable(voteList)) {
241 groups.add(getParties(voteList));
242 }
243 }
244 return groups;
245 }
246
247 /**
248 *
249 * @param voteList a list of votes for a single bid.
250 * @return true if this votelist satisfies the requirements of all
251 * participants and there are &ge; 2 parties
252 */
253 private boolean isViable(Iterable<Vote> voteList) {
254 Set<PartyId> parties = getParties(voteList);
255 Integer totalpower = getTotalPower(parties);
256 return parties.size() >= 2 && totalpower >= getMinPower(voteList)
257 && totalpower <= getMaxPower(voteList);
258 }
259
260 /**
261 * @param voteList list of all {@link Vote}s
262 * @return all parties that did a vote
263 */
264 public static Set<PartyId> getParties(Iterable<Vote> voteList) {
265 Set<PartyId> parties = new HashSet<>();
266 for (Vote vote : voteList) {
267 parties.add(vote.getActor());
268 }
269 return parties;
270 }
271
272 /**
273 *
274 * @param votes a list of {@link Vote}s on one Bid. All parties must be
275 * known
276 * @return the minimum voting power needed for this group, so that all can
277 * accept. This is equal to the max of the vote.getMinPower
278 */
279 private Integer getMinPower(Iterable<Vote> votes) {
280 int max = 0;
281 for (Vote vote : votes) {
282 max = Math.max(max, vote.getMinPower());
283 }
284 return max;
285 }
286
287 /**
288 *
289 * @param votes a list of {@link Vote}s on one Bid. All parties must be
290 * known
291 * @return the maximum voting power needed for this group, so that all can
292 * accept. This is equal to the min of the vote.getMaxPower
293 */
294 private Integer getMaxPower(Iterable<Vote> votes) {
295 int min = Integer.MAX_VALUE;
296 for (Vote vote : votes) {
297 min = Math.min(min, vote.getMaxPower());
298 }
299 return min;
300 }
301
302 private Map<Bid, Set<Vote>> getAllBids1() {
303 Map<Bid, Set<Vote>> bids = new HashMap<>();
304 for (Votes votes : allvotes.values()) {
305 for (Vote vote : votes.getVotes()) {
306 Bid bid = vote.getBid();
307 Set<Vote> list = bids.get(bid);
308 if (list == null)
309 list = new HashSet<Vote>();
310 list.add(vote);
311 bids.put(bid, list);
312 }
313 }
314 return bids;
315 }
316
317 @Override
318 public int hashCode() {
319 final int prime = 31;
320 int result = 1;
321 result = prime * result
322 + ((allvotes == null) ? 0 : allvotes.hashCode());
323 result = prime * result + ((powers == null) ? 0 : powers.hashCode());
324 return result;
325 }
326
327 @Override
328 public boolean equals(Object obj) {
329 if (this == obj)
330 return true;
331 if (obj == null)
332 return false;
333 if (getClass() != obj.getClass())
334 return false;
335 CollectedVotes other = (CollectedVotes) obj;
336 if (allvotes == null) {
337 if (other.allvotes != null)
338 return false;
339 } else if (!allvotes.equals(other.allvotes))
340 return false;
341 if (powers == null) {
342 if (other.powers != null)
343 return false;
344 } else if (!powers.equals(other.powers))
345 return false;
346 return true;
347 }
348
349 @Override
350 public String toString() {
351 return "CollectedVotes[" + allvotes + "," + powers + "]";
352 }
353
354}
Note: See TracBrowser for help on using the repository browser.