Struct Decycler

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

Cycle detector for DFS traversal of a graph.

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

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

Unlike the implementation in HB which supports traversals of arbitrary depth, this is limited to a constant value. Instead of building a forward-linked list of nodes (on the stack) to track the traversal chain, we simply use a fixed size array, indexed by depth, which imposes the limit.

It might be possible to implement the HB algorithm in safe Rust but satisfying the borrow checker would be a challenge and we require a depth limit to prevent stack overflows anyway. Improvements welcome!

Fields

node_ids: [T; D]

depth: usize

Implementations

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

where T: Copy + PartialEq + Default,

pub fn new() -> Self

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

Enters a new graph node with the given value that uniquely identifies the current node.

Returns an error when a cycle is detected or the max depth of the traversal is exceeded. Otherwise, increases the current depth and returns a guard object that will decrease the depth when dropped.

The guard object derefs to the decycler, so it can be passed to a recursive traversal function to check for cycles in descendent nodes in a graph.

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.