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