Yog.FSharp
Getting Started Examples API Reference GitHub

Algorithms Module

Namespace: Yog.Dag
Assembly: Yog.FSharp.dll

DAG-specific algorithms that leverage acyclicity guarantees.

These algorithms are optimized for DAGs and would be incorrect or inefficient on general graphs with cycles. The DAG property enables linear-time solutions for problems that are NP-hard on general graphs.

Algorithms Provided

Algorithm

Complexity

Use Case

topologicalSort

O(V+E)

Task scheduling, dependency ordering

longestPath

O(V+E)

Critical path analysis (PERT/CPM)

shortestPath

O(V+E)

Minimum cost path between nodes

transitiveClosure

O(V²)

Reachability queries, indirect dependencies

transitiveReduction

O(V×E)

Simplify graphs, remove implied edges

countReachability

O(V+E)

Impact analysis, prerequisite counting

lowestCommonAncestors

O(V×(V+E))

Merge bases, shared dependencies

Why DAGs Are Special

DAGs enable efficient algorithms for problems that are intractable on general graphs: - Longest Path: O(V+E) on DAGs vs NP-hard on general graphs - Topological Sort: Always succeeds on DAGs vs may fail with cycles - Shortest Path: O(V+E) on DAGs vs O((V+E) log V) with Dijkstra

References

Functions and values

Function or value Description

countReachability direction dag

Full Usage: countReachability direction dag

Parameters:
Returns: Map<NodeId, int>

Map from node ID to count of reachable nodes in the specified direction.

Count total descendants or ancestors using set-based DP.

Parameters

  • direction: Count Ancestors (can reach node) or Descendants (reachable from node)
  • dag: The input DAG

Complexity

  • Time: O(V + E)
  • Space: O(V²) in worst case (storing all reachability sets)

Example

1: 
2: 
3: 
4: 
5: 

// Count how many tasks depend on each task (descendants)
let impact = Algorithms.countReachability Descendants dag

// Count prerequisites for each task (ancestors)
let prerequisites = Algorithms.countReachability Ancestors dag

Use Cases

  • Impact analysis (how many things break if X fails)
  • Work prioritization (tasks with many prerequisites first)
  • Dependency metrics
val impact: obj
val prerequisites: obj

direction : Direction
dag : Dag<'n, 'e>
Returns: Map<NodeId, int>

Map from node ID to count of reachable nodes in the specified direction.

longestPath dag

Full Usage: longestPath dag

Parameters:
    dag : Dag<'n, int>

Returns: NodeId list

List of node IDs forming the longest path from any source to any sink.

Finds the Longest Path (Critical Path) in O(V+E).

In a DAG, the longest path problem is well-defined and solvable in linear time. This is useful for critical path analysis in project scheduling.

Type Constraint

Edge weights must be integers.

Complexity

  • Time: O(V + E)
  • Space: O(V)

Example

1: 
2: 
3: 
4: 

// Task durations as edge weights
let criticalPath = Algorithms.longestPath dag
printfn "Project duration: %d"
    (criticalPath.Length - 1)

Use Cases

  • Project management (PERT/CPM)
  • Scheduling with dependencies
  • Finding slowest execution path
val criticalPath: obj
val printfn: format: Printf.TextWriterFormat<'T> -> 'T

dag : Dag<'n, int>
Returns: NodeId list

List of node IDs forming the longest path from any source to any sink.

lowestCommonAncestors nodeA nodeB dag

Full Usage: lowestCommonAncestors nodeA nodeB dag

Parameters:
Returns: NodeId list

List of node IDs representing the lowest common ancestors.

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.

Parameters

  • nodeA: First node
  • nodeB: Second node
  • dag: The input DAG

Complexity

  • Time: O(V×(V+E))
  • Space: O(V)

Example

1: 
2: 
3: 

// Given: X->A, X->B, Y->A, Z->B
// LCAs of A and B are [X] - the most specific shared ancestor
let lcas = Algorithms.lowestCommonAncestors nodeA nodeB dag

Use Cases

  • Finding merge bases in version control
  • Identifying shared dependencies
  • Computing dominators in control flow graphs
