algorithm

Algorithms for Directed Acyclic Graphs (DAGs).

This module provides efficient algorithms that leverage the acyclicity guarantee of the Dag type. These algorithms run in linear O(V+E) time, faster than their general-graph counterparts.

Available Algorithms

Algorithm	Function	Use Case
Topological Sort	`topological_sort/1`	Task scheduling, build systems
Longest Path	`longest_path/1`	Critical path analysis, project scheduling
Shortest Path	`shortest_path/3`	Weighted DAG shortest paths
Transitive Closure	`transitive_closure/2`	Reachability queries
Transitive Reduction	`transitive_reduction/2`	Minimal graph representation
LCA	`lowest_common_ancestors/3`	Dependency analysis, merge bases

Time Complexity

Most algorithms run in O(V + E) linear time due to DP on topologically sorted nodes:

Path algorithms: O(V + E)
Transitive closure/reduction: O(V × E) worst case
LCA computation: O(V × (V + E))

Example

import yog/dag/algorithm as dag

// Find critical path in a project schedule (weighted DAG)
let critical_path = dag.longest_path(project_dag)

References

Types

Dag

</>

pub type Dag(node_data, edge_data) =
  model.Dag(node_data, edge_data)

Direction

</>

Direction for reachability counting operations.

Ancestors - Count nodes that can reach the given node (predecessors)
Descendants - Count nodes reachable from the given node (successors)

pub type Direction {
  Ancestors
  Descendants
}

Constructors

```
Ancestors
```
Count nodes that have paths TO the target (incoming reachability).
```
Descendants
```
Count nodes reachable FROM the target (outgoing reachability).

Values

count_reachability

</>

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

Counts the number of ancestors or descendants for every node.

For each node, returns how many other nodes are reachable from it (Descendants) or can reach it (Ancestors).

Uses dynamic programming on the topologically sorted DAG for efficiency. Properly handles diamond patterns where a node is reachable through multiple paths - each node is only counted once.

Time Complexity: O(V × E) in the worst case (sparse graphs), optimized with set operations for common cases.

Example

// Given: A->B, A->C, B->D, C->D (diamond pattern)
// D has 3 ancestors (A, B, C)
// A has 3 descendants (B, C, D) - D counted once despite 2 paths
let descendant_counts = dag.algorithms.count_reachability(dag, Descendants)
// dict.get(descendant_counts, a) == Ok(3)

longest_path

</>

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

Finds the longest path (critical path) in a weighted DAG.

The longest path is the path with maximum total edge weight from any source node to any sink node. This is the dual of shortest path and is useful for:

Project scheduling (finding the critical path)
Dependency chains with durations
Determining minimum time to complete all tasks

Time Complexity: O(V + E) - linear via dynamic programming on the topologically sorted DAG.

Note: For unweighted graphs, this finds the path with most edges. Weights must be non-negative for meaningful results.

Example

// Find the critical path in a project schedule
let critical_path = dag.algorithms.longest_path(project_dag)
// critical_path == [start, task_a, task_b, end]

lowest_common_ancestors

</>

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

Finds the lowest common ancestors (LCAs) of two nodes.

A common ancestor of nodes A and B is any node that has paths to both A and B. The “lowest” common ancestors are those that are not ancestors of any other common ancestor - they are the “closest” shared dependencies.

This is useful for:

Finding merge bases in version control
Identifying shared dependencies
Computing dominators in control flow graphs

Time Complexity: O(V × (V + E))

Example

// Given: X->A, X->B, Y->A, Z->B
// LCAs of A and B are [X] - the most specific shared ancestor
let lcas = dag.algorithms.lowest_common_ancestors(dag, a, b)
// lcas == [x]

shortest_path

</>

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

Finds the shortest path between two specific nodes in a weighted DAG.

Uses dynamic programming on the topologically sorted DAG to find the minimum weight path from from to to. 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.

Time Complexity: O(V + E)

Example

// Find shortest path in a weighted DAG
case dag.algorithms.shortest_path(my_dag, from: start_node, to: end_node) {
  Some(path) -> {
    // path.nodes contains the node sequence
    // path.total_weight is the path length
  }
  None -> // No path exists
}

topological_sort

</>

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

Returns a topological ordering of all nodes in the DAG.

Unlike traversal.topological_sort() which returns Result (since general graphs may contain cycles), this version is total - it always returns a valid ordering because the Dag type guarantees acyclicity.

In a topological ordering, every node appears before all nodes it has edges to. This is useful for scheduling tasks with dependencies, build systems, etc.

Time Complexity: O(V + E)

Example

// Given edges: 1->2, 1->3, 2->4, 3->4
// Valid topological sorts include: [1, 2, 3, 4] or [1, 3, 2, 4]
let sorted = dag.algorithms.topological_sort(my_dag)
// sorted == [1, 2, 3, 4]  // or another valid ordering