Yog.FSharp
Getting Started Examples API Reference GitHub

Traversal Module

Namespace: Yog
Assembly: Yog.FSharp.dll

Graph traversal algorithms - systematic exploration of graph structure.

This module provides fundamental graph traversal algorithms for visiting nodes in a specific order. Traversals are the foundation for most graph algorithms including pathfinding, connectivity analysis, and cycle detection.

Traversal Orders

Order

Strategy

Best For

BFS

Level-by-level

Shortest path (unweighted), finding neighbors

DFS

Deep exploration

Cycle detection, topological sort, connectivity

Core Functions

  • walk with BreadthFirst/DepthFirst: Simple traversals returning visited nodes in order
  • foldWalk: Generic traversal with custom fold function and metadata
  • topologicalSort / lexicographicalTopologicalSort: Ordering for DAGs
  • isCyclic / isAcyclic: Cycle detection via Kahn's algorithm
  • implicitFold / implicitFoldBy / implicitDijkstra: Traversals for implicit graphs

Walk Control

The foldWalk function provides fine-grained control: - Continue: Explore this node's neighbors normally - Stop: Skip this node's neighbors but continue traversal - Halt: Stop the entire traversal immediately

Time Complexity

All traversals run in O(V + E) linear time, visiting each node and edge at most once. Dijkstra-based traversals are O((V + E) log V).

References

Types

Type Description

Order

Traversal order for graph walking algorithms.

WalkControl

Control flow for foldWalk traversal.

WalkMetadata<'nid>

Metadata provided during foldWalk / implicitFold traversal.

Functions and values

Function or value Description

foldWalk start order initial folder graph

Full Usage: foldWalk start order initial folder graph

Parameters:
Returns: 'a

Folds over nodes during graph traversal, accumulating state with metadata.

This function combines traversal with state accumulation, providing metadata about each visited node (depth and parent). The folder function controls the traversal flow:

  • Continue: Explore successors of the current node normally
  • Stop: Skip successors of this node, but continue processing other queued nodes
  • Halt: Stop the entire traversal immediately and return the accumulator

Time Complexity: O(V + E) for both BFS and DFS

Parameters

  • folder: Called for each visited node with (accumulator, node_id, metadata). Returns (WalkControl, new_accumulator).

Use Cases

  • Finding nodes within a certain distance
  • Building shortest path trees (parent pointers)
  • Collecting nodes with custom filtering logic
  • Computing statistics during traversal (depth distribution, etc.)
  • BFS/DFS with early termination based on accumulated state

start : NodeId
order : Order
initial : 'a
folder : 'a -> NodeId -> WalkMetadata<NodeId> -> WalkControl * 'a
graph : Graph<'n, 'e>
Returns: 'a

implicitDijkstra start initial successors folder

Full Usage: implicitDijkstra start initial successors folder

Parameters:
    start : 'nid
    initial : 'a
    successors : 'nid -> ('nid * int) list
    folder : 'a -> 'nid -> int -> WalkControl * 'a

Returns: 'a

Traverses an implicit weighted graph using Dijkstra's algorithm, folding over visited nodes in order of increasing cost.

Like implicitFold but uses a priority queue so nodes are visited cheapest-first. Ideal for shortest-path problems on implicit state spaces where edge costs vary — e.g., state-space search with Manhattan moves, or multi-robot coordination where multiple robots share a key-bitmask state.

  • successors: Given a node, return List<(neighbor * edge_cost)>. Include only valid transitions (filtering here avoids dead states).
  • folder: Called once per node, with (acc, node, cost_so_far). Return (Halt, result) to stop immediately, (Stop, acc) to skip expanding this node's successors, or (Continue, acc) to continue.

Internally maintains a Dictionary<state, cost> of best-known costs; stale priority-queue entries are automatically skipped.

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 

// Shortest path in an implicit maze with uniform cost
implicitDijkstra
  start
  -1
  (fun pos ->
     neighbors pos
     |> List.map (fun nb -> (nb, 1)))  // uniform cost
  (fun acc pos cost ->
     if pos = target then
       (Halt, cost)
     else
       (Continue, acc))

Use Cases

  • Shortest path on infinite grids
  • Weighted state-space search
  • Resource-constrained pathfinding
Multiple items
module List from Microsoft.FSharp.Collections

