Core Directed Acyclic Graph (DAG) type and basic operations.
This module provides the Yog.DAG struct that wraps a regular directed Yog.Graph
and guarantees acyclicity at the type level. Unlike a general graph, a DAG allows
for specialized algorithms like topological sorting and critical path analysis
to be total functions.
Design Goals
- Safety: Ensure acyclicity at creation and during all edge insertions.
- Efficiency: Use targeted path checks for O(V+E) validation on insertion.
- Interoperability: Easy conversion to and from regular
Yog.Graphstructures.
Example
iex> dag = Yog.DAG.Model.new(:directed)
iex> {:ok, dag} = Yog.DAG.Model.add_edge(dag, 1, 2, "depends")
iex> Yog.DAG.Model.add_edge(dag, 2, 1, "cycle")
{:error, :cycle_detected}Summary
Types
Error type representing why a graph cannot be treated as a DAG.
Types
@type error() :: :cycle_detected
Error type representing why a graph cannot be treated as a DAG.
@type t() :: %Yog.DAG{graph: Yog.Graph.t()}
An opaque wrapper around a Graph that guarantees acyclicity at the type level.
Unlike a regular Graph, a DAG is statically proven to contain no cycles,
enabling total functions for operations like topological sorting.
Functions
@spec add_edge(t(), Yog.node_id(), Yog.node_id(), any()) :: {:ok, t()} | {:error, :cycle_detected}
Adds an edge to the DAG.
Because adding an edge can potentially create a cycle, this operation must
validate the resulting graph. Returns {:ok, dag} if no cycle is created,
and {:error, :cycle_detected} otherwise.
Time Complexity: O(V + E) (due to required cycle check on insertion).
Example
iex> dag = Yog.DAG.Model.new(:directed)
iex> {:ok, dag} = Yog.DAG.Model.add_edge(dag, 1, 2, 10)
iex> Yog.DAG.Model.add_edge(dag, 2, 1, 5)
{:error, :cycle_detected}@spec add_node(t(), Yog.node_id(), any()) :: t()
Adds a node to the DAG.
Adding a node cannot create a cycle, so this operation is infallible.
Time Complexity: O(1)
Example
iex> dag = Yog.DAG.Model.new(:directed) |> Yog.DAG.Model.add_node(1, "A")
iex> Yog.DAG.Model.to_graph(dag) |> Yog.node(1)
"A"Attempts to create a DAG from a regular Graph.
Validates that the graph contains no cycles. If validation passes, returns
{:ok, dag}; otherwise returns {:error, :cycle_detected}.
Time Complexity: O(V + E)
Example
iex> graph = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 3}])
iex> {:ok, dag} = Yog.DAG.Model.from_graph(graph)
iex> Yog.DAG.Model.to_graph(dag) == graph
true
iex> graph = Yog.from_unweighted_edges(:directed, [{1, 2}, {2, 1}])
iex> Yog.DAG.Model.from_graph(graph)
{:error, :cycle_detected}@spec new(Yog.Model.graph_type()) :: t()
Creates a new, empty DAG. Only :directed graphs are supported.
Example
iex> dag = Yog.DAG.Model.new(:directed)
iex> Yog.Graph.node_count(Yog.DAG.Model.to_graph(dag))
0@spec remove_edge(t(), Yog.node_id(), Yog.node_id()) :: t()
Removes an edge from the DAG.
Removing edges cannot create a cycle, so this operation is infallible.
Time Complexity: O(1)
Example
iex> {:ok, dag} = Yog.DAG.Model.new(:directed) |> Yog.DAG.Model.add_edge(1, 2, 10)
iex> dag = Yog.DAG.Model.remove_edge(dag, 1, 2)
iex> Yog.DAG.Model.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.
Removing nodes/edges cannot create a cycle, so this operation is infallible.
Time Complexity: O(deg(v)) - proportional to the number of edges connected to the node.
Example
iex> dag = Yog.DAG.Model.new(:directed) |> Yog.DAG.Model.add_node(1, "A")
iex> dag = Yog.DAG.Model.remove_node(dag, 1)
iex> Yog.DAG.Model.to_graph(dag) |> Yog.has_node?(1)
falseUnwraps a DAG back into a regular Graph.
This is useful when you need to use operations that work on any graph type, or when you want to export the DAG to formats that accept general graphs.
Example
iex> dag = Yog.DAG.Model.new(:directed)
iex> graph = Yog.DAG.Model.to_graph(dag)
iex> Yog.graph?(graph)
true