Yog.Property.Cyclicity (YogEx v0.97.0)

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	`acyclic?/1`, `cyclic?/1`	O(V + E)
Cycle detection (undirected)	Union-Find / DFS	`acyclic?/1`, `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

Cyclicity Comparison

digraph G { rankdir=LR; bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; subgraph cluster_acyclic { label="Acyclic (DAG)"; color="#10b981"; style=rounded; A1 -> A2; A2 -> A3; A1 -> A3; } subgraph cluster_cyclic { label="Cyclic"; color="#ef4444"; style=rounded; C1 -> C2; C2 -> C3; C3 -> C1 [color="#ef4444", penwidth=2.5]; } }

iex> alias Yog.Property.Cyclicity
iex> dag = Yog.from_edges(:directed, [{"A1", "A2", 1}, {"A2", "A3", 1}, {"A1", "A3", 1}])
iex> Cyclicity.acyclic?(dag)
true
iex> cycle = Yog.from_edges(:directed, [{"C1", "C2", 1}, {"C2", "C3", 1}, {"C3", "C1", 1}])
iex> Cyclicity.cyclic?(cycle)
true

Examples

# DAG is acyclic
iex> dag = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Cyclicity.acyclic?(dag)
true
iex> Yog.Property.Cyclicity.cyclic?(dag)
false

# Triangle is cyclic
iex> triangle = Yog.undirected()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Property.Cyclicity.cyclic?(triangle)
true

References

Summary

Functions

acyclic?(graph)

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

cyclic?(graph)

Checks if the graph contains at least one cycle.

Functions

acyclic?(graph)

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

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.

Examples

# Empty graph is acyclic
iex> Yog.Property.Cyclicity.acyclic?(Yog.directed())
true

# Single node is acyclic
iex> graph = Yog.directed() |> Yog.add_node(1, "A")
iex> Yog.Property.Cyclicity.acyclic?(graph)
true

# DAG is acyclic
iex> dag = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
iex> Yog.Property.Cyclicity.acyclic?(dag)
true

# Self-loop creates a cycle
iex> cyclic = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_edge_ensure(from: 1, to: 1, with: 1)
iex> Yog.Property.Cyclicity.acyclic?(cyclic)
false

# Triangle is cyclic
iex> triangle = Yog.undirected()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Property.Cyclicity.acyclic?(triangle)
false

Time Complexity

O(V + E)

cyclic?(graph)

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

Checks if the graph contains at least one cycle.

Logical opposite of acyclic?/1.

Examples

# Empty graph is not cyclic
iex> Yog.Property.Cyclicity.cyclic?(Yog.directed())
false

# Simple cycle
iex> cycle = Yog.directed()
...> |> Yog.add_node(1, "A")
...> |> Yog.add_node(2, "B")
...> |> Yog.add_node(3, "C")
...> |> Yog.add_edge_ensure(from: 1, to: 2, with: 1)
...> |> Yog.add_edge_ensure(from: 2, to: 3, with: 1)
...> |> Yog.add_edge_ensure(from: 3, to: 1, with: 1)
iex> Yog.Property.Cyclicity.cyclic?(cycle)
true

Time Complexity

O(V + E)