Schulze Vote

This gem is a Ruby implementation of the Schulze voting method (with help of the Floyd–Warshall algorithm), a type of the Condorcet voting methods. It's the backend algorithm of Agreeder and Airesis.

gem install schulze-vote

Gemfile

gem 'schulze-vote', require: 'schulze_vote'

require 'schulze_vote'
vote_list = <<EOF
C;A;B
C;B;A
A;B;C
A;C;B
B;C;A
B;A;C
EOF
schulze_basic = SchulzeBasic.do(vote_list, candidate_count)
schulze_classifications.classification_with_ties # shows the final classification

Input:

• vote_list
  • Array of Arrays: votes of each voter as weights [ [1,2,3],[3,2,1],[1,1,2] ]
  • String: "A;B;C\nB,A;C\n;3=C;B;A"
  • File: first line must be a single integer, following lines like vote_list type String (see vote lists under examples directory)
• candidate_count Integer: number of options
  • required for vote_list types of Array and String
  • leave empty if vote_list is a File

A typical voters line looks like this:

A;B;C;D;E;F

You also can say that n voters have the same preferences:

n=F;E;D;C;B;A

where n is an integer value for the count.

Also it's possible to say that a voter has candidates equally weighted:

A,B;C,D;E,F

which means, that A + B, C + D and E + F are on the same weight level.

Here only 3 weight levels are used: (A,B) = 3, (C,D) = 2, (E,F) = 1

or: Why I must give a candidate count value for Array/String inputs?

Very easy: The reason is, that voters can leave out candidates (they give no special preferences).

So, schulze-vote needs to know, how many real candidates are in the voting process.

Only weight values, no letters here

require 'schulze_vote'
vote_list_array = [[3,2,1],[1,3,2],[3,1,2]]
vs = SchulzeBasic.do vote_list_array, 3

voter  => A D C B

weight => 4,1,2,3

A is on first position = highest prio == 4
B is on last position                 == 1
C is on third position                == 2
D is on second position               == 3

Next versions will have an automatic Preference-to-Weight algorithm. (Internally only integers are used for calculation of ranking.)

require 'schulze_vote'
vote_list_string = <<EOF
A;B;C
B;C;A
A;C;B
A,C,B
4=C;A;B
EOF
vs = SchulzeBasic.do vote_list_string, 3

require 'schulze_vote'
vs = SchulzeBasic.do File.open('path/to/vote.list')

It doesn't matter if you start counting at 0 (zero) or 1 (one).

Also it's not important, if you use jumps (like 1 3 5 9).

Internally it will only check if candidate X > candidate Y

Output:

• .ranking Array: numbers of total wins for each candidate [candidate A, candidate B, candidate C, ...]
• .winners_array Array: set 1 if the candidate is a potential winner [candidate A, candidate B, candidate C, ...]
• .vote_matrix Matrix: it contains the pairwise defeats
• .play_matrix Matrix: it contains the strongest paths
• .result_matrix Matrix: it contains the beat pairwise
• .beat_couples Array of Pairs: it contains the beat pairwise in array format
• .ties Array of Array: it contains the ties between candidates
• .potential_winners Array: it contains the possible winners

Example 1 from Wikipedia

https://en.wikipedia.org/wiki/User:MarkusSchulze/Schulze_method_examples

Result should be:

votestring = <<EOF
5=A;C;B;E;D
5=A;D;E;C;B
8=B;E;D;A;C
3=C;A;B;E;D
7=C;A;E;B;D
2=C;B;A;D;E
7=D;C;E;B;A
8=E;B;A;D;C
EOF
vs = SchulzeBasic.do(votestring, 5)
puts_m vs.vote_matrix

#=> [0, 20, 26, 30, 22]
    [25, 0, 16, 33, 18]
    [19, 29, 0, 17, 24]
    [15, 12, 28, 0, 14]
    [23, 27, 21, 31, 0]
   
puts_m vs.play_matrix

#=> [0, 28, 28, 30, 24]
    [25, 0, 28, 33, 24]
    [25, 29, 0, 29, 24]
    [25, 28, 28, 0, 24]
    [25, 28, 28, 31, 0]

puts vs.winners_array.to_s

#=> [0, 0, 0, 0, 1]

puts_m vs.result_matrix

#=> [0, 1, 1, 1, 0]
    [0, 0, 0, 1, 0]
    [0, 1, 0, 1, 0]
    [0, 0, 0, 0, 0]
    [1, 1, 1, 1, 0]

vs.classifications.each do |classification|
  puts classification.map { |e| idx_to_chr(e) }.to_s
end

#=> ["E", "A", "C", "B", "D"]

You have a SchulzeClassifications.new(vs).classifications(limit_results = false) that you can call. If the number of results is greater then the limit_results parameter then a TooManyClassificationsException is raised. If you set this parameter to any value other then false be careful to catch and manage the exception properly.

You have a SchulzeClassifications.new(vs).classification_with_ties that you can call. This method return a uniq classification in array of arrays format to display results on screen. Please note that for cases like this: https://en.wikipedia.org/wiki/User:MarkusSchulze/Schulze_method_examples#Example_4 it will return the following: [[B,D], [A,C]]

Run bundle exec rspec to run tests.

You can run bundle exec ruby spec/example_generator.rb [CANDIDATES_NUM] [VOTES_NUM] to generate a random election file in the examples` folder.

• Check out the latest master to make sure the feature hasn't been implemented or the bug hasn't been fixed yet
• Check out the issue tracker to make sure someone already hasn't requested it and/or contributed it
• Fork the project
• Use git-flow
• Start a feature/bugfix branch
• Commit and push until you are happy with your contribution
• Make sure to add tests for it. This is important so I don't break it in a future version unintentionally.
• Please try not to mess with the Rakefile, version, or history. If you want to have your own version, or is otherwise necessary, that is fine, but please isolate to its own commit so I can cherry-pick around it.

Thanks to Christoph Grabo for providing the idea and base code of the gem

• Schulze method (deutsch)
• Schulze method examples
• Floyd-Warshall algorithm

See LICENSE for further details.