stable_toposort 0.1.0

Deterministic and stable topological sorting algorithms
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

use std::collections::HashSet;

use crate::scc;
use crate::stable_toposort;

#[derive(Debug, Clone)]
pub struct Condensation<N> {
    pub components: Vec<Vec<N>>,
    pub edges: Vec<(usize, usize)>,
}

pub fn condensation<N>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
) -> Condensation<N>
where
    N: Eq + std::hash::Hash + Clone,
{
    let nodes: Vec<N> = nodes.into_iter().collect();
    let edges: Vec<(N, N)> = edges.into_iter().collect();

    let components = scc(nodes.clone(), edges.iter().cloned());
    let comp_of: std::collections::HashMap<N, usize> = components
        .iter()
        .enumerate()
        .flat_map(|(i, c)| c.iter().map(move |n| (n.clone(), i)))
        .collect();

    let mut edge_set: HashSet<(usize, usize)> = HashSet::new();
    for (a, b) in &edges {
        if let (Some(&i), Some(&j)) = (comp_of.get(a), comp_of.get(b)) {
            if i != j {
                edge_set.insert((i, j));
            }
        }
    }
    let edges = edge_set.into_iter().collect();

    Condensation { components, edges }
}

pub fn condensation_by_key<N, K>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
    key: impl Fn(&N) -> K,
) -> Condensation<N>
where
    N: Eq + std::hash::Hash + Clone,
    K: Ord,
{
    let mut cond = condensation(nodes, edges);
    for comp in &mut cond.components {
        comp.sort_by_key(&key);
    }
    cond
}

pub fn stable_toposort_scc<N>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
) -> Vec<Vec<N>>
where
    N: Eq + std::hash::Hash + Clone,
{
    let cond = condensation(nodes, edges);
    let order = stable_toposort(
        0..cond.components.len(),
        cond.edges.iter().copied(),
    )
    .expect("condensation is a DAG");
    order
        .into_iter()
        .map(|i| cond.components[i].clone())
        .collect()
}

pub fn stable_toposort_scc_by_key<N, K>(
    nodes: impl IntoIterator<Item = N>,
    edges: impl IntoIterator<Item = (N, N)>,
    key: impl Fn(&N) -> K,
) -> Vec<Vec<N>>
where
    N: Eq + std::hash::Hash + Clone,
    K: Ord,
{
    let mut sccs = stable_toposort_scc(nodes, edges);
    for comp in &mut sccs {
        comp.sort_by_key(&key);
    }
    sccs
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn dag_components_singleton() {
        let cond = condensation([1, 2], [(1, 2)]);
        assert_eq!(cond.components.len(), 2);
        assert_eq!(cond.edges.len(), 1);
    }

    #[test]
    fn by_key_sorts_components() {
        let nodes = ["B", "A", "C"];
        let edges = [("A", "B"), ("B", "C"), ("C", "A")];
        let cond = condensation_by_key(nodes, edges, |n| *n);
        assert_eq!(cond.components.len(), 1);
        assert_eq!(&cond.components[0], &["A", "B", "C"]);
    }

    #[test]
    fn stable_toposort_scc_by_key_orders_within_components() {
        let nodes: [&str; 3] = ["C", "A", "B"];
        let edges = [("A", "B"), ("B", "C")];
        let sccs = super::stable_toposort_scc_by_key(nodes, edges, |n: &&str| *n);
        assert_eq!(sccs.len(), 3);
        assert_eq!(sccs[0], ["A"]);
        assert_eq!(sccs[1], ["B"]);
        assert_eq!(sccs[2], ["C"]);
    }
}