method supported at the moment is CloneproofSSD.
--- /dev/null
+# Extra full path added to fix some require errors on some installations.
+
+require File.dirname(__FILE__) + '/rubyvote/election'
+require File.dirname(__FILE__) + '/rubyvote/condorcet'
+require File.dirname(__FILE__) + '/rubyvote/positional'
+require File.dirname(__FILE__) + '/rubyvote/runoff'
+require File.dirname(__FILE__) + '/rubyvote/range'
+
--- /dev/null
+# election library -- a ruby library for elections
+# copyright © 2005 MIT Media Lab and Benjamin Mako Hill
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+# General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301, USA.
+
+#################################################################
+## ==== condorcet.rb ====
+##
+## This file contains Condorcet election methods. Currently this
+## includes a pure condorcet and a CloneproofSSD implementation
+## modeled after the Python-based Debian project election code and
+## that gives the same results in several tested corner cases.
+#################################################################
+
+##################################################################
+## CondorcetVote Classes and SubClasses
+##
+## The CondorcetVote class is subclassed by the PureCondorcetVote and
+## the CloneproofSSDVote classes but should not be used directly.
+
+class CondorcetVote < ElectionVote
+
+ def tally_vote(vote=nil)
+
+ vote.each_with_index do |winner, index|
+ # only run through this if this *is* preferred to something
+ break if vote.length - 1 == index
+ losers = vote.last( vote.length - index )
+
+ losers.each do |loser|
+ next if winner == loser
+
+ @votes[winner] = Hash.new unless @votes.has_key?(winner)
+ @votes[loser] = Hash.new unless @votes.has_key?(loser)
+
+ if @votes[winner].has_key?(loser)
+ @votes[winner][loser] += 1
+ else
+ @votes[winner][loser] = 1
+ end
+
+ # make sure we have a comparable object
+ @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner )
+
+ @candidates << loser unless @candidates.include?( loser )
+ end
+
+ @candidates << winner unless @candidates.include?( winner )
+ end
+ end
+
+ protected
+ def verify_vote(vote=nil)
+ vote.instance_of?( Array ) and
+ vote == vote.uniq
+ end
+
+end
+
+class PureCondorcetVote < CondorcetVote
+ def result
+ PureCondorcetResult.new( self )
+ end
+end
+
+class CloneproofSSDVote < CondorcetVote
+ def result
+ CloneproofSSDResult.new( self )
+ end
+end
+
+
+##################################################################
+## CondorcetResult Classes and SubClasses
+##
+## The CondorcetResult class is subclassed by the PureCondorcetResult
+## and the CloneproofSSDResult classes but should not be used
+## directly.
+
+class CondorcetResult < ElectionResult
+ def initialize(voteobj=nil)
+ unless voteobj and voteobj.kind_of?( CondorcetVote )
+ raise ArgumentError, "You must pass a CondorcetVote array.", caller
+ end
+ super(voteobj)
+ end
+
+ def defeats(candidates=nil, votes=nil)
+ candidates = @election.candidates unless candidates
+ votes = @election.votes unless votes
+
+ defeats = Array.new
+ candidates.each do |candidate|
+ candidates.each do |challenger|
+ next if candidate == challenger
+ if votes[candidate][challenger] > votes[challenger][candidate]
+ defeats << [ candidate, challenger ]
+ end
+ end
+ end
+
+ defeats
+ end
+
+end
+
+class PureCondorcetResult < CondorcetResult
+ def initialize(voteobj=nil)
+ super(voteobj)
+ self.condorcet()
+ end
+
+ protected
+ def condorcet
+ votes = @election.votes
+ candidates = @election.candidates
+
+ victors = Hash.new
+ candidates.each do |candidate|
+ victors[candidate] = Array.new
+ end
+
+ self.defeats.each do |pair|
+ winner, loser = *pair
+ victors[winner] << loser
+ end
+
+ winners = @election.candidates.find_all do |candidate|
+ victors[candidate].length == @election.candidates.length - 1
+ end
+
+ @winners << winners if winners.length == 1
+ end
+end
+
+class CloneproofSSDResult < CondorcetResult
+ def initialize(voteobj=nil)
+ super(voteobj)
+ @winners = self.cpssd()
+ end
+
+ protected
+ def cpssd
+ votes = @election.votes
+ candidates = *@election.candidates
+
+ def in_schwartz_set?(candidate, candidates, transitive_defeats)
+ candidates.each do |challenger|
+ next if candidate == challenger
+
+ if transitive_defeats.include?( [ challenger, candidate ] ) and
+ not transitive_defeats.include?( [ candidate, challenger ] )
+ return false
+ end
+ end
+ return true
+ end
+
+ loop do
+
+ # see the array with the standard defeats
+ transitive_defeats = self.defeats(candidates, votes)
+
+ candidates.each do |cand1|
+ candidates.each do |cand2|
+ candidates.each do |cand3|
+ if transitive_defeats.include?( [ cand2, cand1 ] ) and
+ transitive_defeats.include?( [ cand1, cand3 ] ) and
+ not transitive_defeats.include?( [ cand2, cand3 ] ) and
+ not cand2 == cand3
+ transitive_defeats << [ cand2, cand3 ]
+ end
+ end
+ end
+ end
+
+ schwartz_set = Array.new
+ candidates.each do |candidate|
+ if in_schwartz_set?(candidate, candidates, transitive_defeats)
+ schwartz_set << candidate
+ end
+ end
+
+ candidates = schwartz_set
+
+ # look through the schwartz set now for defeats
+ defeats = self.defeats(candidates, votes)
+
+ # it's a tie or there's only one option
+ break if defeats.length == 0
+
+ def is_weaker_defeat?( pair1, pair2 )
+ votes = @election.votes
+ if votes[pair1[0]][pair1[1]] > votes[pair2[0]][pair2[1]]
+ return true
+ elsif votes[pair1[0]][pair1[1]] == votes[pair2[0]][pair2[1]] and
+ votes[pair1[1]][pair1[0]] > votes[pair2[1]][pair2[0]]
+ return true
+ else
+ false
+ end
+ end
+
+ defeats.sort! do |pair1, pair2|
+ if is_weaker_defeat?( pair1, pair2 )
+ +1
+ elsif is_weaker_defeat?( pair2, pair1 )
+ -1
+ else
+ 0
+ end
+ end
+
+ votes[defeats[0][0]][defeats[0][1]] = 0
+ votes[defeats[0][1]][defeats[0][0]] = 0
+
+ end
+
+ return candidates
+ end
+
+end
--- /dev/null
+# election library -- a ruby library for elections
+# copyright © 2005 MIT Media Lab and Benjamin Mako Hill
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+# General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301, USA.
+
+#################################################################
+## ==== election.rb ====
+##
+## This file contains the core ElectionVote and ElectionResults
+## classes and the most common and simple election methods including
+## plurality and approval voting.
+#################################################################
+
+##################################################################
+## ElectionVote Classes and SubClasses
+##
+## There classes are used to store, verify, and "tally" (i.e. count
+## votes for the standard Election superclass and for the most common
+## types of elections.
+
+class ElectionVote
+ attr_reader :votes
+ attr_reader :candidates
+
+ def initialize(votes=nil)
+ @votes = Hash.new unless defined?(@votes)
+ @candidates = Array.new unless defined?(@candidates)
+
+ if votes
+ if votes.instance_of?( Array )
+ votes.each do |vote|
+ self.tally_vote(vote) if self.verify_vote(vote)
+ end
+ else
+ raise ElectionError, "Votes must be in the form of an array.", caller
+ end
+ end
+ end
+
+ protected
+ # by default, this is set to look if the vote is defined. it should
+ # be overridden in each class
+ def verify_vote(vote=nil)
+ vote ? true : false
+ end
+
+ # by default, this does nothing. it must be redefined in any subclass
+ def tally_vote
+ self.verify_vote(vote)
+ end
+end
+
+class PluralityVote < ElectionVote
+ def result
+ PluralityResult.new(self)
+ end
+
+ protected
+ def verify_vote(vote=nil)
+ vote.instance_of?( String )
+ end
+
+ def tally_vote(candidate)
+ if @votes.has_key?(candidate)
+ @votes[candidate] += 1
+ else
+ @votes[candidate] = 1
+ @candidates << candidate
+ end
+ end
+end
+
+class ApprovalVote < PluralityVote
+ def result
+ ApprovalResult.new(self)
+ end
+
+ protected
+ def verify_vote(vote=nil)
+ vote.instance_of?( Array ) and vote.length >= 1
+ end
+
+ def tally_vote(approvals)
+ approvals.each {|candidate| super(candidate)}
+ end
+end
+
+
+##################################################################
+## Election Result Classes
+##
+
+## There classes are used to compute and report the results of an
+## election. In almost all cases, these will be returned by the
+## #results method of a corresponding ElectionVote subclass.
+
+class ElectionResult
+ attr_reader :winners
+
+ def initialize(voteobj=nil)
+ unless voteobj and voteobj.kind_of?( ElectionVote )
+ raise ArgumentError, "You must pass a ElectionVote array.", caller
+ end
+
+ @election = voteobj
+ @winners = Array.new
+ end
+
+ def winner
+ @winners[0] if @winners.length > 0
+ end
+
+ def winner?
+ @winners.length > 0
+ end
+
+end
+
+class PluralityResult < ElectionResult
+ attr_reader :ranked_candidates
+
+ def initialize(voteobj=nil)
+ super(voteobj)
+
+ votes = @election.votes
+ candidates = @election.candidates
+
+ @ranked_candidates = votes.sort do |a, b|
+ b[1] <=> a[1]
+ end.collect {|a| a[0]}
+
+ # winners are anyone who has the same number of votes as the
+ # first person
+ @winners = @ranked_candidates.find_all do |i|
+ votes[i] == votes[@ranked_candidates[0]]
+ end
+ end
+end
+
+# this class is complete because results for approval are computed
+# identically to results from plurality
+class ApprovalResult < PluralityResult
+end
+
+class ElectionError < ArgumentError
+end
+
--- /dev/null
+# election library -- a ruby library for elections
+# copyright © 2005 MIT Media Lab and Benjamin Mako Hill
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
+
+# This program is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+# General Public License for more details.
+
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+# 02110-1301, USA.
+
+#################################################################
+## ==== positional.rb ====
+##
+## This file contains positional election methods. Currently only
+## includes an implementation of the Borda count election method.
+#################################################################
+
+##################################################################
+## BordaVote and BordaResult Classes
+##
+## These classes inherit from and/or are modeled after the classes in
+## election.rb and condorcet.rb
+
+class BordaVote < ElectionVote
+
+ def initialize(votes=nil)
+ @candidates = Array.new
+ votes.each do |vote|
+ @candidates = vote.uniq if vote.uniq.length > candidates.length
+ end
+ super(votes)
+ end
+
+ def tally_vote(vote)
+ points = candidates.length - 1
+ vote.each do |candidate|
+ @votes[candidate] = points
+ points -= 1
+ end
+ end
+
+ def verify_vote(vote=nil)
+ vote.instance_of?( Array ) and
+ vote == vote.uniq
+ end
+
+ def result
+ BordaResult.new(self)
+ end
+end
+
+class BordaResult < ElectionResult
+ def initialize(voteobj=nil)
+ super(voteobj)
+ votes = @election.votes
+
+ @ranked_candidates = votes.sort do |a, b|
+ b[1] <=> a[1]
+ end.collect {|i| i[0]}
+
+ @winners = @ranked_candidates.find_all do |i|
+ votes[i] == votes[@ranked_candidates[0]]
+ end
+ end
+
+end
--- /dev/null
+# Range voting as described in wikipedia.
+# (http://en.wikipedia.org/wiki/Range_voting)
+
+class RangeVote < ElectionVote
+ def initialize(votes = nil, range = 1..10)
+ @valid_range = range
+ super(votes)
+ end
+
+ def result
+ RangeResult.new(self)
+ end
+
+ protected
+ def verify_vote(vote=nil)
+ vote.instance_of?(Hash) && vote.all?{|c,score| @valid_range.include?(score)}
+ end
+
+ def tally_vote(vote)
+ vote.each do |candidate, score|
+ if @votes.has_key?(candidate)
+ @votes[candidate] += score
+ else
+ @votes[candidate] = score
+ @candidates << candidate
+ end
+ end
+ end
+end
+
+class RangeResult < PluralityResult
+end
--- /dev/null
+class InstantRunoffVote < ElectionVote
+ def initialize(votes=nil)
+ @candidates = Array.new
+ votes.each do |vote|
+ @candidates = vote.uniq if vote.uniq.length > candidates.length
+ end
+ super(votes)
+ @candidates.each do |candidate|
+ @votes[candidate] = [0, Hash.new] unless @votes.has_key?(candidate)
+ end
+ end
+
+ def result
+ InstantRunoffResult.new(self)
+ end
+
+ protected
+ def tally_vote(vote)
+ votecopy = vote.dup
+ candidate = votecopy.shift
+ votes[candidate] = [0, Hash.new] unless votes.has_key?(candidate)
+ votes[candidate][0] += 1
+ if votes[candidate][1].has_key?(votecopy)
+ votes[candidate][1][votecopy] += 1
+ else
+ votes[candidate][1][votecopy] = 1
+ end
+ end
+
+ def verify_vote(vote=nil)
+ vote.instance_of?( Array ) and
+ vote == vote.uniq
+ end
+end
+
+class InstantRunoffResult < ElectionResult
+ attr_reader :ranked_candidates
+
+ def initialize(voteobj=nil)
+ unless voteobj and voteobj.kind_of?( InstantRunoffVote )
+ raise ArgumentError, "You must pass an InstantRunoffVote array.", caller
+ end
+ super(voteobj)
+
+ votes = @election.votes.clone
+ candidates = @election.candidates
+ majority = votes.inject(0) {|n, value| n + value[1][0]}/2 + 1
+ @ranked_candidates = Array.new()
+ ranked_candidates = Array.new()
+
+ loop do
+ ranked_candidates = votes.sort do |a, b|
+ b[1][0] <=> a[1][0]
+ end.collect {|i| i[0]}
+ @winners = ranked_candidates.find_all do |i|
+ votes[i][0] >= majority
+ end
+
+ loser = ranked_candidates[-1]
+ break if self.winner? or votes[loser][0] == votes[ranked_candidates[-2]][0]
+
+ @ranked_candidates.unshift(loser)
+ runoff(votes, loser)
+ end
+ @ranked_candidates.unshift(*ranked_candidates)
+ end
+
+ def runoff(votes, loser)
+ votes.each_pair do |candidate, morevotes|
+ hash = morevotes[1]
+ hash.each_pair do |vote, count|
+ hash.delete(vote)
+ vote.delete(loser)
+ hash[vote] = count
+ end
+ end
+ votes[loser][1].each_pair do |vote, count|
+ candidate = vote.shift
+ votes[candidate][0] += count
+ if votes[candidate][1].has_key?(vote)
+ votes[candidate][1][vote] += count
+ else
+ votes[candidate][1][vote] = count
+ end
+ end
+ votes.delete(loser)
+ end
+end
projects / selectricity / commitdiff