Model (yog-fsharp) | Yog.FSharp

Model Module

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

Directed Acyclic Graph (DAG) type and operations.

A DAG is a directed graph with no cycles. This module provides a type-safe wrapper around Graph that guarantees acyclicity through construction, enabling total functions for operations that would be partial on general graphs.

Core Concept

The DAG type uses the "smart constructor" pattern: - fromGraph validates acyclicity and wraps the graph - addEdge returns Result because it could create a cycle - addNode/removeNode/removeEdge are safe (cannot create cycles)

Once constructed, the DAG type guarantees no cycles exist, allowing algorithms like topological sort to be total functions.

When to Use

Use Case	Example
Task Scheduling	Build systems (Make, Gradle), CI/CD pipelines
Dependencies	Package managers (npm, cargo), module imports
Partial Orders	Preference rankings, event causality
Control Flow	Compiler IRs, dataflow graphs
Version Control	Git commit history, merge bases
Bayesian Networks	Probabilistic graphical models

Key Properties

Guaranteed acyclic: Type system prevents cycles at construction
Topological sort always succeeds: No need to handle cycle errors
Longest path is well-defined: Can find critical paths in O(V+E)
Shortest path is efficient: O(V+E) vs O((V+E) log V) for general graphs

Comparison with Graph

Aspect	Dag	Graph
Cycles allowed	❌ No	✅ Yes
addEdge result	`Result<Dag, error>`	`Graph`
topologicalSort	Always succeeds	May fail
longestPath	O(V+E)	NP-hard
shortestPath	O(V+E)	O((V+E) log V)

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18:

open Yog.Dag

// Build a task dependency DAG
let dagResult =
    Yog.Model.empty Directed
    |> Yog.Model.addNode 0 "Compile"
    |> Yog.Model.addNode 1 "Link"
    |> Yog.Model.addNode 2 "Test"
    |> Yog.Model.addEdge 0 1 ()
    |> Yog.Model.addEdge 1 2 ()
    |> Model.fromGraph

match dagResult with
| Ok dag ->
    let order = Algorithms.topologicalSort dag
    printfn "Execution order: %A" order
| Error CycleDetected ->
    printfn "Circular dependency detected!"

References

namespace Yog

namespace Yog.Dag

val dagResult: Result<Dag<string,unit>,DagError>

module Model from Yog
<summary> Core graph data structures and basic operations for the yog library. This module defines the fundamental `Graph` type and provides all basic operations for creating and manipulating graphs. The graph uses an adjacency list representation with dual indexing (both outgoing and incoming edges) for efficient traversal in both directions. </summary>

val empty: graphType: Yog.Model.GraphType -> Yog.Model.Graph<'n,'e>
<summary> Creates a new empty graph of the specified type. ## Example ```fsharp let graph = Model.empty Directed ``` </summary>

val addNode: id: Yog.Model.NodeId -> data: 'n -> graph: Yog.Model.Graph<'n,'e> -> Yog.Model.Graph<'n,'e>
<summary> Adds a node to the graph with the given ID and data. If a node with this ID already exists, its data will be replaced. ## Example ```fsharp graph |> addNode 1 "Node A" |> addNode 2 "Node B" ``` </summary>

val addEdge: src: Yog.Model.NodeId -> dst: Yog.Model.NodeId -> weight: 'e -> graph: Yog.Model.Graph<'n,'e> -> Yog.Model.Graph<'n,'e>
<summary> Adds an edge to the graph with the given weight. For directed graphs, adds a single edge from src to dst. For undirected graphs, adds edges in both directions. > **Note:** If `src` or `dst` have not been added via `addNode`, > the edge will still be created in the edge dictionaries, but the > nodes will be missing from `graph.Nodes`. This creates "ghost nodes" > that are traversable but invisible to functions that iterate over > nodes (e.g. `order`, `allNodes`). Use `addEdgeEnsured` to > auto-create missing endpoints with a default value. ## Example ```fsharp graph |> addEdge 1 2 10 ``` </summary>

