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 |
|---|---|---|
| DFS | dfs/2 | Stack (list) |
| BFS | bfs/2 | Queue (:queue) |
| Preorder | preorder/2 | Node IDs in visit order |
| Postorder | postorder/2 | Node IDs in finish order |
| Reachable | reachable/2 | All reachable node IDs |
Key Principle
Iterating with the shrunken graph naturally prevents revisiting nodes and
terminates when the graph is empty — no MapSet of visited nodes needed.
Time Complexity: O(V + E) for both BFS and DFS.
References
Summary
Functions
Performs a Breadth-First Search starting from the given node ID(s).
Performs a Depth-First Search starting from the given node ID(s).
Returns node IDs in Postorder (finishing order, last node finishing first).
Returns node IDs in Preorder (visit order).
Returns all node IDs reachable from the start node(s).
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(s).
Returns a list of node contexts in the order they were visited.
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(s).
Returns a list of node contexts in the order they were visited.
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, last node finishing first).
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 (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(s).
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]