# `Yog.DAG.Model`
[🔗](https://github.com/code-shoily/yog_ex/blob/v1.0.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 $\mathcal{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: $\mathcal{O}(V + E)$

## 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_edge!`

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

Same as `add_edge/4` but raises on error.

Time complexity: $\mathcal{O}(V + E)$

# `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: $\mathcal{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_edges`

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

Creates a DAG from a list of edges.

Time complexity: $\mathcal{O}(V + E)$

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_edges([{1, 2}, {2, 3}])
    iex> Yog.DAG.Model.to_graph(dag) |> Yog.Model.has_edge?(1, 2)
    true

# `from_edges`

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

Creates a DAG from a list of edges with a default weight.

Time complexity: $\mathcal{O}(V + E)$

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_edges([{1, 2}, {2, 3}], 10)
    iex> Yog.DAG.Model.to_graph(dag) |> Yog.Model.edge_data(1, 2)
    10

# `from_edges!`

```elixir
@spec from_edges!(
  [{Yog.node_id(), Yog.node_id()} | {Yog.node_id(), Yog.node_id(), any()}],
  any()
) :: t()
```

Same as `from_edges/1` but raises on error.

Time complexity: $\mathcal{O}(V + E)$

# `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: $\mathcal{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}

# `from_graph!`

```elixir
@spec from_graph!(Yog.graph()) :: t()
```

Same as `from_graph/1` but raises on error.

Time complexity: $\mathcal{O}(V + E)$

# `new`

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

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

Raises `ArgumentError` if graph_type is not `:directed`.

Time complexity: $\mathcal{O}(1)$

## 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: $\mathcal{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: $\mathcal{O}(\text{deg}(v))$

## 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.

Time complexity: $\mathcal{O}(1)$

## 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*