yog - v3.0.0

yog/dag/algorithms

Types

Direction

</> 
pub type Direction {
  Ancestors
  Descendants
}

Constructors 

  • Ancestors
  • Descendants

Values

count_reachability

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

count_reachability(Dag(n, e), Direction) -> Dict(NodeId, Int) Goal: Efficiently count total descendants/ancestors for every node.

Uses sets internally to handle diamond patterns efficiently - a node with multiple paths to the same descendant is only counted once.

longest_path

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

longest_path(Dag(n, Int)) -> List(NodeId) Goal: Find the Critical Path in O(V+E). Returns the list of node IDs forming the longest path in the DAG.

lowest_common_ancestors

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

lowest_common_ancestors(Dag(n, e), NodeId, NodeId) -> List(NodeId) Goal: Find the immediate common dependencies of two nodes.

shortest_path

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

shortest_path(Dag(n, Int), NodeId, NodeId) -> Option(Path(e)) Finds the shortest path between two nodes in a DAG using O(V+E) dynamic programming.

Unlike Dijkstra’s algorithm which works on general graphs in O((V+E) log V), this leverages the DAG property for linear time complexity.

Returns None if no path exists from from to to.

topological_sort

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

topological_sort(Dag(n, e)) -> List(NodeId) Unlike the general version, this version is total (cannot return an Error) because the DAG type guarantees acyclicity.

transitive_closure

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

transitive_closure(Dag(n, e), fn(e, e) -> e) -> Dag(n, e) Goal: Create a “Reachability Map” where an edge (u, v) exists if v is reachable from u. Returns a new Dag representing the transitive closure. The merge_fn combines edge weights when an indirect path dominates.

transitive_reduction

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

transitive_reduction(Dag(n, e), fn(e, e) -> e) -> Dag(n, e) Goal: Remove redundant edges while preserving reachability.

✨ Search Document