module Model from Yog.Dag
<summary> Directed Acyclic Graph (DAG) type and operations. A DAG is a directed graph with no cycles. This module provides a type-safe wrapper around Graph that guarantees acyclicity through construction, enabling total functions for operations that would be partial on general graphs. ## Core Concept The DAG type uses the "smart constructor" pattern: - **fromGraph** validates acyclicity and wraps the graph - **addEdge** returns Result because it could create a cycle - **addNode/removeNode/removeEdge** are safe (cannot create cycles) Once constructed, the DAG type guarantees no cycles exist, allowing algorithms like topological sort to be total functions. ## When to Use | Use Case | Example | |----------|---------| | **Task Scheduling** | Build systems (Make, Gradle), CI/CD pipelines | | **Dependencies** | Package managers (npm, cargo), module imports | | **Partial Orders** | Preference rankings, event causality | | **Control Flow** | Compiler IRs, dataflow graphs | | **Version Control** | Git commit history, merge bases | | **Bayesian Networks** | Probabilistic graphical models | ## Key Properties - **Guaranteed acyclic**: Type system prevents cycles at construction - **Topological sort always succeeds**: No need to handle cycle errors - **Longest path is well-defined**: Can find critical paths in O(V+E) - **Shortest path is efficient**: O(V+E) vs O((V+E) log V) for general graphs ## Comparison with Graph | Aspect | Dag | Graph | |--------|-----|-------| | Cycles allowed | ❌ No | ✅ Yes | | addEdge result | `Result<Dag, error>` | `Graph` | | topologicalSort | Always succeeds | May fail | | longestPath | O(V+E) | NP-hard | | shortestPath | O(V+E) | O((V+E) log V) | ## Example ```fsharp open Yog.Dag // Build a task dependency DAG let dagResult = Yog.Model.empty Directed |> Yog.Model.addNode 0 "Compile" |> Yog.Model.addNode 1 "Link" |> Yog.Model.addNode 2 "Test" |> Yog.Model.addEdge 0 1 () |> Yog.Model.addEdge 1 2 () |> Model.fromGraph match dagResult with | Ok dag -> let order = Algorithms.topologicalSort dag printfn "Execution order: %A" order | Error CycleDetected -> printfn "Circular dependency detected!" ``` ## References - [Wikipedia: Directed Acyclic Graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) - [Topological Sorting](https://en.wikipedia.org/wiki/Topological_sorting) - [Smart Constructors](https://wiki.haskell.org/Smart_constructors) </summary>

val fromGraph: graph: Yog.Model.Graph<'n,'e> -> Result<Dag<'n,'e>,DagError> (requires equality and equality)
<summary> The Guard: Uses isAcyclic to validate the graph. ## Parameters - `graph`: The graph to validate ## Returns - `Ok dag`: If the graph is acyclic - `Error CycleDetected`: If the graph contains a cycle ## Example ```fsharp let result = Model.fromGraph myGraph match result with | Ok dag -> printfn "Valid DAG" | Error CycleDetected -> printfn "Graph has a cycle" ``` </summary>

union case Result.Ok: ResultValue: 'T -> Result<'T,'TError>

val dag: Dag<string,unit>

val order: Yog.Model.NodeId list

