Added tie-breaking rules and multicandidate elimination of weak candidates

before the first round in IRV.
Renamed runoff to irv.

git-svn-id: svn://rubyforge.org/var/svn/rubyvote/trunk@12 1440c7f4-e209-0410-9a04-881b5eb134a8

diff --git a/lib/rubyvote.rb b/lib/rubyvote.rb
index 158538959aff0a1a72db3271061ccedb839edd67..2f11561dd52f33803d13a4965f40e7ae14a2ad32 100644 (file)
--- a/lib/rubyvote.rb
+++ b/lib/rubyvote.rb
@@ -3,6 +3,6 @@
 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/irv'
 require File.dirname(__FILE__) + '/rubyvote/range'
 

diff --git a/lib/rubyvote/irv.rb b/lib/rubyvote/irv.rb
new file mode 100644 (file)
index 0000000..3851738
--- /dev/null
+++ b/lib/rubyvote/irv.rb
@@ -0,0 +1,225 @@
+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(params={})
+    InstantRunoffResult.new(self, params)
+  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 InstantRunoffLogicVote < InstantRunoffVote
+  def result(params={})
+    InstantRunoffLogicResult.new(self, params)
+  end
+end
+
+class InstantRunoffFirstRoundVote < InstantRunoffVote
+  def result(params={})
+    InstantRunoffFirstRoundResult.new(self, params)
+  end
+end
+
+class InstantRunoffAllVote < InstantRunoffVote
+  def result(params={})
+    InstantRunoffAllResult.new(self, params)
+  end
+end
+
+class InstantRunoffRandomVote < InstantRunoffVote
+  def result(params={})
+    InstantRunoffRandomResult.new(self, params)
+  end
+end
+
+class InstantRunoffResult < ElectionResult
+  attr_reader :ranked_candidates
+
+  def initialize(voteobj=nil, params={})
+    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
+    votes_sum = votes.inject(0) {|n, value| n + value[1][0]}
+    @majority = votes_sum/2 + 1
+    @ranked_candidates = Array.new()
+    ranked_candidates = Array.new()
+    losers = Array.new()
+
+    if params.has_key?('candidate_count')
+      apply_candidate_count(votes, params['candidate_count'])
+    end
+    if params.has_key?('vote_minimum')
+      apply_vote_minimum(votes, params['vote_minimum'])
+    end
+    if params.has_key?('percent_minimum')
+      apply_vote_minimum(votes, votes_sum * params['percent_minimum'])
+    end
+    if params.has_key?('percent_retention')
+      apply_retention(votes, votes_sum * params['percent_retention'])
+    end
+    
+    begin
+      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
+    end while not self.winner? and next_round(votes, ranked_candidates)
+    @ranked_candidates.unshift(*ranked_candidates)
+  end
+
+protected
+  def apply_candidate_count(votes, candidate_count)
+    if votes.size > candidate_count
+      losers = votes.sort do |a, b|
+        b[1][0] <=> a[1][0]
+      end.collect {|i| i[0]}.last(votes.size - candidate_count)
+      @ranked_candidates.unshift(losers) unless losers.empty?
+      losers.each { |loser| remove_candidate(votes, loser) }
+    end
+  end
+
+  def apply_vote_minimum(votes, vote_minimum)
+    losers = votes.find_all do |i|
+      i[1][0] < vote_minimum
+    end.collect {|i| i[0]}
+    if losers.length == votes.size
+      votes.clear
+    else
+      @ranked_candidates.unshift(losers) unless losers.empty?
+      losers.each { |loser| remove_candidate(votes, loser) }
+    end
+  end
+
+  def apply_retention(votes, retention)
+    losers = votes.sort do |a, b|
+      b[1][0] <=> a[1][0]
+    end.collect {|i| i[0]}
+    partial_sum = 0
+    while partial_sum < retention
+      partial_sum += votes[losers.shift][0]
+    end
+    @ranked_candidates.unshift(losers) unless losers.empty?
+    losers.each { |loser| remove_candidate(votes, loser) }
+  end
+  
+  def next_round(votes, ranked_candidates)
+    loser = ranked_candidates[-1]
+    if votes.empty? or votes[loser][0] == votes[ranked_candidates[-2]][0]
+      false
+    else
+      @ranked_candidates.unshift(loser)
+      remove_candidate(votes, loser) 
+      true
+    end
+  end
+
+  def remove_candidate(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
+
+class InstantRunoffLogicResult < InstantRunoffResult
+  def next_round(votes, ranked_candidates)
+    losers = ranked_candidates.find_all do |i|
+      votes[i][0] == votes[ranked_candidates[-1]][0]
+    end
+    if losers.inject(0) {|n, loser| n + votes[loser][0]} >= @majority
+      false
+    else
+      @ranked_candidates.unshift(losers)
+      losers.each do |loser|
+        remove_candidate(votes, loser)
+      end
+      true
+    end
+  end
+end
+
+class InstantRunoffFirstRoundResult < InstantRunoffResult
+  def next_round(votes, ranked_candidates)
+    losers = ranked_candidates.find_all do |i|
+      votes[i][0] == votes[ranked_candidates[-1]][0]
+    end
+    loser = losers.sort do |a, b|
+      @election.votes[a][0] <=> @election.votes[b][0]
+    end.last
+    @ranked_candidates.unshift(loser)
+    remove_candidate(votes, loser)
+  end
+end
+
+class InstantRunoffAllResult < InstantRunoffResult
+  def next_round(votes, ranked_candidates)
+    losers = ranked_candidates.find_all do |i|
+      votes[i][0] == votes[ranked_candidates[-1]][0]
+    end
+    if losers.length == ranked_candidates.length
+      false
+    else
+      @ranked_candidates.unshift(losers)
+      losers.each do |loser|
+        remove_candidate(votes, loser)
+      end
+      true
+    end
+  end
+end
+
+class InstantRunoffRandomResult < InstantRunoffResult
+  def next_round(votes, ranked_candidates)
+    losers = ranked_candidates.find_all do |i|
+      votes[i][0] == votes[ranked_candidates[-1]][0]
+    end
+    loser = losers[rand(losers.length)]
+    @ranked_candidates.unshift(loser)
+    remove_candidate(votes, loser)
+  end
+end

diff --git a/lib/rubyvote/runoff.rb b/lib/rubyvote/runoff.rb
deleted file mode 100644 (file)
index 8a69a4e..0000000
--- a/lib/rubyvote/runoff.rb
+++ /dev/null
@@ -1,88 +0,0 @@
-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

diff --git a/test.rb b/test.rb
index e8c03a1d7140e1deed94dd3ceaef4283897ae59e..6b0b5c1cda8950a19fce2a1cecd3e3795a861f94 100755 (executable)
--- a/test.rb
+++ b/test.rb
@@ -126,8 +126,8 @@ def approval_test1
   print_winner( ApprovalVote.new(vote_array).result )
 end
 
-def runoff_test1
-  puts "USING RUNOFF..."
+def irv_test1
+  puts "USING IRV..."
   puts "The winner shold be: A"
 
   vote_array = Array.new
@@ -139,8 +139,8 @@ def runoff_test1
   print_winner( InstantRunoffVote.new(vote_array).result )
 end
 
-def runoff_test2
-  puts "USING RUNOFF..."
+def irv_test2
+  puts "USING IRV..."
   puts "The winner shold be: D"
 
   vote_array = Array.new
@@ -152,8 +152,8 @@ def runoff_test2
   print_winner( InstantRunoffVote.new(vote_array).result )
 end
 
-def runoff_test3
-  puts "USING RUNOFF..."
+def irv_test3
+  puts "USING IRV..."
   puts "The winner shold be: C"
 
   vote_array = Array.new
@@ -180,6 +180,19 @@ def runoff_test3
   print_winner( InstantRunoffVote.new(vote_array).result )
 end
 
+def irvlogic_test1
+  puts "USING IRV LOGIC..."
+  puts "The winner shold be: B"
+
+  vote_array = Array.new
+  42.times {vote_array << "ABCD".split("")}
+  26.times {vote_array << "BCDA".split("")}
+  15.times {vote_array << "CDBA".split("")}
+  15.times {vote_array << "DCBA".split("")}
+
+  print_winner( InstantRunoffLogicVote.new(vote_array).result )
+end
+
 def range_test1
   puts "USING RANGE..."
   puts "The winner shold be: B"
@@ -200,7 +213,8 @@ ssd_test3()
 borda_test1()
 plurality_test1()
 approval_test1()
-runoff_test1()
-runoff_test2()
-runoff_test3()
+irv_test1()
+irv_test2()
+irv_test3()
+irvlogic_test1()
 range_test1()

diff --git a/test/runoff_test.rb b/test/irv_test.rb
similarity index 80%
rename from test/runoff_test.rb
rename to test/irv_test.rb
index d153dd675b762a9f0d7af8bc388a13394967d8a8..640824c42e5f6ac431b2a0f050624e0bcc5c6944 100644 (file)
--- a/test/runoff_test.rb
+++ b/test/irv_test.rb
@@ -6,7 +6,7 @@ require 'election_test_helper'
 class TestRunoffVote < Test::Unit::TestCase
   include ElectionTestHelper
 
-  def test_runoff
+  def test_irv
     vote_array = Array.new
     142.times {vote_array << "ABCD".split("")}
     26.times {vote_array << "BCDA".split("")}
@@ -16,7 +16,7 @@ class TestRunoffVote < Test::Unit::TestCase
     test_winner( "A", InstantRunoffVote.new(vote_array).result )
   end
 
-  def test_runoff2
+  def test_irv2
     vote_array = Array.new
     42.times {vote_array << "ABCD".split("")}
     26.times {vote_array << "BCDA".split("")}
@@ -26,7 +26,7 @@ class TestRunoffVote < Test::Unit::TestCase
     test_winner( "D", InstantRunoffVote.new(vote_array).result )
   end
 
-  def test_runoff3
+  def test_irv3
     vote_array = Array.new
     42.times {vote_array << "ABCD".split("")}
     26.times {vote_array << "ACBD".split("")}
@@ -50,5 +50,16 @@ class TestRunoffVote < Test::Unit::TestCase
 
     test_winner( "C", InstantRunoffVote.new(vote_array).result )
   end
+
+  def test_irv_logic1
+    vote_array = Array.new
+    42.times {vote_array << "ABCD".split("")}
+    26.times {vote_array << "BCDA".split("")}
+    15.times {vote_array << "CDBA".split("")}
+    15.times {vote_array << "DCBA".split("")}
+
+    test_winner ( "B", InstantRunoffLogicVote.new(vote_array).result )
+  end
+  ###TODO: test all the other variants
 end