wolf_graph/algo/
topological_sort.rs

1use std::marker::PhantomData;
2
3use anyhow::Result;
4
5use crate::{DFSVisitor, DepthFirstSearch, EdgeID, Error, NodeID, Nodes, VisitableGraph};
6
7/// A trait for a graph that supports topological sort.
8pub trait TopologicalSort {
9    type Graph: VisitableGraph;
10
11    /// Returns reverse-order of topological sort.
12    fn topological_sort_opt(&self, roots: &Nodes, roots_only: bool) -> Result<Vec<NodeID>>;
13
14    /// Returns reverse-order of topological sort.
15    fn topological_sort(&self) -> Result<Vec<NodeID>> {
16        self.topological_sort_opt(&Nodes::new(), false)
17    }
18
19    fn is_dag(&self) -> bool {
20        self.topological_sort().is_ok()
21    }
22}
23
24impl<G> TopologicalSort for G
25where
26    G: VisitableGraph,
27{
28    type Graph = G;
29
30    fn topological_sort_opt(&self, roots: &Nodes, roots_only: bool) -> Result<Vec<NodeID>> {
31        let mut visitor = TopologicalSortVisitor::with_capacity(self.node_count());
32        self.depth_first_search_opt(&mut visitor, roots, roots_only, None::<EdgeID>)
33    }
34}
35
36pub struct TopologicalSortVisitor<Graph>
37where
38    Graph: VisitableGraph,
39{
40    order: Vec<NodeID>,
41    graph: PhantomData<Graph>,
42}
43
44impl<Graph> TopologicalSortVisitor<Graph>
45where
46    Graph: VisitableGraph,
47{
48    pub fn with_capacity(capacity: usize) -> Self {
49        Self {
50            order: Vec::with_capacity(capacity),
51            graph: PhantomData
52        }
53    }
54}
55
56impl<Graph> DFSVisitor for TopologicalSortVisitor<Graph>
57where
58    Graph: VisitableGraph,
59{
60    type Graph = Graph;
61    type Output = Vec<NodeID>;
62
63    fn back_edge(&mut self, _graph: &Self::Graph, _edge: &EdgeID) -> Result<Option<Self::Output>> {
64        Err(Error::NotADAG.into())
65    }
66
67    fn finish_node(&mut self, _graph: &Self::Graph, node: &NodeID) -> Result<Option<Self::Output>> {
68        self.order.push(node.clone());
69        Ok(None)
70    }
71
72    fn finish(&mut self, _graph: &Self::Graph) -> Result<Self::Output> {
73        Ok(self.order.clone().into_iter().rev().collect())
74    }
75}
wolf_graph/algo/topological_sort.rs

wolf_graph/algo/
topological_sort.rs
