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

Core Directed Acyclic Graph (DAG) type and basic operations.

This module provides the `Yog.DAG` struct that wraps a regular directed `Yog.Graph`
and guarantees acyclicity at the type level. Unlike a general graph, a DAG allows
for specialized algorithms like topological sorting and critical path analysis
to be total functions.

## Design Goals

- **Safety**: Ensure acyclicity at creation and during all edge insertions.
- **Efficiency**: Use targeted path checks for O(V+E) validation on insertion.
- **Interoperability**: Easy conversion to and from regular `Yog.Graph` structures.

## Example

    iex> dag = Yog.DAG.Model.new(:directed)
    iex> {:ok, dag} = Yog.DAG.Model.add_edge(dag, 1, 2, "depends")
    iex> Yog.DAG.Model.add_edge(dag, 2, 1, "cycle")
    {:error, :cycle_detected}

# `error`

```elixir
@type error() :: :cycle_detected
```

Error type representing why a graph cannot be treated as a DAG.

# `t`

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

An opaque wrapper around a `Graph` that guarantees acyclicity at the type level.

Unlike a regular `Graph`, a `DAG` is statically proven to contain no cycles,
enabling total functions for operations like topological sorting.

# `add_edge`

```elixir
@spec add_edge(t(), Yog.node_id(), Yog.node_id(), any()) ::
  {:ok, t()} | {:error, :cycle_detected}
```

Adds an edge to the DAG.

Because adding an edge can potentially create a cycle, this operation must
validate the resulting graph. Returns `{:ok, dag}` if no cycle is created,
and `{:error, :cycle_detected}` otherwise.

**Time Complexity:** O(V + E) (due to required cycle check on insertion).

## Example

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

# `add_node`

```elixir
@spec add_node(t(), Yog.node_id(), any()) :: t()
```

Adds a node to the DAG.

Adding a node cannot create a cycle, so this operation is infallible.

**Time Complexity:** O(1)

## Example

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

# `from_graph`

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

Attempts to create a `DAG` from a regular `Graph`.

Validates that the graph contains no cycles. If validation passes, returns
`{:ok, dag}`; otherwise returns `{:error, :cycle_detected}`.

**Time Complexity:** O(V + E)

## Example

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

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

# `new`

```elixir
@spec new(Yog.Model.graph_type()) :: t()
```

Creates a new, empty DAG. Only `:directed` graphs are supported.

## Example

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

# `remove_edge`

```elixir
@spec remove_edge(t(), Yog.node_id(), Yog.node_id()) :: t()
```

Removes an edge from the DAG.

Removing edges cannot create a cycle, so this operation is infallible.

**Time Complexity:** O(1)

## Example

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

# `remove_node`

```elixir
@spec remove_node(t(), Yog.node_id()) :: t()
```

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

Removing nodes/edges cannot create a cycle, so this operation is infallible.

**Time Complexity:** O(deg(v)) - proportional to the number of edges
connected to the node.

## Example

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

# `to_graph`

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

Unwraps a `DAG` back into a regular `Graph`.

This is useful when you need to use operations that work on any graph type,
or when you want to export the DAG to formats that accept general graphs.

## Example

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

---

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