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.
Examples
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.
Counts the number of ancestors or descendants for every node.
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 a topological ordering of all nodes in the DAG.
Computes the transitive closure of the DAG.
Computes the transitive reduction of the DAG.
Types
@type t() :: %Yog.DAG{graph: Yog.Graph.t()}
Functions
Adds an edge to the DAG, validating for cycles.
Adds a node to the DAG.
Counts the number of ancestors or descendants for every node.
@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.
Finds the longest path (critical path) in a weighted DAG.
Finds the lowest common ancestors (LCAs) of two nodes.
@spec new() :: t()
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.
@spec to_graph(t()) :: Yog.Graph.t()
Unwraps a DAG back into a regular Graph.
Returns a topological ordering of all nodes in the DAG.
Computes the transitive closure of the DAG.
Computes the transitive reduction of the DAG.