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).
 
-`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:
 
index 3655a03..1d98d91 100644 (file)
@@ -62,7 +62,7 @@ class ElectionVote
   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
 
@@ -108,10 +108,15 @@ end
 ## 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
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
+
   def initialize(votes=nil)
     @candidates = Array.new
     votes.each do |vote|
@@ -15,22 +29,22 @@ class InstantRunoffVote < ElectionVote
   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
 
-  def verify_vote(vote=nil)
-    vote.instance_of?( Array ) and
-      vote == vote.uniq
-  end
 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
 
+# 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)
index 5c01f68..cd4df87 100644 (file)
@@ -12,20 +12,20 @@ class RangeVote < ElectionVote
   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
 
 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'
@@ -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]
-    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
@@ -29,7 +27,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     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
@@ -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']], 
-                 CloneproofSSDVote.new(vote_array).results
+                 CloneproofSSDVote.new(vote_array).result.ranked_candidates
   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']], 
-                 CloneproofSSDVote.new(vote_array).results
+                 CloneproofSSDVote.new(vote_array).result.ranked_candidates
   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']], 
-                 CloneproofSSDVote.new(vote_array).results
+                 CloneproofSSDVote.new(vote_array).result.ranked_candidates
   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]
-    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
@@ -106,7 +104,7 @@ class TestCondorcetVote < Test::Unit::TestCase
 
     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
 
   # 
@@ -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]
-    assert_equal [[78]], vote.results
+    assert_equal [[78]], vote.result.ranked_candidates
   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']
-    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
@@ -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]
-    assert_equal [[65, 64], [63, 66]], vote.results
+    assert_equal [[65, 64], [63, 66]], vote.result.ranked_candidates
   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']
-    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']
-    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
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
-  
+  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]

Benjamin Mako Hill || Want to submit a patch?