Subversion Repositories Remote Hare Voting

Rev

Rev 4 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 4 Rev 5
Line -... Line 1...
- 
 
 1 
#!/p/python/python
- 
 
 2 
##
- 
 
 3 
## Compute Hare Ballot
- 
 
 4 
##
- 
 
 5 
## Tim Korb (jtk@cs.purdue.edu), May 2007
- 
 
 6 
##
- 
 
 7 
## A few definitions and notes...
- 
 
 8 
##
- 
 
 9 
## tally: dictionary in which the keys are candidate names and the
- 
 
 10 
## values are lists of ballots currently assigned to that candidate
- 
 
 11 
##
- 
 
 12 
## ballot: list of candidates in the order determined by the voter
- 
 
 13 
##
- 
 
 14 
## winners: list of candidates that have reached the quota of ballots
- 
 
 15 
## or have remained in the running long enough to be declared a winner
- 
 
 16 
##
- 
 
 17 
## losers: list of candidates that have been eliminated from the running
- 
 
 18 
##
- 
 
 19 
## Note that plurals are generally used to indicate lists of other
- 
 
 20 
## objects, e.g., ballots is a list of ballots.
- 
 
 21 
##
- 
 
 22 
import cgi
- 
 
 23 
import string
- 
 
 24 
import sys
- 
 
 25 
import math
- 
 
 26 
import random
- 
 
 27 
 
- 
 
 28 
formaction = string.split(sys.argv[0],"/")[-1]
- 
 
 29 
version = "$Id: vote.py,v 1.2 2007/09/07 20:28:57 jtk Exp jtk $"
- 
 
 30 
 
- 
 
 31 
fTrace = 1
- 
 
 32 
fHTML = 1
- 
 
 33 
 
- 
 
 34 
def emitPreHTML(formaction):
- 
 
 35 
    emitHTML("""Content-type: text/html\n
- 
 
 36 
<html>
- 
 
 37 
<body>
- 
 
 38 
<title>Hare Ballot Calculation</title>
- 
 
 39 
    <h1>Hare Ballot Calculation</h1>
- 
 
 40 
    <form enctype="multipart/form-data" method=POST action=%s>
- 
 
 41 
        <table>
- 
 
 42 
        <tr><td>CSV file of ballots:
- 
 
 43 
                <td><input type=file size=70 name=name>
- 
 
 44 
        </table>
- 
 
 45 
        <p>
- 
 
 46 
        <input type=submit name="run1" value="Run 1 Time">
- 
 
 47 
        <input type=submit name="run1000" value="Run 1000 Times">
- 
 
 48 
        <input type=submit name="convert" value="Convert to BLT Format">
- 
 
 49 
    </form>
- 
 
 50 
    <p>
- 
 
 51 
Input file format is given
- 
 
 52 
<a href="http://www.bikmort.com/wiki/index.php?title=Hare_Voting_Procedure">here</a>.
- 
 
 53 
Almost no error checking is done, so be sure to review the trace output.
- 
 
 54 
The source code is available <a href="%s?fetch=yes">here</a>.
- 
 
 55 
<p>
- 
 
 56 
<small>%s</small>
- 
 
 57 
<hr>
- 
 
 58 
<pre>
- 
 
 59 
""" % (formaction, formaction, version))
- 
 
 60 
    return
- 
 
 61 
 
- 
 
 62 
def emitPostHTML():
- 
 
 63 
    emitHTML("""</pre>
- 
 
 64 
</body>
- 
 
 65 
</html>
- 
 
 66 
""")
- 
 
 67 
    return
- 
 
 68 
 
- 
 
 69 
def emitHTML(s):
- 
 
 70 
    global fHTML
- 
 
 71 
    if fHTML: print s
- 
 
 72 
    return
- 
 
 73 
 
- 
 
 74 
def trace(s):
- 
 
 75 
    global fTrace
- 
 
 76 
    if fTrace: print s
- 
 
 77 
    return
- 
 
 78 
 
- 
 
 79 
def findWinner(winners, losers, tally, quota, nWinners):
- 
 
 80 
    for candidate in tally.keys():
