Directed Acyclic Graph (DAG) data structure.
A DAG is a wrapper around a Yog.Graph that guarantees acyclicity at the type level.
This enables total functions (functions that always succeed) for operations like
topological sorting that would be partial for general graphs.
Example
iex> graph = Yog.Graph.new(:directed)
iex> {:ok, dag} = Yog.DAG.from_graph(graph)
iex> is_struct(dag, Yog.DAG)
trueProtocols
Yog.DAG implements the Enumerable and Inspect protocols:
- Enumerable: Iterates over nodes as
{id, data}tuples via the underlying graph - Inspect: Compact representation showing node and edge counts
Summary
Functions
Adds an edge to the DAG, validating for cycles.
Same as add_edge/4 but raises ArgumentError on cycle detection.
Adds multiple edges to the DAG sequentially, returning {:ok, dag} or {:error, :cycle_detected}.
Same as add_edges/2 but raises ArgumentError if any edge creates a cycle.
Adds a node to the DAG.
Returns all ancestors of a node (includes the node itself).
Returns all descendants of a node (includes the node itself).
Returns the number of edges in the DAG.
Creates a DAG from a list of edges.
Creates a DAG from a list of edges with a default weight.
Creates a DAG from a list of edges, raising ArgumentError if a cycle is detected.
Attempts to create a DAG from a graph.
Creates a DAG from a graph, raising ArgumentError if a cycle is detected.
Checks if an edge exists in the DAG.
Checks if a node exists in the DAG.
Returns the in-degree of a node.
Finds the longest path (critical path) in a weighted DAG.
Finds the longest path between two specific nodes.
Finds the lowest common ancestors (LCAs) of two nodes.
Creates a new empty DAG.
Returns the number of nodes in the DAG.
Returns all node IDs in the DAG.
Returns the out-degree of a node.
Counts the number of distinct paths between two nodes.
Returns all incoming edges to a node as [{from, weight}].
Checks if from can reach to in the DAG.
Removes an edge from the DAG.
Removes a node and all its connected edges from the 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 (out-degree 0).
Returns all source nodes (in-degree 0).
Returns all outgoing edges from a node as [{to, weight}].
Unwraps a DAG back into a regular Graph.
Returns the topological generations of a DAG.
Returns a topological ordering of all nodes in the DAG.
Types
@type t() :: %Yog.DAG{graph: Yog.Graph.t()}
Functions
@spec add_edge(t(), Yog.node_id(), Yog.node_id(), any()) :: {:ok, t()} | {:error, :cycle_detected}
Adds an edge to the DAG, validating for cycles.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> dag = Yog.DAG.new()
iex> {:ok, dag} = Yog.DAG.add_edge(dag, 1, 2, 10)
iex> Yog.DAG.add_edge(dag, 2, 1, 5)
{:error, :cycle_detected}@spec add_edge!(t(), Yog.node_id(), Yog.node_id(), any()) :: t()
Same as add_edge/4 but raises ArgumentError on cycle detection.
Time complexity: $\mathcal{O}(V + E)$
@spec add_edges( t(), [{Yog.node_id(), Yog.node_id()} | {Yog.node_id(), Yog.node_id(), any()}] ) :: {:ok, t()} | {:error, :cycle_detected}
Adds multiple edges to the DAG sequentially, returning {:ok, dag} or {:error, :cycle_detected}.
Time complexity: $\mathcal{O}(E \cdot (V + E))$
@spec add_edges!( t(), [{Yog.node_id(), Yog.node_id()} | {Yog.node_id(), Yog.node_id(), any()}] ) :: t()
Same as add_edges/2 but raises ArgumentError if any edge creates a cycle.
Time complexity: $\mathcal{O}(E \cdot (V + E))$
@spec add_node(t(), Yog.node_id(), any()) :: t()
Adds a node to the DAG.
Time complexity: $\mathcal{O}(1)$
Example
iex> dag = Yog.DAG.new() |> Yog.DAG.add_node(1, "A")
iex> Yog.DAG.to_graph(dag) |> Yog.node(1)
"A"@spec ancestors(t(), Yog.node_id()) :: [Yog.node_id()]
Returns all ancestors of a node (includes the node itself).
Time complexity: $\mathcal{O}(V + E)$
@spec descendants(t(), Yog.node_id()) :: [Yog.node_id()]
Returns all descendants of a node (includes the node itself).
Time complexity: $\mathcal{O}(V + E)$
Returns the number of edges in the DAG.
Time complexity: $\mathcal{O}(1)$
@spec from_edges([ {Yog.node_id(), Yog.node_id()} | {Yog.node_id(), Yog.node_id(), any()} ]) :: {:ok, t()} | {:error, :cycle_detected}
Creates a DAG from a list of edges.
Each edge is a tuple {from, to} or {from, to, weight}.
Returns {:ok, dag} if the graph is acyclic, otherwise {:error, :cycle_detected}.
Time complexity: $\mathcal{O}(V + E)$
Examples
iex> {:ok, dag} = Yog.DAG.from_edges([{:a, :b}, {:b, :c}])
iex> Yog.DAG.topological_sort(dag)
[:a, :b, :c]
iex> Yog.DAG.from_edges([{:a, :b}, {:b, :a}])
{:error, :cycle_detected}@spec from_edges([{Yog.node_id(), Yog.node_id()}], any()) :: {:ok, t()} | {:error, :cycle_detected}
Creates a DAG from a list of edges with a default weight.
Time complexity: $\mathcal{O}(V + E)$
Examples
iex> {:ok, dag} = Yog.DAG.from_edges([{:a, :b}, {:b, :c}], 10)
iex> graph = Yog.DAG.to_graph(dag)
iex> Yog.Model.edge_data(graph, :a, :b)
10@spec from_edges!( [{Yog.node_id(), Yog.node_id()} | {Yog.node_id(), Yog.node_id(), any()}], any() ) :: t()
Creates a DAG from a list of edges, raising ArgumentError if a cycle is detected.
Time complexity: $\mathcal{O}(V + E)$
@spec from_graph(Yog.Graph.t()) :: {:ok, t()} | {:error, :cycle_detected}
Attempts to create a DAG from a graph.
Validates that the graph is directed and contains no cycles.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> graph = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 3}])
iex> {:ok, dag} = Yog.DAG.from_graph(graph)
iex> Yog.DAG.to_graph(dag) == graph
true
iex> graph = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 1}])
iex> Yog.DAG.from_graph(graph)
{:error, :cycle_detected}@spec from_graph!(Yog.Graph.t()) :: t()
Creates a DAG from a graph, raising ArgumentError if a cycle is detected.
Time complexity: $\mathcal{O}(V + E)$
@spec has_edge?(t(), Yog.node_id(), Yog.node_id()) :: boolean()
Checks if an edge exists in the DAG.
Time complexity: $\mathcal{O}(1)$
@spec has_node?(t(), Yog.node_id()) :: boolean()
Checks if a node exists in the DAG.
Time complexity: $\mathcal{O}(1)$
@spec in_degree(t(), Yog.node_id()) :: non_neg_integer()
Returns the in-degree of a node.
Time complexity: $\mathcal{O}(1)$
@spec longest_path(t()) :: [Yog.node_id()]
Finds the longest path (critical path) in a weighted DAG.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> {:ok, dag} = Yog.from_edges(:directed, [{1, 2, 5}, {2, 3, 3}]) |> Yog.DAG.from_graph()
iex> Yog.DAG.longest_path(dag)
[1, 2, 3]@spec longest_path(t(), Yog.node_id(), Yog.node_id()) :: {:ok, Yog.Pathfinding.Path.t()} | :error
Finds the longest path between two specific nodes.
Time complexity: $\mathcal{O}(V + E)$
@spec lowest_common_ancestors(t(), Yog.node_id(), Yog.node_id()) :: [Yog.node_id()]
Finds the lowest common ancestors (LCAs) of two nodes.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> {:ok, dag} = Yog.from_unweighted_edges(:directed, [{1, 3}, {2, 3}]) |> Yog.DAG.from_graph()
iex> Yog.DAG.lowest_common_ancestors(dag, 3, 3)
[3]@spec new() :: t()
Creates a new empty DAG.
Time complexity: $\mathcal{O}(1)$
Example
iex> dag = Yog.DAG.new()
iex> Yog.Model.node_count(Yog.DAG.to_graph(dag))
0Returns the number of nodes in the DAG.
Time complexity: $\mathcal{O}(1)$
@spec nodes(t()) :: [Yog.node_id()]
Returns all node IDs in the DAG.
Time complexity: $\mathcal{O}(V)$
@spec out_degree(t(), Yog.node_id()) :: non_neg_integer()
Returns the out-degree of a node.
Time complexity: $\mathcal{O}(1)$
@spec path_count(t(), Yog.node_id(), Yog.node_id()) :: non_neg_integer()
Counts the number of distinct paths between two nodes.
Time complexity: $\mathcal{O}(V + E)$
@spec predecessors(t(), Yog.node_id()) :: [{Yog.node_id(), any()}]
Returns all incoming edges to a node as [{from, weight}].
Time complexity: $\mathcal{O}(\text{deg}_{\text{in}}(v))$
@spec reachable?(t(), Yog.node_id(), Yog.node_id()) :: boolean()
Checks if from can reach to in the DAG.
Time complexity: $\mathcal{O}(V + E)$
@spec remove_edge(t(), Yog.node_id(), Yog.node_id()) :: t()
Removes an edge from the DAG.
Time complexity: $\mathcal{O}(1)$
Example
iex> {:ok, dag} = Yog.DAG.new() |> Yog.DAG.add_edge(1, 2, 10)
iex> dag = Yog.DAG.remove_edge(dag, 1, 2)
iex> Yog.DAG.to_graph(dag) |> Yog.has_edge?(1, 2)
false@spec remove_node(t(), Yog.node_id()) :: t()
Removes a node and all its connected edges from the DAG.
Time complexity: $\mathcal{O}(\text{deg}(v))$
Example
iex> dag = Yog.DAG.new() |> Yog.DAG.add_node(1, "A")
iex> dag = Yog.DAG.remove_node(dag, 1)
iex> Yog.DAG.to_graph(dag) |> Yog.has_node?(1)
false@spec shortest_path(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.from_edges(:directed, [{1, 2, 3}, {2, 3, 2}]) |> Yog.DAG.from_graph()
iex> {:ok, path} = Yog.DAG.shortest_path(dag, 1, 3)
iex> path.weight
5@spec single_source_distances(t(), Yog.node_id()) :: %{ required(Yog.node_id()) => number() }
Computes single-source shortest distances to all reachable nodes.
Time complexity: $\mathcal{O}(V + E)$
@spec sinks(t()) :: [Yog.node_id()]
Returns all sink nodes (out-degree 0).
Time complexity: $\mathcal{O}(V)$
@spec sources(t()) :: [Yog.node_id()]
Returns all source nodes (in-degree 0).
Time complexity: $\mathcal{O}(V)$
@spec successors(t(), Yog.node_id()) :: [{Yog.node_id(), any()}]
Returns all outgoing edges from a node as [{to, weight}].
Time complexity: $\mathcal{O}(\text{deg}_{\text{out}}(v))$
@spec to_graph(t()) :: Yog.Graph.t()
Unwraps a DAG back into a regular Graph.
Time complexity: $\mathcal{O}(1)$
Example
iex> dag = Yog.DAG.new()
iex> graph = Yog.DAG.to_graph(dag)
iex> Yog.graph?(graph)
true@spec topological_generations(dag :: t()) :: [[Yog.node_id()]]
Returns the topological generations of a DAG.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> {:ok, dag} = Yog.from_unweighted_edges(:directed, [{1, 2}, {1, 3}, {2, 4}, {3, 4}]) |> Yog.DAG.from_graph()
iex> Yog.DAG.topological_generations(dag)
[[1], [2, 3], [4]]@spec topological_sort(t()) :: [Yog.node_id()]
Returns a topological ordering of all nodes in the DAG.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> {:ok, dag} = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 3}]) |> Yog.DAG.from_graph()
iex> Yog.DAG.topological_sort(dag)
[1, 2, 3]