Current section
Files
Jump to
Current section
Files
src/yog@pathfinding@floyd_warshall.erl
-module(yog@pathfinding@floyd_warshall).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/floyd_warshall.gleam").
-export([detect_negative_cycle/4, floyd_warshall/4, floyd_warshall_int/1, floyd_warshall_float/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(" Floyd-Warshall algorithm for all-pairs shortest paths.\n").
-file("src/yog/pathfinding/floyd_warshall.gleam", 96).
?DOC(" Detects if there's a negative cycle by checking if any node has negative distance to itself\n").
-spec detect_negative_cycle(
gleam@dict:dict({integer(), integer()}, OKI),
list(integer()),
OKI,
fun((OKI, OKI) -> gleam@order:order())
) -> boolean().
detect_negative_cycle(Distances, Nodes, Zero, Compare) ->
_pipe = Nodes,
gleam@list:any(
_pipe,
fun(I) -> case gleam_stdlib:map_get(Distances, {I, I}) of
{ok, Dist} ->
case Compare(Dist, Zero) of
lt ->
true;
_ ->
false
end;
{error, nil} ->
false
end end
).
-file("src/yog/pathfinding/floyd_warshall.gleam", 15).
?DOC(
" Computes shortest paths between all pairs of nodes using Floyd-Warshall.\n"
"\n"
" **Time Complexity:** O(V³)\n"
"\n"
" Returns an error if a negative cycle is detected.\n"
).
-spec floyd_warshall(
yog@model:graph(any(), OKB),
OKB,
fun((OKB, OKB) -> OKB),
fun((OKB, OKB) -> gleam@order:order())
) -> {ok, gleam@dict:dict({integer(), integer()}, OKB)} | {error, nil}.
floyd_warshall(Graph, Zero, Add, Compare) ->
Nodes = maps:keys(erlang:element(3, Graph)),
Initial_distances = begin
_pipe = Nodes,
gleam@list:fold(_pipe, maps:new(), fun(Distances, I) -> _pipe@1 = Nodes,
gleam@list:fold(
_pipe@1,
Distances,
fun(Distances@1, J) -> case I =:= J of
true ->
case gleam_stdlib:map_get(
erlang:element(4, Graph),
I
) of
{ok, Neighbors} ->
case gleam_stdlib:map_get(Neighbors, J) of
{ok, Weight} ->
case Compare(Weight, Zero) of
lt ->
gleam@dict:insert(
Distances@1,
{I, J},
Weight
);
_ ->
gleam@dict:insert(
Distances@1,
{I, J},
Zero
)
end;
{error, nil} ->
gleam@dict:insert(
Distances@1,
{I, J},
Zero
)
end;
{error, nil} ->
gleam@dict:insert(
Distances@1,
{I, J},
Zero
)
end;
false ->
case gleam_stdlib:map_get(
erlang:element(4, Graph),
I
) of
{ok, Neighbors@1} ->
case gleam_stdlib:map_get(
Neighbors@1,
J
) of
{ok, Weight@1} ->
gleam@dict:insert(
Distances@1,
{I, J},
Weight@1
);
{error, nil} ->
Distances@1
end;
{error, nil} ->
Distances@1
end
end end
) end)
end,
Final_distances = begin
_pipe@2 = Nodes,
gleam@list:fold(
_pipe@2,
Initial_distances,
fun(Distances@2, K) -> _pipe@3 = Nodes,
gleam@list:fold(
_pipe@3,
Distances@2,
fun(Distances@3, I@1) -> _pipe@4 = Nodes,
gleam@list:fold(
_pipe@4,
Distances@3,
fun(Distances@4, J@1) ->
case gleam_stdlib:map_get(Distances@4, {I@1, K}) of
{error, nil} ->
Distances@4;
{ok, Dist_ik} ->
case gleam_stdlib:map_get(
Distances@4,
{K, J@1}
) of
{error, nil} ->
Distances@4;
{ok, Dist_kj} ->
New_dist = Add(Dist_ik, Dist_kj),
case gleam_stdlib:map_get(
Distances@4,
{I@1, J@1}
) of
{error, nil} ->
gleam@dict:insert(
Distances@4,
{I@1, J@1},
New_dist
);
{ok, Current_dist} ->
case Compare(
New_dist,
Current_dist
) of
lt ->
gleam@dict:insert(
Distances@4,
{I@1, J@1},
New_dist
);
_ ->
Distances@4
end
end
end
end
end
) end
) end
)
end,
case detect_negative_cycle(Final_distances, Nodes, Zero, Compare) of
true ->
{error, nil};
false ->
{ok, Final_distances}
end.
-file("src/yog/pathfinding/floyd_warshall.gleam", 138).
?DOC(
" Computes all-pairs shortest paths with **integer weights**.\n"
"\n"
" This is a convenience wrapper around `floyd_warshall` that uses:\n"
" - `0` as the zero element\n"
" - `int.add` for addition\n"
" - `int.compare` for comparison\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let result = floyd_warshall.floyd_warshall_int(graph)\n"
" // => Ok(Dict([#(#(1, 2), 10), #(#(1, 3), 25), ...]))\n"
" ```\n"
"\n"
" ## When to Use\n"
"\n"
" Use this for dense graphs where you need all-pairs distances with `Int`\n"
" weights. For sparse graphs or single-source queries, prefer Dijkstra.\n"
" Returns `Error(Nil)` if a negative cycle is detected.\n"
).
-spec floyd_warshall_int(yog@model:graph(any(), integer())) -> {ok,
gleam@dict:dict({integer(), integer()}, integer())} |
{error, nil}.
floyd_warshall_int(Graph) ->
floyd_warshall(Graph, 0, fun gleam@int:add/2, fun gleam@int:compare/2).
-file("src/yog/pathfinding/floyd_warshall.gleam", 160).
?DOC(
" Computes all-pairs shortest paths with **float weights**.\n"
"\n"
" This is a convenience wrapper around `floyd_warshall` that uses:\n"
" - `0.0` as the zero element\n"
" - `float.add` for addition\n"
" - `float.compare` for comparison\n"
"\n"
" ## Warning\n"
"\n"
" Float arithmetic has precision limitations. Negative cycles might not be\n"
" detected reliably due to floating-point errors.\n"
).
-spec floyd_warshall_float(yog@model:graph(any(), float())) -> {ok,
gleam@dict:dict({integer(), integer()}, float())} |
{error, nil}.
floyd_warshall_float(Graph) ->
floyd_warshall(
Graph,
+0.0,
fun gleam@float:add/2,
fun gleam@float:compare/2
).