Revision 43e98055
b/stv.py | ||
---|---|---|
46 | 46 |
COUNT_ROUND = "@ROUND" |
47 | 47 |
TRANSFER = ">TRANSFER" |
48 | 48 |
ELIMINATE = "-ELIMINATE" |
49 |
QUOTA ="!QUOTA" |
|
49 | 50 |
ELECT = "+ELECT" |
50 | 51 |
COUNT = ".COUNT" |
51 | 52 |
RANDOM = "*RANDOM" |
... | ... | |
68 | 69 |
_value = 1.0 |
69 | 70 |
|
70 | 71 |
def __init__(self, candidates=[]): |
71 |
self.candidates = filter(None, candidates)
|
|
72 |
self.candidates = candidates
|
|
72 | 73 |
|
73 | 74 |
def add_weight(self, weight): |
74 | 75 |
self.weights.insert(0, weight) |
... | ... | |
107 | 108 |
selected = collected[index] |
108 | 109 |
else: |
109 | 110 |
if not random_generator: |
110 |
print "Missing value for random selection"
|
|
111 |
print "Missing value for random selection among ", collected
|
|
111 | 112 |
sys.exit(1) |
112 | 113 |
selected = random_generator.pop(0) |
113 | 114 |
logger = logging.getLogger(SVT_LOGGER) |
... | ... | |
116 | 117 |
return selected |
117 | 118 |
|
118 | 119 |
|
119 |
def redistribute_ballots(selected, hopefuls, allocated, weight, vote_count):
|
|
120 |
def redistribute_ballots(selected, weight, hopefuls, allocated, vote_count):
|
|
120 | 121 |
"""Redistributes the ballots from selected to the hopefuls. |
121 | 122 |
|
122 | 123 |
Redistributes the ballots currently allocated to the selected |
123 | 124 |
candidate. The ballots are redistributed with the given weight. |
124 |
The total ballot allocation is given by the allocated dict. The current
|
|
125 |
vote count is given by vote_count and is adjusted according to the
|
|
126 |
redistribution. |
|
125 |
The total ballot allocation is given by the allocated map, which
|
|
126 |
is modified accordingly. The current vote count is given by
|
|
127 |
vote_count and is adjusted according to the redistribution.
|
|
127 | 128 |
|
128 | 129 |
""" |
129 | 130 |
|
... | ... | |
172 | 173 |
desc=description)) |
173 | 174 |
allocated[selected][:] = [x for x in allocated[selected] |
174 | 175 |
if x not in transferred ] |
176 |
|
|
177 |
def elect_reject(candidate, vote_count, constituencies, quota_limit, |
|
178 |
current_round, elected, rejected, constituencies_elected): |
|
179 |
"""Elects or rejects the candidate, based on quota restrictions. |
|
180 |
|
|
181 |
If there are no quota limits, the candidate is elected. If there |
|
182 |
are quota limits, the candidate is either elected or rejected, if |
|
183 |
the quota limits are exceeded. The elected and rejected lists |
|
184 |
are modified accordingly, as well as the constituencies_elected map. |
|
185 |
|
|
186 |
Returns true if the candidate is elected, false otherwise. |
|
187 |
""" |
|
175 | 188 |
|
176 |
def count_stv(ballots, droop, seats, rnd_gen=None): |
|
177 |
"""Performs a SVT vote for the given ballots and number of seats. |
|
178 | 189 |
|
190 |
logger = logging.getLogger(SVT_LOGGER) |
|
191 |
quota_exceeded = False |
|
192 |
# If there is a quota limit, check if it is exceeded |
|
193 |
if quota_limit > 0 and candidate in constituencies: |
|
194 |
current_constituency = constituencies[candidate] |
|
195 |
if constituencies_elected[current_constituency] >= quota_limit: |
|
196 |
quota_exceeded = True |
|
197 |
# If the quota limit has been exceeded, reject the candidate |
|
198 |
if quota_exceeded: |
|
199 |
rejected.append((candidate, current_round, vote_count[candidate])) |
|
200 |
d = candidate + " = " + str(vote_count[candidate]) |
|
201 |
msg = LOG_MESSAGE.format(action=Action.QUOTA, desc=d) |
|
202 |
logger.info(msg) |
|
203 |
return False |
|
204 |
# Otherwise, elect the candidate |
|
205 |
else: |
|
206 |
elected.append((candidate, current_round, vote_count[candidate])) |
|
207 |
if constituencies: |
|
208 |
current_constituency = constituencies[candidate] |
|
209 |
constituencies_elected[current_constituency] += 1 |
|
210 |
d = candidate + " = " + str(vote_count[candidate]) |
|
211 |
msg = LOG_MESSAGE.format(action=Action.ELECT, desc=d) |
|
212 |
logger.info(msg) |
|
213 |
return True |
|
214 |
|
|
215 |
def count_stv(ballots, seats, droop = True, constituencies = None, |
|
216 |
quota_limit = 0, rnd_gen=None): |
|
217 |
"""Performs a STV vote for the given ballots and number of seats. |
|
218 |
|
|
219 |
If droop is true the election threshold is calculated according to the |
|
220 |
Droop quota: |
|
221 |
threshold = int(1 + (len(ballots) / (seats + 1.0))) |
|
222 |
otherwise it is calculated according to the following formula: |
|
223 |
threshold = int(math.ceil(1 + len(ballots) / (seats + 1.0))) |
|
224 |
The constituencies argument is a map of candidates to constituencies, if |
|
225 |
any. The quota_limit, if different than zero, is the limit of candidates |
|
226 |
that can be elected by a constituency. |
|
179 | 227 |
""" |
180 | 228 |
|
181 | 229 |
allocated = {} # The allocation of ballots to candidates |
... | ... | |
183 | 231 |
candidates = [] # All candidates |
184 | 232 |
elected = [] # The candidates that have been elected |
185 | 233 |
hopefuls = [] # The candidates that may be elected |
234 |
# The candidates that have been eliminated because of low counts |
|
235 |
eliminated = [] |
|
236 |
# The candidates that have been eliminated because of quota restrictions |
|
237 |
rejected = [] |
|
238 |
# The number of candidates elected per constituency |
|
239 |
constituencies_elected = {} |
|
240 |
for constituency in constituencies.values(): |
|
241 |
constituencies_elected[constituency] = 0 |
|
186 | 242 |
|
187 | 243 |
seed() |
188 | 244 |
|
189 | 245 |
if droop: |
190 |
threshold = int(1 + (len(ballots) / (seats + 1.0)))
|
|
246 |
threshold = int(1 + (len(ballots) / (seats + 1.0))) |
|
191 | 247 |
else: |
192 | 248 |
threshold = int(math.ceil(1 + len(ballots) / (seats + 1.0))) |
193 | 249 |
|
... | ... | |
225 | 281 |
logger.info(LOG_MESSAGE.format(action=Action.COUNT, |
226 | 282 |
desc=description)) |
227 | 283 |
hopefuls_sorted = sorted(hopefuls, key=vote_count.get, reverse=True ) |
228 |
# If there is a surplus try to redistribute the best candidate's votes |
|
229 |
# according to their next preferences |
|
284 |
# If there is a surplus record it so that we can try to |
|
285 |
# redistribute the best candidate's votes according to their |
|
286 |
# next preferences |
|
230 | 287 |
surplus = vote_count[hopefuls_sorted[0]] - threshold |
231 |
remaining_seats = seats - num_elected |
|
232 |
if surplus >= 0 or num_hopefuls <= remaining_seats: |
|
288 |
# If there is either a candidate with surplus votes, or |
|
289 |
# there are hopeful candidates beneath the threshold. |
|
290 |
if surplus >= 0 or num_hopefuls <= (seats - num_elected): |
|
233 | 291 |
best_candidate = randomly_select_first(hopefuls_sorted, |
234 | 292 |
key=vote_count.get, |
235 | 293 |
action=Action.ELECT, |
236 | 294 |
random_generator=rnd_gen) |
295 |
if best_candidate not in hopefuls: |
|
296 |
print "Not a valid candidate: ",best_candidate |
|
297 |
sys.exit(1) |
|
237 | 298 |
hopefuls.remove(best_candidate) |
238 |
elected.append((best_candidate, current_round, |
|
239 |
vote_count[best_candidate])) |
|
240 |
logger.info(LOG_MESSAGE.format(action=Action.ELECT, |
|
241 |
desc=best_candidate |
|
242 |
+ " = " + str(vote_count[best_candidate]))) |
|
299 |
was_elected = elect_reject(best_candidate, vote_count, |
|
300 |
constituencies, quota_limit, |
|
301 |
current_round, |
|
302 |
elected, rejected, |
|
303 |
constituencies_elected) |
|
304 |
if not was_elected: |
|
305 |
redistribute_ballots(best_candidate, 1.0, hopefuls, allocated, |
|
306 |
vote_count) |
|
243 | 307 |
if surplus > 0: |
244 | 308 |
# Calculate the weight for this round |
245 | 309 |
weight = float(surplus) / vote_count[best_candidate] |
246 | 310 |
# Find the next eligible preference for each one of the ballots |
247 | 311 |
# cast for the candidate, and transfer the vote to that |
248 | 312 |
# candidate with its value adjusted by the correct weight. |
249 |
redistribute_ballots(best_candidate, hopefuls, allocated,
|
|
250 |
weight, vote_count)
|
|
251 |
# If there is no surplus, take the least hopeful candidate
|
|
313 |
redistribute_ballots(best_candidate, weight, hopefuls,
|
|
314 |
allocated, vote_count)
|
|
315 |
# If nobody can get elected, take the least hopeful candidate
|
|
252 | 316 |
# (i.e., the hopeful candidate with the less votes) and |
253 | 317 |
# redistribute that candidate's votes. |
254 | 318 |
else: |
... | ... | |
258 | 322 |
action=Action.ELIMINATE, |
259 | 323 |
random_generator=rnd_gen) |
260 | 324 |
hopefuls.remove(worst_candidate) |
261 |
logger.info(LOG_MESSAGE.format(action=Action.ELIMINATE, |
|
262 |
desc=worst_candidate |
|
263 |
+ " = " + str(vote_count[worst_candidate]))) |
|
264 |
redistribute_ballots(worst_candidate, hopefuls, allocated, 1.0, |
|
325 |
eliminated.append(worst_candidate) |
|
326 |
d = worst_candidate + " = " + str(vote_count[worst_candidate]) |
|
327 |
msg = LOG_MESSAGE.format(action=Action.ELIMINATE, desc=d) |
|
328 |
logger.info(msg) |
|
329 |
redistribute_ballots(worst_candidate, 1.0, hopefuls, allocated, |
|
265 | 330 |
vote_count) |
266 | 331 |
|
267 | 332 |
current_round += 1 |
268 | 333 |
num_hopefuls = len(hopefuls) |
269 | 334 |
num_elected = len(elected) |
270 | 335 |
|
336 |
# If there is either a candidate with surplus votes, or |
|
337 |
# there are hopeful candidates beneath the threshold. |
|
338 |
while (seats - num_elected) > 0 and len(eliminated) > 0: |
|
339 |
best_candidate = eliminated.pop() |
|
340 |
elect_reject(best_candidate, vote_count, constituencies, |
|
341 |
quota_limit, current_round, |
|
342 |
elected, rejected, constituencies_elected) |
|
343 |
current_round += 1 |
|
344 |
|
|
271 | 345 |
return elected, vote_count |
272 | 346 |
|
273 | 347 |
if __name__ == "__main__": |
... | ... | |
278 | 352 |
dest='droop', help="don't use droop quota") |
279 | 353 |
parser.add_argument('-s', '--seats', type=int, default=0, |
280 | 354 |
dest='seats', help='number of seats') |
355 |
parser.add_argument('-c', '--constituencies', |
|
356 |
dest='constituencies_file', |
|
357 |
help='input constituencies file') |
|
358 |
parser.add_argument('-q', '--quota', type=int, default=0, |
|
359 |
dest='quota', help='constituency quota') |
|
281 | 360 |
parser.add_argument('-r', '--random', nargs='*', |
282 | 361 |
dest='random', help='random selection results') |
283 | 362 |
parser.add_argument('-l', '--loglevel', default=logging.INFO, |
... | ... | |
291 | 370 |
ballots_file = open(args.ballots_file, 'U') |
292 | 371 |
ballots_reader = csv.reader(ballots_file, delimiter=',', |
293 | 372 |
quotechar='"', |
294 |
skipinitialspace = True)
|
|
373 |
skipinitialspace=True)
|
|
295 | 374 |
for ballot in ballots_reader: |
296 | 375 |
ballots.append(Ballot(ballot)) |
297 | 376 |
|
298 | 377 |
if args.seats == 0: |
299 | 378 |
args.seats = len(ballots) / 2 |
300 |
(elected, vote_count) = count_stv(ballots, args.droop, args.seats, |
|
379 |
|
|
380 |
constituencies = {} |
|
381 |
if args.constituencies_file: |
|
382 |
constituencies_file = open(args.constituencies_file, 'U') |
|
383 |
constituencies_reader = csv.reader(constituencies_file, |
|
384 |
delimiter=',', |
|
385 |
quotechar='"', |
|
386 |
skipinitialspace=True) |
|
387 |
constituency_id = 0 |
|
388 |
for constituency in constituencies_reader: |
|
389 |
for candidate in constituency: |
|
390 |
constituencies[candidate] = constituency_id |
|
391 |
constituency_id += 1 |
|
392 |
|
|
393 |
(elected, vote_count) = count_stv(ballots, args.seats, args.droop, |
|
394 |
constituencies, |
|
395 |
args.quota, |
|
301 | 396 |
args.random) |
302 | 397 |
|
303 | 398 |
print "Results:" |
Also available in: Unified diff