From: Benjamin Mako Hill Date: Fri, 17 Aug 2007 21:46:39 +0000 (+0000) Subject: Cleaned up after Justin's last commit. X-Git-Url: https://projects.mako.cc/source/rubyvote/commitdiff_plain/ccf19d036af800688260e8c2d87d3ef0dbf14aae Cleaned up after Justin's last commit. git-svn-id: svn://rubyforge.org/var/svn/rubyvote/trunk@45 1440c7f4-e209-0410-9a04-881b5eb134a8 --- diff --git a/lib/condorcet.rb b/lib/condorcet.rb deleted file mode 100644 index a78524b..0000000 --- a/lib/condorcet.rb +++ /dev/null @@ -1,344 +0,0 @@ -# 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 - - attr_accessor :results - - def initialize(votes=nil) - unless defined?(@candidates) - @candidates = Array.new - votes.each do |vote_row| - vote_row = vote_row.flatten if vote_row.class == Array - vote_row.each do |vote| - @candidates << vote unless @candidates.include?(vote) - end - end - end - super(votes) - @results = Array.new - end - - def tally_vote(vote=nil) - - vote.each_with_index do |winners, index| - if vote.flatten.length < @candidates.length - implied_losers = @candidates.select { |c| not vote.flatten.include?(c) } - vote.push(implied_losers) - end - if vote.length - 1 == index - losers = [] - else - losers = vote.flatten.last( vote.flatten.length - index - 1) - end - - losers.each do |place| - place = [place] unless place.class == Array - place.each do |loser| - - winners = [winners] unless winners.class == Array - next if winners.include?(loser) - winners.each do |winner| - @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 ) - end - end - end - end - end - - def results - if @results.size < 2 && (not @candidates.empty?) - tabulate - end - @results - end - - def result - find_only_winner unless @winner - @winner - end - - protected - - def verify_vote(vote=nil) - vote.instance_of?( Array ) and - vote == vote.uniq - end - - def tabulate - find_only_winner unless @winner - until @candidates.empty? - aResult = resultFactory( self ) - @results << aResult.winners - filter_out(aResult) - end - end - - def find_only_winner - @winner = resultFactory( self ) - @results << @winner.winners - filter_out(@winner) - end - -end - -class PureCondorcetVote < CondorcetVote - def resultFactory(init) - PureCondorcetResult.new(init) - end -end - -class CloneproofSSDVote < CondorcetVote - def resultFactory(init) - CloneproofSSDResult.new(init) - 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 - attr_reader :matrix - - def initialize(voteobj=nil) - unless voteobj and voteobj.kind_of?( CondorcetVote ) - raise ArgumentError, "You must pass a CondorcetVote array.", caller - end - super(voteobj) - @matrix = voteobj.votes - end - - def victories_and_ties - victors = Array.new - ties = Array.new - victories = Hash.new - candidates = @matrix.keys.sort - - candidates.each do |candidate| - candidates.each do |challenger| - next if candidate == challenger - diff = @matrix[candidate][challenger] - @matrix[challenger][candidate] - if diff > 0 - victors << [candidate, challenger, diff] - elsif diff == 0 && ties.include?([challenger, candidate]) == false - ties << [candidate, challenger] - end - end - end - - victors.each do |list| - if victories.has_key?(list[0]) - victories[list[0]][list[1]] = list[2] - else - victories[list[0]] = Hash.new - victories[list[0]][list[1]] = list[2] - end - end - - return victories, ties - end - - protected - def defeats(candidates=nil, votes=nil) - candidates ||= @election.candidates || [] - # we're assumign that if there are candidates, there must be at - # least one vote for them - votes ||= @election.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 - - unless votes.length > 0 and candidates.length > 0 - return @winners=[] - end - - victors = Hash.new - candidates.each do |candidate| - victors[candidate] = Array.new - end - - self.defeats.each do |pair| - winner, loser = *pair - victors[winner] << loser - end - - victory_margin = 1 - while true - winners = @election.candidates.find_all do |candidate| - victors[candidate].length == @election.candidates.length - victory_margin - end - if winners.length > 0 - @winners = winners - return @winners - else - victory_margin += 1 - end - end - end -end - -class CloneproofSSDResult < CondorcetResult - def initialize(voteobj=nil) - super(voteobj) - @winners = self.cpssd() - end - - protected - - def cpssd - votes = @election.votes - candidates = @election.candidates.dup - - 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) - defeats_hash = Hash.new - transitive_defeats.each { |td| defeats_hash[td] = 1 } - - candidates = [candidates] unless candidates.class == Array - candidates.each do |cand1| - candidates.each do |cand2| - unless cand1 == cand2 - candidates.each do |cand3| - if not cand2 == cand3 and - not cand1 == cand3 and - defeats_hash[[cand2, cand1]] and - defeats_hash[[cand1, cand3]] and - not defeats_hash[[cand2, cand3]] - transitive_defeats << [cand2, cand3] - defeats_hash[[cand2, cand3]] = 1 - end - 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 diff --git a/lib/rubyvote/condorcet.rb b/lib/rubyvote/condorcet.rb index f86e59d..a78524b 100644 --- a/lib/rubyvote/condorcet.rb +++ b/lib/rubyvote/condorcet.rb @@ -157,6 +157,7 @@ class CondorcetResult < ElectionResult def victories_and_ties victors = Array.new ties = Array.new + victories = Hash.new candidates = @matrix.keys.sort candidates.each do |candidate| @@ -169,9 +170,16 @@ class CondorcetResult < ElectionResult ties << [candidate, challenger] end end - end + end - victories = victors.sort {|a,b| b[2] <=> a[2]} + victors.each do |list| + if victories.has_key?(list[0]) + victories[list[0]][list[1]] = list[2] + else + victories[list[0]] = Hash.new + victories[list[0]][list[1]] = list[2] + end + end return victories, ties end