webgraph_algo/
acyclicity.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::{EventPred, SeqPath},
10    visits::{Sequential, StoppedWhenDone},
11};
12use dsi_progress_logger::prelude::*;
13use std::ops::ControlFlow::{Break, Continue};
14use webgraph::traits::RandomAccessGraph;
15
16/// Returns whether the graph is acyclic.
17///
18/// This method performs a depth-first visit of the graph, stopping as soon as
19/// a cycle is detected.
20pub fn is_acyclic(graph: impl RandomAccessGraph, pl: &mut impl ProgressLog) -> bool {
21    let num_nodes = graph.num_nodes();
22    pl.item_name("node");
23    pl.expected_updates(Some(num_nodes));
24    pl.start("Checking acyclicity");
25
26    let mut visit = SeqPath::new(&graph);
27
28    let acyclic = visit.visit(0..num_nodes, |event| {
29        // Stop the visit as soon as a back edge is found.
30        match event {
31            EventPred::Previsit { .. } => {
32                pl.light_update();
33                Continue(())
34            }
35            EventPred::Revisit { on_stack: true, .. } => Break(StoppedWhenDone {}),
36            _ => Continue(()),
37        }
38    });
39
40    pl.done();
41    acyclic.is_continue()
42}
webgraph_algo/acyclicity.rs

webgraph_algo/
acyclicity.rs
