Yog.Traversal.Cycle (YogEx v0.70.0)

Copy Markdown View Source

Cycle detection algorithms for directed and undirected graphs.

Summary

Functions

acyclic?(graph)

Determines if a graph is acyclic (contains no cycles).

cyclic?(graph)

Determines if a graph contains any cycles.

Functions

acyclic?(graph)

@spec acyclic?(Yog.graph()) :: boolean()

Determines if a graph is acyclic (contains no cycles).

Time Complexity: O(V + E)

cyclic?(graph)

@spec cyclic?(Yog.graph()) :: boolean()

Determines if a graph contains any cycles.

For directed graphs, uses Kahn's algorithm (topological sort). For undirected graphs, uses DFS-based back-edge detection.

Time Complexity: O(V + E)