cyclicity

Graph cyclicity and Directed Acyclic Graph (DAG) analysis.

This module provides efficient algorithms for detecting cycles in graphs, which is fundamental for topological sorting, deadlock detection, and validating graph properties.

Algorithms

Problem	Algorithm	Function	Complexity
Cycle detection (directed)	Kahn’s algorithm	`is_acyclic/1`, `is_cyclic/1`	O(V + E)
Cycle detection (undirected)	Union-Find / DFS	`is_acyclic/1`, `is_cyclic/1`	O(V + E)

Key Concepts

Cycle: Path that starts and ends at the same vertex
Simple Cycle: No repeated vertices (except start/end)
Acyclic Graph: Graph with no cycles
DAG: Directed Acyclic Graph - directed graph with no directed cycles
Self-Loop: Edge from a vertex to itself

Cycle Detection Methods

Directed Graphs (Kahn’s Algorithm):

Repeatedly remove vertices with no incoming edges
If all vertices removed → acyclic
If stuck with remaining vertices → cycle exists

Undirected Graphs:

Track visited nodes during DFS
If we revisit a node (that’s not the immediate parent) → cycle exists
Self-loops also count as cycles

Applications of Cycle Detection

Dependency resolution: Detect circular dependencies in package managers
Deadlock detection: Resource allocation graphs in operating systems
Schema validation: Ensure no circular references in data models
Build systems: Detect circular dependencies in Makefiles
Course prerequisites: Validate prerequisite chains aren’t circular

Relationship to Other Properties

Tree: Connected acyclic graph
Forest: Disjoint union of trees (acyclic)
Topological sort: Only possible on DAGs (acyclic directed graphs)
Eulerian paths: Require specific degree conditions related to cycles

References

Values

is_acyclic

</>

pub fn is_acyclic(graph: model.Graph(n, e)) -> Bool

Checks if the graph is a Directed Acyclic Graph (DAG) or has no cycles if undirected.

For directed graphs, a cycle exists if there is a path from a node back to itself. For undirected graphs, a cycle exists if there is a path of length >= 3 from a node back to itself, or a self-loop.

Time Complexity: O(V + E)

is_cyclic

</>

pub fn is_cyclic(graph: model.Graph(n, e)) -> Bool

Checks if the graph contains at least one cycle.

Logical opposite of is_acyclic.

Time Complexity: O(V + E)