X-Git-Url: https://projects.mako.cc/source/selectricity/blobdiff_plain/04f827dd4647f3a7d6e5bd8f5e9083c730a8dccc..3a0cee8424956a5c2d0466175222cacd271da098:/lib/rubyvote/condorcet.rb?ds=sidebyside diff --git a/lib/rubyvote/condorcet.rb b/lib/rubyvote/condorcet.rb index 95663d4..0c6fd56 100644 --- a/lib/rubyvote/condorcet.rb +++ b/lib/rubyvote/condorcet.rb @@ -32,53 +32,74 @@ ## the CloneproofSSDVote classes but should not be used directly. class CondorcetVote < ElectionVote + + 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) + end 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 + 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 - @votes[winner] = Hash.new unless @votes.has_key?(winner) - @votes[loser] = Hash.new unless @votes.has_key?(loser) + 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 - if @votes[winner].has_key?(loser) - @votes[winner][loser] += 1 - else - @votes[winner][loser] = 1 + # make sure we have a comparable object + @votes[loser][winner] = 0 unless @votes[loser].has_key?( winner ) + end 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 ) + PureCondorcetResult.new(self) end end class CloneproofSSDVote < CondorcetVote def result - CloneproofSSDResult.new( self ) + CloneproofSSDResult.new(self) end end @@ -91,16 +112,48 @@ end ## 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 + victories_ties = {} + candidates = @matrix.keys.sort + + candidates.each do |candidate| + candidates.each do |challenger| + next if candidate == challenger + diff = @matrix[candidate][challenger] - @matrix[challenger][candidate] + victories_ties[candidate] = {} unless victories_ties.key?(candidate) + if diff >= 0 + victories_ties[candidate][challenger] = diff + end + end + end + + return victories_ties end + def ranked_candidates + if not defined?(@ranked_candidates) + @ranked_candidates = build_ranked_candidates() + end + + @ranked_candidates + end + + protected def defeats(candidates=nil, votes=nil) - candidates = @election.candidates unless candidates - votes = @election.votes unless votes + 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| @@ -114,6 +167,27 @@ class CondorcetResult < ElectionResult defeats end + + def build_ranked_candidates + # build a lis of ranked candidates by dropping the winner and + # cursing + + ranked_candidates = [] + + resultobj = self.dup + candidates = self.election.candidates + + until candidates.empty? + ranked_candidates << resultobj.winners + + new_voteobj = resultobj.election.dup + candidates = new_voteobj.candidates + new_voteobj.candidates.delete_if {|x| resultobj.winners.include?(x)} + resultobj = new_voteobj.result + end + + ranked_candidates + end end @@ -124,10 +198,15 @@ class PureCondorcetResult < CondorcetResult 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 @@ -138,11 +217,18 @@ class PureCondorcetResult < CondorcetResult victors[winner] << loser end - winners = @election.candidates.find_all do |candidate| - victors[candidate].length == @election.candidates.length - 1 + 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 - - @winners = winners if winners.length == 1 end end @@ -153,9 +239,10 @@ class CloneproofSSDResult < CondorcetResult end protected + def cpssd votes = @election.votes - candidates = *@election.candidates + candidates = @election.candidates.dup def in_schwartz_set?(candidate, candidates, transitive_defeats) candidates.each do |challenger| @@ -173,15 +260,22 @@ class CloneproofSSDResult < CondorcetResult # 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| - 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 ] + 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