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?

I was going to say use `algo::has_path_connecting` from the node, to the node, and if it returns true, it has a cycle. Unfortunately *"If [the node] from and to are equal, this function returns true."* so this doesn't work. — David Sullivan, Feb 27 '21 at 07:50
@DavidSullivan Yep there are a few options like that which seemed promising until you read the full description. ;) — curiousdannii, Feb 27 '21 at 08:04

score 3 · Answer 1 · answered Feb 28 '21 at 05:57

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
}

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

1 Answers1