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([random_walk/4, best_first_fold/5, best_first_walk/3, implicit_fold_by/6, fold_walk/5, walk/3, walk_until/4, implicit_fold/5, topological_sort/1, lexicographical_topological_sort/2]).
-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.
?MODULEDOC(
" Graph traversal algorithms - systematic exploration of graph structure.\n"
"\n"
" This module provides fundamental graph traversal algorithms for visiting nodes\n"
" in a specific order. Traversals are the foundation for most graph algorithms\n"
" including pathfinding, connectivity analysis, and cycle detection.\n"
"\n"
" ## Traversal Orders\n"
"\n"
" | Order | Strategy | Best For |\n"
" |-------|----------|----------|\n"
" | [BFS](https://en.wikipedia.org/wiki/Breadth-first_search) | Level-by-level | Shortest path (unweighted), finding neighbors |\n"
" | [DFS](https://en.wikipedia.org/wiki/Depth-first_search) | Deep exploration | Cycle detection, topological sort, connectivity |\n"
"\n"
" ## Core Functions\n"
"\n"
" | Function | Description |\n"
" |----------|-------------|\n"
" | `walk/3` | Simple traversal returning visited nodes in order |\n"
" | `walk_until/4` | Traversal until a predicate is satisfied |\n"
" | `fold_walk/5` | Generic traversal with custom fold and `WalkControl` |\n"
" | `implicit_fold/6` | `fold_walk` for implicit graphs (no materialised `Graph`) |\n"
" | `implicit_fold_by/7` | `implicit_fold` with custom visited-key function |\n"
" | `best_first_walk/3` | Greedy Best-First Search traversal |\n"
" | `best_first_fold/5` | Greedy Best-First Search with fold control |\n"
" | `random_walk/4` | Stochastic traversal for simulation |\n"
" | `topological_sort/1` | Ordering for DAGs (uses DFS internally) |\n"
" | `lexicographical_topological_sort/2` | Ordering with custom priority |\n"
"\n"
" ## Walk Control\n"
"\n"
" The `fold_walk` and `best_first_fold` functions provide fine-grained control:\n"
" - `Continue`: Explore this node's neighbors normally\n"
" - `Stop`: Skip this node's neighbors but continue traversal\n"
" - `Halt`: Stop the entire traversal immediately and return the accumulator\n"
"\n"
" ## Time Complexity\n"
"\n"
" All traversals run in **O(V + E)** linear time, visiting each node and edge\n"
" at most once.\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Graph Traversal](https://en.wikipedia.org/wiki/Graph_traversal)\n"
" - [CP-Algorithms: DFS/BFS](https://cp-algorithms.com/graph/breadth-first-search.html)\n"
" - [Wikipedia: Topological Sorting](https://en.wikipedia.org/wiki/Topological_sorting)\n"
).
-type order() :: breadth_first | depth_first.
-type walk_control() :: continue | stop | halt.
-type walk_metadata(FRU) :: {walk_metadata, integer(), gleam@option:option(FRU)}.
-file("src/yog/traversal.gleam", 182).
-spec do_random_walk(
yog@model:graph(any(), any()),
integer(),
integer(),
yog@internal@random:rng(),
list(integer())
) -> list(integer()).
do_random_walk(Graph, Current, Remaining, Rng, Acc) ->
case Remaining =< 0 of
true ->
Acc;
false ->
Neighbors = yog@model:successor_ids(Graph, Current),
case Neighbors of
[] ->
Acc;
_ ->
N = erlang:length(Neighbors),
{Idx, Next_rng} = yog@internal@random:next_int(Rng, N),
Next@1 = case begin
_pipe = gleam@list:drop(Neighbors, Idx),
gleam@list:first(_pipe)
end of
{ok, Next} -> Next;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/traversal"/utf8>>,
function => <<"do_random_walk"/utf8>>,
line => 192,
value => _assert_fail,
start => 6246,
'end' => 6331,
pattern_start => 6257,
pattern_end => 6265})
end,
do_random_walk(
Graph,
Next@1,
Remaining - 1,
Next_rng,
[Next@1 | Acc]
)
end
end.
-file("src/yog/traversal.gleam", 171).
?DOC(
" Simulates a random walk on the graph for a specified number of steps.\n"
"\n"
" At each step, one of the current node's neighbors is chosen uniformly\n"
" at random. Returns the sequence of node IDs visited.\n"
"\n"
" ## Parameters\n"
"\n"
" - `steps`: Maximum number of steps to take.\n"
" - `seed`: Optional seed for reproducibility.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" traversal.random_walk(graph, from: 1, steps: 10, seed: Some(42))\n"
" // => [1, 2, 5, 2, 3, 1, ...]\n"
" ```\n"
).
-spec random_walk(
yog@model:graph(any(), any()),
integer(),
integer(),
gleam@option:option(integer())
) -> list(integer()).
random_walk(Graph, Start_id, Limit, Seed) ->
Rng = yog@internal@random:new(Seed),
_pipe = do_random_walk(Graph, Start_id, Limit, Rng, [Start_id]),
lists:reverse(_pipe).
-file("src/yog/traversal.gleam", 261).
-spec do_best_first_fold(
yog@model:graph(any(), any()),
yog@internal@pairing_heap:heap({FXE, integer()}),
gleam@set:set(integer()),
FTH,
fun((integer()) -> FXE),
fun((FTH, integer()) -> {walk_control(), FTH})
) -> FTH.
do_best_first_fold(Graph, Q, Visited, Acc, Score_of, Folder) ->
case yog@internal@priority_queue:pop(Q) of
{error, nil} ->
Acc;
{ok, {{_, Node}, Rest}} ->
case gleam@set:contains(Visited, Node) of
true ->
do_best_first_fold(
Graph,
Rest,
Visited,
Acc,
Score_of,
Folder
);
false ->
{Control, New_acc} = Folder(Acc, Node),
New_visited = gleam@set:insert(Visited, Node),
case Control of
halt ->
New_acc;
stop ->
do_best_first_fold(
Graph,
Rest,
New_visited,
New_acc,
Score_of,
Folder
);
continue ->
Next_q = gleam@list:fold(
yog@model:successor_ids(Graph, Node),
Rest,
fun(Q_acc, Nb) ->
case gleam@set:contains(New_visited, Nb) of
true ->
Q_acc;
false ->
yog@internal@priority_queue:push(
Q_acc,
{Score_of(Nb), Nb}
)
end
end
),
do_best_first_fold(
Graph,
Next_q,
New_visited,
New_acc,
Score_of,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 245).
?DOC(
" Folds over nodes in Best-First order using a priority queue.\n"
"\n"
" Nodes are explored according to the score returned by `score_of` (cheapest first).\n"
" This is a Greedy Best-First Search — if you need cumulative edge costs,\n"
" use `dijkstra.fold` instead.\n"
).
-spec best_first_fold(
yog@model:graph(any(), any()),
integer(),
FTA,
fun((integer()) -> integer()),
fun((FTA, integer()) -> {walk_control(), FTA})
) -> FTA.
best_first_fold(Graph, Start, Acc, Score_of, Folder) ->
Q = begin
_pipe = yog@internal@priority_queue:new(
fun(A, B) ->
gleam@int:compare(erlang:element(1, A), erlang:element(1, B))
end
),
yog@internal@priority_queue:push(_pipe, {Score_of(Start), Start})
end,
do_best_first_fold(Graph, Q, gleam@set:new(), Acc, Score_of, Folder).
-file("src/yog/traversal.gleam", 140).
?DOC(
" Performs a Greedy Best-First Walk starting from the given node.\n"
"\n"
" Visits nodes in order of their score as determined by `score_of`.\n"
" Lower scores are visited first. Unlike Dijkstra, scores are not cumulative.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" traversal.best_first_walk(\n"
" graph,\n"
" from: 1,\n"
" scored_by: fn(node_id) { get_priority(node_id) }\n"
" )\n"
" ```\n"
).
-spec best_first_walk(
yog@model:graph(any(), any()),
integer(),
fun((integer()) -> integer())
) -> list(integer()).
best_first_walk(Graph, Start_id, Score_of) ->
_pipe = best_first_fold(
Graph,
Start_id,
[],
Score_of,
fun(Acc, Node_id) -> {continue, [Node_id | Acc]} end
),
lists:reverse(_pipe).
-file("src/yog/traversal.gleam", 462).
-spec do_walk_bfs(
yog@internal@queue:queue({FTX, walk_metadata(FTX)}),
gleam@set:set(FUA),
FUC,
fun((FTX) -> list(FTX)),
fun((FTX) -> FUA),
fun((FUC, FTX, walk_metadata(FTX)) -> {walk_control(), FUC})
) -> FUC.
do_walk_bfs(Q, Visited, Acc, Successors, Key_fn, Folder) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
Acc;
{ok, {{Node, Meta}, Rest}} ->
Key = Key_fn(Node),
case gleam@set:contains(Visited, Key) of
true ->
do_walk_bfs(Rest, Visited, Acc, Successors, Key_fn, Folder);
false ->
{Control, New_acc} = Folder(Acc, Node, Meta),
New_visited = gleam@set:insert(Visited, Key),
case Control of
halt ->
New_acc;
stop ->
do_walk_bfs(
Rest,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
);
continue ->
Next_meta = fun(_) ->
{walk_metadata,
erlang:element(2, Meta) + 1,
{some, Node}}
end,
Q@2 = gleam@list:fold(
Successors(Node),
Rest,
fun(Q@1, N) ->
yog@internal@queue:push(
Q@1,
{N, Next_meta(N)}
)
end
),
do_walk_bfs(
Q@2,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 507).
-spec do_walk_dfs(
list({FUF, walk_metadata(FUF)}),
gleam@set:set(FUI),
FUK,
fun((FUF) -> list(FUF)),
fun((FUF) -> FUI),
fun((FUK, FUF, walk_metadata(FUF)) -> {walk_control(), FUK})
) -> FUK.
do_walk_dfs(Stack, Visited, Acc, Successors, Key_fn, Folder) ->
case Stack of
[] ->
Acc;
[{Node, Meta} | Tail] ->
Key = Key_fn(Node),
case gleam@set:contains(Visited, Key) of
true ->
do_walk_dfs(Tail, Visited, Acc, Successors, Key_fn, Folder);
false ->
{Control, New_acc} = Folder(Acc, Node, Meta),
New_visited = gleam@set:insert(Visited, Key),
case Control of
halt ->
New_acc;
stop ->
do_walk_dfs(
Tail,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
);
continue ->
Next_meta = fun(_) ->
{walk_metadata,
erlang:element(2, Meta) + 1,
{some, Node}}
end,
Stack@1 = gleam@list:fold_right(
Successors(Node),
Tail,
fun(S, N) -> [{N, Next_meta(N)} | S] end
),
do_walk_dfs(
Stack@1,
New_visited,
New_acc,
Successors,
Key_fn,
Folder
)
end
end
end.
-file("src/yog/traversal.gleam", 442).
?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"
).
-spec implicit_fold_by(
FTS,
order(),
FTT,
fun((FTS) -> list(FTS)),
fun((FTS) -> any()),
fun((FTT, FTS, walk_metadata(FTS)) -> {walk_control(), FTT})
) -> FTT.
implicit_fold_by(Start, Order, Acc, Successors, Key_fn, Folder) ->
Meta = {walk_metadata, 0, none},
case Order of
breadth_first ->
Q = begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, {Start, Meta})
end,
do_walk_bfs(Q, gleam@set:new(), Acc, Successors, Key_fn, Folder);
depth_first ->
do_walk_dfs(
[{Start, Meta}],
gleam@set:new(),
Acc,
Successors,
Key_fn,
Folder
)
end.
-file("src/yog/traversal.gleam", 342).
?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"
).
-spec fold_walk(
yog@model:graph(any(), any()),
integer(),
order(),
FTM,
fun((FTM, integer(), walk_metadata(integer())) -> {walk_control(), FTM})
) -> FTM.
fold_walk(Graph, Start, Order, Acc, Folder) ->
implicit_fold_by(
Start,
Order,
Acc,
fun(Id) -> yog@model:successor_ids(Graph, Id) end,
fun(Id@1) -> Id@1 end,
Folder
).
-file("src/yog/traversal.gleam", 111).
?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", 218).
?DOC(
" Walks the graph but stops early when a condition is met.\n"
"\n"
" Traverses the graph until `until` 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", 383).
?DOC(
" Traverses an *implicit* graph using BFS or DFS, folding over visited nodes.\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(
FTO,
order(),
FTP,
fun((FTO) -> list(FTO)),
fun((FTP, FTO, walk_metadata(FTO)) -> {walk_control(), FTP})
) -> FTP.
implicit_fold(Start, Order, Acc, Successors, Folder) ->
implicit_fold_by(Start, Order, Acc, Successors, fun(Id) -> Id end, Folder).
-file("src/yog/traversal.gleam", 598).
-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_count) ->
case Queue of
[] ->
case erlang:length(Acc) =:= Total_count of
true ->
{ok, lists:reverse(Acc)};
false ->
{error, nil}
end;
[Head | Tail] ->
{Next_q, Next_degrees} = gleam@list:fold(
yog@model:successor_ids(Graph, Head),
{Tail, In_degrees},
fun(State, Nb) ->
{Q, Degrees} = State,
New_deg = begin
_pipe = gleam_stdlib:map_get(Degrees, Nb),
gleam@result:unwrap(_pipe, 0)
end
- 1,
Q@1 = case New_deg =:= 0 of
true ->
[Nb | Q];
false ->
Q
end,
{Q@1, gleam@dict:insert(Degrees, Nb, New_deg)}
end
),
do_kahn(Graph, Next_q, Next_degrees, [Head | Acc], Total_count)
end.
-file("src/yog/traversal.gleam", 579).
?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@1 = gleam@list:map(
_pipe,
fun(Id) -> {Id, yog@model:in_degree(Graph, Id)} end
),
maps:from_list(_pipe@1)
end,
Queue = begin
_pipe@2 = maps:to_list(In_degrees),
gleam@list:filter_map(_pipe@2, fun(P) -> case erlang:element(2, P) of
0 ->
{ok, erlang:element(1, P)};
_ ->
{error, nil}
end end)
end,
do_kahn(Graph, Queue, In_degrees, [], erlang:length(All_nodes)).
-file("src/yog/traversal.gleam", 673).
-spec do_lexical_kahn(
yog@model:graph(any(), any()),
yog@internal@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 yog@internal@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}} ->
{Next_q, Next_degrees} = gleam@list:fold(
yog@model:successor_ids(Graph, Head),
{Rest, In_degrees},
fun(State, Nb) ->
{Q@1, Degrees} = State,
New_deg = begin
_pipe = gleam_stdlib:map_get(Degrees, Nb),
gleam@result:unwrap(_pipe, 0)
end
- 1,
Q@2 = case New_deg =:= 0 of
true ->
yog@internal@priority_queue:push(Q@1, Nb);
false ->
Q@1
end,
{Q@2, gleam@dict:insert(Degrees, Nb, New_deg)}
end
),
do_lexical_kahn(
Graph,
Next_q,
Next_degrees,
[Head | Acc],
Total_count
)
end.
-file("src/yog/traversal.gleam", 643).
?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"
).
-spec lexicographical_topological_sort(
yog@model:graph(FVA, any()),
fun((FVA, FVA) -> 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@1 = gleam@list:map(
_pipe,
fun(Id) -> {Id, yog@model:in_degree(Graph, Id)} end
),
maps:from_list(_pipe@1)
end,
Compare_by_data = fun(A, B) ->
case {gleam_stdlib:map_get(erlang:element(3, Graph), A),
gleam_stdlib:map_get(erlang:element(3, Graph), B)} of
{{ok, Da}, {ok, Db}} ->
Compare_nodes(Da, Db);
{_, _} ->
eq
end
end,
Q = begin
_pipe@2 = maps:to_list(In_degrees),
_pipe@3 = gleam@list:filter_map(
_pipe@2,
fun(P) -> case erlang:element(2, P) of
0 ->
{ok, erlang:element(1, P)};
_ ->
{error, nil}
end end
),
gleam@list:fold(
_pipe@3,
yog@internal@priority_queue:new(Compare_by_data),
fun yog@internal@priority_queue:push/2
)
end,
do_lexical_kahn(Graph, Q, In_degrees, [], erlang:length(All_nodes)).