module Algorithms from Yog.Dag
<summary> 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 - [Wikipedia: Directed Acyclic Graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) - [Longest Path Problem](https://en.wikipedia.org/wiki/Longest_path_problem) - [Transitive Closure](https://en.wikipedia.org/wiki/Transitive_closure) - [Transitive Reduction](https://en.wikipedia.org/wiki/Transitive_reduction) </summary>

val topologicalSort: dag: Dag<'n,'e> -> Yog.Model.NodeId list (requires equality and equality)
<summary> Topological sort guaranteed to succeed for the Dag type. ## Complexity - **Time**: O(V + E) - **Space**: O(V) ## Returns List of node IDs in topological order (sources before targets). ## 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 ```fsharp let order = Algorithms.topologicalSort dag // Process nodes in dependency order for node in order do executeTask node ``` </summary>

val printfn: format: Printf.TextWriterFormat<'T> -> 'T

union case Result.Error: ErrorValue: 'TError -> Result<'T,'TError>

union case DagError.CycleDetected: DagError

Functions and values

Function or value Description


                
                  
                    
                      addEdge src dst weight dag

Full Usage: addEdge src dst weight dag

Parameters:

src : NodeId

dst : NodeId

weight : 'e

dag : Dag<'n, 'e>

Returns: Result<Dag<'n, 'e>, DagError>

Ok updatedDag: If adding the edge doesn't create a cycle
Error CycleDetected: If the edge would create a cycle

Adds an edge. Returns Result because it could create a cycle.

Parameters

src: Source node ID
dst: Target node ID
weight: Edge weight
dag: The DAG to modify

Example

1: 
2: 
3:

match Model.addEdge 0 1 weight dag with
| Ok dag' -> printfn "Edge added"
| Error CycleDetected -> printfn "Would create cycle"

union case Result.Ok: ResultValue: 'T -> Result<'T,'TError>

val dag': obj

val printfn: format: Printf.TextWriterFormat<'T> -> 'T

union case Result.Error: ErrorValue: 'TError -> Result<'T,'TError>

val CycleDetected: obj

src : NodeId
dst : NodeId
weight : 'e
dag : Dag<'n, 'e>

Returns: Result<Dag<'n, 'e>, DagError>

Ok updatedDag: If adding the edge doesn't create a cycle
Error CycleDetected: If the edge would create a cycle


                
                  
                    
                      addNode id data dag

Full Usage: addNode id data dag

Parameters:

id : NodeId

data : 'n

dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>

Adds a node. Safe for DAGs (cannot create cycles).

Example

1:	`let dag2 = Model.addNode 3 "New Task" dag`

val dag2: obj

id : NodeId
data : 'n
dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>


                
                  
                    
                      fromGraph graph

Full Usage: fromGraph graph

Parameters:

graph : Graph<'n, 'e>

Returns: Result<Dag<'n, 'e>, DagError>

Ok dag: If the graph is acyclic
Error CycleDetected: If the graph contains a cycle

The Guard: Uses isAcyclic to validate the graph.

Parameters

graph: The graph to validate

Example

1: 
2: 
3: 
4:

let result = Model.fromGraph myGraph
match result with
| Ok dag -> printfn "Valid DAG"
| Error CycleDetected -> printfn "Graph has a cycle"

val result: Result<obj,obj>

union case Result.Ok: ResultValue: 'T -> Result<'T,'TError>

val dag: obj

val printfn: format: Printf.TextWriterFormat<'T> -> 'T

union case Result.Error: ErrorValue: 'TError -> Result<'T,'TError>

val CycleDetected: obj

graph : Graph<'n, 'e>

Returns: Result<Dag<'n, 'e>, DagError>

Ok dag: If the graph is acyclic
Error CycleDetected: If the graph contains a cycle


                
                  
                    
                      removeEdge src dst dag

Full Usage: removeEdge src dst dag

Parameters:

src : NodeId

dst : NodeId

dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>

Removes an edge. Safe for DAGs.

Removing edges cannot create cycles.

src : NodeId
dst : NodeId
dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>


                
                  
                    
                      removeNode id dag

Full Usage: removeNode id dag

Parameters:

id : NodeId

dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>

Removes a node. Safe for DAGs.

Removing nodes cannot create cycles.

id : NodeId
dag : Dag<'n, 'e>

Returns: Dag<'n, 'e>


                
                  
                    
                      toGraph dag

Full Usage: toGraph dag

Parameters:

dag : Dag<'n, 'e>

Returns: Graph<'n, 'e>

The Exit: Unwraps back into a standard Graph.

Example

1:	`let graph = Model.toGraph myDag`

val graph: obj

dag : Dag<'n, 'e>

Returns: Graph<'n, 'e>