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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

use std::collections::{HashMap, HashSet};

//An online topo-sort from:
//David J. Pearce and Paul H.  J. Kelly.
//A dynamic algorithm for topologically sorting directed acyclic graphs.
//http://www.doc.ic.ac.uk/~phjk/Publications/DynTopoSortWEA2004.pdf

struct Candidate {
    beats: HashSet<u32>,
    beaten: HashSet<u32>,
}
impl Candidate {
    fn new() -> Candidate {
        Candidate {
            beats: HashSet::new(),
            beaten: HashSet::new(),
        }
    }
}

pub struct ForcedDag {
    graph: HashMap<u32, Candidate>,
    n2i: Vec<u32>,
}

impl ForcedDag {
    pub fn new(candidates: u32) -> ForcedDag {
        ForcedDag {
            graph: (0..candidates).map(|c| (c, Candidate::new())).collect(),
            n2i: (0..candidates).collect(),
        }
    }
    fn dfs(
        &self,
        v: u32,
        lim: u32,
        r: &mut Option<Vec<u32>>,
        visited: &mut HashSet<u32>,
        fwd: bool,
    ) -> bool {
        if let Some(x) = r.as_mut() {
            x.push(v);
        }
        visited.insert(v);
        if let Some(vv) = self.graph.get(&v) {
            let next = if fwd { &vv.beats } else { &vv.beaten };
            for vn in next {
                if self.n2i[*vn as usize] == lim {
                    //Cycle detected
                    return false;
                }
                if !visited.contains(vn)
                    && self.n2i[*vn as usize] < lim
                    && !self.dfs(*vn, lim, r, visited, fwd)
                {
                    return false;
                }
            }
        }; //Else never happens
        true
    }
    pub fn add_edge(&mut self, f: u32, t: u32) -> bool {
        let upper = self.n2i[f as usize]; //Position of f
        let lower = self.n2i[t as usize]; //Position of t
        if lower < upper {
            // upper!=lower, when upper<lower we just get lucky and add the edge
            let mut visited = HashSet::new();

            let mut rf: Option<Vec<u32>> = Some(Vec::new());
            if !self.dfs(t, upper, &mut rf, &mut visited, true) {
                return false;
            }

            let mut rb: Option<Vec<u32>> = Some(Vec::new());
            if !self.dfs(f, lower, &mut rb, &mut visited, false) {
                return false;
            }
            //Edge can be added!
            let mut rf = rf.unwrap();
            rf.sort_unstable_by(|&a, &b| self.n2i[a as usize].cmp(&self.n2i[b as usize]));
            let mut rb = rb.unwrap();
            rb.sort_unstable_by(|&a, &b| self.n2i[a as usize].cmp(&self.n2i[b as usize]));
            let to_realloc: Vec<u32> = rb.iter().chain(rf.iter()).cloned().collect();
            let mut idx_we_have: Vec<u32> =
                to_realloc.iter().map(|&x| self.n2i[x as usize]).collect();
            idx_we_have.sort_unstable();
            for (e, into) in to_realloc.iter().zip(idx_we_have) {
                self.n2i[*e as usize] = into
            }
        }
        self.graph.get_mut(&f).unwrap().beats.insert(t);
        self.graph.get_mut(&t).unwrap().beaten.insert(f);
        true
    }
    pub fn try_edge(&self, f: u32, t: u32) -> bool {
        let upper = self.n2i[f as usize]; //Position of f
        let lower = self.n2i[t as usize]; //Position of t
        lower > upper || {
            let mut visited = HashSet::new();
            self.dfs(t, upper, &mut None, &mut visited, true)
                && self.dfs(f, lower, &mut None, &mut visited, false)
        }
    }
    pub fn get_winner(&self) -> Result<u32, ()> {
        //All elements which beaten is null
        let mut winners = self.graph.iter().filter_map(|(&cid, cand)| {
            if cand.beaten.is_empty() {
                Some(cid)
            } else {
                None
            }
        });
        if let Some(winner) = winners.next() {
            if winners.next().is_none() {
                Ok(winner)
            } else {
                Err(())
            }
        } else {
            Err(())
        }
    }
    // pub fn get_topo(&self) -> Vec<u32> {
    //   let mut ans: Vec<u32> = (0..self.candidates).collect();
    //TODO: This is nonsense; just put each cand into topo[n2i[c]]<-c
    //  ans.sort_by(|&a, &b| self.n2i[a as usize].cmp(&self.n2i[b as usize]));
    //  ans
    // }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn basic() {
        let mut fd = ForcedDag::new(6);

        assert!(fd.add_edge(0, 1));
        assert!(fd.add_edge(2, 3));
        assert!(fd.add_edge(4, 5));

        assert!(fd.add_edge(0, 2));
        assert!(fd.add_edge(1, 3));
        assert!(fd.add_edge(4, 0));
        assert!(fd.add_edge(5, 1));

        assert!(!fd.add_edge(2, 4));

        assert!(fd.add_edge(2, 5));
    }
}