val lcas: obj

nodeA : NodeId
nodeB : NodeId
dag : Dag<'n, 'e>
Returns: NodeId list

List of node IDs representing the lowest common ancestors.

shortestPath src dst dag

Full Usage: shortestPath src dst dag

Parameters:
Returns: NodeId list option
  • Some path: List of node IDs from src to dst with minimum total weight
  • None: If no path exists from src to dst

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 src to dst. Unlike Dijkstra's algorithm which works on general graphs in O((V+E) log V), this leverages the DAG property for linear time complexity.

Type Constraint

Edge weights must be integers.

Complexity

  • Time: O(V + E)
  • Space: O(V)

Example

1: 
2: 
3: 
4: 
5: 

match Algorithms.shortestPath dag 0 5 with
| Some path ->
    printfn "Shortest path: %A" path
| None ->
    printfn "No path exists"

Use Cases

  • Finding fastest route in task dependencies
  • Minimum cost path in project networks
  • Critical path alternatives
union case Option.Some: Value: 'T -> Option<'T>
val path: obj
val printfn: format: Printf.TextWriterFormat<'T> -> 'T
union case Option.None: Option<'T>

src : NodeId
dst : NodeId
dag : Dag<'n, int>
Returns: NodeId list option

  • Some path: List of node IDs from src to dst with minimum total weight
  • None: If no path exists from src to dst

topologicalSort dag

Full Usage: topologicalSort dag

Parameters:
    dag : Dag<'n, 'e>

Returns: NodeId list

List of node IDs in topological order (sources before targets).

Topological sort guaranteed to succeed for the Dag type.

Complexity

  • Time: O(V + E)
  • Space: O(V)

Note

This function cannot fail because the Dag type guarantees acyclicity. If it somehow encounters a cycle, it raises an exception (indicating a bug).

Example

1: 
2: 
3: 
4: 

let order = Algorithms.topologicalSort dag
// Process nodes in dependency order
for node in order do
    executeTask node
val order: obj seq
val node: obj

dag : Dag<'n, 'e>
Returns: NodeId list

List of node IDs in topological order (sources before targets).

transitiveClosure mergeFn dag

Full Usage: transitiveClosure mergeFn dag

Parameters:
    mergeFn : 'e -> 'e -> 'e
    dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>

A new DAG representing the transitive closure.

Transitive Closure: Reachability map with merged weights.

Computes a new DAG where there's a direct edge from u to v if v is reachable from u in the original DAG. Edge weights are merged using the provided function.

Parameters

  • mergeFn: Function to combine weights when multiple paths exist
  • dag: The input DAG

Complexity

  • Time: O(V² + VE) - processes each edge and potential path
  • Space: O(V²) - stores reachability for all pairs

Example

1: 
2: 

// Merge by taking minimum weight along any path
let closure = Algorithms.transitiveClosure min dag

Use Cases

  • Dependency analysis (what indirectly depends on what)
  • Reachability queries
  • Partial order completion
val closure: obj
val min: e1: 'T -> e2: 'T -> 'T (requires comparison)

mergeFn : 'e -> 'e -> 'e
dag : Dag<'n, 'e>
Returns: Dag<'n, 'e>

A new DAG representing the transitive closure.

transitiveReduction mergeFn dag

Full Usage: transitiveReduction mergeFn dag

Parameters:
    mergeFn : 'e -> 'e -> 'e
    dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>

A new DAG with redundant edges removed.

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.

Parameters

  • mergeFn: Function to combine weights when multiple paths exist
  • dag: The input DAG

Complexity

  • Time: O(V×E)
  • Space: O(V²)

Example

1: 
2: 
3: 
4: 

// 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 = Algorithms.transitiveReduction min dag

Use Cases

  • Simplifying dependency graphs
  • Removing implied dependencies
  • Creating minimal representations
val minimal: obj
val min: e1: 'T -> e2: 'T -> 'T (requires comparison)

mergeFn : 'e -> 'e -> 'e
dag : Dag<'n, 'e>
Returns: Dag<'n, 'e>

A new DAG with redundant edges removed.