competitive/graph/
topological_sort.rs

1use super::{DirectedGraph, VertexMap};
2
3pub trait TopologicalSortExt: DirectedGraph {
4    fn topological_sort(&self) -> Vec<Self::Vertex>
5    where
6        Self: VertexMap<usize>,
7    {
8        let mut indegree = self.construct_vmap(|| 0);
9        for u in self.vertices() {
10            for neighbor in self.neighbors(u) {
11                *self.vmap_get_mut(&mut indegree, neighbor.to) += 1;
12            }
13        }
14        let mut stack = self
15            .vertices()
16            .filter(|&u| *self.vmap_get(&indegree, u) == 0)
17            .collect::<Vec<_>>();
18        let mut order = Vec::with_capacity(self.vsize());
19        while let Some(u) = stack.pop() {
20            order.push(u);
21            for neighbor in self.neighbors(u) {
22                let indegree = self.vmap_get_mut(&mut indegree, neighbor.to);
23                *indegree -= 1;
24                if *indegree == 0 {
25                    stack.push(neighbor.to);
26                }
27            }
28        }
29        order
30    }
31}
32
33impl<G> TopologicalSortExt for G where G: DirectedGraph + ?Sized {}
34
35#[cfg(test)]
36mod tests {
37    use super::*;
38    use crate::{
39        graph::{DirectedSparseGraph, UsizeGraph},
40        rand,
41        tools::Xorshift,
42    };
43
44    #[test]
45    fn test_topological_sort() {
46        const Q: usize = 1_000;
47        const N: usize = 8;
48        const M: usize = 20;
49        let mut rng = Xorshift::default();
50        for _ in 0..Q {
51            rand!(rng, n: 1..=N, m: 0..=M, edges: [(0..n, 0..n); m]);
52            let mut reachable = vec![vec![false; n]; n];
53            for &(u, v) in &edges {
54                reachable[u][v] = true;
55            }
56            for k in 0..n {
57                for i in 0..n {
58                    for j in 0..n {
59                        if reachable[i][k] && reachable[k][j] {
60                            reachable[i][j] = true;
61                        }
62                    }
63                }
64            }
65            let acyclic = (0..n).all(|u| !reachable[u][u]);
66            let sparse = DirectedSparseGraph::from_edges(n, edges.clone());
67            let closure = UsizeGraph::new(n, |u| {
68                edges
69                    .iter()
70                    .filter(move |&&(from, _)| from == u)
71                    .map(|&(_, to)| (to, ()))
72            });
73
74            for order in [sparse.topological_sort(), closure.topological_sort()] {
75                let mut position = vec![None; n];
76                for (i, vertex) in order.into_iter().enumerate() {
77                    assert!(position[vertex].replace(i).is_none());
78                }
79                for &(u, v) in &edges {
80                    if let Some(v) = position[v] {
81                        assert!(position[u].is_some_and(|u| u < v));
82                    }
83                }
84                assert_eq!(position.iter().all(Option::is_some), acyclic);
85            }
86        }
87    }
88}
competitive/graph/topological_sort.rs

competitive/graph/
topological_sort.rs
