Current section
Files
Jump to
Current section
Files
src/yog@pathfinding@unweighted.erl
-module(yog@pathfinding@unweighted).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/unweighted.gleam").
-export([shortest_path/3, single_source_distances/2, all_pairs_shortest_paths/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(
" Unweighted pathfinding algorithms for graphs where all edges have equal weight.\n"
"\n"
" These algorithms use [Breadth-First Search (BFS)](https://en.wikipedia.org/wiki/Breadth-first_search)\n"
" to find paths and distances based on the number of hops between nodes.\n"
"\n"
" | Algorithm | Function | Complexity | Best For |\n"
" |-----------|----------|------------|----------|\n"
" | BFS Path | `shortest_path/3` | O(V + E) | Single-pair unweighted paths |\n"
" | SSAD | `single_source_distances/2` | O(V + E) | Distances from one node to all others |\n"
" | Unweighted APSP | `all_pairs_shortest_paths/1` | O(V(V + E)) | All-pairs distances in sparse graphs |\n"
"\n"
" ## Why Use Unweighted Algorithms?\n"
"\n"
" If your graph doesn't have custom edge weights (or if all weights are identical),\n"
" Dijkstra and Floyd-Warshall are unnecessarily slow due to their use of priority \n"
" queues or O(V³) matrices. BFS-based algorithms are the most efficient way to\n"
" calculate hop-counts.\n"
"\n"
" ## Comparison with Weighted Algorithms\n"
"\n"
" | Feature | Unweighted (BFS) | Weighted (Dijkstra) |\n"
" |---------|------------------|---------------------|\n"
" | point-to-point | O(V + E) | O((V+E) log V) |\n"
" | SS/APSP | O(V(V + E)) | O(V² log V + VE) |\n"
" | Overhead | Low (simple queue) | Higher (priority queue) |\n"
"\n"
).
-file("src/yog/pathfinding/unweighted.gleam", 60).
-spec do_shortest_path(
yog@model:graph(any(), any()),
integer(),
yog@internal@queue:queue({integer(), list(integer())}),
gleam@dict:dict(integer(), integer())
) -> gleam@option:option(yog@pathfinding@path:path(integer())).
do_shortest_path(Graph, Goal, Q, Visited) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
none;
{ok, {{Current, Path}, Rest_q}} ->
case Current =:= Goal of
true ->
{some, {path, lists:reverse(Path), erlang:length(Path) - 1}};
false ->
Neighbors = yog@model:successor_ids(Graph, Current),
{Next_q, Next_visited} = gleam@list:fold(
Neighbors,
{Rest_q, Visited},
fun(Acc, Neighbor) ->
{Q_acc, V_acc} = Acc,
case gleam@dict:has_key(V_acc, Neighbor) of
true ->
Acc;
false ->
Dist = begin
_pipe = gleam_stdlib:map_get(
V_acc,
Current
),
_pipe@1 = gleam@option:from_result(
_pipe
),
gleam@option:unwrap(_pipe@1, 0)
end,
{yog@internal@queue:push(
Q_acc,
{Neighbor, [Neighbor | Path]}
),
gleam@dict:insert(
V_acc,
Neighbor,
Dist + 1
)}
end
end
),
do_shortest_path(Graph, Goal, Next_q, Next_visited)
end
end.
-file("src/yog/pathfinding/unweighted.gleam", 45).
?DOC(
" Finds the shortest path (minimum hops) between two nodes in an unweighted graph.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" unweighted.shortest_path(graph, from: 1, to: 5)\n"
" // => Some(Path([1, 2, 5], 2))\n"
" ```\n"
).
-spec shortest_path(yog@model:graph(any(), any()), integer(), integer()) -> gleam@option:option(yog@pathfinding@path:path(integer())).
shortest_path(Graph, Start, Goal) ->
case Start =:= Goal of
true ->
{some, {path, [Start], 0}};
false ->
Q = begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, {Start, [Start]})
end,
Visited = begin
_pipe@1 = maps:new(),
gleam@dict:insert(_pipe@1, Start, 0)
end,
do_shortest_path(Graph, Goal, Q, Visited)
end.
-file("src/yog/pathfinding/unweighted.gleam", 120).
-spec do_single_source(
yog@model:graph(any(), any()),
yog@internal@queue:queue(integer()),
gleam@dict:dict(integer(), integer())
) -> gleam@dict:dict(integer(), integer()).
do_single_source(Graph, Q, Distances) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
Distances;
{ok, {Current, Rest_q}} ->
Current_dist = begin
_pipe = gleam_stdlib:map_get(Distances, Current),
_pipe@1 = gleam@option:from_result(_pipe),
gleam@option:unwrap(_pipe@1, 0)
end,
Neighbors = yog@model:successor_ids(Graph, Current),
{Next_q, Next_distances} = gleam@list:fold(
Neighbors,
{Rest_q, Distances},
fun(Acc, Neighbor) ->
{Q_acc, D_acc} = Acc,
case gleam@dict:has_key(D_acc, Neighbor) of
true ->
Acc;
false ->
{yog@internal@queue:push(Q_acc, Neighbor),
gleam@dict:insert(
D_acc,
Neighbor,
Current_dist + 1
)}
end
end
),
do_single_source(Graph, Next_q, Next_distances)
end.
-file("src/yog/pathfinding/unweighted.gleam", 111).
?DOC(
" Computes the shortest distance (in hops) from a source node to all reachable nodes.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" unweighted.single_source_distances(graph, source: 1)\n"
" // => Dict([#(1, 0), #(2, 1), #(5, 2)])\n"
" ```\n"
).
-spec single_source_distances(yog@model:graph(any(), any()), integer()) -> gleam@dict:dict(integer(), integer()).
single_source_distances(Graph, Start) ->
Q = begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, Start)
end,
Visited = maps:from_list([{Start, 0}]),
do_single_source(Graph, Q, Visited).
-file("src/yog/pathfinding/unweighted.gleam", 155).
?DOC(
" Computes hop-count distances between all pairs of nodes in an unweighted graph.\n"
"\n"
" This implementation runs a BFS from every node, which is much more efficient than\n"
" Floyd-Warshall for sparse unweighted graphs.\n"
"\n"
" **Time Complexity:** O(V(V + E))\n"
).
-spec all_pairs_shortest_paths(yog@model:graph(any(), any())) -> gleam@dict:dict({integer(),
integer()}, integer()).
all_pairs_shortest_paths(Graph) ->
Nodes = maps:keys(erlang:element(3, Graph)),
gleam@list:fold(
Nodes,
maps:new(),
fun(Acc, Source) ->
Distances = single_source_distances(Graph, Source),
gleam@dict:fold(
Distances,
Acc,
fun(Apsp_acc, Target, Dist) ->
gleam@dict:insert(Apsp_acc, {Source, Target}, Dist)
end
)
end
).