graph_traversal/
topo.rs

1use crate::cycle::has_cycle_directed;
2use crate::dfs::dfs_full;
3use graph_collections::Queue;
4use graph_core::{Graph, GraphError, NodeId};
5use std::collections::HashMap;
6
7/// Returns a topological ordering of the nodes using **DFS finish order**.
8///
9/// Works only on directed acyclic graphs (DAGs). If the graph contains a
10/// cycle, returns [`GraphError::InvalidOperation`].
11///
12/// The reverse of the DFS finish order is a valid topological sort: a node
13/// appears before all nodes that depend on it.
14///
15/// # Errors
16///
17/// Returns `Err(GraphError::InvalidOperation)` if the graph has a cycle.
18///
19/// # Examples
20///
21/// ```
22/// use graph_core::{AdjacencyList, Graph};
23/// use graph_traversal::topological_sort_dfs;
24///
25/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
26/// let a = g.add_node(());
27/// let b = g.add_node(());
28/// let c = g.add_node(());
29/// g.add_edge(a, b, 1.0).unwrap();
30/// g.add_edge(b, c, 1.0).unwrap();
31///
32/// let order = topological_sort_dfs(&g).unwrap();
33/// // a must come before b, b before c
34/// let pos: std::collections::HashMap<_, _> =
35///     order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
36/// assert!(pos[&a] < pos[&b]);
37/// assert!(pos[&b] < pos[&c]);
38/// ```
39pub fn topological_sort_dfs<G: Graph>(graph: &G) -> Result<Vec<NodeId>, GraphError> {
40    if has_cycle_directed(graph) {
41        return Err(GraphError::InvalidOperation(
42            "topological sort requires a DAG — cycle detected",
43        ));
44    }
45
46    let mut finish_order = dfs_full(graph, &mut |_| {});
47    finish_order.reverse();
48    Ok(finish_order)
49}
50
51/// Returns a topological ordering using **Kahn's algorithm** (in-degree BFS).
52///
53/// Processes nodes with in-degree 0 first; decrementing neighbours' in-degrees
54/// as each node is emitted. If not all nodes are emitted the graph has a cycle.
55///
56/// # Errors
57///
58/// Returns `Err(GraphError::InvalidOperation)` if a cycle is detected.
59///
60/// # Examples
61///
62/// ```
63/// use graph_core::{AdjacencyList, Graph};
64/// use graph_traversal::topological_sort_kahn;
65///
66/// let mut g: AdjacencyList<()> = AdjacencyList::directed();
67/// let a = g.add_node(());
68/// let b = g.add_node(());
69/// let c = g.add_node(());
70/// g.add_edge(a, b, 1.0).unwrap();
71/// g.add_edge(a, c, 1.0).unwrap();
72/// g.add_edge(b, c, 1.0).unwrap();
73///
74/// let order = topological_sort_kahn(&g).unwrap();
75/// let pos: std::collections::HashMap<_, _> =
76///     order.iter().enumerate().map(|(i, &n)| (n, i)).collect();
77/// assert!(pos[&a] < pos[&b]);
78/// assert!(pos[&b] < pos[&c]);
79/// ```
80pub fn topological_sort_kahn<G: Graph>(graph: &G) -> Result<Vec<NodeId>, GraphError> {
81    // Compute in-degrees.
82    let mut in_degree: HashMap<NodeId, usize> = graph.nodes().map(|n| (n, 0usize)).collect();
83
84    for node in graph.nodes() {
85        for (neighbour, _) in graph.neighbors(node) {
86            *in_degree.get_mut(&neighbour).unwrap() += 1;
87        }
88    }
89
90    // Seed queue with all zero-in-degree nodes.
91    let mut queue: Queue<NodeId> = Queue::new();
92    for (&node, &deg) in &in_degree {
93        if deg == 0 {
94            queue.enqueue(node);
95        }
96    }
97
98    let mut order: Vec<NodeId> = Vec::new();
99
100    while let Some(node) = queue.dequeue() {
101        order.push(node);
102        for (neighbour, _) in graph.neighbors(node) {
103            let deg = in_degree.get_mut(&neighbour).unwrap();
104            *deg -= 1;
105            if *deg == 0 {
106                queue.enqueue(neighbour);
107            }
108        }
109    }
110
111    if order.len() != graph.node_count() {
112        return Err(GraphError::InvalidOperation(
113            "topological sort requires a DAG — cycle detected",
114        ));
115    }
116
117    Ok(order)
118}
graph_traversal/topo.rs

graph_traversal/
topo.rs
