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.
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.
Attempts to create a DAG from a graph.
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
Adds an edge to the DAG, validating for cycles.
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}Adds a node to the DAG.
Example
iex> dag = Yog.DAG.new() |> Yog.DAG.add_node(1, "A")
iex> Yog.DAG.to_graph(dag) |> Yog.node(1)
"A"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.
@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}.
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.
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_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.
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}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.
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]Finds the longest path between two specific nodes.
Finds the lowest common ancestors (LCAs) of two nodes.
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.
Example
iex> dag = Yog.DAG.new()
iex> Yog.Model.node_count(Yog.DAG.to_graph(dag))
0Returns 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.
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)
falseRemoves a node and all its connected edges from the DAG.
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)
falseFinds the shortest path between two nodes in a weighted DAG.
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
5Computes 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}].
@spec to_graph(t()) :: Yog.Graph.t()
Unwraps a DAG back into a regular Graph.
Example
iex> dag = Yog.DAG.new()
iex> graph = Yog.DAG.to_graph(dag)
iex> Yog.graph?(graph)
trueReturns the topological generations of a DAG.
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]]Returns a topological ordering of all nodes in the DAG.
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]