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

Algorithms for Directed Acyclic Graphs (DAGs).

These algorithms leverage the acyclic structure of DAGs to provide
efficient, total functions for operations like topological sorting,
longest path, transitive closure, and more.

# `ancestors`

```elixir
@spec ancestors(Yog.DAG.t(), Yog.node_id()) :: [Yog.node_id()]
```

Returns all ancestors of a node (nodes that have a path to the given node).

The result includes the node itself.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:b, :c, 1)
    ...> )
    iex> Yog.DAG.Algorithm.ancestors(dag, :c)
    [:a, :b, :c]

# `descendants`

```elixir
@spec descendants(Yog.DAG.t(), Yog.node_id()) :: [Yog.node_id()]
```

Returns all descendants of a node (nodes reachable from the given node).

The result includes the node itself.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:b, :c, 1)
    ...> )
    iex> Yog.DAG.Algorithm.descendants(dag, :a)
    [:a, :b, :c]

# `longest_path`

```elixir
@spec longest_path(Yog.DAG.t()) :: [Yog.node_id()]
```

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

The longest path is the path with maximum total edge weight from any source
node to any sink node.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 5)
    ...>   |> Yog.add_edge_ensure(:b, :c, 3)
    ...> )
    iex> path = Yog.DAG.Algorithm.longest_path(dag)
    iex> length(path)
    3

# `longest_path`

```elixir
@spec longest_path(Yog.DAG.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, Yog.Pathfinding.Path.t()} | :error
```

Finds the longest path between two specific nodes in a weighted DAG.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_node(:d, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:a, :c, 5)
    ...>   |> Yog.add_edge_ensure(:b, :d, 1)
    ...>   |> Yog.add_edge_ensure(:c, :d, 1)
    ...> )
    iex> {:ok, path} = Yog.DAG.Algorithm.longest_path(dag, :a, :d)
    iex> path.nodes
    [:a, :c, :d]
    iex> path.weight
    6

# `lowest_common_ancestors`

```elixir
@spec lowest_common_ancestors(Yog.DAG.t(), Yog.node_id(), Yog.node_id()) :: [
  Yog.node_id()
]
```

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

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:x, nil)
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_edge_ensure(:x, :a, 1)
    ...>   |> Yog.add_edge_ensure(:x, :b, 1)
    ...> )
    iex> lcas = Yog.DAG.Algorithm.lowest_common_ancestors(dag, :a, :b)
    iex> :x in lcas
    true

# `path_count`

```elixir
@spec path_count(Yog.DAG.t(), Yog.node_id(), Yog.node_id()) :: non_neg_integer()
```

Counts the number of distinct paths between two nodes in a DAG.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_node(:d, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:a, :c, 1)
    ...>   |> Yog.add_edge_ensure(:b, :d, 1)
    ...>   |> Yog.add_edge_ensure(:c, :d, 1)
    ...> )
    iex> Yog.DAG.Algorithm.path_count(dag, :a, :d)
    2

# `shortest_path`

```elixir
@spec shortest_path(Yog.DAG.t(), Yog.node_id(), Yog.node_id()) ::
  {:ok, Yog.Pathfinding.Path.t()} | :error
```

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

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 3)
    ...>   |> Yog.add_edge_ensure(:b, :c, 2)
    ...> )
    iex> {:ok, path} = Yog.DAG.Algorithm.shortest_path(dag, :a, :c)
    iex> path.nodes == [:a, :b, :c] and path.weight == 5
    true

# `single_source_distances`

```elixir
@spec single_source_distances(Yog.DAG.t(), Yog.node_id()) :: %{
  required(Yog.node_id()) => number()
}
```

Computes single-source shortest distances to all reachable nodes.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 3)
    ...>   |> Yog.add_edge_ensure(:b, :c, 2)
    ...>   |> Yog.add_edge_ensure(:a, :c, 10)
    ...> )
    iex> Yog.DAG.Algorithm.single_source_distances(dag, :a)
    %{a: 0, b: 3, c: 5}

# `sinks`

```elixir
@spec sinks(Yog.DAG.t()) :: [Yog.node_id()]
```

Returns all sink nodes (nodes with out-degree 0).

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:a, :c, 1)
    ...> )
    iex> Yog.DAG.Algorithm.sinks(dag)
    [:b, :c]

# `sources`

```elixir
@spec sources(Yog.DAG.t()) :: [Yog.node_id()]
```

Returns all source nodes (nodes with in-degree 0).

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:a, :c, 1)
    ...> )
    iex> Yog.DAG.Algorithm.sources(dag)
    [:a]

# `topological_generations`

```elixir
@spec topological_generations(Yog.DAG.t()) :: [[Yog.node_id()]]
```

Returns the topological generations of a DAG.

Each generation is a list of nodes with the same longest-path distance
from a source. Nodes within the same generation are independent and can
be processed in parallel.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(:a, nil)
    ...>   |> Yog.add_node(:b, nil)
    ...>   |> Yog.add_node(:c, nil)
    ...>   |> Yog.add_node(:d, nil)
    ...>   |> Yog.add_edge_ensure(:a, :b, 1)
    ...>   |> Yog.add_edge_ensure(:a, :c, 1)
    ...>   |> Yog.add_edge_ensure(:b, :d, 1)
    ...>   |> Yog.add_edge_ensure(:c, :d, 1)
    ...> )
    iex> Yog.DAG.Algorithm.topological_generations(dag)
    [[:a], [:b, :c], [:d]]

# `topological_sort`

```elixir
@spec topological_sort(Yog.DAG.t()) :: [Yog.node_id()]
```

Returns a topological ordering of all nodes in the DAG.

In a topological ordering, every node appears before all nodes it has edges to.
This is useful for scheduling tasks with dependencies, build systems, etc.

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

## Example

    iex> {:ok, dag} = Yog.DAG.Model.from_graph(
    ...>   Yog.directed()
    ...>   |> Yog.add_node(1, nil)
    ...>   |> Yog.add_node(2, nil)
    ...>   |> Yog.add_node(3, nil)
    ...>   |> Yog.add_node(4, nil)
    ...>   |> Yog.add_edge_ensure(1, 2, 1)
    ...>   |> Yog.add_edge_ensure(1, 3, 1)
    ...>   |> Yog.add_edge_ensure(2, 4, 1)
    ...>   |> Yog.add_edge_ensure(3, 4, 1)
    ...> )
    iex> sorted = Yog.DAG.Algorithm.topological_sort(dag)
    iex> hd(sorted)
    1
    iex> List.last(sorted)
    4

---

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