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

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

@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

@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

@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

@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

@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

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

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

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

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

@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