causal_hub/graphs/algorithms/traversal/
topological_sort.rs

1use std::collections::{HashMap, VecDeque};
2
3use crate::{graphs::DirectedGraph, Ch, V};
4
5/// Topological sort search structure.
6pub struct TopologicalSort<'a, G>
7where
8    G: DirectedGraph,
9{
10    /// Given graph reference.
11    g: &'a G,
12    // To-be-visited queue.
13    queue: VecDeque<usize>,
14    // Visit map with vertices in-degrees.
15    visit: HashMap<usize, usize>,
16}
17
18impl<'a, G> TopologicalSort<'a, G>
19where
20    G: DirectedGraph,
21{
22    /// Build a TopologicalSort iterator.
23    ///
24    /// Build a TopologicalSort[^1] iterator for a given directed graph.
25    ///
26    /// If the graph is cyclic, this iterator returns an error while unrolling.
27    ///
28    /// [^1]: [Kahn, A. B. (1962). Topological sorting of large networks. Communications of the ACM, 5(11), 558-562.](https://scholar.google.com/scholar?q=Topological+sorting+of+large+networks)
29    ///
30    pub fn new(g: &'a G) -> Self {
31        // Initialize default search object.
32        let mut search = Self {
33            // Set target graph.
34            g,
35            // Initialize the to-be-visited queue with the source vertex.
36            queue: Default::default(),
37            // Initialize the visit map.
38            visit: Default::default(),
39        };
40        // For each vertex in the graph.
41        for x in V!(search.g) {
42            // Compute its in-degree.
43            match search.g.in_degree(x) {
44                // If the in-degree is zero, then add it to the queue.
45                0 => search.queue.push_back(x),
46                // Otherwise, add it to the map.
47                y => {
48                    search.visit.insert(x, y);
49                }
50            }
51        }
52
53        search
54    }
55}
56
57impl<'a, G> Iterator for TopologicalSort<'a, G>
58where
59    G: DirectedGraph,
60{
61    type Item = usize;
62
63    fn next(&mut self) -> Option<Self::Item> {
64        // While there are still vertices with zero in-degree.
65        if let Some(x) = self.queue.pop_front() {
66            // For each child of the selected vertex.
67            for y in Ch!(self.g, x) {
68                // If it was not visited before.
69                if let Some(z) = self.visit.get(&y) {
70                    // Update its in-degree.
71                    match z - 1 {
72                        // If the in-degree is zero ...
73                        0 => {
74                            // ... then add it to the queue ...
75                            self.queue.push_back(y);
76                            // ... and remove it from the visit map.
77                            self.visit.remove(&y);
78                        }
79                        // Otherwise, update its in-degree into the map.
80                        z => {
81                            self.visit.insert(y, z);
82                        }
83                    }
84                }
85            }
86            // Return current vertex.
87            return Some(x);
88        }
89
90        // If there are still vertices with non-zero in-degree ...
91        if !self.visit.is_empty() {
92            // ... no topological sort is defined, i.e. cyclic graph.
93            panic!("No topological sort is defined, i.e. cyclic graph");
94        }
95
96        None
97    }
98}
99
100impl<'a, G> From<&'a G> for TopologicalSort<'a, G>
101where
102    G: DirectedGraph,
103{
104    /// Builds a search object from a given graph.
105    ///
106    fn from(g: &'a G) -> Self {
107        Self::new(g)
108    }
109}
causal_hub/graphs/algorithms/traversal/topological_sort.rs

causal_hub/graphs/algorithms/traversal/
topological_sort.rs
