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.
Summary
Functions
Returns all ancestors of a node (nodes that have a path to the given node).
Returns all descendants of a node (nodes reachable from the given node).
Finds the longest path (critical path) in a weighted DAG.
Finds the longest path between two specific nodes in a weighted DAG.
Finds the lowest common ancestors (LCAs) of two nodes.
Counts the number of distinct paths between two nodes in a DAG.
Finds the shortest path between two nodes in a weighted DAG.
Computes single-source shortest distances to all reachable nodes.
Returns all sink nodes (nodes with out-degree 0).
Returns all source nodes (nodes with in-degree 0).
Returns the topological generations of a DAG.
Returns a topological ordering of all nodes in the DAG.
Functions
@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]@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]@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@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@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@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@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@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}@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]@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]@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]]@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