root / stv.py @ 50eaf441
History | View | Annotate | Download (17.5 kB)
1 | cd255017 | Panos Louridas | # Copyright 2011 GRNET S.A. All rights reserved.
|
---|---|---|---|
2 | cd255017 | Panos Louridas | #
|
3 | cd255017 | Panos Louridas | # Redistribution and use in source and binary forms, with or without
|
4 | cd255017 | Panos Louridas | # modification, are permitted provided that the following conditions
|
5 | cd255017 | Panos Louridas | # are met:
|
6 | cd255017 | Panos Louridas | #
|
7 | cd255017 | Panos Louridas | # 1. Redistributions of source code must retain the above copyright
|
8 | cd255017 | Panos Louridas | # notice, this list of conditions and the following disclaimer.
|
9 | cd255017 | Panos Louridas | #
|
10 | cd255017 | Panos Louridas | # 2. Redistributions in binary form must reproduce the above
|
11 | cd255017 | Panos Louridas | # copyright notice, this list of conditions and the following
|
12 | cd255017 | Panos Louridas | # disclaimer in the documentation and/or other materials provided
|
13 | cd255017 | Panos Louridas | # with the distribution.
|
14 | cd255017 | Panos Louridas | #
|
15 | cd255017 | Panos Louridas | # THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
|
16 | cd255017 | Panos Louridas | # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
|
17 | cd255017 | Panos Louridas | # TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
|
18 | cd255017 | Panos Louridas | # PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
|
19 | cd255017 | Panos Louridas | # CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
20 | cd255017 | Panos Louridas | # SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
21 | cd255017 | Panos Louridas | # LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
|
22 | cd255017 | Panos Louridas | # USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
|
23 | cd255017 | Panos Louridas | # ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
|
24 | cd255017 | Panos Louridas | # OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
|
25 | cd255017 | Panos Louridas | # OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
26 | cd255017 | Panos Louridas | # SUCH DAMAGE.
|
27 | cd255017 | Panos Louridas | #
|
28 | cd255017 | Panos Louridas | # The views and conclusions contained in the software and
|
29 | cd255017 | Panos Louridas | # documentation are those of the authors and should not be interpreted
|
30 | cd255017 | Panos Louridas | # as representing official policies, either expressed or implied, of
|
31 | cd255017 | Panos Louridas | # GRNET S.A.
|
32 | cd255017 | Panos Louridas | |
33 | cd255017 | Panos Louridas | from operator import mul, itemgetter |
34 | cd255017 | Panos Louridas | from random import random, seed |
35 | cd255017 | Panos Louridas | import logging |
36 | cd255017 | Panos Louridas | import sys |
37 | f60cffcf | Panos Louridas | import math |
38 | d7628da9 | Panos Louridas | import csv |
39 | d7628da9 | Panos Louridas | import argparse |
40 | cd255017 | Panos Louridas | |
41 | cd255017 | Panos Louridas | SVT_LOGGER = 'SVT'
|
42 | fdd44e42 | Panos Louridas | LOGGER_FORMAT = '%(message)s'
|
43 | 0695112d | Panos Louridas | LOG_MESSAGE = "{action} {desc}"
|
44 | cd255017 | Panos Louridas | |
45 | 0695112d | Panos Louridas | class Action: |
46 | 2d1ec6b5 | Panos Louridas | COUNT_ROUND = "@ROUND"
|
47 | 2d1ec6b5 | Panos Louridas | TRANSFER = ">TRANSFER"
|
48 | 2d1ec6b5 | Panos Louridas | ELIMINATE = "-ELIMINATE"
|
49 | 43e98055 | Panos Louridas | QUOTA ="!QUOTA"
|
50 | 2d1ec6b5 | Panos Louridas | ELECT = "+ELECT"
|
51 | 2d1ec6b5 | Panos Louridas | COUNT = ".COUNT"
|
52 | cb368e3b | Panos Louridas | ZOMBIES = "~ZOMBIES"
|
53 | 2d1ec6b5 | Panos Louridas | RANDOM = "*RANDOM"
|
54 | 2d1ec6b5 | Panos Louridas | THRESHOLD = "^THRESHOLD"
|
55 | cd255017 | Panos Louridas | |
56 | cd255017 | Panos Louridas | class Ballot: |
57 | cd255017 | Panos Louridas | """A ballot class for Single Transferable Voting.
|
58 | cd255017 | Panos Louridas |
|
59 | cd255017 | Panos Louridas | The ballot class contains an ordered list of candidates (in
|
60 | cd255017 | Panos Louridas | decreasing order of preference) and an ordered list of weights
|
61 | cd255017 | Panos Louridas | (new weights are added to the front of the list). The index of the
|
62 | cd255017 | Panos Louridas | current preference (for the first count and subsequent rounds)
|
63 | 79948f90 | Panos Louridas | is also kept.
|
64 | cd255017 | Panos Louridas |
|
65 | cd255017 | Panos Louridas | """
|
66 | cd255017 | Panos Louridas | |
67 | cd255017 | Panos Louridas | candidates = [] |
68 | 70a98c11 | Panos Louridas | weights = [1.0]
|
69 | 79948f90 | Panos Louridas | current_preference = 0
|
70 | 70a98c11 | Panos Louridas | _value = 1.0
|
71 | cd255017 | Panos Louridas | |
72 | cd255017 | Panos Louridas | def __init__(self, candidates=[]): |
73 | 43e98055 | Panos Louridas | self.candidates = candidates
|
74 | cd255017 | Panos Louridas | |
75 | cd255017 | Panos Louridas | def add_weight(self, weight): |
76 | cd255017 | Panos Louridas | self.weights.insert(0, weight) |
77 | cd255017 | Panos Louridas | self._value *= weight
|
78 | cd255017 | Panos Louridas | |
79 | cd255017 | Panos Louridas | def get_value(self): |
80 | cd255017 | Panos Louridas | return self._value |
81 | 2d1ec6b5 | Panos Louridas | |
82 | 2d1ec6b5 | Panos Louridas | def randomly_select_first(sequence, key, action, random_generator=None): |
83 | cd255017 | Panos Louridas | """Selects the first item of equals in a sorted sequence of items.
|
84 | cd255017 | Panos Louridas |
|
85 | cd255017 | Panos Louridas | For the given sorted sequence, returns the first item if it
|
86 | cd255017 | Panos Louridas | is different than the second; if there are ties so that there
|
87 | cd255017 | Panos Louridas | are items with equal values, it randomly selects among those items.
|
88 | cd255017 | Panos Louridas | The value of each item in the sequence is provided by applying the
|
89 | 35531055 | Panos Louridas | function key to the item. The action parameter indicates the context
|
90 | 35531055 | Panos Louridas | in which the random selection takes place (election or elimination).
|
91 | 2d1ec6b5 | Panos Louridas | random_generator, if given, is the function that produces the random
|
92 | 2d1ec6b5 | Panos Louridas | selection.
|
93 | cd255017 | Panos Louridas |
|
94 | cd255017 | Panos Louridas | """
|
95 | 2d1ec6b5 | Panos Louridas | |
96 | cd255017 | Panos Louridas | first_value = key(sequence[0])
|
97 | cd255017 | Panos Louridas | collected = [] |
98 | cd255017 | Panos Louridas | for item in sequence: |
99 | cd255017 | Panos Louridas | if key(item) == first_value:
|
100 | cd255017 | Panos Louridas | collected.append(item) |
101 | cd255017 | Panos Louridas | else:
|
102 | cd255017 | Panos Louridas | break
|
103 | feabfa93 | Panos Louridas | index = 0
|
104 | 361b3942 | Panos Louridas | selected = collected[index] |
105 | 2d1ec6b5 | Panos Louridas | num_eligibles = len(collected)
|
106 | 2d1ec6b5 | Panos Louridas | if (num_eligibles > 1): |
107 | 2d1ec6b5 | Panos Louridas | if random_generator is None: |
108 | 2d1ec6b5 | Panos Louridas | index = int(random() * num_eligibles)
|
109 | 361b3942 | Panos Louridas | selected = collected[index] |
110 | 2d1ec6b5 | Panos Louridas | else:
|
111 | 361b3942 | Panos Louridas | if not random_generator: |
112 | 43e98055 | Panos Louridas | print "Missing value for random selection among ", collected |
113 | 361b3942 | Panos Louridas | sys.exit(1)
|
114 | 361b3942 | Panos Louridas | selected = random_generator.pop(0)
|
115 | 35531055 | Panos Louridas | logger = logging.getLogger(SVT_LOGGER) |
116 | 35531055 | Panos Louridas | description = "{0} from {1} to {2}".format(selected, collected, action)
|
117 | 35531055 | Panos Louridas | logger.info(LOG_MESSAGE.format(action=Action.RANDOM, desc=description)) |
118 | 361b3942 | Panos Louridas | return selected
|
119 | cd255017 | Panos Louridas | |
120 | cd255017 | Panos Louridas | |
121 | 43e98055 | Panos Louridas | def redistribute_ballots(selected, weight, hopefuls, allocated, vote_count): |
122 | cd255017 | Panos Louridas | """Redistributes the ballots from selected to the hopefuls.
|
123 | cd255017 | Panos Louridas |
|
124 | cd255017 | Panos Louridas | Redistributes the ballots currently allocated to the selected
|
125 | cd255017 | Panos Louridas | candidate. The ballots are redistributed with the given weight.
|
126 | 43e98055 | Panos Louridas | The total ballot allocation is given by the allocated map, which
|
127 | 43e98055 | Panos Louridas | is modified accordingly. The current vote count is given by
|
128 | 43e98055 | Panos Louridas | vote_count and is adjusted according to the redistribution.
|
129 | cd255017 | Panos Louridas |
|
130 | cd255017 | Panos Louridas | """
|
131 | cd255017 | Panos Louridas | |
132 | cd255017 | Panos Louridas | logger = logging.getLogger(SVT_LOGGER) |
133 | cd255017 | Panos Louridas | transferred = [] |
134 | 79948f90 | Panos Louridas | # Keep a hash of ballot moves for logging purposes.
|
135 | aaba50db | Panos Louridas | # Keys are a tuple of the form (from_recipient, to_recipient, value)
|
136 | aaba50db | Panos Louridas | # where value is the current value of the ballot. Each tuple points
|
137 | aaba50db | Panos Louridas | # to the ballot being moved.
|
138 | 0695112d | Panos Louridas | moves = {} |
139 | cd255017 | Panos Louridas | |
140 | cd255017 | Panos Louridas | for ballot in allocated[selected]: |
141 | cd255017 | Panos Louridas | reallocated = False
|
142 | 79948f90 | Panos Louridas | i = ballot.current_preference + 1
|
143 | cd255017 | Panos Louridas | while not reallocated and i < len(ballot.candidates): |
144 | cd255017 | Panos Louridas | recipient = ballot.candidates[i] |
145 | cd255017 | Panos Louridas | if recipient in hopefuls: |
146 | 79948f90 | Panos Louridas | ballot.current_preference = i |
147 | cd255017 | Panos Louridas | ballot.add_weight(weight) |
148 | 79948f90 | Panos Louridas | current_value = ballot.get_value() |
149 | cd255017 | Panos Louridas | if recipient in allocated: |
150 | cd255017 | Panos Louridas | allocated[recipient].append(ballot) |
151 | cd255017 | Panos Louridas | else:
|
152 | cd255017 | Panos Louridas | allocated[recipient] = [ballot] |
153 | de57b302 | Panos Louridas | if recipient in vote_count: |
154 | 79948f90 | Panos Louridas | vote_count[recipient] += current_value |
155 | de57b302 | Panos Louridas | else:
|
156 | 79948f90 | Panos Louridas | vote_count[recipient] = current_value |
157 | 79948f90 | Panos Louridas | vote_count[selected] -= current_value |
158 | cd255017 | Panos Louridas | reallocated = True
|
159 | 79948f90 | Panos Louridas | if (selected, recipient, current_value) in moves: |
160 | aaba50db | Panos Louridas | moves[(selected, recipient, current_value)].append(ballot) |
161 | 0695112d | Panos Louridas | else:
|
162 | aaba50db | Panos Louridas | moves[(selected, recipient, current_value)] = [ballot] |
163 | cd255017 | Panos Louridas | transferred.append(ballot) |
164 | cd255017 | Panos Louridas | else:
|
165 | cd255017 | Panos Louridas | i += 1
|
166 | aaba50db | Panos Louridas | for move, ballots in moves.iteritems(): |
167 | aaba50db | Panos Louridas | times = len(ballots)
|
168 | 79948f90 | Panos Louridas | description = "from {0} to {1} {2}*{3}={4}".format(move[0], |
169 | 79948f90 | Panos Louridas | move[1],
|
170 | ad21afde | Panos Louridas | times, |
171 | 79948f90 | Panos Louridas | move[2],
|
172 | d736e543 | Panos Louridas | times * move[2])
|
173 | d736e543 | Panos Louridas | logger.debug(LOG_MESSAGE.format(action=Action.TRANSFER, |
174 | d736e543 | Panos Louridas | desc=description)) |
175 | cd255017 | Panos Louridas | allocated[selected][:] = [x for x in allocated[selected] |
176 | cd255017 | Panos Louridas | if x not in transferred ] |
177 | 43e98055 | Panos Louridas | |
178 | 43e98055 | Panos Louridas | def elect_reject(candidate, vote_count, constituencies, quota_limit, |
179 | 43e98055 | Panos Louridas | current_round, elected, rejected, constituencies_elected): |
180 | 43e98055 | Panos Louridas | """Elects or rejects the candidate, based on quota restrictions.
|
181 | 43e98055 | Panos Louridas |
|
182 | 43e98055 | Panos Louridas | If there are no quota limits, the candidate is elected. If there
|
183 | 43e98055 | Panos Louridas | are quota limits, the candidate is either elected or rejected, if
|
184 | 43e98055 | Panos Louridas | the quota limits are exceeded. The elected and rejected lists
|
185 | 43e98055 | Panos Louridas | are modified accordingly, as well as the constituencies_elected map.
|
186 | 43e98055 | Panos Louridas |
|
187 | 43e98055 | Panos Louridas | Returns true if the candidate is elected, false otherwise.
|
188 | 43e98055 | Panos Louridas | """
|
189 | cd255017 | Panos Louridas | |
190 | 2d1ec6b5 | Panos Louridas | |
191 | 43e98055 | Panos Louridas | logger = logging.getLogger(SVT_LOGGER) |
192 | 43e98055 | Panos Louridas | quota_exceeded = False
|
193 | 43e98055 | Panos Louridas | # If there is a quota limit, check if it is exceeded
|
194 | 43e98055 | Panos Louridas | if quota_limit > 0 and candidate in constituencies: |
195 | 43e98055 | Panos Louridas | current_constituency = constituencies[candidate] |
196 | 43e98055 | Panos Louridas | if constituencies_elected[current_constituency] >= quota_limit:
|
197 | 43e98055 | Panos Louridas | quota_exceeded = True
|
198 | 43e98055 | Panos Louridas | # If the quota limit has been exceeded, reject the candidate
|
199 | 43e98055 | Panos Louridas | if quota_exceeded:
|
200 | 43e98055 | Panos Louridas | rejected.append((candidate, current_round, vote_count[candidate])) |
201 | 43e98055 | Panos Louridas | d = candidate + " = " + str(vote_count[candidate]) |
202 | 43e98055 | Panos Louridas | msg = LOG_MESSAGE.format(action=Action.QUOTA, desc=d) |
203 | 43e98055 | Panos Louridas | logger.info(msg) |
204 | 43e98055 | Panos Louridas | return False |
205 | 43e98055 | Panos Louridas | # Otherwise, elect the candidate
|
206 | 43e98055 | Panos Louridas | else:
|
207 | 43e98055 | Panos Louridas | elected.append((candidate, current_round, vote_count[candidate])) |
208 | 43e98055 | Panos Louridas | if constituencies:
|
209 | 43e98055 | Panos Louridas | current_constituency = constituencies[candidate] |
210 | 43e98055 | Panos Louridas | constituencies_elected[current_constituency] += 1
|
211 | 43e98055 | Panos Louridas | d = candidate + " = " + str(vote_count[candidate]) |
212 | 43e98055 | Panos Louridas | msg = LOG_MESSAGE.format(action=Action.ELECT, desc=d) |
213 | 43e98055 | Panos Louridas | logger.info(msg) |
214 | 43e98055 | Panos Louridas | return True |
215 | 43e98055 | Panos Louridas | |
216 | cb368e3b | Panos Louridas | def count_description(vote_count, candidates): |
217 | cb368e3b | Panos Louridas | """Returns a string with count results.
|
218 | cb368e3b | Panos Louridas |
|
219 | cb368e3b | Panos Louridas | The string is of the form of {0} = {1} separated by ; where each {0}
|
220 | cb368e3b | Panos Louridas | is a candidate and each {1} is the corresponding vote count.
|
221 | cb368e3b | Panos Louridas | """
|
222 | cb368e3b | Panos Louridas | |
223 | cb368e3b | Panos Louridas | return ';'.join(map(lambda x: "{0} = {1}".format(x, vote_count[x]), |
224 | cb368e3b | Panos Louridas | candidates)) |
225 | cb368e3b | Panos Louridas | |
226 | cb368e3b | Panos Louridas | |
227 | 43e98055 | Panos Louridas | def count_stv(ballots, seats, droop = True, constituencies = None, |
228 | 43e98055 | Panos Louridas | quota_limit = 0, rnd_gen=None): |
229 | 43e98055 | Panos Louridas | """Performs a STV vote for the given ballots and number of seats.
|
230 | 43e98055 | Panos Louridas |
|
231 | 43e98055 | Panos Louridas | If droop is true the election threshold is calculated according to the
|
232 | 43e98055 | Panos Louridas | Droop quota:
|
233 | 43e98055 | Panos Louridas | threshold = int(1 + (len(ballots) / (seats + 1.0)))
|
234 | 43e98055 | Panos Louridas | otherwise it is calculated according to the following formula:
|
235 | 43e98055 | Panos Louridas | threshold = int(math.ceil(1 + len(ballots) / (seats + 1.0)))
|
236 | 43e98055 | Panos Louridas | The constituencies argument is a map of candidates to constituencies, if
|
237 | 43e98055 | Panos Louridas | any. The quota_limit, if different than zero, is the limit of candidates
|
238 | 43e98055 | Panos Louridas | that can be elected by a constituency.
|
239 | cd255017 | Panos Louridas | """
|
240 | cd255017 | Panos Louridas | |
241 | 2d1ec6b5 | Panos Louridas | allocated = {} # The allocation of ballots to candidates
|
242 | 2d1ec6b5 | Panos Louridas | vote_count = {} # A hash of ballot counts, indexed by candidates
|
243 | 2d1ec6b5 | Panos Louridas | candidates = [] # All candidates
|
244 | 2d1ec6b5 | Panos Louridas | elected = [] # The candidates that have been elected
|
245 | 2d1ec6b5 | Panos Louridas | hopefuls = [] # The candidates that may be elected
|
246 | 43e98055 | Panos Louridas | # The candidates that have been eliminated because of low counts
|
247 | 43e98055 | Panos Louridas | eliminated = [] |
248 | 43e98055 | Panos Louridas | # The candidates that have been eliminated because of quota restrictions
|
249 | 43e98055 | Panos Louridas | rejected = [] |
250 | 43e98055 | Panos Louridas | # The number of candidates elected per constituency
|
251 | 43e98055 | Panos Louridas | constituencies_elected = {} |
252 | 43e98055 | Panos Louridas | for constituency in constituencies.values(): |
253 | 43e98055 | Panos Louridas | constituencies_elected[constituency] = 0
|
254 | cd255017 | Panos Louridas | |
255 | cd255017 | Panos Louridas | seed() |
256 | cd255017 | Panos Louridas | |
257 | 361b3942 | Panos Louridas | if droop:
|
258 | 43e98055 | Panos Louridas | threshold = int(1 + (len(ballots) / (seats + 1.0))) |
259 | 361b3942 | Panos Louridas | else:
|
260 | 361b3942 | Panos Louridas | threshold = int(math.ceil(1 + len(ballots) / (seats + 1.0))) |
261 | cd255017 | Panos Louridas | |
262 | cd255017 | Panos Louridas | logger = logging.getLogger(SVT_LOGGER) |
263 | 2d1ec6b5 | Panos Louridas | logger.info(LOG_MESSAGE.format(action=Action.THRESHOLD, |
264 | 2d1ec6b5 | Panos Louridas | desc=threshold)) |
265 | cd255017 | Panos Louridas | |
266 | 2d1ec6b5 | Panos Louridas | # Do initial count
|
267 | cd255017 | Panos Louridas | for ballot in ballots: |
268 | cd255017 | Panos Louridas | selected = ballot.candidates[0]
|
269 | cd255017 | Panos Louridas | for candidate in ballot.candidates: |
270 | cd255017 | Panos Louridas | if candidate not in candidates: |
271 | cd255017 | Panos Louridas | candidates.append(candidate) |
272 | d7628da9 | Panos Louridas | vote_count[candidate] = 0
|
273 | 50eaf441 | Panos Louridas | if candidate not in allocated: |
274 | 50eaf441 | Panos Louridas | allocated[candidate] = [] |
275 | 50eaf441 | Panos Louridas | allocated[selected].append(ballot) |
276 | d7628da9 | Panos Louridas | vote_count[selected] += 1
|
277 | cd255017 | Panos Louridas | |
278 | 2d1ec6b5 | Panos Louridas | # In the beginning, all candidates are hopefuls
|
279 | cd255017 | Panos Louridas | hopefuls = [x for x in candidates] |
280 | cd255017 | Panos Louridas | |
281 | 2d1ec6b5 | Panos Louridas | # Start rounds
|
282 | 2d1ec6b5 | Panos Louridas | current_round = 1
|
283 | 2d1ec6b5 | Panos Louridas | num_elected = len(elected)
|
284 | 2d1ec6b5 | Panos Louridas | num_hopefuls = len(hopefuls)
|
285 | 2d1ec6b5 | Panos Louridas | while num_elected < seats and num_hopefuls > 0: |
286 | cb368e3b | Panos Louridas | # Log round
|
287 | 0695112d | Panos Louridas | logger.info(LOG_MESSAGE.format(action=Action.COUNT_ROUND, |
288 | 0695112d | Panos Louridas | desc=current_round)) |
289 | d736e543 | Panos Louridas | # Log count
|
290 | cb368e3b | Panos Louridas | description = count_description(vote_count, hopefuls) |
291 | cb368e3b | Panos Louridas | |
292 | 2d1ec6b5 | Panos Louridas | logger.info(LOG_MESSAGE.format(action=Action.COUNT, |
293 | 2d1ec6b5 | Panos Louridas | desc=description)) |
294 | 2d1ec6b5 | Panos Louridas | hopefuls_sorted = sorted(hopefuls, key=vote_count.get, reverse=True ) |
295 | 43e98055 | Panos Louridas | # If there is a surplus record it so that we can try to
|
296 | 43e98055 | Panos Louridas | # redistribute the best candidate's votes according to their
|
297 | 43e98055 | Panos Louridas | # next preferences
|
298 | 2d1ec6b5 | Panos Louridas | surplus = vote_count[hopefuls_sorted[0]] - threshold
|
299 | 43e98055 | Panos Louridas | # If there is either a candidate with surplus votes, or
|
300 | 43e98055 | Panos Louridas | # there are hopeful candidates beneath the threshold.
|
301 | 43e98055 | Panos Louridas | if surplus >= 0 or num_hopefuls <= (seats - num_elected): |
302 | 2d1ec6b5 | Panos Louridas | best_candidate = randomly_select_first(hopefuls_sorted, |
303 | 35531055 | Panos Louridas | key=vote_count.get, |
304 | 2d1ec6b5 | Panos Louridas | action=Action.ELECT, |
305 | 2d1ec6b5 | Panos Louridas | random_generator=rnd_gen) |
306 | 43e98055 | Panos Louridas | if best_candidate not in hopefuls: |
307 | 43e98055 | Panos Louridas | print "Not a valid candidate: ",best_candidate |
308 | 43e98055 | Panos Louridas | sys.exit(1)
|
309 | 2d1ec6b5 | Panos Louridas | hopefuls.remove(best_candidate) |
310 | 43e98055 | Panos Louridas | was_elected = elect_reject(best_candidate, vote_count, |
311 | 43e98055 | Panos Louridas | constituencies, quota_limit, |
312 | 43e98055 | Panos Louridas | current_round, |
313 | 43e98055 | Panos Louridas | elected, rejected, |
314 | 43e98055 | Panos Louridas | constituencies_elected) |
315 | 43e98055 | Panos Louridas | if not was_elected: |
316 | 43e98055 | Panos Louridas | redistribute_ballots(best_candidate, 1.0, hopefuls, allocated,
|
317 | 43e98055 | Panos Louridas | vote_count) |
318 | 2d1ec6b5 | Panos Louridas | if surplus > 0: |
319 | 2d1ec6b5 | Panos Louridas | # Calculate the weight for this round
|
320 | 2d1ec6b5 | Panos Louridas | weight = float(surplus) / vote_count[best_candidate]
|
321 | 2d1ec6b5 | Panos Louridas | # Find the next eligible preference for each one of the ballots
|
322 | 2d1ec6b5 | Panos Louridas | # cast for the candidate, and transfer the vote to that
|
323 | 2d1ec6b5 | Panos Louridas | # candidate with its value adjusted by the correct weight.
|
324 | 43e98055 | Panos Louridas | redistribute_ballots(best_candidate, weight, hopefuls, |
325 | 43e98055 | Panos Louridas | allocated, vote_count) |
326 | 43e98055 | Panos Louridas | # If nobody can get elected, take the least hopeful candidate
|
327 | cd255017 | Panos Louridas | # (i.e., the hopeful candidate with the less votes) and
|
328 | cd255017 | Panos Louridas | # redistribute that candidate's votes.
|
329 | cd255017 | Panos Louridas | else:
|
330 | 2d1ec6b5 | Panos Louridas | hopefuls_sorted.reverse() |
331 | cd255017 | Panos Louridas | worst_candidate = randomly_select_first(hopefuls_sorted, |
332 | 35531055 | Panos Louridas | key=vote_count.get, |
333 | 2d1ec6b5 | Panos Louridas | action=Action.ELIMINATE, |
334 | 2d1ec6b5 | Panos Louridas | random_generator=rnd_gen) |
335 | 2d1ec6b5 | Panos Louridas | hopefuls.remove(worst_candidate) |
336 | 43e98055 | Panos Louridas | eliminated.append(worst_candidate) |
337 | 43e98055 | Panos Louridas | d = worst_candidate + " = " + str(vote_count[worst_candidate]) |
338 | 43e98055 | Panos Louridas | msg = LOG_MESSAGE.format(action=Action.ELIMINATE, desc=d) |
339 | 43e98055 | Panos Louridas | logger.info(msg) |
340 | 43e98055 | Panos Louridas | redistribute_ballots(worst_candidate, 1.0, hopefuls, allocated,
|
341 | de57b302 | Panos Louridas | vote_count) |
342 | 2d1ec6b5 | Panos Louridas | |
343 | 2d1ec6b5 | Panos Louridas | current_round += 1
|
344 | 2d1ec6b5 | Panos Louridas | num_hopefuls = len(hopefuls)
|
345 | 2d1ec6b5 | Panos Louridas | num_elected = len(elected)
|
346 | cd255017 | Panos Louridas | |
347 | 43e98055 | Panos Louridas | # If there is either a candidate with surplus votes, or
|
348 | 43e98055 | Panos Louridas | # there are hopeful candidates beneath the threshold.
|
349 | 43e98055 | Panos Louridas | while (seats - num_elected) > 0 and len(eliminated) > 0: |
350 | cb368e3b | Panos Louridas | logger.info(LOG_MESSAGE.format(action=Action.COUNT_ROUND, |
351 | cb368e3b | Panos Louridas | desc=current_round)) |
352 | cb368e3b | Panos Louridas | description = count_description(vote_count, eliminated) |
353 | cb368e3b | Panos Louridas | |
354 | cb368e3b | Panos Louridas | logger.info(LOG_MESSAGE.format(action=Action.ZOMBIES, |
355 | cb368e3b | Panos Louridas | desc=description)) |
356 | cb368e3b | Panos Louridas | |
357 | 43e98055 | Panos Louridas | best_candidate = eliminated.pop() |
358 | 43e98055 | Panos Louridas | elect_reject(best_candidate, vote_count, constituencies, |
359 | 43e98055 | Panos Louridas | quota_limit, current_round, |
360 | 43e98055 | Panos Louridas | elected, rejected, constituencies_elected) |
361 | 43e98055 | Panos Louridas | current_round += 1
|
362 | 43e98055 | Panos Louridas | |
363 | 0695112d | Panos Louridas | return elected, vote_count
|
364 | cd255017 | Panos Louridas | |
365 | cd255017 | Panos Louridas | if __name__ == "__main__": |
366 | d7628da9 | Panos Louridas | parser = argparse.ArgumentParser(description='Perform STV')
|
367 | 361b3942 | Panos Louridas | parser.add_argument('-b', '--ballots', default='sys.stdin', |
368 | d7628da9 | Panos Louridas | dest='ballots_file', help='input ballots file') |
369 | 361b3942 | Panos Louridas | parser.add_argument('-n', '--not_droop', action="store_false", |
370 | 361b3942 | Panos Louridas | dest='droop', help="don't use droop quota") |
371 | 361b3942 | Panos Louridas | parser.add_argument('-s', '--seats', type=int, default=0, |
372 | 79948f90 | Panos Louridas | dest='seats', help='number of seats') |
373 | 43e98055 | Panos Louridas | parser.add_argument('-c', '--constituencies', |
374 | 43e98055 | Panos Louridas | dest='constituencies_file',
|
375 | 43e98055 | Panos Louridas | help='input constituencies file')
|
376 | 43e98055 | Panos Louridas | parser.add_argument('-q', '--quota', type=int, default=0, |
377 | 43e98055 | Panos Louridas | dest='quota', help='constituency quota') |
378 | 361b3942 | Panos Louridas | parser.add_argument('-r', '--random', nargs='*', |
379 | 361b3942 | Panos Louridas | dest='random', help='random selection results') |
380 | 361b3942 | Panos Louridas | parser.add_argument('-l', '--loglevel', default=logging.INFO, |
381 | d736e543 | Panos Louridas | dest='loglevel', help='logging level') |
382 | d7628da9 | Panos Louridas | args = parser.parse_args() |
383 | d88a1c50 | Panos Louridas | |
384 | d88a1c50 | Panos Louridas | stream_handler = logging.StreamHandler(stream=sys.stdout) |
385 | d88a1c50 | Panos Louridas | logger = logging.getLogger(SVT_LOGGER) |
386 | d88a1c50 | Panos Louridas | logger.setLevel(args.loglevel) |
387 | d88a1c50 | Panos Louridas | logger.addHandler(stream_handler) |
388 | d88a1c50 | Panos Louridas | |
389 | cd255017 | Panos Louridas | ballots = [] |
390 | d7628da9 | Panos Louridas | ballots_file = sys.stdin |
391 | d7628da9 | Panos Louridas | if args.ballots_file != 'sys.stdin': |
392 | 361b3942 | Panos Louridas | ballots_file = open(args.ballots_file, 'U') |
393 | d7628da9 | Panos Louridas | ballots_reader = csv.reader(ballots_file, delimiter=',',
|
394 | d7628da9 | Panos Louridas | quotechar='"',
|
395 | 43e98055 | Panos Louridas | skipinitialspace=True)
|
396 | d7628da9 | Panos Louridas | for ballot in ballots_reader: |
397 | d7628da9 | Panos Louridas | ballots.append(Ballot(ballot)) |
398 | cd255017 | Panos Louridas | |
399 | 79948f90 | Panos Louridas | if args.seats == 0: |
400 | 79948f90 | Panos Louridas | args.seats = len(ballots) / 2 |
401 | 43e98055 | Panos Louridas | |
402 | 43e98055 | Panos Louridas | constituencies = {} |
403 | 43e98055 | Panos Louridas | if args.constituencies_file:
|
404 | 43e98055 | Panos Louridas | constituencies_file = open(args.constituencies_file, 'U') |
405 | 43e98055 | Panos Louridas | constituencies_reader = csv.reader(constituencies_file, |
406 | 43e98055 | Panos Louridas | delimiter=',',
|
407 | 43e98055 | Panos Louridas | quotechar='"',
|
408 | 43e98055 | Panos Louridas | skipinitialspace=True)
|
409 | 43e98055 | Panos Louridas | constituency_id = 0
|
410 | 43e98055 | Panos Louridas | for constituency in constituencies_reader: |
411 | 43e98055 | Panos Louridas | for candidate in constituency: |
412 | 43e98055 | Panos Louridas | constituencies[candidate] = constituency_id |
413 | 43e98055 | Panos Louridas | constituency_id += 1
|
414 | 43e98055 | Panos Louridas | |
415 | 43e98055 | Panos Louridas | (elected, vote_count) = count_stv(ballots, args.seats, args.droop, |
416 | 43e98055 | Panos Louridas | constituencies, |
417 | 43e98055 | Panos Louridas | args.quota, |
418 | 361b3942 | Panos Louridas | args.random) |
419 | cd255017 | Panos Louridas | |
420 | cd255017 | Panos Louridas | print "Results:" |
421 | d736e543 | Panos Louridas | for result in elected: |
422 | d736e543 | Panos Louridas | print result |