- 
 
 81 
        if candidate not in winners and len(tally[candidate]) >= quota:
- 
 
 82 
            return candidate
- 
 
 83 
 
- 
 
 84 
    # Check to see if only enough candidates remain
- 
 
 85 
    n = 0
- 
 
 86 
    last = ""
- 
 
 87 
    for candidate in tally.keys():
- 
 
 88 
        if candidate not in winners and candidate not in losers:
- 
 
 89 
            last = candidate
- 
 
 90 
            n = n + 1
- 
 
 91 
    if nWinners - len(winners) >= n:
- 
 
 92 
        return last
- 
 
 93 
    return
- 
 
 94 
 
- 
 
 95 
def redistributeWinner(winner, winners, losers, tally, quota):
- 
 
 96 
    excess = len(tally[winner]) - quota
- 
 
 97 
    if excess <= 0:
- 
 
 98 
	trace("\tno excess ballots to redistribute")
- 
 
 99 
    else:
- 
 
 100 
	trace("\tredistributing %d excess ballot(s) at random from %s" %
- 
 
 101 
	      (excess, winner))
- 
 
 102 
	while len(tally[winner]) > quota:
- 
 
 103 
	    i = int(random.uniform(0, len(tally[winner])))
- 
 
 104 
	    trace("\trandom choice = ballot %d" % (i+1))
- 
 
 105 
	    ballot = tally[winner][i]
- 
 
 106 
	    tally[winner] = tally[winner][0:i] + tally[winner][i+1:]
- 
 
 107 
	    redistributeBallot(ballot, winner, winners, losers, tally)
- 
 
 108 
    traceTally(quota, tally)
- 
 
 109 
 
- 
 
 110 
def redistributeBallot(ballot, candidateFrom, winners, losers, tally):
- 
 
 111 
    for candidateTo in ballot:
- 
 
 112 
	if candidateTo not in winners and candidateTo not in losers:
- 
 
 113 
	    trace("\tto %s: %s" % (candidateTo, ballot))
- 
 
 114 
	    if not tally.has_key(candidateTo): tally[candidateTo] = []
- 
 
 115 
	    tally[candidateTo].append(ballot)
- 
 
 116 
	    ballot = ""
- 
 
 117 
	    break
- 
 
 118 
    if ballot:
- 
 
 119 
	trace("\tineffective ballot dropped: %s" % ballot)
- 
 
 120 
 
- 
 
 121 
def findLoser(losers, winners, tally):
- 
 
 122 
    cMin = sys.maxint  # least number of votes for candidate loser
- 
 
 123 
    lMin = []          # list of candidates with least votes
- 
 
 124 
    for c in tally.keys():
- 
 
 125 
        if c not in losers and c not in winners and len(tally[c]) <= cMin:
- 
 
 126 
	    if len(tally[c]) == cMin:
- 
 
 127 
		lMin.append(c)
- 
 
 128 
	    else:
- 
 
 129 
		lMin = [c]
- 
 
 130 
		cMin = len(tally[c])
- 
 
 131 
    trace("\nELIMINATING LOW CANDIDATE RANDOMLY FROM %s" % lMin)
- 
 
 132 
    if len(lMin) == 0:
- 
 
 133 
        return None
- 
 
 134 
    else:
- 
 
 135 
        return random.choice(lMin)
- 
 
 136 
 
- 
 
 137 
def redistributeLoser(loser, losers, winners, tally, quota):
- 
 
 138 
    excess = len(tally[loser])
- 
 
 139 
    if excess <= 0:
- 
 
 140 
	trace("\tno ballots to redistribute")
- 
 
 141 
    else:
- 
 
 142 
	trace("\tredistributing %d ballot(s) from %s" % (excess, loser))
- 
 
 143 
	while len(tally[loser]) > 0:
- 
 
 144 
	    ballot = tally[loser][0]
- 
 
 145 
	    tally[loser] = tally[loser][1:]
- 
 
 146 
	    redistributeBallot(ballot, loser, winners, losers, tally)
- 
 
 147 
    traceTally(quota, tally)
- 
 
 148 
    return
- 
 
 149 
 
- 
 
 150 
