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

Directed Acyclic Graph (DAG) data structure.

A DAG is a wrapper around a `Yog.Graph` that guarantees acyclicity at the type level.
This enables total functions (functions that always succeed) for operations like
topological sorting that would be partial for general graphs.

## Example

    iex> graph = Yog.Graph.new(:directed)
    iex> {:ok, dag} = Yog.DAG.from_graph(graph)
    iex> is_struct(dag, Yog.DAG)
    true

## Protocols

`Yog.DAG` implements the `Enumerable` and `Inspect` protocols:

- **Enumerable**: Iterates over nodes as `{id, data}` tuples via the underlying graph
- **Inspect**: Compact representation showing node and edge counts

# `t`

```elixir
@type t() :: %Yog.DAG{graph: Yog.Graph.t()}
```

# `add_edge`

Adds an edge to the DAG, validating for cycles.

## Example

    iex> dag = Yog.DAG.new()
    iex> {:ok, dag} = Yog.DAG.add_edge(dag, 1, 2, 10)
    iex> Yog.DAG.add_edge(dag, 2, 1, 5)
    {:error, :cycle_detected}

# `add_node`

Adds a node to the DAG.

## Example

    iex> dag = Yog.DAG.new() |> Yog.DAG.add_node(1, "A")
    iex> Yog.DAG.to_graph(dag) |> Yog.node(1)
    "A"

# `from_graph`

```elixir
@spec from_graph(Yog.Graph.t()) :: {:ok, t()} | {:error, :cycle_detected}
```

Attempts to create a DAG from a graph.

Validates that the graph is directed and contains no cycles.

## Example

    iex> graph = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 3}])
    iex> {:ok, dag} = Yog.DAG.from_graph(graph)
    iex> Yog.DAG.to_graph(dag) == graph
    true

    iex> graph = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 1}])
    iex> Yog.DAG.from_graph(graph)
    {:error, :cycle_detected}

# `longest_path`

Finds the longest path (critical path) in a weighted DAG.

## Example

    iex> {:ok, dag} = Yog.from_edges(:directed, [{1, 2, 5}, {2, 3, 3}]) |> Yog.DAG.from_graph()
    iex> Yog.DAG.longest_path(dag)
    [1, 2, 3]

# `lowest_common_ancestors`

Finds the lowest common ancestors (LCAs) of two nodes.

## Example

    iex> {:ok, dag} = Yog.from_unweighted_edges(:directed, [{1, 3}, {2, 3}]) |> Yog.DAG.from_graph()
    iex> Yog.DAG.lowest_common_ancestors(dag, 3, 3)
    [3]

# `new`

```elixir
@spec new() :: t()
```

Creates a new empty DAG.

## Example

    iex> dag = Yog.DAG.new()
    iex> Yog.Model.node_count(Yog.DAG.to_graph(dag))
    0

# `remove_edge`

Removes an edge from the DAG.

## Example

    iex> {:ok, dag} = Yog.DAG.new() |> Yog.DAG.add_edge(1, 2, 10)
    iex> dag = Yog.DAG.remove_edge(dag, 1, 2)
    iex> Yog.DAG.to_graph(dag) |> Yog.has_edge?(1, 2)
    false

# `remove_node`

Removes a node and all its connected edges from the DAG.

## Example

    iex> dag = Yog.DAG.new() |> Yog.DAG.add_node(1, "A")
    iex> dag = Yog.DAG.remove_node(dag, 1)
    iex> Yog.DAG.to_graph(dag) |> Yog.has_node?(1)
    false

# `shortest_path`

Finds the shortest path between two nodes in a weighted DAG.

## Example

    iex> {:ok, dag} = Yog.from_edges(:directed, [{1, 2, 3}, {2, 3, 2}]) |> Yog.DAG.from_graph()
    iex> {:ok, path} = Yog.DAG.shortest_path(dag, 1, 3)
    iex> path.weight
    5

# `to_graph`

```elixir
@spec to_graph(t()) :: Yog.Graph.t()
```

Unwraps a DAG back into a regular Graph.

## Example

    iex> dag = Yog.DAG.new()
    iex> graph = Yog.DAG.to_graph(dag)
    iex> Yog.graph?(graph)
    true

# `topological_generations`

Returns the topological generations of a DAG.

## Example

    iex> {:ok, dag} = Yog.from_unweighted_edges(:directed, [{1, 2}, {1, 3}, {2, 4}, {3, 4}]) |> Yog.DAG.from_graph()
    iex> Yog.DAG.topological_generations(dag)
    [[1], [2, 3], [4]]

# `topological_sort`

Returns a topological ordering of all nodes in the DAG.

## Example

    iex> {:ok, dag} = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 3}]) |> Yog.DAG.from_graph()
    iex> Yog.DAG.topological_sort(dag)
    [1, 2, 3]

---

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