Current section
Files
Jump to
Current section
Files
src/yog@traversal.erl
-module(yog@traversal).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/traversal.gleam").
-export([fold_walk/5, walk/3, walk_until/4, implicit_fold/5, implicit_fold_by/6, implicit_dijkstra/4, lexicographical_topological_sort/2, topological_sort/1, is_cyclic/1, is_acyclic/1]).
-export_type([order/0, walk_control/0, walk_metadata/1]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
-type order() :: breadth_first | depth_first.
-type walk_control() :: continue | stop | halt.
-type walk_metadata(HPK) :: {walk_metadata, integer(), gleam@option:option(HPK)}.
-file("src/yog/traversal.gleam", 103).
-spec check_undirected_cycle(
yog@model:graph(any(), any()),
integer(),
gleam@option:option(integer()),
gleam@set:set(integer())
) -> {boolean(), gleam@set:set(integer())}.
check_undirected_cycle(Graph, Node, Parent, Visited) ->
New_visited = gleam@set:insert(Visited, Node),
Neighbors = yog@model:successor_ids(Graph, Node),
gleam@list:fold_until(
Neighbors,
{false, New_visited},
fun(Acc, Neighbor) ->
{_, Current_visited} = Acc,
case gleam@set:contains(Current_visited, Neighbor) of
true ->
Is_parent = case Parent of
{some, P} ->
P =:= Neighbor;
none ->
false
end,
case Is_parent of
true ->
{continue, {false, Current_visited}};
false ->
{stop, {true, Current_visited}}
end;
false ->
{Has_cycle, Next_visited} = check_undirected_cycle(
Graph,
Neighbor,
{some, Node},
Current_visited
),
case Has_cycle of
true ->
{stop, {true, Next_visited}};
false ->
{continue, {false, Next_visited}}
end
end
end
).
-file("src/yog/traversal.gleam", 80).
-spec do_has_undirected_cycle(
yog@model:graph(any(), any()),
list(integer()),
gleam@set:set(integer())
) -> boolean().
do_has_undirected_cycle(Graph, Nodes, Visited) ->
case Nodes of
[] ->
false;
[Node | Rest] ->
case gleam@set:contains(Visited, Node) of
true ->
do_has_undirected_cycle(Graph, Rest, Visited);
false ->
{Cycle, New_visited} = check_undirected_cycle(
Graph,
Node,
none,
Visited
),
case Cycle of
true ->
true;
false ->
do_has_undirected_cycle(Graph, Rest, New_visited)
end
end
end.
-file("src/yog/traversal.gleam", 463).
-spec do_fold_walk_bfs(
yog@model:graph(any(), any()),
yog@internal@queue:queue({integer(), walk_metadata(integer())}),
gleam@set:set(integer()),
HRM,
fun((HRM, integer(), walk_metadata(integer())) -> {walk_control(), HRM})
) -> HRM.
do_fold_walk_bfs(Graph, Q, Visited, Acc, Folder) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
Acc;
{ok, {{Node_id, Metadata}, Rest}} ->
case gleam@set:contains(Visited, Node_id) of
true ->
do_fold_walk_bfs(Graph, Rest, Visited, Acc, Folder);
false ->
{Control, New_acc} = Folder(Acc, Node_id, Metadata),
New_visited = gleam@set:insert(Visited, Node_id),
case Control of
halt ->
New_acc;
stop ->
do_fold_walk_bfs(
Graph,
Rest,
New_visited,
New_acc,
Folder
);
continue ->
Next_nodes = yog@model:successor_ids(Graph, Node_id),
Next_queue = gleam@list:fold(
Next_nodes,
Rest,
fun(Current_queue, Next_id) ->
Next_meta = {walk_metadata,
erlang:element(2, Metadata) + 1,
{some, Node_id}},
yog@internal@queue:push(
Current_queue,
{Next_id, Next_meta}
)
end
),
do_fold_walk_bfs(
Graph,
Next_queue,
New_visited,
New_acc,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 506).
-spec do_fold_walk_dfs(
yog@model:graph(any(), any()),
list({integer(), walk_metadata(integer())}),
gleam@set:set(integer()),
HRV,
fun((HRV, integer(), walk_metadata(integer())) -> {walk_control(), HRV})
) -> HRV.
do_fold_walk_dfs(Graph, Stack, Visited, Acc, Folder) ->
case Stack of
[] ->
Acc;
[{Node_id, Metadata} | Tail] ->
case gleam@set:contains(Visited, Node_id) of
true ->
do_fold_walk_dfs(Graph, Tail, Visited, Acc, Folder);
false ->
{Control, New_acc} = Folder(Acc, Node_id, Metadata),
New_visited = gleam@set:insert(Visited, Node_id),
case Control of
halt ->
New_acc;
stop ->
do_fold_walk_dfs(
Graph,
Tail,
New_visited,
New_acc,
Folder
);
continue ->
Next_nodes = yog@model:successor_ids(Graph, Node_id),
Next_stack = gleam@list:fold_right(
Next_nodes,
Tail,
fun(Current_stack, Next_id) ->
Next_meta = {walk_metadata,
erlang:element(2, Metadata) + 1,
{some, Node_id}},
[{Next_id, Next_meta} | Current_stack]
end
),
do_fold_walk_dfs(
Graph,
Next_stack,
New_visited,
New_acc,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 293).
?DOC(
" Folds over nodes during graph traversal, accumulating state with metadata.\n"
"\n"
" This function combines traversal with state accumulation, providing metadata\n"
" about each visited node (depth and parent). The folder function controls the\n"
" traversal flow:\n"
"\n"
" - `Continue`: Explore successors of the current node normally\n"
" - `Stop`: Skip successors of this node, but continue processing other queued nodes\n"
" - `Halt`: Stop the entire traversal immediately and return the accumulator\n"
"\n"
" **Time Complexity:** O(V + E) for both BFS and DFS\n"
"\n"
" ## Parameters\n"
"\n"
" - `folder`: Called for each visited node with (accumulator, node_id, metadata).\n"
" Returns `#(WalkControl, new_accumulator)`.\n"
"\n"
" ## Examples\n"
"\n"
" ```gleam\n"
" import gleam/dict\n"
" import yog/traversal.{BreadthFirst, Continue, Halt, Stop, WalkMetadata}\n"
"\n"
" // Find all nodes within distance 3 from start\n"
" let nearby = traversal.fold_walk(\n"
" graph,\n"
" from: 1,\n"
" using: BreadthFirst,\n"
" initial: dict.new(),\n"
" with: fn(acc, node_id, meta) {\n"
" case meta.depth <= 3 {\n"
" True -> #(Continue, dict.insert(acc, node_id, meta.depth))\n"
" False -> #(Stop, acc) // Don't explore beyond depth 3\n"
" }\n"
" }\n"
" )\n"
"\n"
" // Stop immediately when target is found (like walk_until)\n"
" let path_to_target = traversal.fold_walk(\n"
" graph,\n"
" from: start,\n"
" using: BreadthFirst,\n"
" initial: [],\n"
" with: fn(acc, node_id, _meta) {\n"
" let new_acc = [node_id, ..acc]\n"
" case node_id == target {\n"
" True -> #(Halt, new_acc) // Stop entire traversal\n"
" False -> #(Continue, new_acc)\n"
" }\n"
" }\n"
" )\n"
"\n"
" // Build a parent map for path reconstruction\n"
" let parents = traversal.fold_walk(\n"
" graph,\n"
" from: start,\n"
" using: BreadthFirst,\n"
" initial: dict.new(),\n"
" with: fn(acc, node_id, meta) {\n"
" let new_acc = case meta.parent {\n"
" Some(p) -> dict.insert(acc, node_id, p)\n"
" None -> acc\n"
" }\n"
" #(Continue, new_acc)\n"
" }\n"
" )\n"
"\n"
" // Count nodes at each depth level\n"
" let depth_counts = traversal.fold_walk(\n"
" graph,\n"
" from: root,\n"
" using: BreadthFirst,\n"
" initial: dict.new(),\n"
" with: fn(acc, _node_id, meta) {\n"
" let count = dict.get(acc, meta.depth) |> result.unwrap(0)\n"
" #(Continue, dict.insert(acc, meta.depth, count + 1))\n"
" }\n"
" )\n"
" ```\n"
"\n"
" ## Use Cases\n"
"\n"
" - Finding nodes within a certain distance\n"
" - Building shortest path trees (parent pointers)\n"
" - Collecting nodes with custom filtering logic\n"
" - Computing statistics during traversal (depth distribution, etc.)\n"
" - BFS/DFS with early termination based on accumulated state\n"
).
-spec fold_walk(
yog@model:graph(any(), any()),
integer(),
order(),
HQU,
fun((HQU, integer(), walk_metadata(integer())) -> {walk_control(), HQU})
) -> HQU.
fold_walk(Graph, Start, Order, Acc, Folder) ->
Start_metadata = {walk_metadata, 0, none},
case Order of
breadth_first ->
do_fold_walk_bfs(
Graph,
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, {Start, Start_metadata})
end,
gleam@set:new(),
Acc,
Folder
);
depth_first ->
do_fold_walk_dfs(
Graph,
[{Start, Start_metadata}],
gleam@set:new(),
Acc,
Folder
)
end.
-file("src/yog/traversal.gleam", 153).
?DOC(
" Walks the graph starting from the given node, visiting all reachable nodes.\n"
"\n"
" Returns a list of NodeIds in the order they were visited.\n"
" Uses successors to follow directed paths.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // BFS traversal\n"
" traversal.walk(graph, from: 1, using: BreadthFirst)\n"
" // => [1, 2, 3, 4, 5]\n"
"\n"
" // DFS traversal\n"
" traversal.walk(graph, from: 1, using: DepthFirst)\n"
" // => [1, 2, 4, 5, 3]\n"
" ```\n"
).
-spec walk(yog@model:graph(any(), any()), integer(), order()) -> list(integer()).
walk(Graph, Start_id, Order) ->
_pipe = fold_walk(
Graph,
Start_id,
Order,
[],
fun(Acc, Node_id, _) -> {continue, [Node_id | Acc]} end
),
lists:reverse(_pipe).
-file("src/yog/traversal.gleam", 184).
?DOC(
" Walks the graph but stops early when a condition is met.\n"
"\n"
" Traverses the graph until `should_stop` returns True for a node.\n"
" Returns all nodes visited including the one that stopped traversal.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Stop when we find node 5\n"
" traversal.walk_until(\n"
" graph,\n"
" from: 1,\n"
" using: BreadthFirst,\n"
" until: fn(node) { node == 5 }\n"
" )\n"
" ```\n"
).
-spec walk_until(
yog@model:graph(any(), any()),
integer(),
order(),
fun((integer()) -> boolean())
) -> list(integer()).
walk_until(Graph, Start_id, Order, Should_stop) ->
_pipe = fold_walk(
Graph,
Start_id,
Order,
[],
fun(Acc, Node_id, _) ->
New_acc = [Node_id | Acc],
case Should_stop(Node_id) of
true ->
{halt, New_acc};
false ->
{continue, New_acc}
end
end
),
lists:reverse(_pipe).
-file("src/yog/traversal.gleam", 546).
-spec do_implicit_bfs(
yog@internal@queue:queue({HRX, walk_metadata(HRX)}),
gleam@set:set(HRX),
HSB,
fun((HRX) -> list(HRX)),
fun((HSB, HRX, walk_metadata(HRX)) -> {walk_control(), HSB})
) -> HSB.
do_implicit_bfs(Q, Visited, Acc, Successors, Folder) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
Acc;
{ok, {{Node_id, Metadata}, Rest}} ->
case gleam@set:contains(Visited, Node_id) of
true ->
do_implicit_bfs(Rest, Visited, Acc, Successors, Folder);
false ->
{Control, New_acc} = Folder(Acc, Node_id, Metadata),
New_visited = gleam@set:insert(Visited, Node_id),
case Control of
halt ->
New_acc;
stop ->
do_implicit_bfs(
Rest,
New_visited,
New_acc,
Successors,
Folder
);
continue ->
Next_queue = gleam@list:fold(
Successors(Node_id),
Rest,
fun(Q2, Next_id) ->
yog@internal@queue:push(
Q2,
{Next_id,
{walk_metadata,
erlang:element(2, Metadata) + 1,
{some, Node_id}}}
)
end
),
do_implicit_bfs(
Next_queue,
New_visited,
New_acc,
Successors,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 591).
-spec do_implicit_dfs(
list({HSE, walk_metadata(HSE)}),
gleam@set:set(HSE),
HSI,
fun((HSE) -> list(HSE)),
fun((HSI, HSE, walk_metadata(HSE)) -> {walk_control(), HSI})
) -> HSI.
do_implicit_dfs(Stack, Visited, Acc, Successors, Folder) ->
case Stack of
[] ->
Acc;
[{Node_id, Metadata} | Tail] ->
case gleam@set:contains(Visited, Node_id) of
true ->
do_implicit_dfs(Tail, Visited, Acc, Successors, Folder);
false ->
{Control, New_acc} = Folder(Acc, Node_id, Metadata),
New_visited = gleam@set:insert(Visited, Node_id),
case Control of
halt ->
New_acc;
stop ->
do_implicit_dfs(
Tail,
New_visited,
New_acc,
Successors,
Folder
);
continue ->
Next_stack = gleam@list:fold_right(
Successors(Node_id),
Tail,
fun(Stk, Next_id) ->
[{Next_id,
{walk_metadata,
erlang:element(2, Metadata) + 1,
{some, Node_id}}} |
Stk]
end
),
do_implicit_dfs(
Next_stack,
New_visited,
New_acc,
Successors,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 347).
?DOC(
" Traverses an *implicit* graph using BFS or DFS,\n"
" folding over visited nodes with metadata.\n"
"\n"
" Unlike `fold_walk`, this does not require a materialised `Graph` value.\n"
" Instead, you supply a `successors_of` function that computes neighbours\n"
" on the fly — ideal for infinite grids, state-space search, or any\n"
" graph that is too large or expensive to build upfront.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // BFS shortest path in an implicit maze\n"
" traversal.implicit_fold(\n"
" from: #(1, 1),\n"
" using: BreadthFirst,\n"
" initial: -1,\n"
" successors_of: fn(pos) { open_neighbours(pos, fav) },\n"
" with: fn(acc, pos, meta) {\n"
" case pos == target {\n"
" True -> #(Halt, meta.depth)\n"
" False -> #(Continue, acc)\n"
" }\n"
" },\n"
" )\n"
" ```\n"
).
-spec implicit_fold(
HQW,
order(),
HQX,
fun((HQW) -> list(HQW)),
fun((HQX, HQW, walk_metadata(HQW)) -> {walk_control(), HQX})
) -> HQX.
implicit_fold(Start, Order, Acc, Successors, Folder) ->
Start_meta = {walk_metadata, 0, none},
case Order of
breadth_first ->
do_implicit_bfs(
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, {Start, Start_meta})
end,
gleam@set:new(),
Acc,
Successors,
Folder
);
depth_first ->
do_implicit_dfs(
[{Start, Start_meta}],
gleam@set:new(),
Acc,
Successors,
Folder
)
end.
-file("src/yog/traversal.gleam", 640).
-spec do_implicit_bfs_by(
yog@internal@queue:queue({HSL, walk_metadata(HSL)}),
gleam@set:set(HSO),
HSQ,
fun((HSL) -> list(HSL)),
fun((HSL) -> HSO),
fun((HSQ, HSL, walk_metadata(HSL)) -> {walk_control(), HSQ})
) -> HSQ.
do_implicit_bfs_by(Q, Visited, Acc, Successors, Key_fn, Folder) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
Acc;
{ok, {{Node_id, Metadata}, Rest}} ->
Node_key = Key_fn(Node_id),
case gleam@set:contains(Visited, Node_key) of
true ->
do_implicit_bfs_by(
Rest,
Visited,
Acc,
Successors,
Key_fn,
Folder
);
false ->
{Control, New_acc} = Folder(Acc, Node_id, Metadata),
New_visited = gleam@set:insert(Visited, Node_key),
case Control of
halt ->
New_acc;
stop ->
do_implicit_bfs_by(
Rest,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
);
continue ->
Next_queue = gleam@list:fold(
Successors(Node_id),
Rest,
fun(Q2, Next_id) ->
yog@internal@queue:push(
Q2,
{Next_id,
{walk_metadata,
erlang:element(2, Metadata) + 1,
{some, Node_id}}}
)
end
),
do_implicit_bfs_by(
Next_queue,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 698).
-spec do_implicit_dfs_by(
list({HST, walk_metadata(HST)}),
gleam@set:set(HSW),
HSY,
fun((HST) -> list(HST)),
fun((HST) -> HSW),
fun((HSY, HST, walk_metadata(HST)) -> {walk_control(), HSY})
) -> HSY.
do_implicit_dfs_by(Stack, Visited, Acc, Successors, Key_fn, Folder) ->
case Stack of
[] ->
Acc;
[{Node_id, Metadata} | Tail] ->
Node_key = Key_fn(Node_id),
case gleam@set:contains(Visited, Node_key) of
true ->
do_implicit_dfs_by(
Tail,
Visited,
Acc,
Successors,
Key_fn,
Folder
);
false ->
{Control, New_acc} = Folder(Acc, Node_id, Metadata),
New_visited = gleam@set:insert(Visited, Node_key),
case Control of
halt ->
New_acc;
stop ->
do_implicit_dfs_by(
Tail,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
);
continue ->
Next_stack = gleam@list:fold_right(
Successors(Node_id),
Tail,
fun(Stk, Next_id) ->
[{Next_id,
{walk_metadata,
erlang:element(2, Metadata) + 1,
{some, Node_id}}} |
Stk]
end
),
do_implicit_dfs_by(
Next_stack,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 431).
?DOC(
" Like `implicit_fold`, but deduplicates visited nodes by a custom key.\n"
"\n"
" This is essential when your node type carries extra state beyond what\n"
" defines \"identity\". For example, in state-space search you might have\n"
" `#(Position, Mask)` nodes, but only want to visit each `Position` once —\n"
" the `Mask` is just carried state, not part of the identity.\n"
"\n"
" The `visited_by` function extracts the deduplication key from each node.\n"
" Internally, a `Set(key)` tracks which keys have been visited, but the\n"
" full `nid` value (with all its state) is still passed to your folder.\n"
"\n"
" **Time Complexity:** O(V + E) for both BFS and DFS, where V and E are\n"
" measured in terms of unique *keys* (not unique nodes).\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Search a maze where nodes carry both position and step count\n"
" // but we only want to visit each position once (first-visit wins)\n"
" type State {\n"
" State(pos: #(Int, Int), steps: Int)\n"
" }\n"
"\n"
" traversal.implicit_fold_by(\n"
" from: State(#(0, 0), 0),\n"
" using: BreadthFirst,\n"
" initial: None,\n"
" successors_of: fn(state) {\n"
" neighbors(state.pos)\n"
" |> list.map(fn(next_pos) {\n"
" State(next_pos, state.steps + 1)\n"
" })\n"
" },\n"
" visited_by: fn(state) { state.pos }, // Dedupe by position only\n"
" with: fn(acc, state, _meta) {\n"
" case state.pos == target {\n"
" True -> #(Halt, Some(state.steps))\n"
" False -> #(Continue, acc)\n"
" }\n"
" },\n"
" )\n"
" ```\n"
"\n"
" ## Use Cases\n"
"\n"
" - **Puzzle solving**: `#(board_state, moves)` → dedupe by `board_state`\n"
" - **Path finding with budget**: `#(pos, fuel_left)` → dedupe by `pos`\n"
" - **Game state search**: `#(position, inventory)` → dedupe by `position`\n"
" - **Graph search with metadata**: `#(node_id, path_history)` → dedupe by `node_id`\n"
"\n"
" ## Comparison to `implicit_fold`\n"
"\n"
" - `implicit_fold`: Deduplicates by the entire node value `nid`\n"
" - `implicit_fold_by`: Deduplicates by `visited_by(nid)` but keeps full `nid`\n"
"\n"
" Similar to SQL's `DISTINCT ON(key)` or Python's `key=` parameter.\n"
).
-spec implicit_fold_by(
HRA,
order(),
HRB,
fun((HRA) -> list(HRA)),
fun((HRA) -> any()),
fun((HRB, HRA, walk_metadata(HRA)) -> {walk_control(), HRB})
) -> HRB.
implicit_fold_by(Start, Order, Acc, Successors, Key_fn, Folder) ->
Start_meta = {walk_metadata, 0, none},
case Order of
breadth_first ->
do_implicit_bfs_by(
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, {Start, Start_meta})
end,
gleam@set:new(),
Acc,
Successors,
Key_fn,
Folder
);
depth_first ->
do_implicit_dfs_by(
[{Start, Start_meta}],
gleam@set:new(),
Acc,
Successors,
Key_fn,
Folder
)
end.
-file("src/yog/traversal.gleam", 807).
-spec do_implicit_dijkstra(
gleamy@pairing_heap:heap({integer(), HTE}),
gleam@dict:dict(HTE, integer()),
HTI,
fun((HTE) -> list({HTE, integer()})),
fun((HTI, HTE, integer()) -> {walk_control(), HTI})
) -> HTI.
do_implicit_dijkstra(Frontier, Best, Acc, Successors, Folder) ->
case gleamy@priority_queue:pop(Frontier) of
{error, nil} ->
Acc;
{ok, {{Cost, Node}, Rest}} ->
case gleam_stdlib:map_get(Best, Node) of
{ok, Prev} when Prev < Cost ->
do_implicit_dijkstra(Rest, Best, Acc, Successors, Folder);
_ ->
New_best = gleam@dict:insert(Best, Node, Cost),
{Control, New_acc} = Folder(Acc, Node, Cost),
case Control of
halt ->
New_acc;
stop ->
do_implicit_dijkstra(
Rest,
New_best,
New_acc,
Successors,
Folder
);
continue ->
Next_frontier = gleam@list:fold(
Successors(Node),
Rest,
fun(Q, Neighbor) ->
{Nb_node, Edge_cost} = Neighbor,
New_cost = Cost + Edge_cost,
case gleam_stdlib:map_get(New_best, Nb_node) of
{ok, Prev_cost} when Prev_cost =< New_cost ->
Q;
_ ->
gleamy@priority_queue:push(
Q,
{New_cost, Nb_node}
)
end
end
),
do_implicit_dijkstra(
Next_frontier,
New_best,
New_acc,
Successors,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 793).
?DOC(
" Traverses an *implicit* weighted graph using Dijkstra's algorithm,\n"
" folding over visited nodes in order of increasing cost.\n"
"\n"
" Like `implicit_fold` but uses a priority queue so nodes are visited\n"
" cheapest-first. Ideal for shortest-path problems on implicit state spaces\n"
" where edge costs vary — e.g., state-space search with Manhattan moves, or\n"
" multi-robot coordination where multiple robots share a key-bitmask state.\n"
"\n"
" - `successors_of`: Given a node, return `List(#(neighbor, edge_cost))`.\n"
" Include only valid transitions (filtering here avoids dead states).\n"
" - `folder`: Called once per node, with `(acc, node, cost_so_far)`.\n"
" Return `#(Halt, result)` to stop immediately, `#(Stop, acc)` to skip\n"
" expanding this node's successors, or `#(Continue, acc)` to continue.\n"
"\n"
" Internally maintains a `Dict(nid, Int)` of best-known costs;\n"
" stale priority-queue entries are automatically skipped.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Shortest path in an implicit maze with uniform cost\n"
" traversal.implicit_dijkstra(\n"
" from: start,\n"
" initial: -1,\n"
" successors_of: fn(pos) {\n"
" neighbours(pos)\n"
" |> list.map(fn(nb) { #(nb, 1) }) // uniform cost\n"
" },\n"
" with: fn(acc, pos, cost) {\n"
" case pos == target {\n"
" True -> #(Halt, cost)\n"
" False -> #(Continue, acc)\n"
" }\n"
" },\n"
" )\n"
" ```\n"
).
-spec implicit_dijkstra(
HTB,
HTC,
fun((HTB) -> list({HTB, integer()})),
fun((HTC, HTB, integer()) -> {walk_control(), HTC})
) -> HTC.
implicit_dijkstra(Start, Acc, Successors, Folder) ->
Frontier = begin
_pipe = gleamy@priority_queue:new(
fun(A, B) ->
gleam@int:compare(erlang:element(1, A), erlang:element(1, B))
end
),
gleamy@priority_queue:push(_pipe, {0, Start})
end,
do_implicit_dijkstra(Frontier, maps:new(), Acc, Successors, Folder).
-file("src/yog/traversal.gleam", 949).
-spec do_lexical_kahn(
yog@model:graph(any(), any()),
gleamy@pairing_heap:heap(integer()),
gleam@dict:dict(integer(), integer()),
list(integer()),
integer()
) -> {ok, list(integer())} | {error, nil}.
do_lexical_kahn(Graph, Q, In_degrees, Acc, Total_count) ->
case gleamy@priority_queue:pop(Q) of
{error, nil} ->
case erlang:length(Acc) =:= Total_count of
true ->
{ok, lists:reverse(Acc)};
false ->
{error, nil}
end;
{ok, {Head, Rest_q}} ->
Neighbors = yog@model:successor_ids(Graph, Head),
{Next_q, Next_in_degrees} = gleam@list:fold(
Neighbors,
{Rest_q, In_degrees},
fun(State, Neighbor) ->
{Current_q, Degrees} = State,
Current_degree = begin
_pipe = gleam_stdlib:map_get(Degrees, Neighbor),
gleam@result:unwrap(_pipe, 0)
end,
New_degree = Current_degree - 1,
New_degrees = gleam@dict:insert(
Degrees,
Neighbor,
New_degree
),
Updated_q = case New_degree =:= 0 of
true ->
gleamy@priority_queue:push(Current_q, Neighbor);
false ->
Current_q
end,
{Updated_q, New_degrees}
end
),
do_lexical_kahn(
Graph,
Next_q,
Next_in_degrees,
[Head | Acc],
Total_count
)
end.
-file("src/yog/traversal.gleam", 914).
?DOC(
" Performs a topological sort that returns the lexicographically smallest sequence.\n"
"\n"
" Uses a heap-based version of Kahn's algorithm to ensure that when multiple\n"
" nodes have in-degree 0, the smallest one (according to `compare_nodes`) is chosen first.\n"
"\n"
" The comparison function operates on **node data**, not node IDs, allowing intuitive\n"
" comparisons like `string.compare` for alphabetical ordering.\n"
"\n"
" Returns `Error(Nil)` if the graph contains a cycle.\n"
"\n"
" **Time Complexity:** O(V log V + E) due to heap operations\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Get alphabetical ordering by node data\n"
" traversal.lexicographical_topological_sort(graph, string.compare)\n"
" // => Ok([0, 1, 2]) // Node IDs ordered by their string data\n"
"\n"
" // Custom comparison by priority\n"
" traversal.lexicographical_topological_sort(graph, fn(a, b) {\n"
" int.compare(a.priority, b.priority)\n"
" })\n"
" ```\n"
).
-spec lexicographical_topological_sort(
yog@model:graph(HTR, any()),
fun((HTR, HTR) -> gleam@order:order())
) -> {ok, list(integer())} | {error, nil}.
lexicographical_topological_sort(Graph, Compare_nodes) ->
All_nodes = yog@model:all_nodes(Graph),
In_degrees = begin
_pipe = All_nodes,
_pipe@3 = gleam@list:map(
_pipe,
fun(Id) ->
Degree = begin
_pipe@1 = gleam_stdlib:map_get(erlang:element(5, Graph), Id),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:size/1),
gleam@result:unwrap(_pipe@2, 0)
end,
{Id, Degree}
end
),
maps:from_list(_pipe@3)
end,
Compare_by_data = fun(Id_a, Id_b) ->
case {gleam_stdlib:map_get(erlang:element(3, Graph), Id_a),
gleam_stdlib:map_get(erlang:element(3, Graph), Id_b)} of
{{ok, Data_a}, {ok, Data_b}} ->
Compare_nodes(Data_a, Data_b);
{_, _} ->
eq
end
end,
Initial_queue = begin
_pipe@4 = maps:to_list(In_degrees),
_pipe@5 = gleam@list:filter(
_pipe@4,
fun(Pair) -> erlang:element(2, Pair) =:= 0 end
),
_pipe@6 = gleam@list:map(
_pipe@5,
fun(Pair@1) -> erlang:element(1, Pair@1) end
),
gleam@list:fold(
_pipe@6,
gleamy@priority_queue:new(Compare_by_data),
fun(Q, Id@1) -> gleamy@priority_queue:push(Q, Id@1) end
)
end,
do_lexical_kahn(
Graph,
Initial_queue,
In_degrees,
[],
erlang:length(All_nodes)
).
-file("src/yog/traversal.gleam", 985).
-spec do_kahn(
yog@model:graph(any(), any()),
list(integer()),
gleam@dict:dict(integer(), integer()),
list(integer()),
integer()
) -> {ok, list(integer())} | {error, nil}.
do_kahn(Graph, Queue, In_degrees, Acc, Total_node_count) ->
case Queue of
[] ->
case erlang:length(Acc) =:= Total_node_count of
true ->
{ok, lists:reverse(Acc)};
false ->
{error, nil}
end;
[Head | Tail] ->
Neighbors = yog@model:successor_ids(Graph, Head),
{Next_queue, Next_in_degrees} = gleam@list:fold(
Neighbors,
{Tail, In_degrees},
fun(State, Neighbor) ->
{Q, Degrees} = State,
Current_degree = begin
_pipe = gleam_stdlib:map_get(Degrees, Neighbor),
gleam@result:unwrap(_pipe, 0)
end,
New_degree = Current_degree - 1,
New_degrees = gleam@dict:insert(
Degrees,
Neighbor,
New_degree
),
New_q = case New_degree =:= 0 of
true ->
[Neighbor | Q];
false ->
Q
end,
{New_q, New_degrees}
end
),
do_kahn(
Graph,
Next_queue,
Next_in_degrees,
[Head | Acc],
Total_node_count
)
end.
-file("src/yog/traversal.gleam", 868).
?DOC(
" Performs a topological sort on a directed graph using Kahn's algorithm.\n"
"\n"
" Returns a linear ordering of nodes such that for every directed edge (u, v),\n"
" node u comes before node v in the ordering.\n"
"\n"
" Returns `Error(Nil)` if the graph contains a cycle.\n"
"\n"
" **Time Complexity:** O(V + E) where V is vertices and E is edges\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" traversal.topological_sort(graph)\n"
" // => Ok([1, 2, 3, 4]) // Valid ordering\n"
" // or Error(Nil) // Cycle detected\n"
" ```\n"
).
-spec topological_sort(yog@model:graph(any(), any())) -> {ok, list(integer())} |
{error, nil}.
topological_sort(Graph) ->
All_nodes = yog@model:all_nodes(Graph),
In_degrees = begin
_pipe = All_nodes,
_pipe@3 = gleam@list:map(
_pipe,
fun(Id) ->
Degree = begin
_pipe@1 = gleam_stdlib:map_get(erlang:element(5, Graph), Id),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:size/1),
gleam@result:unwrap(_pipe@2, 0)
end,
{Id, Degree}
end
),
maps:from_list(_pipe@3)
end,
Queue = begin
_pipe@4 = maps:to_list(In_degrees),
_pipe@5 = gleam@list:filter(
_pipe@4,
fun(Pair) -> erlang:element(2, Pair) =:= 0 end
),
gleam@list:map(_pipe@5, fun(Pair@1) -> erlang:element(1, Pair@1) end)
end,
do_kahn(Graph, Queue, In_degrees, [], erlang:length(All_nodes)).
-file("src/yog/traversal.gleam", 55).
?DOC(
" Determines if a graph contains any cycles.\n"
"\n"
" For directed graphs, a cycle exists if there is a path from a node back to itself\n"
" (evaluated efficiently via Kahn's algorithm).\n"
" For undirected graphs, a cycle exists if there is a path of length >= 3 from a node back to itself,\n"
" or a self-loop.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" traversal.is_cyclic(graph)\n"
" // => True // Cycle detected\n"
" ```\n"
).
-spec is_cyclic(yog@model:graph(any(), any())) -> boolean().
is_cyclic(Graph) ->
case erlang:element(2, Graph) of
directed ->
gleam@result:is_error(topological_sort(Graph));
undirected ->
do_has_undirected_cycle(
Graph,
yog@model:all_nodes(Graph),
gleam@set:new()
)
end.
-file("src/yog/traversal.gleam", 76).
?DOC(
" Determines if a graph is acyclic (contains no cycles).\n"
"\n"
" This is the logical opposite of `is_cyclic`. For directed graphs, returning\n"
" `True` means the graph is a Directed Acyclic Graph (DAG).\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" traversal.is_acyclic(graph)\n"
" // => True // Valid DAG or undirected forest\n"
" ```\n"
).
-spec is_acyclic(yog@model:graph(any(), any())) -> boolean().
is_acyclic(Graph) ->
not is_cyclic(Graph).