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