# `Yog.Property.Cyclicity`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/property/cyclicity.ex#L1)

Graph [cyclicity](https://en.wikipedia.org/wiki/Cycle_(graph_theory)) and
[Directed Acyclic Graph (DAG)](https://en.wikipedia.org/wiki/Directed_acyclic_graph) 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](https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm) | `acyclic?/1`, `cyclic?/1` | O(V + E) |
| Cycle detection (undirected) | [Union-Find / DFS](https://en.wikipedia.org/wiki/Cycle_detection) | `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

<div class="graphviz">
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];
  }
}
</div>

    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

- [Wikipedia: Cycle Detection](https://en.wikipedia.org/wiki/Cycle_detection)
- [Wikipedia: Directed Acyclic Graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)
- [Wikipedia: Kahn's Algorithm](https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm)
- [CP-Algorithms: Finding Cycles](https://cp-algorithms.com/graph/finding-cycle.html)

# `acyclic?`

```elixir
@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?`

```elixir
@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)

---

*Consult [api-reference.md](api-reference.md) for complete listing*