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.
Attempts to create a DAG from a graph.
Finds the longest path (critical path) in a weighted DAG.
Finds the lowest common ancestors (LCAs) of two nodes.
Creates a new empty 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.
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"@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}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 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))
0Removes 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
5@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]