@spec count_reachability(Yog.DAG.t(), direction()) :: %{
  required(Yog.node_id()) => integer()
}

Counts the number of ancestors or descendants for every node.

For each node, returns how many other nodes are reachable from it (:descendants) or can reach it (:ancestors).

Uses dynamic programming on the topologically sorted DAG for efficiency. Properly handles diamond patterns where a node is reachable through multiple paths - each node is only counted once.

Time Complexity

O(V × E) in the worst case (sparse graphs), optimized with set operations for common cases.

Examples

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!(:a, :b, 1)
...>   |> Yog.add_edge!(:a, :c, 1)
...>   |> Yog.add_edge!(:b, :d, 1)
...>   |> Yog.add_edge!(:c, :d, 1)
...> )
iex> counts = Yog.DAG.Algorithm.count_reachability(dag, :descendants)
iex> counts[:a]
3
iex> counts[:d]
0

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

Examples

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!(:a, :b, 5)
...>   |> Yog.add_edge!(:b, :c, 3)
...> )
iex> path = Yog.DAG.Algorithm.longest_path(dag)
iex> length(path)
3

@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))

Examples

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!(:x, :a, 1)
...>   |> Yog.add_edge!(:x, :b, 1)
...> )
iex> lcas = Yog.DAG.Algorithm.lowest_common_ancestors(dag, :a, :b)
iex> :x in lcas
true

@spec shortest_path(Yog.DAG.t(), Yog.node_id(), Yog.node_id()) ::
  {:some, Yog.Pathfinding.Utils.path(any())} | :none

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

Uses dynamic programming on the topologically sorted DAG.

Time Complexity

O(V + E)

Examples

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!(:a, :b, 3)
...>   |> Yog.add_edge!(:b, :c, 2)
...> )
iex> {:some, path} = Yog.DAG.Algorithm.shortest_path(dag, :a, :c)
iex> {:path, [:a, :b, :c], 5} = path

@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)

Examples

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!(1, 2, 1)
...>   |> Yog.add_edge!(1, 3, 1)
...>   |> Yog.add_edge!(2, 4, 1)
...>   |> Yog.add_edge!(3, 4, 1)
...> )
iex> sorted = Yog.DAG.Algorithm.topological_sort(dag)
iex> hd(sorted)
1
iex> List.last(sorted)
4

@spec transitive_closure(Yog.DAG.t()) :: Yog.DAG.t()

Computes the transitive closure of the DAG.

The transitive closure adds an edge from node A to node C whenever there is a path from A to C. The result is a DAG where reachability can be checked in O(1) by looking for a direct edge.

Time Complexity

O(V × (V + E))

Examples

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!(:a, :b, 1)
...>   |> Yog.add_edge!(:b, :c, 1)
...> )
iex> closure = Yog.DAG.Algorithm.transitive_closure(dag)
iex> is_struct(closure, Yog.DAG)
true

@spec transitive_reduction(Yog.DAG.t()) :: Yog.DAG.t()

Computes the transitive reduction of the DAG.

The transitive reduction removes edges that are implied by transitivity. It produces the minimal DAG with the same reachability properties.

Time Complexity

O(V × (V + E))

Examples

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!(:a, :b, 1)
...>   |> Yog.add_edge!(:b, :c, 1)
...> )
iex> reduction = Yog.DAG.Algorithm.transitive_reduction(dag)
iex> is_struct(reduction, Yog.DAG)
true