Core DAG type and basic operations.
This module provides the Yog.DAG struct that wraps a regular graph
and guarantees acyclicity at the type level.
Summary
Types
Error type representing why a graph cannot be treated as a DAG.
An opaque wrapper around a Graph that guarantees acyclicity at the type level.
Functions
Adds an edge to the DAG.
Adds a node to the DAG.
Attempts to create a DAG from a regular Graph.
Creates a new, empty DAG.
Removes an edge from the DAG.
Removes a node and all its connected edges from the DAG.
Unwraps a DAG back into a regular Graph.
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 and returns a Result type.
Time Complexity
O(V + E) (due to required cycle check on insertion).
@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)
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)
@spec new(Yog.Model.graph_type()) :: t()
Creates a new, empty DAG.
@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)
@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(V + E) in the worst case (removing all edges of the node).
Unwraps 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.