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)

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]

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]

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
}

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

Computes the transitive closure of a DAG.

The transitive closure adds edges between all pairs of nodes where a path exists in the original graph. If u can reach v through any path, the closure will have a direct edge u -> v.

The merge_fn is used to combine edge weights when multiple paths exist between the same pair of nodes.

Use cases:

• Reachability queries (is A reachable from B?)
• Precomputing path relationships
• Dependency analysis (what indirectly depends on what?)

Time Complexity: O(V × E) in the worst case

Example

// Original edges: A->B (weight 2), B->C (weight 3)
// Closure adds: A->C (weight 5 = 2+3)
let closure = dag.algorithms.transitive_closure(dag, int.add)

Computes the transitive reduction of a DAG.

The transitive reduction removes all edges that are redundant - i.e., edges u -> v where there exists an indirect path from u to v through other nodes. The result has the minimum number of edges while preserving all reachability relationships.

This is the inverse of transitive closure. It’s useful for:

• Simplifying dependency graphs
• Removing implied dependencies
• Creating minimal representations

Time Complexity: O(V × E)

Example

// Original: A->B, B->C, A->C (A->C is implied by A->B->C)
// Reduction removes: A->C
// Result: A->B, B->C
let minimal = dag.algorithms.transitive_reduction(dag, int.add)