Current section
Files
Jump to
Current section
Files
src/yog@pathfinding.erl
-module(yog@pathfinding).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding.gleam").
-export([shortest_path/6, single_source_distances/5, a_star/7, bellman_ford/6, floyd_warshall/4]).
-export_type([path/1, bellman_ford_result/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 path(GBC) :: {path, list(integer()), GBC}.
-type bellman_ford_result(GBD) :: {shortest_path, path(GBD)} |
negative_cycle |
no_path.
-file("src/yog/pathfinding.gleam", 104).
-spec compare_frontier(
{GBU, list(integer())},
{GBU, list(integer())},
fun((GBU, GBU) -> gleam@order:order())
) -> gleam@order:order().
compare_frontier(A, B, Cmp) ->
Cmp(erlang:element(1, A), erlang:element(1, B)).
-file("src/yog/pathfinding.gleam", 114).
?DOC(
" Helper to determine if a node should be explored based on distance comparison.\n"
" Returns True if the node hasn't been visited or if the new distance is shorter.\n"
).
-spec should_explore_node(
gleam@dict:dict(integer(), GBX),
integer(),
GBX,
fun((GBX, GBX) -> gleam@order:order())
) -> boolean().
should_explore_node(Visited, Node, New_dist, Compare) ->
case gleam_stdlib:map_get(Visited, Node) of
{ok, Prev_dist} ->
case Compare(New_dist, Prev_dist) of
lt ->
true;
_ ->
false
end;
{error, nil} ->
true
end.
-file("src/yog/pathfinding.gleam", 56).
-spec do_dijkstra(
yog@model:graph(any(), GBL),
integer(),
yog@internal@heap:heap({GBL, list(integer())}),
gleam@dict:dict(integer(), GBL),
fun((GBL, GBL) -> GBL),
fun((GBL, GBL) -> gleam@order:order())
) -> gleam@option:option(path(GBL)).
do_dijkstra(Graph, Goal, Frontier, Visited, Add, Compare) ->
case yog@internal@heap:find_min(Frontier) of
{error, nil} ->
none;
{ok, {Dist, [Current | _] = Path}} ->
Rest_frontier = begin
_pipe = yog@internal@heap:delete_min(
Frontier,
fun(A, B) -> compare_frontier(A, B, Compare) end
),
gleam@result:unwrap(_pipe, yog@internal@heap:new())
end,
case Current =:= Goal of
true ->
{some, {path, lists:reverse(Path), Dist}};
false ->
Should_explore = should_explore_node(
Visited,
Current,
Dist,
Compare
),
case Should_explore of
false ->
do_dijkstra(
Graph,
Goal,
Rest_frontier,
Visited,
Add,
Compare
);
true ->
New_visited = gleam@dict:insert(
Visited,
Current,
Dist
),
Next_frontier = begin
_pipe@1 = yog@model:successors(Graph, Current),
gleam@list:fold(
_pipe@1,
Rest_frontier,
fun(H, Neighbor) ->
{Next_id, Weight} = Neighbor,
yog@internal@heap:insert(
H,
{Add(Dist, Weight),
[Next_id | Path]},
fun(A@1, B@1) ->
compare_frontier(
A@1,
B@1,
Compare
)
end
)
end
)
end,
do_dijkstra(
Graph,
Goal,
Next_frontier,
New_visited,
Add,
Compare
)
end
end;
{ok, _} ->
none
end.
-file("src/yog/pathfinding.gleam", 39).
?DOC(
" Finds the shortest path between two nodes using Dijkstra's algorithm.\n"
"\n"
" Works with non-negative edge weights only. For negative weights, use `bellman_ford`.\n"
"\n"
" **Time Complexity:** O((V + E) log V) with heap\n"
"\n"
" ## Parameters\n"
"\n"
" - `zero`: The identity element for addition (e.g., 0 for integers)\n"
" - `add`: Function to add two weights\n"
" - `compare`: Function to compare two weights\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" pathfinding.shortest_path(\n"
" in: graph,\n"
" from: 1,\n"
" to: 5,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" )\n"
" // => Some(Path([1, 2, 5], 15))\n"
" ```\n"
).
-spec shortest_path(
yog@model:graph(any(), GBF),
integer(),
integer(),
GBF,
fun((GBF, GBF) -> GBF),
fun((GBF, GBF) -> gleam@order:order())
) -> gleam@option:option(path(GBF)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
Frontier = begin
_pipe = yog@internal@heap:new(),
yog@internal@heap:insert(
_pipe,
{Zero, [Start]},
fun(A, B) -> compare_frontier(A, B, Compare) end
)
end,
do_dijkstra(Graph, Goal, Frontier, maps:new(), Add, Compare).
-file("src/yog/pathfinding.gleam", 189).
-spec do_single_source_dijkstra(
yog@model:graph(any(), GCH),
yog@internal@heap:heap({GCH, integer()}),
gleam@dict:dict(integer(), GCH),
fun((GCH, GCH) -> GCH),
fun((GCH, GCH) -> gleam@order:order())
) -> gleam@dict:dict(integer(), GCH).
do_single_source_dijkstra(Graph, Frontier, Distances, Add, Compare) ->
case yog@internal@heap:find_min(Frontier) of
{error, nil} ->
Distances;
{ok, {Dist, Current}} ->
Rest_frontier = begin
_pipe = yog@internal@heap:delete_min(
Frontier,
fun(A, B) ->
Compare(erlang:element(1, A), erlang:element(1, B))
end
),
gleam@result:unwrap(_pipe, yog@internal@heap:new())
end,
Should_explore = should_explore_node(
Distances,
Current,
Dist,
Compare
),
case Should_explore of
false ->
do_single_source_dijkstra(
Graph,
Rest_frontier,
Distances,
Add,
Compare
);
true ->
New_distances = gleam@dict:insert(Distances, Current, Dist),
Next_frontier = begin
_pipe@1 = yog@model:successors(Graph, Current),
gleam@list:fold(
_pipe@1,
Rest_frontier,
fun(H, Neighbor) ->
{Next_id, Weight} = Neighbor,
yog@internal@heap:insert(
H,
{Add(Dist, Weight), Next_id},
fun(A@1, B@1) ->
Compare(
erlang:element(1, A@1),
erlang:element(1, B@1)
)
end
)
end
)
end,
do_single_source_dijkstra(
Graph,
Next_frontier,
New_distances,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding.gleam", 175).
?DOC(
" Computes shortest distances from a source node to all reachable nodes.\n"
"\n"
" Returns a dictionary mapping each reachable node to its shortest distance\n"
" from the source. Unreachable nodes are not included in the result.\n"
"\n"
" This is useful when you need distances to multiple destinations, or want\n"
" to find the closest target among many options. More efficient than running\n"
" `shortest_path` multiple times.\n"
"\n"
" **Time Complexity:** O((V + E) log V) with heap\n"
"\n"
" ## Parameters\n"
"\n"
" - `zero`: The identity element for addition (e.g., 0 for integers)\n"
" - `add`: Function to add two weights\n"
" - `compare`: Function to compare two weights\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Find distances from node 1 to all reachable nodes\n"
" let distances = pathfinding.single_source_distances(\n"
" in: graph,\n"
" from: 1,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" )\n"
" // => dict.from_list([#(1, 0), #(2, 5), #(3, 8), #(4, 15)])\n"
"\n"
" // Find closest target among many options\n"
" let targets = [10, 20, 30]\n"
" let closest = targets\n"
" |> list.filter_map(fn(t) { dict.get(distances, t) })\n"
" |> list.sort(int.compare)\n"
" |> list.first\n"
" ```\n"
"\n"
" ## Use Cases\n"
"\n"
" - Finding nearest target among multiple options\n"
" - Computing distance maps for game AI\n"
" - Network routing table generation\n"
" - Graph analysis (centrality measures)\n"
" - Reverse pathfinding (with `transform.transpose`)\n"
).
-spec single_source_distances(
yog@model:graph(any(), GCB),
integer(),
GCB,
fun((GCB, GCB) -> GCB),
fun((GCB, GCB) -> gleam@order:order())
) -> gleam@dict:dict(integer(), GCB).
single_source_distances(Graph, Source, Zero, Add, Compare) ->
Frontier = begin
_pipe = yog@internal@heap:new(),
yog@internal@heap:insert(
_pipe,
{Zero, Source},
fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
)
end,
do_single_source_dijkstra(Graph, Frontier, maps:new(), Add, Compare).
-file("src/yog/pathfinding.gleam", 292).
-spec do_a_star(
yog@model:graph(any(), GKM),
integer(),
yog@internal@heap:heap({GKJ, GKJ, list(integer())}),
gleam@dict:dict(integer(), GKJ),
fun((GKJ, GKM) -> GKJ),
fun((GKJ, GKJ) -> gleam@order:order()),
fun((integer(), integer()) -> GKM)
) -> gleam@option:option(path(GKJ)).
do_a_star(Graph, Goal, Frontier, Visited, Add, Compare, H) ->
case yog@internal@heap:find_min(Frontier) of
{error, nil} ->
none;
{ok, {_, Dist, [Current | _] = Path}} ->
Rest_frontier = begin
_pipe = yog@internal@heap:delete_min(
Frontier,
fun(A, B) ->
Compare(erlang:element(1, A), erlang:element(1, B))
end
),
gleam@result:unwrap(_pipe, yog@internal@heap:new())
end,
case Current =:= Goal of
true ->
{some, {path, lists:reverse(Path), Dist}};
false ->
Should_explore = should_explore_node(
Visited,
Current,
Dist,
Compare
),
case Should_explore of
false ->
do_a_star(
Graph,
Goal,
Rest_frontier,
Visited,
Add,
Compare,
H
);
true ->
New_visited = gleam@dict:insert(
Visited,
Current,
Dist
),
Next_frontier = begin
_pipe@1 = yog@model:successors(Graph, Current),
gleam@list:fold(
_pipe@1,
Rest_frontier,
fun(Acc_h, Neighbor) ->
{Next_id, Weight} = Neighbor,
Next_dist = Add(Dist, Weight),
F_score = Add(
Next_dist,
H(Next_id, Goal)
),
yog@internal@heap:insert(
Acc_h,
{F_score,
Next_dist,
[Next_id | Path]},
fun(A@1, B@1) ->
Compare(
erlang:element(1, A@1),
erlang:element(1, B@1)
)
end
)
end
)
end,
do_a_star(
Graph,
Goal,
Next_frontier,
New_visited,
Add,
Compare,
H
)
end
end;
_ ->
none
end.
-file("src/yog/pathfinding.gleam", 274).
?DOC(
" Finds the shortest path using A* search with a heuristic function.\n"
"\n"
" A* is more efficient than Dijkstra when you have a good heuristic estimate\n"
" of the remaining distance to the goal. The heuristic must be admissible\n"
" (never overestimate the actual distance) to guarantee finding the shortest path.\n"
"\n"
" **Time Complexity:** O((V + E) log V), but often faster than Dijkstra in practice\n"
"\n"
" ## Parameters\n"
"\n"
" - `heuristic`: A function that estimates distance from any node to the goal.\n"
" Must be admissible (h(n) ≤ actual distance) to guarantee shortest path.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Manhattan distance heuristic for grid\n"
" let h = fn(node, goal) {\n"
" int.absolute_value(node.x - goal.x) + int.absolute_value(node.y - goal.y)\n"
" }\n"
"\n"
" pathfinding.a_star(\n"
" in: graph,\n"
" from: start,\n"
" to: goal,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare,\n"
" heuristic: h\n"
" )\n"
" ```\n"
).
-spec a_star(
yog@model:graph(any(), GCQ),
integer(),
integer(),
GCQ,
fun((GCQ, GCQ) -> GCQ),
fun((GCQ, GCQ) -> gleam@order:order()),
fun((integer(), integer()) -> GCQ)
) -> gleam@option:option(path(GCQ)).
a_star(Graph, Start, Goal, Zero, Add, Compare, H) ->
Initial_f = H(Start, Goal),
Frontier = begin
_pipe = yog@internal@heap:new(),
yog@internal@heap:insert(
_pipe,
{Initial_f, Zero, [Start]},
fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
)
end,
do_a_star(Graph, Goal, Frontier, maps:new(), Add, Compare, H).
-file("src/yog/pathfinding.gleam", 428).
-spec relaxation_passes(
yog@model:graph(any(), GDJ),
list(integer()),
gleam@dict:dict(integer(), GDJ),
gleam@dict:dict(integer(), integer()),
integer(),
fun((GDJ, GDJ) -> GDJ),
fun((GDJ, GDJ) -> gleam@order:order())
) -> {gleam@dict:dict(integer(), GDJ), gleam@dict:dict(integer(), integer())}.
relaxation_passes(
Graph,
Nodes,
Distances,
Predecessors,
Remaining,
Add,
Compare
) ->
case Remaining =< 0 of
true ->
{Distances, Predecessors};
false ->
{New_distances, New_predecessors} = gleam@list:fold(
Nodes,
{Distances, Predecessors},
fun(Acc, U) ->
{Dists, Preds} = Acc,
case gleam_stdlib:map_get(Dists, U) of
{error, nil} ->
Acc;
{ok, U_dist} ->
Neighbors = yog@model:successors(Graph, U),
gleam@list:fold(
Neighbors,
{Dists, Preds},
fun(Inner_acc, Edge) ->
{V, Weight} = Edge,
{Curr_dists, Curr_preds} = Inner_acc,
New_dist = Add(U_dist, Weight),
case gleam_stdlib:map_get(Curr_dists, V) of
{error, nil} ->
{gleam@dict:insert(
Curr_dists,
V,
New_dist
),
gleam@dict:insert(
Curr_preds,
V,
U
)};
{ok, V_dist} ->
case Compare(New_dist, V_dist) of
lt ->
{gleam@dict:insert(
Curr_dists,
V,
New_dist
),
gleam@dict:insert(
Curr_preds,
V,
U
)};
_ ->
Inner_acc
end
end
end
)
end
end
),
relaxation_passes(
Graph,
Nodes,
New_distances,
New_predecessors,
Remaining - 1,
Add,
Compare
)
end.
-file("src/yog/pathfinding.gleam", 492).
-spec has_negative_cycle(
yog@model:graph(any(), GDW),
list(integer()),
gleam@dict:dict(integer(), GDW),
fun((GDW, GDW) -> GDW),
fun((GDW, GDW) -> gleam@order:order())
) -> boolean().
has_negative_cycle(Graph, Nodes, Distances, Add, Compare) ->
gleam@list:any(Nodes, fun(U) -> case gleam_stdlib:map_get(Distances, U) of
{error, nil} ->
false;
{ok, U_dist} ->
_pipe = yog@model:successors(Graph, U),
gleam@list:any(
_pipe,
fun(Edge) ->
{V, Weight} = Edge,
New_dist = Add(U_dist, Weight),
case gleam_stdlib:map_get(Distances, V) of
{error, nil} ->
false;
{ok, V_dist} ->
case Compare(New_dist, V_dist) of
lt ->
true;
_ ->
false
end
end
end
)
end end).
-file("src/yog/pathfinding.gleam", 524).
-spec reconstruct_path(
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
list(integer())
) -> {ok, list(integer())} | {error, nil}.
reconstruct_path(Predecessors, Start, Current, Acc) ->
case Current =:= Start of
true ->
{ok, Acc};
false ->
case gleam_stdlib:map_get(Predecessors, Current) of
{error, nil} ->
{error, nil};
{ok, Pred} ->
reconstruct_path(Predecessors, Start, Pred, [Pred | Acc])
end
end.
-file("src/yog/pathfinding.gleam", 382).
?DOC(
" Finds shortest path with support for negative edge weights using Bellman-Ford.\n"
"\n"
" Unlike Dijkstra and A*, this algorithm can handle negative edge weights.\n"
" It also detects negative cycles reachable from the source node.\n"
"\n"
" **Time Complexity:** O(VE) where V is vertices and E is edges\n"
"\n"
" ## Returns\n"
"\n"
" - `ShortestPath(path)`: If a valid shortest path exists\n"
" - `NegativeCycle`: If a negative cycle is reachable from the start node\n"
" - `NoPath`: If no path exists from start to goal\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" pathfinding.bellman_ford(\n"
" in: graph,\n"
" from: 1,\n"
" to: 5,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" )\n"
" // => ShortestPath(Path([1, 3, 5], -2)) // Can have negative total weight\n"
" // or NegativeCycle // If cycle detected\n"
" // or NoPath // If unreachable\n"
" ```\n"
).
-spec bellman_ford(
yog@model:graph(any(), GDE),
integer(),
integer(),
GDE,
fun((GDE, GDE) -> GDE),
fun((GDE, GDE) -> gleam@order:order())
) -> bellman_ford_result(GDE).
bellman_ford(Graph, Start, Goal, Zero, Add, Compare) ->
All_nodes = yog@model:all_nodes(Graph),
Initial_distances = maps:from_list([{Start, Zero}]),
Initial_predecessors = maps:new(),
Node_count = erlang:length(All_nodes),
{Distances, Predecessors} = relaxation_passes(
Graph,
All_nodes,
Initial_distances,
Initial_predecessors,
Node_count - 1,
Add,
Compare
),
case has_negative_cycle(Graph, All_nodes, Distances, Add, Compare) of
true ->
negative_cycle;
false ->
case gleam_stdlib:map_get(Distances, Goal) of
{error, nil} ->
no_path;
{ok, Dist} ->
case reconstruct_path(Predecessors, Start, Goal, [Goal]) of
{ok, Path} ->
{shortest_path, {path, Path, Dist}};
{error, nil} ->
no_path
end
end
end.
-file("src/yog/pathfinding.gleam", 722).
?DOC(" Helper to get distance from the nested dictionary structure\n").
-spec get_distance(
gleam@dict:dict(integer(), gleam@dict:dict(integer(), GES)),
integer(),
integer()
) -> {ok, GES} | {error, nil}.
get_distance(Distances, I, J) ->
case gleam_stdlib:map_get(Distances, I) of
{ok, Row} ->
gleam_stdlib:map_get(Row, J);
{error, nil} ->
{error, nil}
end.
-file("src/yog/pathfinding.gleam", 734).
?DOC(" Helper to update distance in the nested dictionary structure\n").
-spec update_distance(
gleam@dict:dict(integer(), gleam@dict:dict(integer(), GEZ)),
integer(),
integer(),
GEZ
) -> gleam@dict:dict(integer(), gleam@dict:dict(integer(), GEZ)).
update_distance(Distances, I, J, Dist) ->
case gleam_stdlib:map_get(Distances, I) of
{ok, Row} ->
New_row = gleam@dict:insert(Row, J, Dist),
gleam@dict:insert(Distances, I, New_row);
{error, nil} ->
New_row@1 = begin
_pipe = maps:new(),
gleam@dict:insert(_pipe, J, Dist)
end,
gleam@dict:insert(Distances, I, New_row@1)
end.
-file("src/yog/pathfinding.gleam", 754).
?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(), gleam@dict:dict(integer(), GFI)),
list(integer()),
GFI,
fun((GFI, GFI) -> gleam@order:order())
) -> boolean().
detect_negative_cycle(Distances, Nodes, Zero, Compare) ->
_pipe = Nodes,
gleam@list:any(_pipe, fun(I) -> case get_distance(Distances, I, I) of
{ok, Dist} ->
case Compare(Dist, Zero) of
lt ->
true;
_ ->
false
end;
{error, nil} ->
false
end end).
-file("src/yog/pathfinding.gleam", 627).
?DOC(
" Computes shortest paths between all pairs of nodes using the Floyd-Warshall algorithm.\n"
"\n"
" Returns a nested dictionary where `distances[i][j]` gives the shortest distance from node `i` to node `j`.\n"
" If no path exists between two nodes, the pair will not be present in the dictionary.\n"
"\n"
" Returns `Error(Nil)` if a negative cycle is detected in the graph.\n"
"\n"
" **Time Complexity:** O(V³)\n"
" **Space Complexity:** O(V²)\n"
"\n"
" ## Parameters\n"
"\n"
" - `zero`: The identity element for addition (e.g., `0` for integers, `0.0` for floats)\n"
" - `add`: Function to add two weights\n"
" - `compare`: Function to compare two weights\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import gleam/dict\n"
" import gleam/int\n"
" import gleam/io\n"
" import yog\n"
" import yog/pathfinding\n"
"\n"
" pub fn main() {\n"
" let graph =\n"
" yog.directed()\n"
" |> yog.add_node(1, \"A\")\n"
" |> yog.add_node(2, \"B\")\n"
" |> yog.add_node(3, \"C\")\n"
" |> yog.add_edge(from: 1, to: 2, with: 4)\n"
" |> yog.add_edge(from: 2, to: 3, with: 3)\n"
" |> yog.add_edge(from: 1, to: 3, with: 10)\n"
"\n"
" case pathfinding.floyd_warshall(\n"
" in: graph,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" ) {\n"
" Ok(distances) -> {\n"
" // Query distance from node 1 to node 3\n"
" let assert Ok(row) = dict.get(distances, 1)\n"
" let assert Ok(dist) = dict.get(row, 3)\n"
" // dist = 7 (via node 2: 4 + 3)\n"
" io.println(\"Distance from 1 to 3: \" <> int.to_string(dist))\n"
" }\n"
" Error(Nil) -> io.println(\"Negative cycle detected!\")\n"
" }\n"
" }\n"
" ```\n"
"\n"
" ## Handling Negative Weights\n"
"\n"
" Floyd-Warshall can handle negative edge weights and will detect negative cycles:\n"
"\n"
" ```gleam\n"
" let graph_with_negative_cycle =\n"
" yog.directed()\n"
" |> yog.add_node(1, \"A\")\n"
" |> yog.add_node(2, \"B\")\n"
" |> yog.add_edge(from: 1, to: 2, with: 5)\n"
" |> yog.add_edge(from: 2, to: 1, with: -10)\n"
"\n"
" case pathfinding.floyd_warshall(\n"
" in: graph_with_negative_cycle,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" ) {\n"
" Ok(_) -> io.println(\"No negative cycle\")\n"
" Error(Nil) -> io.println(\"Negative cycle detected!\") // This will execute\n"
" }\n"
" ```\n"
"\n"
" ## Use Cases\n"
"\n"
" - Computing distance matrices for all node pairs\n"
" - Finding transitive closure of a graph\n"
" - Detecting negative cycles\n"
" - Preprocessing for queries about arbitrary node pairs\n"
" - Graph metrics (diameter, centrality)\n"
).
-spec floyd_warshall(
yog@model:graph(any(), GEJ),
GEJ,
fun((GEJ, GEJ) -> GEJ),
fun((GEJ, GEJ) -> gleam@order:order())
) -> {ok, gleam@dict:dict(integer(), gleam@dict:dict(integer(), GEJ))} |
{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) ->
Row@1 = begin
_pipe@1 = Nodes,
gleam@list:fold(
_pipe@1,
maps:new(),
fun(Row, 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(
Row,
J,
Weight
);
_ ->
gleam@dict:insert(
Row,
J,
Zero
)
end;
{error, nil} ->
gleam@dict:insert(
Row,
J,
Zero
)
end;
{error, nil} ->
gleam@dict:insert(Row, 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(
Row,
J,
Weight@1
);
{error, nil} ->
Row
end;
{error, nil} ->
Row
end
end end
)
end,
gleam@dict:insert(Distances, I, Row@1)
end
)
end,
Final_distances = begin
_pipe@2 = Nodes,
gleam@list:fold(
_pipe@2,
Initial_distances,
fun(Distances@1, K) -> _pipe@3 = Nodes,
gleam@list:fold(
_pipe@3,
Distances@1,
fun(Distances@2, I@1) -> _pipe@4 = Nodes,
gleam@list:fold(
_pipe@4,
Distances@2,
fun(Distances@3, J@1) ->
case get_distance(Distances@3, I@1, K) of
{error, nil} ->
Distances@3;
{ok, Dist_ik} ->
case get_distance(Distances@3, K, J@1) of
{error, nil} ->
Distances@3;
{ok, Dist_kj} ->
New_dist = Add(Dist_ik, Dist_kj),
case get_distance(
Distances@3,
I@1,
J@1
) of
{error, nil} ->
update_distance(
Distances@3,
I@1,
J@1,
New_dist
);
{ok, Current_dist} ->
case Compare(
New_dist,
Current_dist
) of
lt ->
update_distance(
Distances@3,
I@1,
J@1,
New_dist
);
_ ->
Distances@3
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.