ranked-pairs 0.0.2-alpha

A ranked pairs (Tideman method) election tallying library.
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

use std::collections::BTreeSet;

#[derive(Clone, PartialEq, Eq, Hash)]
pub struct AcyclicGraph {
    nodes: u16,
    edges: BTreeSet<(u16, u16)>,
}

impl AcyclicGraph {
    pub fn new(nodes: u16) -> Self {
        Self {
            nodes,
            edges: BTreeSet::new(),
        }
    }

    /// Try to add an edge, fails if it would cause a cycle
    ///
    /// Returns true if adding the edge succeeds and it is new.
    pub fn try_add_edge(&mut self, src: u16, dst: u16) -> bool {
        assert!(src < self.nodes);
        assert!(dst < self.nodes);

        if src != dst && self.dfs(dst).all(|e| e != src) {
            self.edges.insert((src, dst))
        } else {
            false
        }
    }

    pub fn roots(&self) -> impl Iterator<Item = u16> {
        #[allow(clippy::single_range_in_vec_init)]
        let mut elements = rangemap::RangeSet::from([0..self.nodes]);
        for e in &self.edges {
            elements.remove(e.1..e.1 + 1);
        }
        elements.into_iter().flatten()
    }

    fn dfs(&self, start: u16) -> impl Iterator<Item = u16> {
        debug_assert!(start < self.nodes);

        Dfs {
            graph: self,
            visited: Vec::new(),
            node: start,
        }
    }

    fn outgoing(&self, src: u16) -> impl Iterator<Item = u16> {
        debug_assert!(src < self.nodes);

        self.edges
            .iter()
            .copied()
            .filter_map(move |(s, d)| (s == src).then_some(d))
    }
}

struct Dfs<'g> {
    graph: &'g AcyclicGraph,
    visited: Vec<(u16, u16)>,
    node: u16,
}

impl Iterator for Dfs<'_> {
    type Item = u16;
    fn next(&mut self) -> Option<Self::Item> {
        match self.graph.outgoing(self.node).next() {
            Some(dst) => {
                self.visited.push((self.node, dst));
                self.node = dst;
                Some(dst)
            }
            None => loop {
                match self.visited.pop() {
                    Some(last) => {
                        let mut cursor = self
                            .graph
                            .edges
                            .upper_bound(std::ops::Bound::Included(&last));
                        while let Some((src, dst)) = cursor.next().copied() {
                            if src == last.0 {
                                self.visited.push((src, dst));
                                self.node = dst;
                                return Some(dst);
                            }
                        }
                    }
                    None => return None,
                }
            },
        }
    }
}

impl std::iter::FusedIterator for Dfs<'_> {}

#[cfg(test)]
mod test {
    use crate::graph::AcyclicGraph;

    #[test]
    fn dfs() {
        let mut graph = AcyclicGraph::new(12);

        // root to each child
        assert!(graph.try_add_edge(8, 9));
        assert!(graph.try_add_edge(8, 2));
        assert!(graph.try_add_edge(8, 3));

        // left child of root
        assert!(graph.try_add_edge(9, 10));
        assert!(graph.try_add_edge(10, 11));
        assert!(graph.try_add_edge(10, 0));
        assert!(graph.try_add_edge(9, 1));

        // right child of root
        assert!(graph.try_add_edge(3, 4));
        assert!(graph.try_add_edge(4, 5));
        assert!(graph.try_add_edge(4, 6));
        assert!(graph.try_add_edge(3, 7));

        assert_eq!(
            graph.dfs(8).collect::<Vec<_>>(),
            &[2, 3, 4, 5, 6, 7, 9, 1, 10, 0, 11]
        );
    }
}