From: Justin Sharps Date: Fri, 17 Aug 2007 21:42:48 +0000 (+0000) Subject: Created victories_and_ties method for table use. X-Git-Url: https://projects.mako.cc/source/rubyvote/commitdiff_plain/39441f5a3033c1eb4a5e0d4beeed2cc17a3e20cd?ds=sidebyside Created victories_and_ties method for table use. git-svn-id: svn://rubyforge.org/var/svn/rubyvote/trunk@44 1440c7f4-e209-0410-9a04-881b5eb134a8 --- diff --git a/lib/condorcet.rb b/lib/condorcet.rb new file mode 100644 index 0000000..a78524b --- /dev/null +++ b/lib/condorcet.rb @@ -0,0 +1,344 @@ +# 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