Struct Decycler 

pub(crate) struct Decycler<T, const D: usize> {
    node_ids: [T; D],
    depth: usize,
}

Cycle detector for a depth first traversal of a graph.

The graph is expected to have unique node identifiers of type T, and the traversal is limited to a depth of D.

Based on hb_decycler_t in HarfBuzz (https://github.com/harfbuzz/harfbuzz/blob/a2ea5d28cb5387f4de2049802474b817be15ad5b/src/hb-decycler.hh), an extension of Floyd’s tortoise and hare algorithm (https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare) to depth first traversals.

Unlike HarfBuzz, which supports traversals of any depth with a linked list on the stack, this stores the chain in a fixed array indexed by depth. This imposes the depth limit, which is also needed to prevent stack overflow.

Fields

node_ids: [T; D]

depth: usize

Implementations

impl<T, const D: usize> Decycler<T, D>

where T: Copy + PartialEq + Default,

pub(super) fn new() -> Self

pub(super) fn enter( &mut self, node_id: T, ) -> Result<DecyclerGuard<'_, T, D>, DecyclerError>

Enters the node uniquely identified by node_id.

Returns an error if a cycle is detected or the depth limit is reached. Otherwise, increases the depth and returns a guard that decreases it when dropped.

The guard dereferences to the decycler, so a recursive traversal can pass it down to check child nodes.

Trait Implementations

impl<T, const D: usize> Default for Decycler<T, D>

where T: Copy + PartialEq + Default,

fn default() -> Self

Returns the “default value” for a type.