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](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) \n"
" for all-pairs shortest paths in weighted graphs.\n"
"\n"
" The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes\n"
" in a single execution. It uses dynamic programming to iteratively improve shortest\n"
" path estimates by considering each node as a potential intermediate vertex.\n"
"\n"
" ## Algorithm\n"
"\n"
" | Algorithm | Function | Complexity | Best For |\n"
" |-----------|----------|------------|----------|\n"
" | [Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) | `floyd_warshall/4` | O(V³) | Dense graphs, all-pairs paths |\n"
"\n"
" ## Key Concepts\n"
"\n"
" - **Dynamic Programming**: Builds solution from smaller subproblems\n"
" - **K-Intermediate Nodes**: After k iterations, paths use only nodes {1,...,k} as intermediates\n"
" - **Path Reconstruction**: Predecessor matrix allows full path recovery\n"
" - **Transitive Closure**: Can be adapted for reachability (boolean weights)\n"
"\n"
" ## The DP Recurrence\n"
"\n"
" ```\n"
" dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n"
" ```\n"
"\n"
" For each intermediate node k, check if going through k improves the path from i to j.\n"
"\n"
" ## Comparison with Running Dijkstra V Times\n"
"\n"
" | Approach | Complexity | Best For |\n"
" |----------|------------|----------|\n"
" | Floyd-Warshall | O(V³) | Dense graphs (E ≈ V²) |\n"
" | V × Dijkstra | O(V(V+E) log V) | Sparse graphs |\n"
" | Johnson's | O(V² log V + VE) | Sparse graphs with negative weights |\n"
"\n"
" **Rule of thumb**: Use Floyd-Warshall when E > V × log V (fairly dense)\n"
"\n"
" ## Negative Cycles\n"
"\n"
" The algorithm can detect negative cycles: after completion, if any node has\n"
" dist[node][node] < 0, a negative cycle exists.\n"
"\n"
" ## Variants\n"
"\n"
" - **Transitive Closure**: Use boolean OR instead of min-plus (Warshall's algorithm)\n"
" - **Successor Matrix**: Track next hop for path reconstruction\n"
"\n"
" ## Use Cases\n"
"\n"
" - **All-pairs routing**: Precompute distances for fast lookup\n"
" - **Transitive closure**: Reachability queries in databases\n"
" - **Centrality metrics**: Closeness and betweenness calculations\n"
" - **Graph analysis**: Detecting negative cycles\n"
"\n"
" ## History\n"
"\n"
" Published independently by Robert Floyd (1962), Stephen Warshall (1962),\n"
" and Bernard Roy (1959). Floyd's version included path reconstruction.\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Floyd-Warshall Algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm)\n"
" - [Wikipedia: Warshall's Algorithm (Transitive Closure)](https://en.wikipedia.org/wiki/Transitive_closure#Computing_the_transitive_closure)\n"
" - [CP-Algorithms: Floyd-Warshall](https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html)\n"
" - [MIT 6.006: Dynamic Programming](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/)\n"
).
-file("src/yog/pathfinding/floyd_warshall.gleam", 161).
?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()}, SXW),
list(integer()),
SXW,
fun((SXW, SXW) -> 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", 80).
?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(), SXP),
SXP,
fun((SXP, SXP) -> SXP),
fun((SXP, SXP) -> gleam@order:order())
) -> {ok, gleam@dict:dict({integer(), integer()}, SXP)} | {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", 203).
?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", 225).
?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
).