Traversal

Best-first / min-priority-queue traversal. Smallest element dequeued first. Requires Ordering[V] in scope.

Best-first / max-priority-queue traversal. Largest element dequeued first. Requires Ordering[V] in scope.

Best-first traversal with an explicit CostUpdate — for Dijkstra and Prim.

The frontier element type W is typically (E, V) where E is the cost type and V is the vertex type. The caller supplies:

• start: the seed element, e.g. (zero, startVertex)
• a given IndexedPrioQueue[W] = IndexedPrioQueue.empty[W] (always empty; traverse seeds the frontier from start's neighbours)
• a given CostUpdate[W, IndexedPrioQueue] that calls decreaseKey after each settle
• Neighbours[W, W] expanding (cost, vertex) to (newCost, neighbour) pairs

NOTE: discover is not called in bestFirstWeighted — the came-from relationship for weighted traversals is already tracked via the pred map inside WeightedTraversal.CostUpdate.

Breadth-first search traversal.

discover(neighbour, node) is called for each unvisited neighbour before it is offered to the frontier, recording the came-from relationship at discovery time.

Depth-first search with configurable pre- or post-order recording.

The internal stack holds Either[V, V] frames:

• Left(v) means "expand v — push its children and a record frame"
• Right(v) means "record v in the visitor now"

Pre-order: record before expanding → Right(v) on top, visited first. Post-order: record after expanding → children expanded before v is recorded.

discover(child, node) is called for each unvisited child at expand time (the Left(node) branch), before the child frames are pushed to the stack. This records the came-from relationship at the point of discovery.

The goal predicate is checked on Right (record) frames — i.e. after a node is visited. Traversal halts after recording the first node satisfying goal; its remaining siblings and their subtrees are not visited.

Traverses a (homogeneous) graph structure starting from a given node, visiting nodes iteratively and accumulating results into a visitor.

After each node's neighbours are offered to the frontier, cu.update is called to apply any priority improvements (e.g. decreaseKey in Dijkstra/Prim). For DFS and BFS the default no-op CostUpdate is resolved automatically.

The start node is always visited and recorded first, before any goal check or frontier expansion. If goal(start) is true, traversal stops immediately after recording the start node — no neighbours are expanded.

For all subsequent nodes, traversal stops after recording the first node for which goal(node) returns true — that node is recorded in the journal but its neighbours are not expanded.

discover(neighbour, node) is called for each unvisited neighbour before it is offered to the frontier, recording the came-from relationship at discovery time.

Traverses a tree-like structure starting from a given root node, visiting nodes as specified by the provided Visitor.

NOTE: traverseTree does not visit the root start itself (there is no Evaluable[H, R] in scope for H), so the visitor is unseeded before the loop begins — unlike traverse where visitor.visit(start) is called first.

The order parameter controls pre- or post-order recording, using the same Either-tagged stack mechanism as dfs:

• Left(v) — expand node: mark visited, push children and a record frame
• Right(v) — record node: call visitor.visit(v)

The seed step uses rootNbrs (H → V) to get the initial children from the root. All subsequent steps use graphNbrs (V → V).

Traversal stops after recording the first V node for which goal(node) returns true. The goal node is recorded in the journal but its neighbours are not expanded.

NOTE: discover is not called in traverseTree — the tree structure implies the came-from relationship is already known from the tree shape.