wybr/methods/schulze.rs
1//! Schulze method
2//!
3//! [Schulze](https://en.wikipedia.org/wiki/Schulze_method) method expands the beat graph with
4//! widest beat-paths between candidates, and then attempts to find a Condorcet winner.
5//!
6//! # Examples
7//!
8//! ```
9//! use wybr::{Tally,Schulze,Outcome};
10//!
11//! //Load the Tennessee Wikipedia example
12//! let tally=Tally::from_blt_file("examples/tennessee.blt").unwrap();
13//!
14//! //Perform simple election with default parameters
15//! let outcome=Schulze::new(&tally).run().unwrap();
16//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
17//!
18//! //Change pair score to `Margin`; this won't change the outcome, though
19//! use wybr::PairScore;
20//! let outcome=Schulze::new(&tally).pair_score(PairScore::Margin).run().unwrap();
21//! assert_eq!(outcome.winner_name().unwrap(),"Nashville");
22//! ```
23use self::PairScore::*;
24use crate::common::{ElectionError, PairScore};
25use crate::outcome::GenericOutcome;
26use crate::tally::{Tally, VoteMatrix};
27use std::collections::HashMap;
28
29pub struct Schulze<'a> {
30 tally: &'a VoteMatrix,
31 pair_score: PairScore,
32}
33
34fn strongest_paths<S: ::std::hash::BuildHasher>(n: u32, x: &mut HashMap<(u32, u32), u64, S>) {
35 use std::cmp::{max, min};
36 for i in 0..n {
37 for j in 0..n {
38 for k in 0..n {
39 if i != j && i != k && j != k {
40 if let Some(&pji) = x.get(&(j, i)) {
41 if let Some(&pik) = x.get(&(i, k)) {
42 let alt = min(pji, pik);
43 x.entry((j, k))
44 .and_modify(|e| *e = max(*e, alt))
45 .or_insert(alt);
46 }
47 }
48 }
49 }
50 }
51 }
52 //Retain winning paths only
53 for i in 1..n {
54 for j in 0..i {
55 if let Some(&vij) = x.get(&(i, j)) {
56 if let Some(&vji) = x.get(&(j, i)) {
57 if vij >= vji {
58 x.remove(&(j, i));
59 }
60 if vji >= vij {
61 x.remove(&(i, j));
62 }
63 }
64 }
65 }
66 }
67}
68
69///A builder for the setup of Schulze method
70///
71///See [the module level documentation](index.html) for more.
72///
73///Default configuration can be generated with `Schulze::new(&tally)`, where `tally` is a
74///`VoteMatrix` object.
75///Count is triggered by the `run()` method, which returns a solitary winner, or an error.
76impl<'a> Schulze<'a> {
77 ///Acquire reference to a vote matrix tally and initiate default configuration, which can be altered
78 ///with other builder methods.
79 ///The default configuration involves using Winning pair scoring.
80 pub fn new(tally: &'a VoteMatrix) -> Self {
81 Self {
82 tally,
83 pair_score: Winning,
84 }
85 }
86
87 ///Alters the random seed potentially used by the election algorithm to break ties.
88 pub fn pair_score(&mut self, pair_score: PairScore) -> &mut Self {
89 self.pair_score = pair_score;
90 self
91 }
92
93 /// Performs a Schulze (beat-path) election
94 ///
95 /// # Errors
96 /// * `NotEnoughCandidates`, in case there is no candidates.
97 /// * `DegeneratedElectionGraph`, in case when there is no winner in the final graph.
98 /// Anyhow, such situation happens extremely rarely in practice, especially when indifferent votes
99 /// are disallowed (this is what wybr does).
100 ///
101 /// # Notes
102 /// This is a basic version of the Schulze method, with no tie-breaking at all; there is also a
103 /// more sophisticated version with forbidden links which fends off some ties, and even more
104 /// complex one that uses a random ballot to break ties.
105 /// Hence, it does not use pseudo-random generator at all.
106 pub fn run(&self) -> Result<GenericOutcome<'a>, ElectionError> {
107 if self.tally.get_candidates() == 0 {
108 return Err(ElectionError::NotEnoughCandidates);
109 }
110 //Initiate pairs with winning votes
111 let mut paths: HashMap<(u32, u32), u64> = self
112 .tally
113 .pairs()
114 .filter_map(|((runner, opponent), (win, opposition))| {
115 let score: u64 = match (win > opposition, self.pair_score) {
116 (true, Margin) => win - opposition,
117 (true, Winning) => win,
118 (_, Opposition) => win,
119 _ => 0,
120 };
121 if score > 0 {
122 Some(((runner, opponent), score))
123 } else {
124 None
125 }
126 })
127 .collect();
128 //Complete paths to strongest paths
129 strongest_paths(self.tally.get_candidates(), &mut paths);
130
131 //Establish who can be a Condorcet winner
132 let mut is_winner: HashMap<u32, bool> = HashMap::new();
133 for (&(winner, looser), _) in paths.iter() {
134 is_winner.entry(winner).or_insert(true);
135 is_winner.insert(looser, false);
136 }
137 let mut winner_iter = is_winner
138 .iter()
139 .filter_map(|(&c, &w)| if w { Some(c) } else { None });
140 if let Some(final_winner) = winner_iter.next() {
141 if winner_iter.next().is_none() {
142 Ok(GenericOutcome::new(
143 Some(final_winner),
144 None,
145 self.tally.get_candidates(),
146 true,
147 self.tally.get_meta(),
148 ))
149 } else {
150 //Winner list is > 1
151 Err(ElectionError::DegeneratedElectionGraph)
152 }
153 } else {
154 //Winner list is empty
155 Err(ElectionError::DegeneratedElectionGraph)
156 }
157 }
158}
159
160#[cfg(test)]
161mod tests {
162 use super::*;
163 use crate::ElectionError;
164 use crate::Outcome;
165 #[test]
166 fn schulze_basic() {
167 let x = VoteMatrix::with_vector_bycol(
168 //Tennessee
169 &vec![58, 58, 58, 42, 32, 32, 42, 68, 17, 42, 68, 83],
170 );
171
172 assert_eq!(Schulze::new(&x).run().unwrap().winner().unwrap(), 1);
173 }
174 #[test]
175 fn schulze_wiki() {
176 let x = VoteMatrix::with_vector_bycol(&vec![
177 25, 0, 0, 23, 0, 29, 0, 27, 26, 0, 28, 0, 30, 33, 0, 31, 0, 0, 24, 0,
178 ]);
179 assert_eq!(Schulze::new(&x).run().unwrap().winner().unwrap(), 4);
180 }
181
182 #[test]
183 fn schulze_no_wins() {
184 let x = VoteMatrix::with_vector_bycol(&vec![3, 3, 3, 3, 3, 3]);
185 match Schulze::new(&x).run().unwrap_err() {
186 ElectionError::DegeneratedElectionGraph => (),
187 _ => unreachable!(),
188 }
189 }
190 #[test]
191 fn schulze_no_cands() {
192 let x: VoteMatrix = VoteMatrix::with_vector_bycol(&vec![]);
193 match Schulze::new(&x).run().unwrap_err() {
194 ElectionError::NotEnoughCandidates => (),
195 _ => unreachable!(),
196 }
197 }
198}