--------------------
type List<'T> = | op_Nil | op_ColonColon of Head: 'T * Tail: 'T list interface IReadOnlyList<'T> interface IReadOnlyCollection<'T> interface IEnumerable interface IEnumerable<'T> member GetReverseIndex: rank: int * offset: int -> int member GetSlice: startIndex: int option * endIndex: int option -> 'T list static member Cons: head: 'T * tail: 'T list -> 'T list member Head: 'T with get member IsEmpty: bool with get member Item: index: int -> 'T with get ...
val map: mapping: ('T -> 'U) -> list: 'T list -> 'U list

start : 'nid
initial : 'a
successors : 'nid -> ('nid * int) list
folder : 'a -> 'nid -> int -> WalkControl * 'a
Returns: 'a

implicitFold start order initial successors folder

Full Usage: implicitFold start order initial successors folder

Parameters:
Returns: 'a

Traverses an implicit graph using BFS or DFS, folding over visited nodes with metadata.

Unlike foldWalk, this does not require a materialised Graph value. Instead, you supply a successors function that computes neighbours on the fly — ideal for infinite grids, state-space search, or any graph that is too large or expensive to build upfront.

Example

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 

// BFS shortest path in an implicit maze
implicitFold
  (1, 1)
  BreadthFirst
  -1
  (fun pos -> openNeighbors pos)
  (fun acc pos meta ->
     if pos = target then
       (Halt, meta.Depth)
     else
       (Continue, acc))

Use Cases

  • Infinite grids (e.g., cellular automata, game maps)
  • State-space search (puzzle solving, pathfinding)
  • On-demand graph generation (procedural content)

start : 'nid
order : Order
initial : 'a
successors : 'nid -> 'nid list
folder : 'a -> 'nid -> WalkMetadata<'nid> -> WalkControl * 'a
Returns: 'a

implicitFoldBy start order initial successors visitedBy folder

Full Usage: implicitFoldBy start order initial successors visitedBy folder

Parameters:
    start : 'nid
    order : Order
    initial : 'a
    successors : 'nid -> 'nid list
    visitedBy : 'nid -> 'key
    folder : 'a -> 'nid -> WalkMetadata<'nid> -> WalkControl * 'a

Returns: 'a

Like implicitFold, but deduplicates visited nodes by a custom key.

This is essential when your node type carries extra state beyond what defines "identity". For example, in state-space search you might have (Position * Mask) nodes, but only want to visit each Position once — the Mask is just carried state, not part of the identity.

The visitedBy function extracts the deduplication key from each node. Internally, a HashSet<key> tracks which keys have been visited, but the full nid value (with all its state) is still passed to your folder.

Time Complexity: O(V + E) for both BFS and DFS, where V and E are measured in terms of unique keys (not unique nodes).

Example

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

// Search a maze where nodes carry both position and step count
// but we only want to visit each position once (first-visit wins)
type State = { Pos: int * int; Steps: int }

implicitFoldBy
  { Pos = (0, 0); Steps = 0 }
  BreadthFirst
  None
  (fun state ->
     neighbors state.Pos
     |> List.map (fun nextPos -> { Pos = nextPos; Steps = state.Steps + 1 }))
  (fun state -> state.Pos)  // Dedupe by position only
  (fun acc state _meta ->
     if state.Pos = target then
       (Halt, Some state.Steps)
     else
       (Continue, acc))

Use Cases

  • Puzzle solving: (board_state, moves) → dedupe by board_state
  • Path finding with budget: (pos, fuel_left) → dedupe by pos
  • Game state search: (position, inventory) → dedupe by position
  • Graph search with metadata: (node_id, path_history) → dedupe by node_id

Comparison to implicitFold

  • implicitFold: Deduplicates by the entire node value nid
  • implicitFoldBy: Deduplicates by visitedBy(nid) but keeps full nid
type State = { Pos: int * int Steps: int }
Multiple items
val int: value: 'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
union case Option.None: Option<'T>
Multiple items
module List from Microsoft.FSharp.Collections

--------------------
type List<'T> = | op_Nil | op_ColonColon of Head: 'T * Tail: 'T list interface IReadOnlyList<'T> interface IReadOnlyCollection<'T> interface IEnumerable interface IEnumerable<'T> member GetReverseIndex: rank: int * offset: int -> int member GetSlice: startIndex: int option * endIndex: int option -> 'T list static member Cons: head: 'T * tail: 'T list -> 'T list member Head: 'T with get member IsEmpty: bool with get member Item: index: int -> 'T with get ...
val map: mapping: ('T -> 'U) -> list: 'T list -> 'U list
union case Option.Some: Value: 'T -> Option<'T>

