Current section
Files
Jump to
Current section
Files
src/yog@pathfinding@bellman_ford.erl
-module(yog@pathfinding@bellman_ford).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/bellman_ford.gleam").
-export([relaxation_passes/7, has_negative_cycle/5, reconstruct_path/4, bellman_ford/6, implicit_bellman_ford/6, implicit_bellman_ford_by/7, bellman_ford_int/3, bellman_ford_float/3]).
-export_type([bellman_ford_result/1, implicit_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.
?MODULEDOC(" Bellman-Ford algorithm for finding shortest paths in graphs with negative edge weights.\n").
-type bellman_ford_result(SYN) :: {shortest_path,
yog@pathfinding@utils:path(SYN)} |
negative_cycle |
no_path.
-type implicit_bellman_ford_result(SYO) :: {found_goal, SYO} |
detected_negative_cycle |
no_goal.
-file("src/yog/pathfinding/bellman_ford.gleam", 84).
-spec relaxation_passes(
yog@model:graph(any(), SYV),
list(integer()),
gleam@dict:dict(integer(), SYV),
gleam@dict:dict(integer(), integer()),
integer(),
fun((SYV, SYV) -> SYV),
fun((SYV, SYV) -> gleam@order:order())
) -> {gleam@dict:dict(integer(), SYV), 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/bellman_ford.gleam", 142).
-spec has_negative_cycle(
yog@model:graph(any(), SZI),
list(integer()),
gleam@dict:dict(integer(), SZI),
fun((SZI, SZI) -> SZI),
fun((SZI, SZI) -> 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/bellman_ford.gleam", 172).
-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/bellman_ford.gleam", 43).
?DOC(
" Finds shortest path with support for negative edge weights using Bellman-Ford.\n"
"\n"
" **Time Complexity:** O(VE)\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"
).
-spec bellman_ford(
yog@model:graph(any(), SYQ),
integer(),
integer(),
SYQ,
fun((SYQ, SYQ) -> SYQ),
fun((SYQ, SYQ) -> gleam@order:order())
) -> bellman_ford_result(SYQ).
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/bellman_ford.gleam", 219).
-spec do_implicit_bellman_ford(
yog@internal@queue:queue(SZY),
gleam@dict:dict(SZY, TAA),
gleam@dict:dict(SZY, integer()),
gleam@set:set(SZY),
fun((SZY) -> list({SZY, TAA})),
fun((SZY) -> boolean()),
TAA,
fun((TAA, TAA) -> TAA),
fun((TAA, TAA) -> gleam@order:order())
) -> implicit_bellman_ford_result(TAA).
do_implicit_bellman_ford(
Q,
Distances,
Relax_counts,
In_queue,
Successors,
Is_goal,
Zero,
Add,
Compare
) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
_pipe = Distances,
_pipe@1 = maps:to_list(_pipe),
_pipe@2 = gleam@list:filter(
_pipe@1,
fun(Entry) -> Is_goal(erlang:element(1, Entry)) end
),
_pipe@3 = gleam@list:sort(
_pipe@2,
fun(A, B) ->
Compare(erlang:element(2, A), erlang:element(2, B))
end
),
_pipe@4 = gleam@list:first(_pipe@3),
_pipe@5 = gleam@result:map(
_pipe@4,
fun(Entry@1) -> {found_goal, erlang:element(2, Entry@1)} end
),
gleam@result:unwrap(_pipe@5, no_goal);
{ok, {Current, Rest_queue}} ->
New_in_queue = gleam@set:delete(In_queue, Current),
Current_dist = begin
_pipe@6 = gleam_stdlib:map_get(Distances, Current),
gleam@result:unwrap(_pipe@6, Zero)
end,
{New_distances, New_counts, New_queue, New_in_q} = begin
_pipe@7 = Successors(Current),
gleam@list:fold(
_pipe@7,
{Distances, Relax_counts, Rest_queue, New_in_queue},
fun(Acc, Neighbor) ->
{Dists, Counts, Q_acc, In_q_acc} = Acc,
{Next_state, Edge_cost} = Neighbor,
New_dist = Add(Current_dist, Edge_cost),
case gleam_stdlib:map_get(Dists, Next_state) of
{ok, Prev_dist} ->
case Compare(New_dist, Prev_dist) of
lt ->
Updated_dists = gleam@dict:insert(
Dists,
Next_state,
New_dist
),
Relax_count = begin
_pipe@8 = gleam_stdlib:map_get(
Counts,
Next_state
),
gleam@result:unwrap(_pipe@8, 0)
end,
New_count = Relax_count + 1,
Updated_counts = gleam@dict:insert(
Counts,
Next_state,
New_count
),
case New_count > maps:size(Dists) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
case gleam@set:contains(
In_q_acc,
Next_state
) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
{Updated_dists,
Updated_counts,
yog@internal@queue:push(
Q_acc,
Next_state
),
gleam@set:insert(
In_q_acc,
Next_state
)}
end
end;
_ ->
Acc
end;
{error, nil} ->
Updated_dists@1 = gleam@dict:insert(
Dists,
Next_state,
New_dist
),
Updated_counts@1 = gleam@dict:insert(
Counts,
Next_state,
1
),
{Updated_dists@1,
Updated_counts@1,
yog@internal@queue:push(Q_acc, Next_state),
gleam@set:insert(In_q_acc, Next_state)}
end
end
)
end,
Has_negative_cycle = begin
_pipe@9 = New_counts,
_pipe@10 = maps:to_list(_pipe@9),
gleam@list:any(
_pipe@10,
fun(Entry@2) ->
erlang:element(2, Entry@2) > maps:size(New_distances)
end
)
end,
case Has_negative_cycle of
true ->
detected_negative_cycle;
false ->
do_implicit_bellman_ford(
New_queue,
New_distances,
New_counts,
New_in_q,
Successors,
Is_goal,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 198).
?DOC(
" Finds shortest path in implicit graphs with support for negative edge weights.\n"
"\n"
" **Time Complexity:** O(VE) average case\n"
"\n"
" ## Returns\n"
"\n"
" - `FoundGoal(cost)`: If a valid shortest path to goal exists\n"
" - `DetectedNegativeCycle`: If a negative cycle is reachable from start\n"
" - `NoGoal`: If no goal state is reached\n"
).
-spec implicit_bellman_ford(
SZU,
fun((SZU) -> list({SZU, SZV})),
fun((SZU) -> boolean()),
SZV,
fun((SZV, SZV) -> SZV),
fun((SZV, SZV) -> gleam@order:order())
) -> implicit_bellman_ford_result(SZV).
implicit_bellman_ford(Start, Successors, Is_goal, Zero, Add, Compare) ->
do_implicit_bellman_ford(
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, Start)
end,
maps:from_list([{Start, Zero}]),
maps:from_list([{Start, 0}]),
gleam@set:new(),
Successors,
Is_goal,
Zero,
Add,
Compare
).
-file("src/yog/pathfinding/bellman_ford.gleam", 348).
-spec do_implicit_bellman_ford_by(
yog@internal@queue:queue(TAN),
gleam@dict:dict(TAP, {TAQ, TAN}),
gleam@dict:dict(TAP, integer()),
gleam@set:set(TAN),
fun((TAN) -> list({TAN, TAQ})),
fun((TAN) -> TAP),
fun((TAN) -> boolean()),
TAQ,
fun((TAQ, TAQ) -> TAQ),
fun((TAQ, TAQ) -> gleam@order:order())
) -> implicit_bellman_ford_result(TAQ).
do_implicit_bellman_ford_by(
Q,
Distances,
Relax_counts,
In_queue,
Successors,
Key_fn,
Is_goal,
Zero,
Add,
Compare
) ->
case yog@internal@queue:pop(Q) of
{error, nil} ->
_pipe = Distances,
_pipe@1 = maps:to_list(_pipe),
_pipe@2 = gleam@list:filter(
_pipe@1,
fun(Entry) ->
Is_goal(erlang:element(2, erlang:element(2, Entry)))
end
),
_pipe@3 = gleam@list:sort(
_pipe@2,
fun(A, B) ->
Compare(
erlang:element(1, erlang:element(2, A)),
erlang:element(1, erlang:element(2, B))
)
end
),
_pipe@4 = gleam@list:first(_pipe@3),
_pipe@5 = gleam@result:map(
_pipe@4,
fun(Entry@1) ->
{found_goal, erlang:element(1, erlang:element(2, Entry@1))}
end
),
gleam@result:unwrap(_pipe@5, no_goal);
{ok, {Current, Rest_queue}} ->
Current_key = Key_fn(Current),
New_in_queue = gleam@set:delete(In_queue, Current),
{Current_dist, _} = begin
_pipe@6 = gleam_stdlib:map_get(Distances, Current_key),
gleam@result:unwrap(_pipe@6, {Zero, Current})
end,
{New_distances, New_counts, New_queue, New_in_q} = begin
_pipe@7 = Successors(Current),
gleam@list:fold(
_pipe@7,
{Distances, Relax_counts, Rest_queue, New_in_queue},
fun(Acc, Neighbor) ->
{Dists, Counts, Q_acc, In_q_acc} = Acc,
{Next_state, Edge_cost} = Neighbor,
Next_key = Key_fn(Next_state),
New_dist = Add(Current_dist, Edge_cost),
case gleam_stdlib:map_get(Dists, Next_key) of
{ok, {Prev_dist, _}} ->
case Compare(New_dist, Prev_dist) of
lt ->
Updated_dists = gleam@dict:insert(
Dists,
Next_key,
{New_dist, Next_state}
),
Relax_count = begin
_pipe@8 = gleam_stdlib:map_get(
Counts,
Next_key
),
gleam@result:unwrap(_pipe@8, 0)
end,
New_count = Relax_count + 1,
Updated_counts = gleam@dict:insert(
Counts,
Next_key,
New_count
),
case New_count > maps:size(Dists) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
case gleam@set:contains(
In_q_acc,
Next_state
) of
true ->
{Updated_dists,
Updated_counts,
Q_acc,
In_q_acc};
false ->
{Updated_dists,
Updated_counts,
yog@internal@queue:push(
Q_acc,
Next_state
),
gleam@set:insert(
In_q_acc,
Next_state
)}
end
end;
_ ->
Acc
end;
{error, nil} ->
Updated_dists@1 = gleam@dict:insert(
Dists,
Next_key,
{New_dist, Next_state}
),
Updated_counts@1 = gleam@dict:insert(
Counts,
Next_key,
1
),
{Updated_dists@1,
Updated_counts@1,
yog@internal@queue:push(Q_acc, Next_state),
gleam@set:insert(In_q_acc, Next_state)}
end
end
)
end,
Has_negative_cycle = begin
_pipe@9 = New_counts,
_pipe@10 = maps:to_list(_pipe@9),
gleam@list:any(
_pipe@10,
fun(Entry@2) ->
erlang:element(2, Entry@2) > maps:size(New_distances)
end
)
end,
case Has_negative_cycle of
true ->
detected_negative_cycle;
false ->
do_implicit_bellman_ford_by(
New_queue,
New_distances,
New_counts,
New_in_q,
Successors,
Key_fn,
Is_goal,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bellman_ford.gleam", 324).
?DOC(" Like `implicit_bellman_ford`, but deduplicates visited states by a custom key.\n").
-spec implicit_bellman_ford_by(
TAI,
fun((TAI) -> list({TAI, TAJ})),
fun((TAI) -> any()),
fun((TAI) -> boolean()),
TAJ,
fun((TAJ, TAJ) -> TAJ),
fun((TAJ, TAJ) -> gleam@order:order())
) -> implicit_bellman_ford_result(TAJ).
implicit_bellman_ford_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) ->
Start_key = Key_fn(Start),
do_implicit_bellman_ford_by(
begin
_pipe = yog@internal@queue:new(),
yog@internal@queue:push(_pipe, Start)
end,
maps:from_list([{Start_key, {Zero, Start}}]),
maps:from_list([{Start_key, 0}]),
gleam@set:new(),
Successors,
Key_fn,
Is_goal,
Zero,
Add,
Compare
).
-file("src/yog/pathfinding/bellman_ford.gleam", 482).
?DOC(
" Finds shortest path with **integer weights**, handling negative edges.\n"
"\n"
" This is a convenience wrapper around `bellman_ford` 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"
" bellman_ford.bellman_ford_int(graph, from: 1, to: 5)\n"
" // => ShortestPath(Path([1, 2, 5], 15))\n"
" ```\n"
"\n"
" ## When to Use\n"
"\n"
" Use this for graphs with `Int` edge weights that may be negative (arbitrage\n"
" detection, time-dependent costs, etc.). For graphs with only non-negative\n"
" weights, prefer `dijkstra.shortest_path_int` which is faster.\n"
).
-spec bellman_ford_int(yog@model:graph(any(), integer()), integer(), integer()) -> bellman_ford_result(integer()).
bellman_ford_int(Graph, Start, Goal) ->
bellman_ford(
Graph,
Start,
Goal,
0,
fun gleam@int:add/2,
fun gleam@int:compare/2
).
-file("src/yog/pathfinding/bellman_ford.gleam", 509).
?DOC(
" Finds shortest path with **float weights**, handling negative edges.\n"
"\n"
" This is a convenience wrapper around `bellman_ford` 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. Prefer `Int` weights for\n"
" critical calculations.\n"
).
-spec bellman_ford_float(yog@model:graph(any(), float()), integer(), integer()) -> bellman_ford_result(float()).
bellman_ford_float(Graph, Start, Goal) ->
bellman_ford(
Graph,
Start,
Goal,
+0.0,
fun gleam@float:add/2,
fun gleam@float:compare/2
).