yog/traversal

Types

Order

Traversal order for graph walking algorithms.

pub type Order {
  BreadthFirst
  DepthFirst
}

Constructors

```
BreadthFirst
```
Breadth-First Search: visit all neighbors before going deeper.
```
DepthFirst
```
Depth-First Search: visit as deep as possible before backtracking.

Values

walk

</>

pub fn walk(
  from start_id: Int,
  in graph: model.Graph(n, e),
  using order: Order,
) -> List(Int)

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]

walk_until

</>

pub fn walk_until(
  from start_id: Int,
  in graph: model.Graph(n, e),
  using order: Order,
  until should_stop: fn(Int) -> Bool,
) -> List(Int)

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