Skip to main content

open_hypergraphs/strict/hypergraph/
acyclic.rs

1use crate::array::{Array, ArrayKind, NaturalArray};
2use crate::strict::graph;
3use crate::strict::hypergraph::Hypergraph;
4use num_traits::Zero;
5
6impl<K: ArrayKind, O, A> Hypergraph<K, O, A>
7where
8    K::Type<K::I>: NaturalArray<K>,
9    K::Type<O>: Array<K, O>,
10{
11    /// Returns true if there is no directed path from any node to itself.
12    ///
13    pub fn is_acyclic(&self) -> bool {
14        if self.w.len() == K::I::zero() {
15            return true;
16        }
17
18        let adjacency = graph::node_adjacency(self);
19        let (_order, unvisited) = graph::kahn(&adjacency);
20        unvisited.sum() == K::I::zero()
21    }
22}