Yog.Traversal.Walk (YogEx v0.97.0)

Copy Markdown View Source

Graph walking algorithms — BFS, DFS, Best-First, and Random traversals.

This module provides a unified API for exploring graphs starting from a given node. It supports both standard discovery (BFS, DFS) and informed discovery where the next nodes are prioritized based on weights, heuristics, or randomness.

Discovery Visualization

Traversals like BFS explore a graph in layers, prioritizing nodes based on their distance from the source.

digraph G { bgcolor="transparent"; node [shape=circle, fontname="inherit"]; edge [fontname="inherit", fontsize=10]; Root [label="Root", color="#6366f1", penwidth=2.5, style=bold]; // Discovery steps Root -> A [label="1"]; Root -> B [label="2"]; A -> C [label="3"]; A -> D [label="4"]; B -> E [label="5"]; // BFS Layers subgraph cluster_l1 { label="Layer 1 (dist=1)"; color="#6366f1"; style=rounded; A; B; } subgraph cluster_l2 { label="Layer 2 (dist=2)"; color="#f43f5e"; style=rounded; C; D; E; } }
iex> alias Yog.Traversal.Walk
iex> graph = Yog.from_edges(:directed, [
...>   {"Root", "A", 1}, {"Root", "B", 1},
...>   {"A", "C", 1}, {"A", "D", 1}, {"B", "E", 1}
...> ])
iex> Walk.walk(in: graph, from: "Root", using: :breadth_first)
["Root", "A", "B", "C", "D", "E"]

Summary

Types

order()
priority_fn()
walk_control()
walk_metadata()

Functions

find_path(graph, from, to)

Finds the shortest path between two nodes using BFS.

fold_walk(opts)

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

fold_walk(graph, from, order, initial, folder)
random_walk(graph, from, steps)

Performs a random walk of fixed length from the given starting node.

reachable?(graph, from, to)

Checks if there is a path between two nodes.

walk(opts)

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

walk(graph, from, order)
walk_until(opts)

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

walk_until(graph, from, order, should_stop)

Types

order()

@type order() :: :breadth_first | :depth_first | :best_first | :random

priority_fn()

@type priority_fn() :: (Yog.node_id(), number(), walk_metadata() -> number())

walk_control()

@type walk_control() :: :continue | :stop | :halt

walk_metadata()

@type walk_metadata() :: %{depth: integer(), parent: Yog.node_id() | nil}

Functions

find_path(graph, from, to)

@spec find_path(Yog.graph(), Yog.node_id(), Yog.node_id()) :: [Yog.node_id()] | nil

Finds the shortest path between two nodes using BFS.

fold_walk(opts)

@spec fold_walk(keyword()) :: any()

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

The folder function receives (accumulator, node_id, metadata) and should return {control, new_accumulator}.

Metadata

The metadata map contains:

  • :depth - Distance from the starting node.
  • :parent - The node ID that led to this node.

Control Signals

  • :continue - Continue traversal normally.
  • :stop - Do not explore successors of the current node, but continue with the rest of the frontier.
  • :halt - Stop the entire traversal immediately.

fold_walk(graph, from, order, initial, folder)

@spec fold_walk(
  Yog.graph(),
  Yog.node_id(),
  order(),
  acc,
  (acc, Yog.node_id(), walk_metadata() -> {walk_control(), acc})
) :: acc
when acc: var

random_walk(graph, from, steps)

@spec random_walk(Yog.graph(), Yog.node_id(), integer()) :: [Yog.node_id()]

Performs a random walk of fixed length from the given starting node.

Unlike discovery traversals (BFS/DFS), a random walk does not keep track of visited nodes and may cross the same node or edge multiple times.

Parameters

  • graph: The graph to walk.
  • from: The starting node ID.
  • steps: The number of jumps/edges to transition (path length in edges).

Examples

iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil) |> Yog.add_edge_ensure(2, 1, 1, nil)
iex> path = Yog.Traversal.Walk.random_walk(graph, 1, 3)
iex> length(path)
4

reachable?(graph, from, to)

@spec reachable?(Yog.graph(), Yog.node_id(), Yog.node_id()) :: boolean()

Checks if there is a path between two nodes.

walk(opts)

@spec walk(keyword()) :: [Yog.node_id()]

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

Options

  • :from - Starting node ID
  • :in - The graph to traverse
  • :using - Traversal order. Options:
    • :breadth_first (BFS)
    • :depth_first (DFS)
    • :best_first - Prioritizes discovery based on a :priority function.
    • :random - Randomizes discovery order.
  • :priority - Required if :using is :best_first. A function taking (node_id, weight, meta).

Examples

# Simple BFS walk
iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 1, nil)
iex> Yog.Traversal.Walk.walk(in: graph, from: 1, using: :breadth_first)
[1, 2]

# Greedy walk using edge weights (lowest weight first)
iex> graph = Yog.directed() |> Yog.add_edge_ensure(1, 2, 10, nil) |> Yog.add_edge_ensure(1, 3, 5, nil)
iex> Yog.Traversal.Walk.walk(in: graph, from: 1, using: :best_first, priority: fn _, w, _ -> w end)
[1, 3, 2]

walk(graph, from, order)

@spec walk(Yog.graph(), Yog.node_id(), order()) :: [Yog.node_id()]

walk_until(opts)

@spec walk_until(keyword()) :: [Yog.node_id()]

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

walk_until(graph, from, order, should_stop)

@spec walk_until(Yog.graph(), Yog.node_id(), order(), (Yog.node_id() -> boolean())) ::
  [Yog.node_id()]