rust_igraph/algorithms/properties/
topological_sorting.rs

1//! Topological sorting (ALGO-PR-021).
2//!
3//! Counterpart of `igraph_topological_sorting()` from
4//! `references/igraph/src/properties/dag.c:54`. Produces a linear
5//! ordering of a directed graph's vertices such that for every
6//! edge `u → v`, `u` precedes `v` in the order (under
7//! [`DijkstraMode::Out`]; flip for [`DijkstraMode::In`]).
8//!
9//! Algorithm: Kahn's algorithm — same peel loop as
10//! [`crate::is_dag`] but recording each popped vertex in the
11//! output rather than just counting. **Self-loops are ignored**
12//! when computing degrees: a vertex's own self-loop does not
13//! contribute to its in/out-degree, so a self-loop alone does not
14//! block topological sorting (matches upstream).
15//!
16//! Time complexity: `O(V + E)`.
17
18use std::collections::VecDeque;
19
20use crate::algorithms::paths::dijkstra::DijkstraMode;
21use crate::core::Graph;
22use crate::core::error::{IgraphError, IgraphResult};
23use crate::core::graph::VertexId;
24
25/// Returns a topological ordering of `graph`'s vertices.
26///
27/// `mode` controls the direction of "precedes":
28/// - [`DijkstraMode::Out`] (most common): for every edge `u → v`,
29///   `u` appears before `v` in the result. Vertices with no
30///   incoming edges come first.
31/// - [`DijkstraMode::In`]: reversed — for every edge `u → v`,
32///   `v` appears before `u`. Vertices with no outgoing edges come
33///   first.
34/// - [`DijkstraMode::All`]: rejected with
35///   [`IgraphError::InvalidArgument`] — topological sorting only
36///   makes sense in a directional sense.
37///
38/// Self-loops are ignored when computing degrees (matches
39/// upstream): a single self-loop with no other in/out edges
40/// does not block sorting.
41///
42/// Errors:
43/// - [`IgraphError::InvalidArgument`] if the graph is undirected.
44/// - [`IgraphError::InvalidArgument`] if the graph contains a
45///   non-trivial cycle (a topological ordering does not exist).
46///
47/// Counterpart of `igraph_topological_sorting(_, _, mode)` from
48/// `references/igraph/src/properties/dag.c:54`.
49///
50/// # Examples
51///
52/// ```
53/// use rust_igraph::{Graph, topological_sorting, DijkstraMode};
54///
55/// // 0 → 1, 0 → 2, 1 → 3, 2 → 3: a DAG with two valid orderings.
56/// let mut g = Graph::new(4, true).unwrap();
57/// g.add_edges(vec![(0u32, 1u32), (0, 2), (1, 3), (2, 3)]).unwrap();
58/// let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
59/// // 0 must come first; 3 must come last.
60/// assert_eq!(order[0], 0);
61/// assert_eq!(order[3], 3);
62/// ```
63pub fn topological_sorting(graph: &Graph, mode: DijkstraMode) -> IgraphResult<Vec<VertexId>> {
64    if !graph.is_directed() {
65        return Err(IgraphError::InvalidArgument(
66            "topological_sorting requires a directed graph".to_string(),
67        ));
68    }
69    if matches!(mode, DijkstraMode::All) {
70        return Err(IgraphError::InvalidArgument(
71            "topological_sorting does not accept DijkstraMode::All".to_string(),
72        ));
73    }
74    let walk_forward = matches!(mode, DijkstraMode::Out);
75
76    let n = graph.vcount();
77    let n_us = n as usize;
78
79    // `degrees[v]` = number of edges to be consumed before v is
80    // ready to emit. For OUT mode this is the in-degree; for IN
81    // mode the out-degree. Self-loops are NOT counted (upstream
82    // passes IGRAPH_NO_LOOPS to igraph_degree).
83    let mut degrees: Vec<u32> = vec![0; n_us];
84    for v in 0..n {
85        let incidents = if walk_forward {
86            graph.incident_in(v)?
87        } else {
88            graph.incident(v)?
89        };
90        let mut count: u32 = 0;
91        for eid in incidents {
92            let other = graph.edge_other(eid, v)?;
93            if other != v {
94                count = count.saturating_add(1);
95            }
96        }
97        degrees[v as usize] = count;
98    }
99
100    // Seed the queue with every zero-degree vertex.
101    let mut sources: VecDeque<VertexId> = VecDeque::new();
102    for v in 0..n {
103        if degrees[v as usize] == 0 {
104            sources.push_back(v);
105        }
106    }
107
108    let mut order: Vec<VertexId> = Vec::with_capacity(n_us);
109    while let Some(v) = sources.pop_front() {
110        order.push(v);
111        // Walk v's edges in the forward direction; for each
112        // out-neighbour (in OUT mode) or in-neighbour (in IN mode),
113        // decrement its degree counter.
114        let outgoing = if walk_forward {
115            graph.incident(v)?
116        } else {
117            graph.incident_in(v)?
118        };
119        for eid in outgoing {
120            let nei = graph.edge_other(eid, v)?;
121            if nei == v {
122                // Self-loop: ignored.
123                continue;
124            }
125            let nei_idx = nei as usize;
126            degrees[nei_idx] = degrees[nei_idx].saturating_sub(1);
127            if degrees[nei_idx] == 0 {
128                sources.push_back(nei);
129            }
130        }
131    }
132
133    if order.len() != n_us {
134        return Err(IgraphError::InvalidArgument(
135            "topological_sorting: graph contains a cycle (no valid ordering exists)".to_string(),
136        ));
137    }
138    Ok(order)
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144    use crate::core::Graph;
145
146    #[test]
147    fn empty_directed_graph_returns_empty_order() {
148        let g = Graph::new(0, true).unwrap();
149        let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
150        assert!(order.is_empty());
151    }
152
153    #[test]
154    fn isolated_vertices_only_returns_all_in_some_order() {
155        let g = Graph::new(3, true).unwrap();
156        let mut order = topological_sorting(&g, DijkstraMode::Out).unwrap();
157        order.sort_unstable();
158        assert_eq!(order, vec![0, 1, 2]);
159    }
160
161    #[test]
162    fn linear_chain_out_mode_preserves_order() {
163        // 0 → 1 → 2 → 3: only one valid topological order in OUT mode.
164        let mut g = Graph::new(4, true).unwrap();
165        g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 3)]).unwrap();
166        let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
167        assert_eq!(order, vec![0, 1, 2, 3]);
168    }
169
170    #[test]
171    fn linear_chain_in_mode_reverses_order() {
172        // 0 → 1 → 2 → 3 with IN mode: sinks first.
173        let mut g = Graph::new(4, true).unwrap();
174        g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 3)]).unwrap();
175        let order = topological_sorting(&g, DijkstraMode::In).unwrap();
176        assert_eq!(order, vec![3, 2, 1, 0]);
177    }
178
179    #[test]
180    fn diamond_dag_respects_edge_order() {
181        // 0 → 1, 0 → 2, 1 → 3, 2 → 3. Valid orders: [0,1,2,3], [0,2,1,3].
182        let mut g = Graph::new(4, true).unwrap();
183        g.add_edges(vec![(0u32, 1u32), (0, 2), (1, 3), (2, 3)])
184            .unwrap();
185        let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
186        // 0 first, 3 last; 1 and 2 in between.
187        assert_eq!(order[0], 0);
188        assert_eq!(order[3], 3);
189        assert!(
190            order == vec![0, 1, 2, 3] || order == vec![0, 2, 1, 3],
191            "unexpected order: {order:?}"
192        );
193    }
194
195    #[test]
196    fn self_loop_does_not_block_sorting() {
197        // 0 with self-loop, then 0 → 1. Order should be [0, 1].
198        let mut g = Graph::new(2, true).unwrap();
199        g.add_edge(0, 0).unwrap();
200        g.add_edge(0, 1).unwrap();
201        let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
202        assert_eq!(order, vec![0, 1]);
203    }
204
205    #[test]
206    fn three_cycle_errors() {
207        let mut g = Graph::new(3, true).unwrap();
208        g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 0)]).unwrap();
209        let err = topological_sorting(&g, DijkstraMode::Out).unwrap_err();
210        assert!(matches!(err, IgraphError::InvalidArgument(_)));
211    }
212
213    #[test]
214    fn undirected_graph_errors() {
215        let mut g = Graph::with_vertices(2);
216        g.add_edge(0, 1).unwrap();
217        let err = topological_sorting(&g, DijkstraMode::Out).unwrap_err();
218        assert!(matches!(err, IgraphError::InvalidArgument(_)));
219    }
220
221    #[test]
222    fn all_mode_errors() {
223        let mut g = Graph::new(2, true).unwrap();
224        g.add_edge(0, 1).unwrap();
225        let err = topological_sorting(&g, DijkstraMode::All).unwrap_err();
226        assert!(matches!(err, IgraphError::InvalidArgument(_)));
227    }
228
229    #[test]
230    fn parallel_edges_dont_block_ordering() {
231        // 0 → 1 with parallel edges; still valid DAG, order = [0, 1].
232        let mut g = Graph::new(2, true).unwrap();
233        g.add_edge(0, 1).unwrap();
234        g.add_edge(0, 1).unwrap();
235        let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
236        assert_eq!(order, vec![0, 1]);
237    }
238
239    #[test]
240    fn topological_order_respects_every_edge() {
241        // 0 → 2, 1 → 2, 2 → 3, 2 → 4 — order must place 0,1 before 2,
242        // and 2 before 3,4.
243        let mut g = Graph::new(5, true).unwrap();
244        g.add_edges(vec![(0u32, 2u32), (1, 2), (2, 3), (2, 4)])
245            .unwrap();
246        let order = topological_sorting(&g, DijkstraMode::Out).unwrap();
247        let pos: Vec<usize> = {
248            let mut p = vec![0usize; 5];
249            for (i, &v) in order.iter().enumerate() {
250                p[v as usize] = i;
251            }
252            p
253        };
254        // Every edge u → v must have pos[u] < pos[v].
255        let m = u32::try_from(g.ecount()).expect("ecount fits in u32 in test");
256        for e in 0..m {
257            let (u, v) = g.edge(e).unwrap();
258            if u == v {
259                continue;
260            }
261            assert!(
262                pos[u as usize] < pos[v as usize],
263                "edge {u}→{v} violates order"
264            );
265        }
266    }
267
268    #[test]
269    fn cycle_with_tail_still_errors() {
270        // 0 → 1 → 2 → 0 (cycle) + extra source 3 → 0. Tail 3 can be
271        // peeled but the cycle remains → error.
272        let mut g = Graph::new(4, true).unwrap();
273        g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 0), (3, 0)])
274            .unwrap();
275        let err = topological_sorting(&g, DijkstraMode::Out).unwrap_err();
276        assert!(matches!(err, IgraphError::InvalidArgument(_)));
277    }
278}
rust_igraph/algorithms/properties/topological_sorting.rs

rust_igraph/algorithms/properties/
topological_sorting.rs
