@spec bfs(Yog.Multi.Model.t(), Yog.node_id()) :: [Yog.node_id()]

Performs a Breadth-First Search from source, returning visited node IDs in BFS order.

Unlike simple-graph BFS, this traversal uses edge IDs to correctly handle parallel edges — each edge is traversed at most once, but a node may be reached via multiple edges (the first visit wins for ordering purposes).

Time Complexity

O(V + E)

Examples

nodes = Yog.Multi.Traversal.bfs(multi, :a)
#=> [:a, :b, :c, :d]

@spec dfs(Yog.Multi.Model.t(), Yog.node_id()) :: [Yog.node_id()]

Performs a Depth-First Search from source, returning visited node IDs in DFS pre-order.

Time Complexity

O(V + E)

Examples

nodes = Yog.Multi.Traversal.dfs(multi, :a)
#=> [:a, :b, :d, :c]

@spec fold_walk(
  Yog.Multi.Model.t(),
  Yog.node_id(),
  acc,
  (acc, Yog.node_id(), walk_metadata() -> {walk_control(), acc})
) :: acc
when acc: var

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

This function combines traversal with state accumulation, providing metadata about each visited node including which specific edge was used to reach it. The folder function controls the traversal flow:

• :continue - Explore successors of the current node normally
• :stop - Skip successors of this node, but continue with other queued nodes
• :halt - Stop the entire traversal immediately and return the accumulator

For multigraphs, the metadata includes the specific EdgeId used to reach each node, which is important when parallel edges exist.

Time Complexity

O(V + E)

Examples

# Build a parent map tracking which edge led to each node
parents = Yog.Multi.Traversal.fold_walk(multi, :a, %{}, fn acc, node_id, meta ->
  new_acc = case meta.parent do
    {parent_node, edge_id} -> Map.put(acc, node_id, {parent_node, edge_id})
    nil -> acc
  end
  {:continue, new_acc}
end)

# Find all nodes within distance 3
nearby = Yog.Multi.Traversal.fold_walk(multi, :a, [], fn acc, node_id, meta ->
  if meta.depth <= 3 do
    {:continue, [node_id | acc]}
  else
    {:stop, acc}
  end
end)