stv_tool.py was named with an underscore so that it is importable. You shouldn't need to copy/paste all of its code ...
(tho of course, it doesn't live in lib/ ... maybe it should 'svn mv' into lib?) On Thu, Mar 26, 2015 at 2:10 PM, <humbed...@apache.org> wrote: > 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 { > > >