def traceTally(quota, tally):
- 
 
 151 
    global fTrace
- 
 
 152 
    if not fTrace: return
- 
 
 153 
    trace("\nCURRENT ASSIGNMENT OF BALLOTS (%d needed to win)" % quota)
- 
 
 154 
    for candidate in tally.keys():
- 
 
 155 
        trace("\t%s:" % candidate)
- 
 
 156 
        for ballot in tally[candidate]:
- 
 
 157 
            trace("\t\t%s" % ballot)
- 
 
 158 
    return
- 
 
 159 
 
- 
 
 160 
# The basic Single Transferable Vote algorithm with Hare quota
- 
 
 161 
#
- 
 
 162 
# while winners < nWinners:
- 
 
 163 
#   if a candidate has more than quota votes:
- 
 
 164 
#       redistribute excess votes to next priority candidate
- 
 
 165 
#   else:
- 
 
 166 
#       eliminate lowest ranking candidate
- 
 
 167 
#       redistribute wasted votes to next priority candidate
- 
 
 168 
#
- 
 
 169 
def dotally(nWinners, ballots):
- 
 
 170 
    nBallots = len(ballots)
- 
 
 171 
    quota = int(math.ceil((nBallots + 1.0)/(nWinners + 1)))
- 
 
 172 
 
- 
 
 173 
    trace("INPUT SUMMARY")
- 
 
 174 
    trace("\t%d ballots" % nBallots)
- 
 
 175 
    trace("\tChoosing %s winners" % nWinners)
- 
 
 176 
    trace("\tNeed ceil((%d + 1)/(%d + 1)) = %d ballots to win" %
- 
 
 177 
	  (nBallots, nWinners, quota))
- 
 
 178 
 
- 
 
 179 
    # Create initial tally
- 
 
 180 
    #
- 
 
 181 
    tally = {}
- 
 
 182 
    for ballot in ballots:
- 
 
 183 
        candidate = ballot[0]
- 
 
 184 
        if not tally.has_key(candidate):
- 
 
 185 
            tally[candidate] = []
- 
 
 186 
        tally[candidate].append(ballot)
- 
 
 187 
    traceTally(quota, tally)
- 
 
 188
- 
 
 189 
    winners = []
- 
 
 190 
    losers = []
- 
 
 191 
 
- 
 
 192 
    while len(winners) < nWinners:
- 
 
 193 
        winner = findWinner(winners, losers, tally, quota, nWinners)
- 
 
 194 
        if winner:
- 
 
 195 
            winners.append(winner)
- 
 
 196 
            trace("\nSELECTION #%d: %s" % (len(winners), winner))
- 
 
 197 
            redistributeWinner(winner, winners, losers, tally, quota)
- 
 
 198 
        else:
- 
 
 199 
            loser = findLoser(losers, winners, tally)
- 
 
 200 
            if loser:
- 
 
 201 
                losers.append(loser)
- 
 
 202 
                trace("\nELIMINATED: %s" % loser)
- 
 
 203 
                redistributeLoser(loser, losers, winners, tally, quota)
- 
 
 204 
            else:
- 
 
 205 
                trace("Not enough chosen candidates to fill all positions")
- 
 
 206 
                break
- 
 
 207 
 
- 
 
 208 
    return winners
- 
 
 209 
 
- 
 
 210 
# Parse input file
- 
 
 211 
#
- 
 
 212 
# input: lines of comma-separated values
- 
 
 213 
#	nWinners, ...ignored fields...
- 
 
 214 
#	candidate1, ballot1rank, ballot2rank, ...
- 
 
 215 
#	candidate2, ballot1rank, ballot2rank, ...
- 
 
 216 
#
- 
 
 217 
# output: list of lists of ballots
- 
 
 218 
#	[[1stcandbal1, 2ndcandbal1, ...], [1stcandbal2, 2ndcandbal2, ...], ...]
- 
 
 219 
 
- 
 
 220 
def parsecontents(contents):
- 
 
 221 
    lines = string.split(contents, "\r\n")
- 
 
 222 
    fields = string.split(lines[0], ",")
- 
 
 223 
    nWinners = int(fields[0])