start : 'nid
order : Order
initial : 'a
successors : 'nid -> 'nid list
visitedBy : 'nid -> 'key
folder : 'a -> 'nid -> WalkMetadata<'nid> -> WalkControl * 'a
Returns: 'a

isAcyclic graph

Full Usage: isAcyclic graph

Parameters:
Returns: bool

Determines if a graph is acyclic (contains no cycles).

This is the logical opposite of isCyclic. For directed graphs, returning true means the graph is a Directed Acyclic Graph (DAG).

Time Complexity: O(V + E)

Example

1: 
2: 

isAcyclic graph
// => true  // Valid DAG or undirected forest

graph : Graph<'n, 'e>
Returns: bool

isCyclic graph

Full Usage: isCyclic graph

Parameters:
Returns: bool

Determines if a graph contains any cycles.

For directed graphs, a cycle exists if there is a path from a node back to itself (evaluated efficiently via Kahn's algorithm). For undirected graphs, a cycle exists if there is a path of length >= 3 from a node back to itself, or a self-loop.

Time Complexity: O(V + E)

Example

1: 
2: 

isCyclic graph
// => true  // Cycle detected

graph : Graph<'n, 'e>
Returns: bool

lexicographicalTopologicalSort compareNodes graph

Full Usage: lexicographicalTopologicalSort compareNodes graph

Parameters:
    compareNodes : 'n -> 'n -> int
    graph : Graph<'n, 'e>

Returns: Result<NodeId list, unit>

Performs a topological sort that returns the lexicographically smallest sequence.

Uses a heap-based version of Kahn's algorithm to ensure that when multiple nodes have in-degree 0, the smallest one (according to compareNodes) is chosen first.

The comparison function operates on node data, not node IDs, allowing intuitive comparisons like String.compare for alphabetical ordering.

Returns Error() if the graph contains a cycle.

Time Complexity: O(V log V + E) due to heap operations

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 

// Get alphabetical ordering by node data
lexicographicalTopologicalSort (fun a b -> String.compare(a, b)) graph
// => Ok [0; 1; 2]  // Node IDs ordered by their string data

// Custom comparison by priority
lexicographicalTopologicalSort (fun a b ->
  compare a.Priority b.Priority) graph

Use Cases

  • Deterministic task ordering (when multiple valid orderings exist)
  • Alphabetical/lexicographical ordering of tasks
  • Priority-based scheduling
module String from Microsoft.FSharp.Core
val compare: e1: 'T -> e2: 'T -> int (requires comparison)

compareNodes : 'n -> 'n -> int
graph : Graph<'n, 'e>
Returns: Result<NodeId list, unit>

topologicalSort graph

Full Usage: topologicalSort graph

Parameters:
Returns: Result<NodeId list, unit>

Performs a topological sort on a directed graph using Kahn's algorithm.

Returns a linear ordering of nodes such that for every directed edge (u, v), node u comes before node v in the ordering.

Returns Error() if the graph contains a cycle.

Time Complexity: O(V + E) where V is vertices and E is edges

Example

1: 
2: 
3: 

topologicalSort graph
// => Ok [1; 2; 3; 4]  // Valid ordering
// or Error()          // Cycle detected

Use Cases

  • Task scheduling with dependencies
  • Compilation ordering
  • Resolving symbol dependencies

graph : Graph<'n, 'e>
Returns: Result<NodeId list, unit>

walk startId order graph

Full Usage: walk startId order graph

Parameters:
Returns: NodeId list

Walks the graph starting from the given node, visiting all reachable nodes.

Returns a list of NodeIds in the order they were visited. Uses successors to follow directed paths.

Example

1: 
2: 
3: 
4: 
5: 
6: 
7: 

// BFS traversal
walk 1 BreadthFirst graph
// => [1; 2; 3; 4; 5]

// DFS traversal
walk 1 DepthFirst graph
// => [1; 2; 4; 5; 3]

startId : NodeId
order : Order
graph : Graph<'n, 'e>
Returns: NodeId list

walkUntil startId order shouldStop graph

Full Usage: walkUntil startId order shouldStop graph

Parameters:
Returns: NodeId list

Walks the graph but stops early when a condition is met.

Traverses the graph until shouldStop returns True for a node. Returns all nodes visited including the one that stopped traversal.

Example

1: 
2: 

// Stop when we find node 5
walkUntil 1 BreadthFirst (fun node -> node = 5) graph

startId : NodeId
order : Order
shouldStop : NodeId -> bool
graph : Graph<'n, 'e>
Returns: NodeId list