yog/dag

Frugal Directed Acyclic Graphs

This module provides a strictly typed wrapper Dag(n, e) for modeling Directed Acyclic Graphs (DAGs) without runtime cycle-checking overhead during standard graph building.

The Frugal DAG Philosophy

Yog treats DAGs as a specialized view of a graph, rather than a fundamentally different structure. The standard way to create a DAG is to:

Build a normal graph first using yog.directed() and standard add_node/add_edge.
Once built, “seal” it as a DAG using dag.from_graph(graph). This runs a fast $O(V+E)$ validation.
Utilize DAG-only algorithms (like $O(V+E)$ longest paths or transitive closures) on the returned Dag instance.

Do not build graphs exclusively with dag.add_edge()!

While mutating functions like add_node, remove_node, and add_edge are available here, they are designed strictly for experimentation or minor updates to an already-validated DAG. Because add_edge can introduce a cycle, calling it forces an $O(V+E)$ property check immediately, returning a Result(Dag, DagError). Attempting to build a 100,000-edge graph using dag.add_edge will result in $O(N \cdot (V+E))$ performance decay.

Values

add_edge

</>

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

add_node

</>

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

count_reachability

</>

pub fn count_reachability(
  dag: models.Dag(n, e),
  direction: algorithms.Direction,
) -> dict.Dict(Int, Int)

from_graph

</>

pub fn from_graph(
  graph: model.Graph(a, b),
) -> Result(models.Dag(a, b), models.DagError)

longest_path

</>

pub fn longest_path(dag: models.Dag(n, Int)) -> List(Int)

lowest_common_ancestors

</>

pub fn lowest_common_ancestors(
  dag: models.Dag(n, e),
  node_a: Int,
  node_b: Int,
) -> List(Int)

remove_edge

</>

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

remove_node

</>

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

shortest_path

</>

pub fn shortest_path(
  dag: models.Dag(n, Int),
  from start: Int,
  to goal: Int,
) -> option.Option(utils.Path(Int))

to_graph

</>

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

topological_sort

</>

pub fn topological_sort(dag: models.Dag(n, e)) -> List(Int)

transitive_closure

</>

pub fn transitive_closure(
  dag: models.Dag(n, e),
  with merge_fn: fn(e, e) -> e,
) -> models.Dag(n, e)

transitive_reduction

</>

pub fn transitive_reduction(
  dag: models.Dag(n, e),
  with merge_fn: fn(e, e) -> e,
) -> models.Dag(n, e)