Author: humbedooh
Date: Thu Mar 26 19:10:31 2015
New Revision: 1669412
URL: http://svn.apache.org/r1669412
Log:
use stv_tool.py's calculations instead, they actually work.
Modified:
steve/trunk/pysteve/lib/plugins/stv.py
Modified: steve/trunk/pysteve/lib/plugins/stv.py
URL:
http://svn.apache.org/viewvc/steve/trunk/pysteve/lib/plugins/stv.py?rev=1669412&r1=1669411&r2=1669412&view=diff
==============================================================================
--- steve/trunk/pysteve/lib/plugins/stv.py (original)
+++ steve/trunk/pysteve/lib/plugins/stv.py Thu Mar 26 19:10:31 2015
@@ -17,8 +17,19 @@
""" STV Voting Plugin """
import re, json, random
+ELECTED = 1
+HOPEFUL = 2
+ELIMINATED = 4
+ALMOST = 8
+
+ERROR_MARGIN = 0.00001
+BILLIONTH = 0.000000001
+
+
from lib import constants
+debug = []
+
def validateSTV(vote, issue):
"Tries to validate a vote, returns why if not valid, None otherwise"
letters = [chr(i) for i in range(ord('a'), ord('a') +
len(issue['candidates']))]
@@ -64,99 +75,307 @@ def getproportion(votes, winners, step,
-def tallySTV(votes, issue):
- m = re.match(r"stv(\d+)", issue['type'])
- if not m:
- raise Exception("Not an STV vote!")
-
- numseats = int(m.group(1))
- candidates = []
- for c in issue['candidates']:
- candidates.append(c['name'])
-
- debug = []
-
- # Set up letters for mangling
- letters = [chr(i) for i in range(ord('a'), ord('a') + len(candidates))]
- cc = "".join(letters)
-
- # Keep score of votes
- points = {}
-
- # Set all scores to 0 at first
- for c in cc:
- points[c] = 0
- # keep score of winners
- winners = []
- turn = 0
- # Find quota to win a seat
- quota = ( len(votes) / (numseats + 1) ) + 1
- debug.append("Seats available: %u. Votes cast: %u" % (numseats,
len(votes)))
- debug.append("Votes required to win a seat: %u ( (%u/(%u+1))+1 )" %
(quota, len(votes), numseats))
+def run_vote(names, votes, num_seats):
+ candidates = CandidateList(names)
-
- surplus = 0
- # While we still have seats to fill
- if not len(candidates) < numseats:
- y = 0
- while len(winners) < numseats and len(cc) > 0 and turn < 1000: #Don't
run for > 1000 iterations, that's a bug
- turn += 1
+ # name -> Candidate
+ remap = dict((c.name, c) for c in candidates.l)
- s = 0
+ # Turn VOTES into a list of ordered-lists of Candidate objects
+ votes = [[remap[n] for n in choices] for choices in votes.values()]
+
+ if candidates.count(ELECTED + HOPEFUL) <= num_seats:
+ debug.append('All candidates elected')
+ candidates.change_state(HOPEFUL, ELECTED)
+ return
+ if num_seats <= 0:
+ candidates.change_state(HOPEFUL, ELIMINATED)
+ return
+
+ quota = None # not used on first pass
+ iteration = 1
+ while candidates.count(ELECTED) < num_seats:
+ debug.append('Iteration %d' % iteration)
+ iteration += 1
+ quota = iterate_one(quota, votes, candidates, num_seats)
+ candidates.reverse_random()
+
+ debug.append('All seats full')
+ candidates.change_state(HOPEFUL, ELIMINATED)
+
+ return candidates.retval()
+
+
+class CandidateList(object):
+ def __init__(self, names):
+ num_cand = len(names)
+ randset = generate_random(num_cand)
+
+ self.l = [ ]
+ for n, r in zip(names, randset):
+ c = Candidate(n, r, num_cand-1)
+ self.l.append(c)
+
+ def count(self, state):
+ count = 0
+ for c in self.l:
+ if (c.status & state) != 0:
+ count += 1
+ return count
+ def retval(self):
+ winners = []
+ for c in self.l:
+ if c.status == ELECTED:
+ winners.append(c.name)
+ return winners
- # Get votes
- xpoints = getproportion(votes, winners, 0, surplus)
- surplus = 0
- if turn == 1:
- debug.append("Initial tally: %s" % json.dumps(xpoints))
- else:
- debug.append("Proportional move: %s" % json.dumps(xpoints))
-
- for x in xpoints:
- points[x] += xpoints[x]
- mq = 0
-
- # For each candidate letter, find if someone won a seat
- for c in cc:
- if len(winners) >= numseats:
- break
- if points[c] >= quota and not c in winners:
- winners.append(c)
- debug.append("WINNER: %s got elected in with %u votes! %u
seats remain" % (c, points[c], numseats - len(winners)))
- cc.replace(c, "")
- mq += 1
- surplus += points[c] - quota
-
- # If we found no winners in this round, eliminate the lowest
scorer and retally
- if mq < 1:
- lowest = 99999999
- lowestC = None
- for c in cc:
- if points[c] < lowest:
- lowest = points[c]
- lowestC = c
-
- debug.append("DRAW: %s is eliminated" % lowestC)
- if lowestC:
- cc.replace(lowestC, "")
- else:
- debug.append("No more canididates?? buggo?")
- break
- y += 1
+ def change_state(self, from_state, to_state):
+ any_changed = False
+ for c in self.l:
+ if (c.status & from_state) != 0:
+ c.status = to_state
+ if to_state == ELECTED:
+ c.elect()
+ elif to_state == ELIMINATED:
+ c.eliminate()
+ any_changed = True
+ return any_changed
+
+ def reverse_random(self):
+ # Flip the values to create a different ordering among candidates. Note
+ # that this will alternate the domain between [0.0, 1.0) and (0.0, 1.0]
+ for c in self.l:
+ c.rand = 1.0 - c.rand
+
+ def adjust_weights(self, quota):
+ for c in self.l:
+ if c.status == ELECTED:
+ c.adjust_weight(quota)
+
+ def print_results(self):
+ for c in self.l:
+ print '%-40s%selected' % (c.name, c.status == ELECTED and ' ' or ' not ')
+
+ def dbg_display_tables(self, excess):
+ total = excess
+ for c in self.l:
+ debug.append('%-20s %15.9f %15.9f' % (c.name, c.weight, c.vote))
+ total += c.vote
+ debug.append('%-20s %15s %15.9f' %( 'Non-transferable', ' ', excess))
+ debug.append('%-20s %15s %15.9f' % ( 'Total', ' ', total))
+
+
+class Candidate(object):
+ def __init__(self, name, rand, ahead):
+ self.name = name
+ self.rand = rand
+ self.ahead = ahead
+ self.status = HOPEFUL
+ self.weight = 1.0
+ self.vote = None # calculated later
+
+ def elect(self):
+ self.status = ELECTED
+ debug.append('Elected: %s' % self.name)
+
+ def eliminate(self):
+ self.status = ELIMINATED
+ self.weight = 0.0
+ debug.append('Eliminated: %s' % self.name)
+
+ def adjust_weight(self, quota):
+ assert quota is not None
+ self.weight = (self.weight * quota) / self.vote
+
+ def __cmp__(self, other):
+ if self.ahead < other.ahead:
+ return -1
+ if self.ahead == other.ahead:
+ return cmp(self.vote, other.vote)
+ return 1
+
+
+def iterate_one(quota, votes, candidates, num_seats):
+ # assume that: count(ELECTED) < num_seats
+ if candidates.count(ELECTED + HOPEFUL) <= num_seats:
+ debug.append('All remaining candidates elected')
+ candidates.change_state(HOPEFUL, ELECTED)
+ return None
+
+ candidates.adjust_weights(quota)
- # Everyone's a winner!!
+ changed, new_quota, surplus = recalc(votes, candidates, num_seats)
+ if not changed and surplus < ERROR_MARGIN:
+ debug.append('Remove Lowest (forced)')
+ exclude_lowest(candidates.l)
+ return new_quota
+
+
+def recalc(votes, candidates, num_seats):
+ excess = calc_totals(votes, candidates)
+ calc_aheads(candidates)
+ candidates.dbg_display_tables(excess)
+ quota = calc_quota(len(votes), excess, num_seats)
+ any_changed = elect(quota, candidates, num_seats)
+ surplus = calc_surplus(quota, candidates)
+ any_changed |= try_remove_lowest(surplus, candidates)
+ return any_changed, quota, surplus
+
+
+def calc_totals(votes, candidates):
+ for c in candidates.l:
+ c.vote = 0.0
+ excess = 0.0
+ for choices in votes:
+ vote = 1.0
+ for c in choices:
+ if c.status == HOPEFUL:
+ c.vote += vote
+ vote = 0.0
+ break
+ if c.status != ELIMINATED:
+ wv = c.weight * vote # weighted vote
+ c.vote += wv
+ vote -= wv
+ if vote == 0.0: # nothing left to distribute
+ break
+ excess += vote
+ return excess
+
+
+def calc_aheads(candidates):
+ c_sorted = sorted(candidates.l)
+ last = 0
+ for i in range(1, len(c_sorted)+1):
+ if i == len(c_sorted) or c_sorted[last] != c_sorted[i]:
+ for c in c_sorted[last:i]:
+ c.ahead = (i - 1) + last
+ last = i
+
+
+def calc_quota(num_voters, excess, num_seats):
+ if num_seats > 2:
+ quota = (float(num_voters) - excess) / (float(num_seats + 1) + BILLIONTH)
+ else:
+ quota = (float(num_voters) - excess) / float(num_seats + 1)
+ if quota < ERROR_MARGIN:
+ raise Exception('Internal Error - very low quota')
+ debug.append('Quota = %.9f' % quota)
+ return quota
+
+
+def elect(quota, candidates, num_seats):
+ for c in candidates.l:
+ if c.status == HOPEFUL and c.vote >= quota:
+ c.status = ALMOST
+
+ any_changed = False
+
+ while candidates.count(ELECTED + ALMOST) > num_seats:
+ debug.append('Vote tiebreaker! voters: %d seats: %d' %(
candidates.count(ELECTED + ALMOST), num_seats))
+ candidates.change_state(HOPEFUL, ELIMINATED)
+ exclude_lowest(candidates.l)
+ any_changed = True # we changed the candidates via exclude_lowest()
+
+ any_changed |= candidates.change_state(ALMOST, ELECTED)
+ return any_changed
+
+
+def calc_surplus(quota, candidates):
+ surplus = 0.0
+ for c in candidates.l:
+ if c.status == ELECTED:
+ surplus += c.vote - quota
+ debug.append('Total Surplus = %.9f' % surplus)
+ return surplus
+
+
+def try_remove_lowest(surplus, candidates):
+ lowest1 = 1e18
+ lowest2 = 1e18
+ which = None
+ for c in candidates.l:
+ if c.status == HOPEFUL and c.vote < lowest1:
+ lowest1 = c.vote
+ which = c
+ for c in candidates.l:
+ if c != which and c.status != ELIMINATED and c.vote < lowest2:
+ lowest2 = c.vote
+
+ diff = lowest2 - lowest1
+ if diff >= 0.0:
+ debug.append('Lowest Difference = %.9f - %.9f = %.9f' % ( lowest2,
lowest1, diff))
+ if diff > surplus:
+ debug.append('Remove Lowest (unforced)')
+ which.eliminate()
+ return True
+ return False
+
+
+def exclude_lowest(candidates):
+ ### use: ahead = len(candidates) ??
+ ahead = 1000000000. # greater than any possible candidate.ahead
+ rand = 1.1 # greater than any possible candidate.rand
+ which = None
+ used_rand = False
+
+ for c in candidates:
+ if c.status == HOPEFUL or c.status == ALMOST:
+ if c.ahead < ahead:
+ ahead = c.ahead
+ rand = c.rand
+ which = c
+ use_rand = False
+ elif c.ahead == ahead:
+ use_rand = True
+ if c.rand < rand:
+ ran = c.rand
+ which = c
+
+ if use_rand:
+ debug.append('Random choice used!')
+
+ assert which
+ which.eliminate()
+
+
+def generate_random(count):
+ random.seed(0) ### choose a seed based on input? for now: repeatable.
+ while True:
+ # Generate COUNT values in [0.0, 1.0)
+ values = [random.random() for x in range(count)]
+
+ # Ensure there are no duplicates
+ for value in values:
+ if values.count(value) > 1:
+ break
else:
- winners = letters
+ # The loop finished without breaking out
+ return values
- # Compile list of winner names
+
+def tallySTV(votes, issue):
+
+ m = re.match(r"stv(\d+)", issue['type'])
+ if not m:
+ raise Exception("Not an STV vote!")
+
+ numseats = int(m.group(1))
+ candidates = {}
+ z = 0
+ for c in issue['candidates']:
+ candidates[chr(ord('a') + z)] = c['name']
+ z += 1
+
+ # run the stv calc
+ winners = run_vote(candidates, votes, numseats)
winnernames = []
- random.shuffle(winners)
+
for c in winners:
- i = ord(c) - ord('a')
- winnernames.append(candidates[i])
+ winnernames.append(candidates[c])
# Return the data
return {
