model

Type-safe Directed Acyclic Graph (DAG) model with compile-time acyclicity guarantees.

This module provides an opaque Dag type that wraps a regular Graph with a compile-time guarantee of acyclicity. This enables total functions for operations like topological sorting and linear-time algorithms for path finding.

Key Features

Type Safety: The Dag type proves acyclicity at compile time
Total Functions: Operations like topological_sort/1 cannot fail
Linear Algorithms: Pathfinding runs in O(V+E) vs O((V+E) log V) for Dijkstra
Safe Construction: Conversion from Graph validates acyclicity

Construction

Create a Dag from an existing graph using from_graph():

import yog/dag/model

case model.from_graph(my_graph) {
  Ok(dag) -> // Safe to use DAG-only operations
  Error(model.CycleDetected) -> // Handle cyclic graph
}

Safe Modifications

Operation	Safety	Returns
`add_node/3`	Safe	`Dag` directly
`remove_node/2`	Safe	`Dag` directly
`remove_edge/3`	Safe	`Dag` directly
`add_edge/5`	Validated	`Result(Dag, DagError)`

References

Types

Dag

opaque </>

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.

Construction

Create a Dag from an existing graph using from_graph():

import yog/dag/model

case model.from_graph(my_graph) {
  Ok(dag) -> // Safe to use DAG-only operations
  Error(model.CycleDetected) -> // Handle cyclic graph
}

Type Safety

Once constructed, the Dag type ensures that all operations preserve acyclicity. Functions that could potentially create cycles (like add_edge) return Result types.

pub opaque type Dag(node_data, edge_data)

DagError

</>

Error type representing why a graph cannot be treated as a DAG.

pub type DagError {
  CycleDetected
  InvalidEdge(String)
}

Constructors

```
CycleDetected
```
Returned when attempting to create a DAG from a graph that contains cycles.
```
InvalidEdge(String)
```
Returned when attempting to add an invalid edge to a DAG.

Values

add_edge

</>

pub fn add_edge(
  dag: Dag(n, e),
  from src: Int,
  to dst: Int,
  with weight: e,
) -> Result(Dag(n, e), DagError)

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(Dag, DagError).

Time Complexity: O(V+E) (due to required cycle check on insertion).

add_node

</>

pub fn add_node(dag: Dag(n, e), id: Int, data: n) -> Dag(n, e)

Adds a node to the DAG.

Adding a node cannot create a cycle, so this operation is infallible and returns a Dag directly.

Time Complexity: O(1)

from_graph

</>

pub fn from_graph(
  graph: model.Graph(n, e),
) -> Result(Dag(n, e), DagError)

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(CycleDetected).

Time Complexity: O(V + E)

remove_edge

</>

pub fn remove_edge(
  dag: Dag(n, e),
  from src: Int,
  to dst: Int,
) -> Dag(n, e)

Removes an edge from the DAG.

Removing edges cannot create a cycle, so this operation is infallible and returns a Dag directly.

Time Complexity: O(1)

remove_node

</>

pub fn remove_node(dag: Dag(n, e), id: Int) -> Dag(n, e)

Removes a node and all its connected edges from the DAG.

Removing nodes/edges cannot create a cycle, so this operation is infallible and returns a Dag directly.

Time Complexity: O(V + E) in the worst case (removing all edges of the node).

to_graph

</>

pub fn to_graph(dag: Dag(n, e)) -> model.Graph(n, e)

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.