# `Yog.DAG.Algorithm`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.98.5/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:** 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:** 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. This is the dual of shortest path and is useful for:
- Project scheduling (finding the critical path)
- Dependency chains with durations
- Determining minimum time to complete all tasks

**Time Complexity:** O(V + E) - linear via dynamic programming on the topologically sorted DAG.

## Note

For unweighted graphs, this finds the path with most edges.
Weights must be non-negative for meaningful results.

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

A common ancestor of nodes A and B is any node that has paths to both A and B.
The "lowest" common ancestors are those that are not ancestors of any other
common ancestor - they are the "closest" shared dependencies.

This is useful for:
- Finding merge bases in version control
- Identifying shared dependencies
- Computing dominators in control flow graphs

**Time Complexity:** O(V × (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.

Uses dynamic programming on the topological order.

**Time Complexity:** 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.

Uses dynamic programming on the topologically sorted DAG.

**Time Complexity:** 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.

Uses dynamic programming on the topological order for O(V + E) performance,
faster than Dijkstra's O((V + E) log V).

**Time Complexity:** 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).

Sink nodes have no outgoing edges and represent terminal points
in a DAG (e.g., final deliverables with no downstream tasks).

**Time Complexity:** 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).

Source nodes have no incoming edges and represent starting points
in a DAG (e.g., tasks with no prerequisites).

**Time Complexity:** 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. This is especially useful in Elixir for
batching `Task.async_stream` workloads over a dependency graph.

**Time Complexity:** 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.

Unlike `Yog.traversal.topological_sort/1` which returns `{:ok, sorted}` or
`{:error, :cycle_detected}` (since general graphs may contain cycles), this
version is **total** - it always returns a valid ordering because the `DAG`
type guarantees acyclicity.

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