a number of improvements master
authorBenjamin Mako Hill <mako@atdot.cc>
Sun, 24 Oct 2010 22:34:15 +0000 (22:34 +0000)
committerBenjamin Mako Hill <mako@atdot.cc>
Sun, 24 Oct 2010 22:34:15 +0000 (22:34 +0000)
- switched IRV's add_vote to tally_vote to make it consistent
- added description and documentation to each method/time
- fixed typo in README
- added a new IRV test (which i'm not sure is wrong) but which was
  causing big problems on selectricity

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

README
lib/rubyvote/election.rb
lib/rubyvote/irv.rb
lib/rubyvote/positional.rb
lib/rubyvote/range.rb
test/condorcet_test.rb
test/irv_test.rb

diff --git a/README b/README
index efd0ddf..a603a04 100644 (file)
--- a/README
+++ b/README
@@ -51,7 +51,7 @@ simply takes the raw "tallies" of votes and computes the results.
 Currently, it does not include any sample interfaces (although if
 contributed, these may be included).
 
 Currently, it does not include any sample interfaces (although if
 contributed, these may be included).
 
-`RubyVote` current includes a set of classes to tally votes and compute
+`RubyVote` currently includes a set of classes to tally votes and compute
 winners in elections or votes using a series of different methods.
 Currently these include:
 
 winners in elections or votes using a series of different methods.
 Currently these include:
 
index 3655a03..1d98d91 100644 (file)
@@ -62,7 +62,7 @@ class ElectionVote
   end
 
   # by default, this does nothing. it must be redefined in any subclass
   end
 
   # by default, this does nothing. it must be redefined in any subclass
-  def tally_vote
+  def tally_vote(vote)
     self.verify_vote(vote)
   end
 
     self.verify_vote(vote)
   end
 
@@ -108,10 +108,15 @@ end
 ## Election Result Classes
 ##
 
 ## 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.
-
+# ElectionResult and its subclasses are used to identify and report the results
+# of an election. In almost all cases, these will be returned by the #results
+# method of a corresponding ElectionVote subclass.
+#
+# Each ElectionResult object has the following methods:
+#
+#  * #winner? -- return Boolean as to the winner or winners of an election
+#  * #winners -- an array of winners of the election
+#  * #ranked_candidates -- (where available) a list of ranked candidates
 class ElectionResult
   attr_reader :winners
   attr_reader :election
 class ElectionResult
   attr_reader :winners
   attr_reader :election
index c3fabe6..aa94115 100644 (file)
@@ -1,4 +1,18 @@
+# IRV is a preferential voting system used widely for government elections
+# in Australia and New Zealand and elsewhere. IRV asks voters to rank
+# candidates in preference and then holds a series of "runoff" elections
+# by eliminating the weakest candidate and recomputing the election
+# results until there exists a candidate who has a majority of the
+# remaining votes.
+
+# Example::
+
+#   require 'irv'
+#   vote_array = [ ["A", "B"],  ["B", "A"], ["B", "A"] ]
+#   resultobject = InstantRunoffVote.new(vote_array).result
+#
 class InstantRunoffVote < ElectionVote
 class InstantRunoffVote < ElectionVote
+
   def initialize(votes=nil)
     @candidates = Array.new
     votes.each do |vote|
   def initialize(votes=nil)
     @candidates = Array.new
     votes.each do |vote|
@@ -15,22 +29,22 @@ class InstantRunoffVote < ElectionVote
   end
   
   protected
   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
+    def vote_valid?(vote = nil)
+      super && vote.is_a?(Array) && vote == vote.uniq
+    end
+
+    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
     end
-  end
 
 
-  def verify_vote(vote=nil)
-    vote.instance_of?( Array ) and
-      vote == vote.uniq
-  end
 end
 
 class InstantRunoffLogicVote < InstantRunoffVote
 end
 
 class InstantRunoffLogicVote < InstantRunoffVote
index 056194b..d72f8a7 100644 (file)
 ## These classes inherit from and/or are modeled after the classes in
 ## election.rb and condorcet.rb
 
 ## These classes inherit from and/or are modeled after the classes in
 ## election.rb and condorcet.rb
 
+# Borda is a positional voting system and, as a result, takes a list of
+# ranked candidates and assigns points to each candidates based on their
+# order. In Borda, there are *n* candidate and the first candidates is
+# assigned *n* - 1 points and each subsequent candidate is assigned one
+# less point. The candidate is assigned no points.
+#
+# Currently, all candidates should be ranked in each ballot.
+#
+# Example::
+#
+#   require 'positional'
+#   vote_array = [ ["A", "B"],  ["B", "A"], ["B", "A"] ]
+#   resultobject = BordaVote.new(vote_array).result
 class BordaVote < ElectionVote
 
   def initialize(votes=nil)
 class BordaVote < ElectionVote
 
   def initialize(votes=nil)
index 5c01f68..cd4df87 100644 (file)
@@ -12,20 +12,20 @@ class RangeVote < ElectionVote
   end
 
   protected
   end
 
   protected
-  def verify_vote(vote=nil)
-    vote.instance_of?(Hash) && vote.all?{|c,score| @valid_range.include?(score)}
-  end
+    def vote_valid?(vote=nil)
+      super && vote.is_a?(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
+    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
     end
-  end
 end
 
 class RangeResult < PluralityResult
 end
 
 class RangeResult < PluralityResult
index b2d5dc4..0e45d4a 100644 (file)
@@ -1,5 +1,3 @@
-#!/usr/bin/ruby -Ilib
-
 require 'test/unit'
 require 'rubyvote/election'
 require 'rubyvote/condorcet'
 require 'test/unit'
 require 'rubyvote/election'
 require 'rubyvote/condorcet'
@@ -18,7 +16,7 @@ class TestCondorcetVote < Test::Unit::TestCase
     2.times {vote_array << "BAC".split("")}
 
     assert_equal "B", PureCondorcetVote.new(vote_array).result.winners[0]
     2.times {vote_array << "BAC".split("")}
 
     assert_equal "B", PureCondorcetVote.new(vote_array).result.winners[0]
-    assert_equal [['B'], ['A'], ['C']], PureCondorcetVote.new(vote_array).results
+    assert_equal [['B'], ['A'], ['C']], PureCondorcetVote.new(vote_array).result.ranked_candidates
   end
 
   def test_condorcet_2
   end
 
   def test_condorcet_2
@@ -29,7 +27,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     v = PureCondorcetVote.new(vote_array)
     assert_equal ["6", "7"], v.result.winners
 
     v = PureCondorcetVote.new(vote_array)
     assert_equal ["6", "7"], v.result.winners
-    assert_equal [['6', '7'], ['8']], v.results
+    assert_equal [['6', '7'], ['8']], v.result.ranked_candidates
   end
 
   def test_ssd_empty
   end
 
   def test_ssd_empty
@@ -51,7 +49,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     assert_equal "E", CloneproofSSDVote.new(vote_array).result.winners[0]
     assert_equal [['E'], ['A'], ['C'], ['B'], ['D']], 
 
     assert_equal "E", CloneproofSSDVote.new(vote_array).result.winners[0]
     assert_equal [['E'], ['A'], ['C'], ['B'], ['D']], 
-                 CloneproofSSDVote.new(vote_array).results
+                 CloneproofSSDVote.new(vote_array).result.ranked_candidates
   end
 
   def test_ssd2
   end
 
   def test_ssd2
@@ -68,7 +66,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     assert_equal "D", CloneproofSSDVote.new(vote_array).result.winners[0] 
     assert_equal [['D'], ['A'], ['C'], ['B']], 
 
     assert_equal "D", CloneproofSSDVote.new(vote_array).result.winners[0] 
     assert_equal [['D'], ['A'], ['C'], ['B']], 
-                 CloneproofSSDVote.new(vote_array).results
+                 CloneproofSSDVote.new(vote_array).result.ranked_candidates
   end
 
   def test_ssd3
   end
 
   def test_ssd3
@@ -80,7 +78,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     assert_equal "B", CloneproofSSDVote.new(vote_array).result.winners[0]
     assert_equal [['B'], ['C'], ['D'], ['A']], 
 
     assert_equal "B", CloneproofSSDVote.new(vote_array).result.winners[0]
     assert_equal [['B'], ['C'], ['D'], ['A']], 
-                 CloneproofSSDVote.new(vote_array).results
+                 CloneproofSSDVote.new(vote_array).result.ranked_candidates
   end
 
   def test_ssd_incomplete_votes
   end
 
   def test_ssd_incomplete_votes
@@ -93,7 +91,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     vote = CloneproofSSDVote.new(vote_array)
     assert_equal "B", vote.result.winners[0]
 
     vote = CloneproofSSDVote.new(vote_array)
     assert_equal "B", vote.result.winners[0]
-    assert_equal [['B'], ['C'], ['D'], ['A']], vote.results
+    assert_equal [['B'], ['C'], ['D'], ['A']], vote.result.ranked_candidates
   end
 
   def test_ssd_incomplete_votes_2
   end
 
   def test_ssd_incomplete_votes_2
@@ -106,7 +104,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     vote = CloneproofSSDVote.new(vote_array)
     assert_equal "B", vote.result.winners[0]
 
     vote = CloneproofSSDVote.new(vote_array)
     assert_equal "B", vote.result.winners[0]
-    assert_equal [['B'], ['C'], ['D'], ['A']], vote.results
+    assert_equal [['B'], ['C'], ['D'], ['A']], vote.result.ranked_candidates
   end
 
   # 
   end
 
   # 
@@ -118,7 +116,7 @@ class TestCondorcetVote < Test::Unit::TestCase
   def test_ssd_single_vote
     vote = CloneproofSSDVote.new([[78]])
     assert_equal 78, vote.result.winners[0]
   def test_ssd_single_vote
     vote = CloneproofSSDVote.new([[78]])
     assert_equal 78, vote.result.winners[0]
-    assert_equal [[78]], vote.results
+    assert_equal [[78]], vote.result.ranked_candidates
   end
 
   def test_ssd_sparse
   end
 
   def test_ssd_sparse
@@ -126,8 +124,8 @@ class TestCondorcetVote < Test::Unit::TestCase
     vote_array << ['B', 'D']
     vote_array << ['A', 'C']
     vote_array << ['E', 'C']
     vote_array << ['B', 'D']
     vote_array << ['A', 'C']
     vote_array << ['E', 'C']
-    results = CloneproofSSDVote.new(vote_array).results
-    assert_equal 5, results.flatten.size
+    ranked_candidates = CloneproofSSDVote.new(vote_array).result.ranked_candidates
+    assert_equal 5, ranked_candidates.flatten.size
   end
 
   def test_ssd_sparse_2
   end
 
   def test_ssd_sparse_2
@@ -136,7 +134,7 @@ class TestCondorcetVote < Test::Unit::TestCase
     vote_array << [64, 65, 66, 63]
     vote = CloneproofSSDVote.new(vote_array)
     assert_equal 65, vote.result.winners[0]
     vote_array << [64, 65, 66, 63]
     vote = CloneproofSSDVote.new(vote_array)
     assert_equal 65, vote.result.winners[0]
-    assert_equal [[65, 64], [63, 66]], vote.results
+    assert_equal [[65, 64], [63, 66]], vote.result.ranked_candidates
   end
 
   def test_ssd_multiple_equivalent
   end
 
   def test_ssd_multiple_equivalent
@@ -144,19 +142,17 @@ class TestCondorcetVote < Test::Unit::TestCase
     vote_array << ['B', ['A', 'C'], 'D']
     vote_array << ['A', 'C']
     vote_array << [['E', 'D'], 'C']
     vote_array << ['B', ['A', 'C'], 'D']
     vote_array << ['A', 'C']
     vote_array << [['E', 'D'], 'C']
-    results = CloneproofSSDVote.new(vote_array).results
-    assert_equal 5, results.flatten.size
-    assert_equal [['A', 'C'], ['B', 'D'], ['E']], results
+    ranked_candidates = CloneproofSSDVote.new(vote_array).result.ranked_candidates
+    assert_equal 5, ranked_candidates.flatten.size
+    assert_equal [['A', 'C'], ['B', 'D'], ['E']], ranked_candidates
   end
 
   def test_ssd_multiple_equivalent_2
     vote_array = Array.new
     vote_array << ['B', ['A'], 'C']
     vote_array << ['B', ['C'], 'A']
   end
 
   def test_ssd_multiple_equivalent_2
     vote_array = Array.new
     vote_array << ['B', ['A'], 'C']
     vote_array << ['B', ['C'], 'A']
-    results = CloneproofSSDVote.new(vote_array).results
-    assert_equal 3, results.flatten.size
-    assert_equal [['B'], ['A', 'C']], results
+    ranked_candidates = CloneproofSSDVote.new(vote_array).result.ranked_candidates
+    assert_equal 3, ranked_candidates.flatten.size
+    assert_equal [['B'], ['A', 'C']], ranked_candidates
   end
   end
-
-
 end
 end
index d3a57a7..2974296 100644 (file)
@@ -56,7 +56,68 @@ class TestRunoffVote < Test::Unit::TestCase
 
     assert_equal( "C", InstantRunoffVote.new(vote_array).result.winners[0] )
   end
 
     assert_equal( "C", InstantRunoffVote.new(vote_array).result.winners[0] )
   end
-  
+  def test_irv4
+    # this was causing selectricity to crash
+
+    raw_vote_array = ["GFECADBIH", "ABCDEFGHI", "IGHBADFCE",
+                      "FABCDEGHI", "ABCDEFGHI", "ABCDEFGHI",
+                      "ABCDEFGHI", "ABCDEFGHI", "ABCDEFGHI",
+                      "EHBICDAGF", "ECGDFBIAH", "BDHIGFECA",
+                      "ECDBFIHAG", "FEDBCAHIG", "CDABHIEFG",
+                      "FCBDIHAEG", "AIHFBECGD", "BACHDEFIG",
+                      "CDEFIBHAG", "BDICAFEGH", "ABCDEFGHI",
+                      "CBIHDFAEG", "ABCDEFGHI", "CDFIBAGEH",
+                      "ECDBIFHGA", "BDACEHFIG", "CFDIHABEG",
+                      "ADCFGBIHE", "CDHIBEAGF", "ABCFDHIEG",
+                      "ABCDEFGHI", "DCFHIBAGE", "CDFEABHIG",
+                      "DFHIBEAGC", "EDCBFIGAH", "BAECDFHGI",
+                      "BAHCEDFGI", "HBCDIAFEG", "ABCDEFGHI",
+                      "ABCDEFGHI", "EDCBIGAHF", "EIBDCGAFH",
+                      "HIACGDFBE", "DEACBIFGH", "CIDEFABGH",
+                      "ABHDIECGF", "ECIDBFGHA", "CEDFBHIGA",
+                      "ABHCEIDFG", "CFDBEIHGA", "ICEDBGFAH",
+                      "EDCIFBAGH", "ECFDBAHGI", "EBCADFIGH",
+                      "EFBHAGICD", "CDBIEFAHG", "ABCDEFGHI",
+                      "FCDBEIHGA", "AIEBDCFHG", "CDFEBIGAH",
+                      "CABDEFGHI", "DCEIBFGHA", "EADCIBHFG",
+                      "DBCAHIGEF", "EDFBCIAHG", "EDCBIHAGF",
+                      "CFIAEDGHB", "CDEIHABGF", "CEBHIDAFG",
+                      "BCFEDIHAG", "CDIHBFGEA", "CFEDIGBAH",
+                      "IHFEADCBG", "EBDCIGAHF", "BCEDFIAGH",
+                      "ABHEGICDF", "CABFHDIEG", "HEABDCFGI",
+                      "CDEBFAIHG", "CDBFIHAGE", "ABGFEDHCI",
+                      "IBHDCAEFG", "EBDICHAFG", "ABCDEFGHI",
+                      "EFBHAICGD", "CBDFHAIEG", "CDBAEIHGF",
+                      "ABCDEFGHI", "BECDHIFGA", "DAGCIHFBE",
+                      "BIECDGAHF", "ABCDEFGHI", "ACDEBHIFG",
+                      "AEBCIDHFG", "ABCDEFGHI", "ABCDEFGHI",
+                      "ABCDEFGHI", "ABCDEFGHI", "ABCDEFGHI",
+                      "ABCDEFGHI", "ECFDIHBAG", "BIDCHEAGF",
+                      "BCEDFIGHA", "CBDAFEGHI", "ABCDEFGHI",
+                      "FACEGDHBI", "ABCDEFGHI", "FDIBCGHAE",
+                      "EBIHADCFG", "EDBIHAGCF", "AHDICBFEG",
+                      "DCBIHAGFE", "CABFIDEHG", "IFCBHADEG",
+                      "EDCFHIBAG", "DCABEFGHI", "FCBDIGHEA",
+                      "ABCDEFGHI", "HBACIDEFG", "ABCDEFGHI",
+                      "ABCDEFGHI", "EADCBIHGF", "BDCIHAGFE",
+                      "ABCDEFGHI", "ABCDEFGHI", "ABCDEFGHI",
+                      "ABCDEFGHI", "ABCDEFGHI", "ICDGAHBEF",
+                      "EGBCFIHDA", "DFGACHIEB", "BCAGDFHIE",
+                      "DBGHCEAFI", "IGHEBCADF", "FEDIHBCAG",
+                      "HAICBGEFD", "EBFDAICGH", "ECGAHFIBD",
+                      "GEFICAHDB", "ACEHGIBDF", "EGIFBHCAD",
+                      "GHFEDCIBA", "DGAEHFICB", "HGDICBAFE",
+                      "HEACGDBFI", "IAGDFHCEB", "EGIACHBDF",
+                      "CBFGDIEAH", "CGAIBDEFH", "AHEDIGCBF",
+                      "BAEFHIDCG", "BIDGAFCHE", "CHBAEDFIG",
+                      "IBGCFADEH", "GHACDEFIB", "CFDBEAHIG",
+                      "GDEFAICHB"]
+    vote_array = raw_vote_array.collect {|v| v.split("")}
+    print InstantRunoffVote.new(vote_array).result.winners, "\n"
+    assert_equal(true, InstantRunoffVote.new(vote_array).result.winner?)
+  end
+
   def test_irv_logic_empty
     vote_array = Array.new
     assert_nil InstantRunoffLogicVote.new(vote_array).result.winners[0]
   def test_irv_logic_empty
     vote_array = Array.new
     assert_nil InstantRunoffLogicVote.new(vote_array).result.winners[0]

Benjamin Mako Hill || Want to submit a patch?