webgraph_algo/
top_sort.rs

1/*
2 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4 *
5 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6 */
7
8use crate::{
9    visits::depth_first::SeqPred,
10    visits::{depth_first::*, Sequential},
11};
12use dsi_progress_logger::ProgressLog;
13use no_break::NoBreak;
14use std::ops::ControlFlow::Continue;
15use webgraph::traits::RandomAccessGraph;
16
17/// Returns the node of the graph in topological-sort order, if the graph is
18/// acyclic.
19///
20/// Otherwise, the order reflects the exit times from a depth-first visit of the
21/// graph.
22pub fn top_sort(graph: impl RandomAccessGraph, pl: &mut impl ProgressLog) -> Box<[usize]> {
23    let num_nodes = graph.num_nodes();
24    pl.item_name("node");
25    pl.expected_updates(Some(num_nodes));
26    pl.start("Computing topological sort");
27
28    let mut visit = SeqPred::new(&graph);
29    let mut top_sort = Box::new_uninit_slice(num_nodes);
30    let mut pos = num_nodes;
31
32    visit
33        .visit(0..num_nodes, |event| {
34            match event {
35                EventPred::Previsit { .. } => {
36                    pl.light_update();
37                }
38                EventPred::Postvisit { node, .. } => {
39                    pos -= 1;
40                    top_sort[pos].write(node);
41                }
42                _ => (),
43            }
44            Continue(())
45        })
46        .continue_value_no_break();
47
48    pl.done();
49    // SAFETY: we write in each element of top_sort
50    unsafe { top_sort.assume_init() }
51}
webgraph_algo/top_sort.rs

webgraph_algo/
top_sort.rs
