yog - v6.0.0

yog/multi/traversal

Graph traversal algorithms for multigraphs.

This module provides BFS and DFS traversal algorithms adapted for multigraphs. Unlike simple graph traversals, these algorithms use edge IDs to correctly handle parallel edges.

Key Differences from Simple Graph Traversal

Available Functions

Walk Control

The fold_walk function provides fine-grained control:

Time Complexity

All traversals run in O(V + E) linear time.

References

Types

WalkControl

</>

Control flow for fold_walk traversal.

pub type WalkControl {
  Continue
  Stop
  Halt
}

Constructors 

  • Continue

    Continue exploring from this node’s successors.

  • Stop

    Stop exploring from this node (but continue with other queued nodes).

  • Halt

    Halt the entire traversal immediately and return the accumulator.

WalkMetadata

</>

Metadata provided during fold_walk traversal for multigraphs.

Unlike simple graphs, this includes the specific edge used to reach each node.

pub type WalkMetadata {
  WalkMetadata(depth: Int, parent: option.Option(#(Int, Int)))
}

Constructors 

  • WalkMetadata(depth: Int, parent: option.Option(#(Int, Int)))

    Arguments

    depth

    Distance from the start node (number of edges traversed).

    parent

    The parent node and edge that led to this node (None for the start node).

Values

bfs

</> 
pub fn bfs(
  graph: model.MultiGraph(n, e),
  source: Int,
) -> List(Int)

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)

dfs

</> 
pub fn dfs(
  graph: model.MultiGraph(n, e),
  source: Int,
) -> List(Int)

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

Time Complexity: O(V + E)

fold_walk

</> 
pub fn fold_walk(
  over graph: model.MultiGraph(n, e),
  from start: Int,
  initial acc: a,
  with folder: fn(a, Int, WalkMetadata) -> #(WalkControl, a),
) -> a

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

Parameters

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

Examples

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

// Build a parent map tracking which edge led to each node
let parents = traversal.fold_walk(
  over: graph,
  from: start,
  initial: dict.new(),
  with: fn(acc, node_id, meta) {
    let new_acc = case meta.parent {
      Some(#(parent_node, edge_id)) ->
        dict.insert(acc, node_id, #(parent_node, edge_id))
      None -> acc
    }
    #(Continue, new_acc)
  }
)

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

// Collect all edges in the traversal path
let path_edges = traversal.fold_walk(
  over: graph,
  from: start,
  initial: [],
  with: fn(acc, _node_id, meta) {
    let new_acc = case meta.parent {
      Some(#(_, edge_id)) -> [edge_id, ..acc]
      None -> acc
    }
    #(Continue, new_acc)
  }
)
✨ Search Document