- 
 
 224 
 
- 
 
 225 
    votes = []
- 
 
 226 
    for line in lines[1:]:
- 
 
 227 
        fields = string.split(line, ",")
- 
 
 228 
        candidate = fields[0]
- 
 
 229 
	positions = fields[1:]
- 
 
 230 
        ballotnumber = 0
- 
 
 231 
	for position in positions:
- 
 
 232 
            if position:
- 
 
 233 
                votes.append([ballotnumber, int(position), candidate])
- 
 
 234 
            ballotnumber = ballotnumber + 1
- 
 
 235 
 
- 
 
 236 
    votes.sort()
- 
 
 237 
 
- 
 
 238 
    ballots = []
- 
 
 239 
    ballotnumber = ""
- 
 
 240 
    ballot = ""
- 
 
 241 
    for triple in votes:
- 
 
 242 
        if ballotnumber == triple[0]:
- 
 
 243 
	    ballot.append(triple[2])
- 
 
 244 
        else:
- 
 
 245 
            if ballot:
- 
 
 246 
                ballots.append(ballot)
- 
 
 247 
            ballot = [triple[2]]
- 
 
 248 
            ballotnumber = triple[0]
- 
 
 249 
 
- 
 
 250 
    ballots.append(ballot)
- 
 
 251 
    return nWinners, ballots
- 
 
 252 
 
- 
 
 253 
def main():
- 
 
 254 
    global fTrace
- 
 
 255 
    emitPreHTML(formaction)
- 
 
 256 
 
- 
 
 257 
    form = cgi.FieldStorage()
- 
 
 258 
 
- 
 
 259 
    if not form:
- 
 
 260 
        emitHTML("Enter file name and press a button to see results.")
- 
 
 261 
    elif form.has_key("fetch"):
- 
 
 262 
	source = open(formaction).read()
- 
 
 263 
	print cgi.escape(source)
- 
 
 264 
    elif not form.has_key("name"):
- 
 
 265 
        emitHTML("Error: no file received")
- 
 
 266 
    elif not form["name"].filename:
- 
 
 267 
        emitHTML("Error: file name missing")
- 
 
 268 
    else:
- 
 
 269 
        name = form["name"].filename
- 
 
 270 
        contents = form["name"].value
- 
 
 271 
 
- 
 
 272 
	trace("INPUT FILE")
- 
 
 273 
	trace(contents)
- 
 
 274 
 
- 
 
 275 
        nWinners, ballots = parsecontents(contents)
- 
 
 276 
	if form.has_key("run1"):
- 
 
 277 
	    results = dotally(nWinners, ballots)
- 
 
 278 
	    print "\nFINAL RESULTS"
- 
 
 279 
	    for winner in results:
1 
print "Hello there."
 280 
		print "\t%s" % winner
- 
 
 281 
	elif form.has_key("run1000"):
- 
 
 282 
	    print "RUNNING 1000 TIMES"
- 
 
 283 
	    fTrace = 0
- 
 
 284 
	    summary = {}
- 
 
 285 
	    for i in range(1000):
- 
 
 286 
		results = str(dotally(nWinners, ballots))
- 
 
 287 
		# print "Run %2d: %s" % (i+1, results)
- 
 
 288 
		if not summary.has_key(results):
- 
 
 289 
		    summary[results] = 0
- 
 
 290 
		summary[results] = summary[results] + 1
- 
 
 291 
	    print "\nSUMMARY"
- 
 
 292 
	    l = summary.items()
- 
 
 293 
	    l.sort(lambda x,y: cmp(y[1], x[1]))
- 
 
 294 
	    for pair in l:
- 
 
 295 
		print "%2d %s" % (pair[1], pair[0])
- 
 
 296 
	elif form.has_key("convert"):
- 
 
 297 
	    print "Convert feature not supported yet"
- 
 
 298 
	else:
- 
 
 299 
	    print "UNEXPECTED SUBMIT BUTTON: %s" % form
- 
 
 300
- 
 
 301 
    emitPostHTML()
- 
 
 302 
    return
- 
 
 303 
 
- 
 
 304 
main()