Inductive graph traversals — BFS and DFS without explicit visited sets.
Unlike traditional graph traversals that maintain a separate "visited" set, these
implementations rely on the structural match/2 operation. When a node is extracted,
it is removed from the graph along with all its incident edges, so the shrunken
graph naturally prevents revisits.
Available Traversals
| Traversal | Function | Data Structure | Return value |
|---|---|---|---|
| DFS | dfs/2 | Stack (list) | Node contexts |
| BFS | bfs/2 | Queue (:queue) | Node contexts |
| Preorder | preorder/2 | DFS wrapper | Node IDs in visit order |
| Postorder | postorder/2 | Recursive finishing order | Node IDs in finish order |
| Reachable | reachable/2 | DFS wrapper | Reachable node IDs |
Key Principle
Iterating with the shrunken graph naturally prevents revisiting nodes and
terminates when no queued start/candidate nodes remain — no MapSet of visited
nodes is needed.
Semantics
- Traversal starts can be a single node ID or a list of node IDs.
- Missing start nodes are skipped.
- Duplicate start nodes or duplicate neighbor discoveries are visited at most once because already-matched nodes are absent from the remaining graph.
- Directed graphs follow outgoing edges only. Undirected graphs store edges symmetrically, so outgoing edges represent all adjacent nodes.
- Neighbor order follows map key iteration order and should be treated as unspecified.
Complexity
BFS and DFS are O(V + E) over the reachable portion of the graph. Because this
is an inductive/persistent representation, traversals allocate shrunken graph
versions as they progress; use adjacency-based Yog.Traversal.Walk for raw
traversal throughput on large production graphs.
References
Summary
Functions
Performs a breadth-first search starting from the given node ID or node IDs.
Performs a depth-first search starting from the given node ID or node IDs.
Returns node IDs in postorder (finishing order).
Returns node IDs in preorder (DFS visit order).
Returns all node IDs reachable from the start node or node IDs.
Functions
@spec bfs( Yog.Functional.Model.t(), Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()] ) :: [Yog.Functional.Model.Context.t()]
Performs a breadth-first search starting from the given node ID or node IDs.
Returns a list of node contexts in the order they were visited. Missing start nodes are skipped.
This is an inductive BFS: each step calls match/2 to extract a node
and obtain the shrunken graph, ensuring nodes are visited at most once.
Examples
iex> alias Yog.Functional.{Model, Traversal}
iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.add_edge!(1, 2)
iex> visited = Traversal.bfs(graph, 1)
iex> Enum.map(visited, & &1.id)
[1, 2]@spec dfs( Yog.Functional.Model.t(), Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()] ) :: [Yog.Functional.Model.Context.t()]
Performs a depth-first search starting from the given node ID or node IDs.
Returns a list of node contexts in the order they were visited. Missing start nodes are skipped.
This is an inductive DFS: each step calls match/2 to simultaneously
extract a node and obtain the shrunken graph without that node.
Revisit prevention comes naturally from the graph shrinking — a node already
visited simply won't be found in the remaining graph.
For directed graphs, only outgoing edges are followed. For undirected graphs,
edges are stored symmetrically so out_edges covers all adjacent nodes.
Examples
iex> alias Yog.Functional.{Model, Traversal}
iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.add_edge!(1, 2)
iex> visited = Traversal.dfs(graph, 1)
iex> Enum.map(visited, & &1.id)
[1, 2]@spec postorder( Yog.Functional.Model.t(), Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()] ) :: [Yog.Functional.Model.node_id()]
Returns node IDs in postorder (finishing order).
Examples
iex> alias Yog.Functional.{Model, Traversal}
iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.add_edge!(1, 2)
iex> Traversal.postorder(graph, 1)
[2, 1]@spec preorder( Yog.Functional.Model.t(), Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()] ) :: [Yog.Functional.Model.node_id()]
Returns node IDs in preorder (DFS visit order).
Examples
iex> alias Yog.Functional.{Model, Traversal}
iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.add_edge!(1, 2)
iex> Traversal.preorder(graph, 1)
[1, 2]@spec reachable( Yog.Functional.Model.t(), Yog.Functional.Model.node_id() | [Yog.Functional.Model.node_id()] ) :: [Yog.Functional.Model.node_id()]
Returns all node IDs reachable from the start node or node IDs.
This is a thin wrapper around dfs/2, returning IDs instead of contexts.
Examples
iex> alias Yog.Functional.{Model, Traversal}
iex> graph = Model.empty() |> Model.put_node(1, "A") |> Model.put_node(2, "B")
...> |> Model.add_edge!(1, 2)
iex> Traversal.reachable(graph, 1) |> Enum.sort()
[1, 2]