yog - v5.1.0

yog/dag/model

⚠️ Experimental Module

This module is experimental and provides minimal, working functionality. The implementation is functional but may not be fully optimized for performance.

Expected changes:

Use with caution in production environments.

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.

✨ Search Document