algorithms_edu/algo/graph/
topological_sort.rs

1//! # Topological Sort
2//!
3//! This topological sort implementation takes an adjacency list of an acyclic graph and returns an
4//! array with the indexes of the nodes in a (non unique) topological order which tells you how to
5//! process the nodes in the graph. More precisely from wiki: A topological ordering is a linear
6//! ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes
7//! before v in the ordering.
8//!
9//! - Time Complexity: O(V + E)
10//!
11//! # Resources
12//!
13//! - [W. Fiset's video](https://www.youtube.com/watch?v=eL-KzMXSXXI&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=15)
14//! - [W. Fiset's video (Khan's algorithm)](https://www.youtube.com/watch?v=cIBFEhD77b4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=16)
15
16use crate::algo::graph::{Edge, WeightedAdjacencyList};
17use partial_min_max::min;
18
19impl WeightedAdjacencyList {
20    pub fn toposort(&self) -> Vec<usize> {
21        let n = self.node_count();
22        let mut visited = vec![false; n];
23        let mut ordering = vec![0usize; n];
24        let mut i = n - 1;
25
26        fn _dfs(
27            mut i: usize,
28            at: usize,
29            visited: &mut [bool],
30            ordering: &mut [usize],
31            graph: &WeightedAdjacencyList,
32        ) -> usize {
33            visited[at] = true;
34            for &edge in &graph[at] {
35                if !visited[edge.to] {
36                    i = _dfs(i, edge.to, visited, ordering, graph);
37                }
38            }
39            ordering[i] = at;
40            i.saturating_sub(1)
41        }
42
43        for at in 0..n {
44            if !visited[at] {
45                i = _dfs(i, at, &mut visited, &mut ordering, &self);
46            }
47        }
48
49        ordering
50    }
51    /// Imagine building a program with dependencies
52    pub fn toposort_khan(&self) -> Vec<usize> {
53        let n = self.node_count();
54        // `dependencies[i]` is the number of nodes pointing to node `i`
55        let mut dependencies = vec![0; n];
56        // identify all dependencies
57        for (_dependency, dependent, _cost) in self.edges() {
58            dependencies[dependent] += 1;
59        }
60        // a "buildable" is not pointed to by other nodes
61        let mut buildables: Vec<_> = (0..n).filter(|&i| dependencies[i] == 0).collect();
62        let mut i = 0;
63        // Remove buildable nodes and decrease the degree of each node adding new buildable nodes progressively
64        // until only the centers remain.
65        let mut ordering = vec![0; n];
66        while i < n {
67            let mut new_buildables = Vec::new();
68            for &buildable in &buildables {
69                ordering[i] = buildable;
70                i += 1;
71                for &dependent in &self[buildable] {
72                    let x = &mut dependencies[dependent.to];
73                    *x -= 1;
74                    if *x == 0 {
75                        new_buildables.push(dependent.to);
76                    }
77                }
78            }
79            buildables = new_buildables;
80        }
81        ordering
82    }
83    pub fn dag_shortest_path(&self, start: usize) -> Vec<f64> {
84        let toposort = self.toposort_khan();
85        let mut dists = vec![f64::INFINITY; self.node_count()];
86        dists[start] = 0.;
87        let i = toposort
88            .iter()
89            .position(|&node_id| node_id == start)
90            .unwrap();
91        toposort.into_iter().skip(i).for_each(|node_id| {
92            let cur_dist = dists[node_id];
93            if cur_dist.is_finite() {
94                for &Edge { to, weight } in &self[node_id] {
95                    let new_dist = cur_dist + weight;
96                    let dist = &mut dists[to];
97                    *dist = min(*dist, new_dist);
98                }
99            }
100        });
101        dists
102    }
103}
104
105#[cfg(test)]
106mod tests {
107
108    use super::*;
109    #[test]
110    fn test_toposort() {
111        // Example from https://www.youtube.com/watch?v=cIBFEhD77b4&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=16
112        // 7:12 of the video.
113        let edges = [
114            [0, 2],
115            [3, 1],
116            [1, 4],
117            [4, 5],
118            [3, 4],
119            [2, 6],
120            [6, 7],
121            [4, 8],
122            [9, 2],
123            [9, 10],
124            [10, 6],
125            [6, 11],
126            [11, 12],
127            [12, 8],
128            [7, 12],
129            [0, 6],
130        ];
131        let graph = WeightedAdjacencyList::new_directed_unweighted(13, &edges);
132        let ordering = graph.toposort_khan();
133        assert!(check_sort_result(&ordering, &edges));
134        let ordering = graph.toposort();
135        assert!(check_sort_result(&ordering, &edges));
136
137        fn check_sort_result(result: &[usize], edges: &[[usize; 2]]) -> bool {
138            let mut rank = vec![0; result.len()];
139            for (i, &node) in result.iter().enumerate() {
140                rank[node] = i;
141            }
142            edges
143                .iter()
144                .all(|&[dependency, dependent]| rank[dependency] < rank[dependent])
145        }
146    }
147    #[test]
148    fn test_dag_shortest_path() {
149        let edges = &[
150            (0, 1, 3.),
151            (0, 2, 2.),
152            (0, 5, 3.),
153            (1, 3, 1.),
154            (1, 2, 6.),
155            (2, 3, 1.),
156            (2, 4, 10.),
157            (3, 4, 5.),
158            (5, 4, 7.),
159        ];
160        let graph = WeightedAdjacencyList::new_directed(7, edges);
161        let dists = graph.dag_shortest_path(0);
162        assert_eq!(&dists, &[0., 3., 2., 3., 8., 3., f64::INFINITY])
163    }
164}
algorithms_edu/algo/graph/topological_sort.rs

algorithms_edu/algo/graph/
topological_sort.rs
