ranked_pairs/
lib.rs

1#![warn(missing_docs)]
2#![feature(btree_cursors)]
3
4//! Ranked pairs (Tideman method) election method, with handling of ties.
5
6mod graph;
7mod pairwise;
8
9#[cfg(test)]
10mod test;
11
12use std::collections::{BTreeSet, HashSet};
13
14use itertools::Itertools as _;
15
16/// Tally election results
17///
18/// Each ballot consists of a list of choices in order, candidate numbers are zero-based. The
19/// function returns the set of winners, using the algorithm in "Independence of clones as a
20/// criterion for voting rules" (Tideman, 1986). Specifically, as each winning margin is added to
21/// the graph, every possible order is considered. Any candidate who is can win in any scenario is
22/// considered to be in the winning set.
23///
24/// # Errors
25/// An error will be returned if any ballot contains an invalid candidate number (`>= candidates`)
26/// or contains the same candidate more than once.
27pub fn tally<B: AsRef<[u16]>>(ballots: &[B], candidates: u16) -> Result<BTreeSet<u16>, Error> {
28    check_ballots(ballots, candidates)?;
29
30    // return easy cases immediately
31    match candidates {
32        0 => return Ok(BTreeSet::from([])),
33        1 => return Ok(BTreeSet::from([0])),
34        _ => {}
35    }
36
37    let pairwise_results = pairwise::tabulate_pairwise_results(ballots, candidates);
38
39    // create a graph
40    let mut graphs = HashSet::from([graph::AcyclicGraph::new(candidates)]);
41
42    println!("{pairwise_results:?}");
43
44    // iterate over each group of equal-margin pairings, in order from largest margin of victory to
45    // smallest (reverse of usual order)
46    for pairings in pairwise_results.into_values().rev() {
47        // get every possible ordering of the pairings with this margin of victory
48        let possible_match_orders = pairings.iter().copied().permutations(pairings.len());
49
50        // take every possible graph so far and modify it in each possible order
51        graphs = graphs
52            .into_iter()
53            .cartesian_product(possible_match_orders)
54            .map(|(mut graph, matches)| {
55                for (winner, loser) in matches {
56                    // just skip adding if it would add a cycle
57                    graph.try_add_edge(winner, loser);
58                }
59                graph
60            })
61            .collect();
62    }
63
64    // return nodes with no incoming edges (unbeaten candidates) in any possible scenario
65    Ok(graphs.iter().flat_map(|graph| graph.roots()).collect())
66}
67
68fn check_ballots<B: AsRef<[u16]>>(ballots: &[B], candidates: u16) -> Result<(), Error> {
69    for ballot in ballots {
70        let ballot = ballot.as_ref();
71
72        // tracker for what candidates have been seen in this ballot
73        let mut selections = range_set_blaze::RangeSetBlaze::new();
74
75        for v in ballot {
76            if *v >= candidates {
77                // invalid candidate number
78                return Err(Error::InvalidCandidate);
79            }
80
81            let v = usize::from(*v);
82            if !selections.insert(v) {
83                // duplicate candidate number
84                return Err(Error::InvalidBallot);
85            }
86        }
87    }
88
89    Ok(())
90}
91
92/// An error while tallying an election
93#[derive(thiserror::Error, Debug, PartialEq, Eq)]
94#[non_exhaustive]
95pub enum Error {
96    /// A ballot had a duplicate choice
97    #[error("an invalid ballot was given")]
98    InvalidBallot,
99    /// A ballot contained an invalid candidate number
100    #[error("an invalid candidate was voted for")]
101    InvalidCandidate,
102}
ranked_pairs/lib.rs

ranked_pairs/
lib.rs
