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 $\mathcal{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.
Functions
Adds an edge to the DAG.
Same as add_edge/4 but raises on error.
Adds a node to the DAG.
Creates a DAG from a list of edges.
Creates a DAG from a list of edges with a default weight.
Same as from_edges/1 but raises on error.
Attempts to create a DAG from a regular Graph.
Same as from_graph/1 but raises on error.
Creates a new, empty DAG. Only :directed graphs are supported.
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. Returns {:ok, dag} if no cycle is created,
and {:error, :cycle_detected} otherwise.
Time complexity: $\mathcal{O}(V + E)$
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_edge!(t(), Yog.node_id(), Yog.node_id(), any()) :: t()
Same as add_edge/4 but raises on error.
Time complexity: $\mathcal{O}(V + E)$
@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: $\mathcal{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"@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.
Time complexity: $\mathcal{O}(V + E)$
Example
iex> {:ok, dag} = Yog.DAG.Model.from_edges([{1, 2}, {2, 3}])
iex> Yog.DAG.Model.to_graph(dag) |> Yog.Model.has_edge?(1, 2)
true@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)$
Example
iex> {:ok, dag} = Yog.DAG.Model.from_edges([{1, 2}, {2, 3}], 10)
iex> Yog.DAG.Model.to_graph(dag) |> Yog.Model.edge_data(1, 2)
10@spec from_edges!( [{Yog.node_id(), Yog.node_id()} | {Yog.node_id(), Yog.node_id(), any()}], any() ) :: t()
Same as from_edges/1 but raises on error.
Time complexity: $\mathcal{O}(V + E)$
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: $\mathcal{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}Same as from_graph/1 but raises on error.
Time complexity: $\mathcal{O}(V + E)$
@spec new(Yog.Model.graph_type()) :: t()
Creates a new, empty DAG. Only :directed graphs are supported.
Raises ArgumentError if graph_type is not :directed.
Time complexity: $\mathcal{O}(1)$
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: $\mathcal{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: $\mathcal{O}(\text{deg}(v))$
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.
Time complexity: $\mathcal{O}(1)$
Example
iex> dag = Yog.DAG.Model.new(:directed)
iex> graph = Yog.DAG.Model.to_graph(dag)
iex> Yog.graph?(graph)
true