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(
  over: 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
    }
  }
)

// Stop immediately when target is found (like walk_until)
let path_to_target = traversal.fold_walk(
  over: graph,
  from: start,
  using: BreadthFirst,
  initial: [],
  with: fn(acc, node_id, _meta) {
    let new_acc = [node_id, ..acc]
    case node_id == target {
      True -> #(Halt, new_acc)   // Stop entire traversal
      False -> #(Continue, new_acc)
    }
  }
)

// Build a parent map for path reconstruction
let parents = traversal.fold_walk(
  over: graph,
  from: start,
  using: BreadthFirst,
  initial: dict.new(),
  with: fn(acc, node_id, meta) {
    let new_acc = case meta.parent {
      Some(p) -> dict.insert(acc, node_id, p)
      None -> acc
    }
    #(Continue, new_acc)
  }
)

// Count nodes at each depth level
let depth_counts = traversal.fold_walk(
  over: graph,
  from: root,
  using: BreadthFirst,
  initial: dict.new(),
  with: fn(acc, _node_id, meta) {
    let count = dict.get(acc, meta.depth) |> result.unwrap(0)
    #(Continue, dict.insert(acc, meta.depth, count + 1))
  }
)

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

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

Like implicit_fold 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_of: 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 Dict(nid, Int) of best-known costs; stale priority-queue entries are automatically skipped.

Example

// Shortest path in an implicit maze with uniform cost
traversal.implicit_dijkstra(
  from: start,
  initial: -1,
  successors_of: fn(pos) {
    neighbours(pos)
    |> list.map(fn(nb) { #(nb, 1) })  // uniform cost
  },
  with: fn(acc, pos, cost) {
    case pos == target {
      True -> #(Halt, cost)
      False -> #(Continue, acc)
    }
  },
)

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

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)
    }
  },
)

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 implicit_fold

• implicit_fold: Deduplicates by the entire node value nid
• implicit_fold_by: Deduplicates by visited_by(nid) but keeps full nid

Similar to SQL’s DISTINCT ON(key) or Python’s key= parameter.

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

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

Time Complexity: O(V + E)

Example

traversal.is_acyclic(graph)
// => True // Valid DAG or undirected forest

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

traversal.is_cyclic(graph)
// => True // 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(from: 1, in: graph, using: BreadthFirst)
// => [1, 2, 3, 4, 5]

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

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

Traverses the graph until should_stop 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(
  from: 1,
  in: graph,
  using: BreadthFirst,
  until: fn(node) { node == 5 }
)