In Rust's petgraph how can I test whether a node is part of a cycle?

Question

I'm using Rust's petgraph library and am wondering how I can check if a node is part of a cycle. The petgraph::algo::is_cyclic_directed function will tell me whether there is any cycle in the graph, but after looking all through the docs I couldn't find any functions that would tell me whether a node is part of a cycle or not. I would have thought it would be a common enough task that a helper function would be warranted.

Now I could traverse the graph myself, but the code I could come up with would neither be the most concise nor would it be likely to be highly efficient.

What's the best option here?

Answer 1

I think this code is working, but would appreciate alternatives if anyone knows of a better way!

use petgraph::{algo, visit};
fn is_node_in_cycle<G>(graph: G, node: G::NodeId) -> bool
where G: visit::IntoNeighbors + visit::Visitable {
    let mut space = algo::DfsSpace::new(&graph);
    for neighbour in graph.neighbors(node) {
        if algo::has_path_connecting(graph, neighbour, node, Some(&mut space)) {
            return true
        }
    }
    false
}