Folds over nodes in Best-First order using a priority queue.

Nodes are explored according to the score returned by score_of (cheapest first). This is a Greedy Best-First Search — if you need cumulative edge costs, use dijkstra.fold instead.

Performs a Greedy Best-First Walk starting from the given node.

Visits nodes in order of their score as determined by score_of. Lower scores are visited first. Unlike Dijkstra, scores are not cumulative.

Example

traversal.best_first_walk(
  graph,
  from: 1,
  scored_by: fn(node_id) { get_priority(node_id) }
)

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).

Examples

import gleam/dict
import yog/traversal.{BreadthFirst, Continue, Halt, Stop, WalkMetadata}

// Find all nodes within distance 3 from start
let nearby = traversal.fold_walk(
  graph,
  from: 1,
  using: BreadthFirst,
  initial: dict.new(),
  with: fn(acc, node_id, meta) {
    case meta.depth <= 3 {
      True -> #(Continue, dict.insert(acc, node_id, meta.depth))
      False -> #(Stop, acc)  // Don't explore beyond depth 3
    }
  }
)

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

Unlike fold_walk, this does not require a materialised Graph value. Instead, you supply a successors_of 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

// BFS shortest path in an implicit maze
traversal.implicit_fold(
  from: #(1, 1),
  using: BreadthFirst,
  initial: -1,
  successors_of: fn(pos) { open_neighbours(pos, fav) },
  with: fn(acc, pos, meta) {
    case pos == target {
      True -> #(Halt, meta.depth)
      False -> #(Continue, acc)
    }
  },
)

Like implicit_fold, 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 visited_by function extracts the deduplication key from each node. Internally, a Set(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

// 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 {
  State(pos: #(Int, Int), steps: Int)
}

traversal.implicit_fold_by(
  from: State(#(0, 0), 0),
  using: BreadthFirst,
  initial: None,
  successors_of: fn(state) {
    neighbors(state.pos)
    |> list.map(fn(next_pos) {
      State(next_pos, state.steps + 1)
    })
  },
  visited_by: fn(state) { state.pos },  // Dedupe by position only
  with: fn(acc, state, _meta) {
    case state.pos == target {
      True -> #(Halt, Some(state.steps))
      False -> #(Continue, acc)
    }
  },
)

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 compare_nodes) is chosen first.

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

Returns Error(Nil) if the graph contains a cycle.

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

Example

// Get alphabetical ordering by node data
traversal.lexicographical_topological_sort(graph, string.compare)
// => Ok([0, 1, 2])  // Node IDs ordered by their string data

Simulates a random walk on the graph for a specified number of steps.

At each step, one of the current node’s neighbors is chosen uniformly at random. Returns the sequence of node IDs visited.

Parameters

• steps: Maximum number of steps to take.
• seed: Optional seed for reproducibility.

Example

traversal.random_walk(graph, from: 1, steps: 10, seed: Some(42))
// => [1, 2, 5, 2, 3, 1, ...]

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(Nil) if the graph contains a cycle.

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

Example

traversal.topological_sort(graph)
// => Ok([1, 2, 3, 4])  // Valid ordering
// or Error(Nil)         // Cycle detected

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

// BFS traversal
traversal.walk(graph, from: 1, using: BreadthFirst)
// => [1, 2, 3, 4, 5]

// DFS traversal
traversal.walk(graph, from: 1, using: DepthFirst)
// => [1, 2, 4, 5, 3]

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

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

Example

// Stop when we find node 5
traversal.walk_until(
  graph,
  from: 1,
  using: BreadthFirst,
  until: fn(node) { node == 5 }
)