wybr 0.0.6

Collection of preferential voting methods
Documentation 
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

//! Smith and Schwartz set calculation
//!
//! Beat graph can be divided into a directed acyclic graph of [strongly connected
//! components](https://en.wikipedia.org/wiki/Strongly_connected_component); union of the [maximal
//! elements](https://en.wikipedia.org/wiki/Maximal_element) of this DAG is either a
//! [Smith](https://en.wikipedia.org/wiki/Smith_set) or
//! [Schwartz](https://en.wikipedia.org/wiki/Schwartz_set) set, depending whether one considers
//! strong beats only (Schwartz), or beats and ties (Smith).
//! Whenever there is a Condorcet winner, both sets are single element and contain only them.

mod strongly_connected;
use self::SetType::*;
use crate::common::SetType;
use crate::tally::{Tally, VoteMatrix};
use strongly_connected::StronglyConnected;

/// Extracts Smith or Schwartz graph condensation
///
/// # Arguments
/// * `x` election tally, VoteMatrix object
/// * `set` mode of action, Smith or Schwartz
///
/// # Note
/// This is a low-level utility, it does not copy metadata.
/// For election-like API with Outcome, use smith_set or schwartz_set
pub fn smith_schwartz_condensation(x: &VoteMatrix, set: SetType) -> StronglyConnected {
    match set {
        Smith => x
            .pairs()
            .filter_map(|((r, o), (win, opp))| if win >= opp { Some((r, o)) } else { None })
            .collect(),
        Schwartz => x
            .pairs()
            .filter_map(|((r, o), (win, opp))| if win > opp { Some((r, o)) } else { None })
            // Candidates with only ties would not appear on the graph, hence we add an
            // edge c->c for each candidate
            .chain((0..x.get_candidates()).map(|x| (x, x)))
            .collect(),
    }
}

/// Extracts the Smith set
///
/// Smith set is a maximal strongly connected component in a condensation of a graph of a relation
/// candidate x strongly beats or ties with candidate y.
/// In other words, a smallest set of candidates such that its every member beats all candidates
/// outside the set.
/// Also called GETCHA or top cycle.
///
/// # Arguments
/// * `x` election tally, VoteMatrix object
pub fn smith_set(x: &VoteMatrix) -> Vec<u32> {
    let mut members = smith_schwartz_condensation(x, Smith).get_max();
    members.sort_unstable();
    members
}

/// Extracts the Schwartz set
///
/// Schwartz set is an union of maximal strongly connected components in a condensation of a graph
/// of a relation candidate x strongly beats candidate y.
///
/// # Arguments
/// * `x` election tally, VoteMatrix object
pub fn schwartz_set(x: &VoteMatrix) -> Vec<u32> {
    let mut members = smith_schwartz_condensation(x, Schwartz).get_max();
    members.sort_unstable();
    members
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn ss_simple() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //https://wiki.electorama.com/wiki/Beatpath_examples_3 ex1
            &vec![1, 2, 3, 4, 5, 6],
        );
        let sh = smith_set(&x);
        let sz = schwartz_set(&x);
        assert_eq!(sh, vec![0]);
        assert_eq!(sz, vec![0]);
    }
    #[test]
    fn ss_weak() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //https://wiki.electorama.com/wiki/Beatpath_examples_3 ex2
            &vec![1, 4, 2, 3, 4, 5],
        );
        assert_eq!(smith_set(&x), vec![0, 1, 2]);
        assert_eq!(schwartz_set(&x), vec![0]);
    }
    #[test]
    fn ss_leader_tie() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //https://wiki.electorama.com/wiki/Beatpath_examples_3 ex3
            &vec![9, 1, 9, 2, 3, 4],
        );
        assert_eq!(smith_set(&x), vec![0, 1]);
        assert_eq!(schwartz_set(&x), vec![0, 1]);
    }
    #[test]
    fn ss_full_tie() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //https://wiki.electorama.com/wiki/Beatpath_examples_3 ex4
            &vec![7, 7, 7, 7, 7, 7],
        );
        assert_eq!(smith_set(&x), vec![0, 1, 2]);
        assert_eq!(schwartz_set(&x), vec![0, 1, 2]);
    }
    #[test]
    fn ss_cycle() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //https://wiki.electorama.com/wiki/Beatpath_examples_3 ex5
            &vec![1, 2, 2, 1, 1, 2],
        );
        assert_eq!(smith_set(&x), vec![0, 1, 2]);
        assert_eq!(schwartz_set(&x), vec![0, 1, 2]);
    }

    #[test]
    fn ss_cycle_alt() {
        let x: VoteMatrix = VoteMatrix::with_vector_bycol(
            //https://wiki.electorama.com/wiki/Beatpath_examples_3 ex5
            &vec![0, 1, 1, 0, 0, 1],
        );
        assert_eq!(smith_set(&x), vec![0, 1, 2]);
        assert_eq!(schwartz_set(&x), vec![0, 1, 2]);
    }
}