From c9649b477b0e94c4f7f36e6d42225e0d6a113f57 Mon Sep 17 00:00:00 2001 From: Benjamin Mako Hill Date: Sun, 24 Oct 2010 22:34:15 +0000 Subject: [PATCH] a number of improvements - 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 | 2 +- lib/rubyvote/election.rb | 15 ++++++--- lib/rubyvote/irv.rb | 42 ++++++++++++++++--------- lib/rubyvote/positional.rb | 13 ++++++++ lib/rubyvote/range.rb | 22 ++++++------- test/condorcet_test.rb | 38 ++++++++++------------- test/irv_test.rb | 63 +++++++++++++++++++++++++++++++++++++- 7 files changed, 142 insertions(+), 53 deletions(-) diff --git a/README b/README index efd0ddf..a603a04 100644 --- 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: diff --git a/lib/rubyvote/election.rb b/lib/rubyvote/election.rb index 3655a03..1d98d91 100644 --- a/lib/rubyvote/election.rb +++ b/lib/rubyvote/election.rb @@ -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 diff --git a/lib/rubyvote/irv.rb b/lib/rubyvote/irv.rb index c3fabe6..aa94115 100644 --- a/lib/rubyvote/irv.rb +++ b/lib/rubyvote/irv.rb @@ -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 diff --git a/lib/rubyvote/positional.rb b/lib/rubyvote/positional.rb index 056194b..d72f8a7 100644 --- a/lib/rubyvote/positional.rb +++ b/lib/rubyvote/positional.rb @@ -29,6 +29,19 @@ ## 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) diff --git a/lib/rubyvote/range.rb b/lib/rubyvote/range.rb index 5c01f68..cd4df87 100644 --- a/lib/rubyvote/range.rb +++ b/lib/rubyvote/range.rb @@ -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 diff --git a/test/condorcet_test.rb b/test/condorcet_test.rb index b2d5dc4..0e45d4a 100644 --- a/test/condorcet_test.rb +++ b/test/condorcet_test.rb @@ -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 diff --git a/test/irv_test.rb b/test/irv_test.rb index d3a57a7..2974296 100644 --- a/test/irv_test.rb +++ b/test/irv_test.rb @@ -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] -- 2.39.5