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(QWE) :: {shortest_path,
yog@pathfinding@utils:path(QWE)} |
negative_cycle |
no_path.
-type implicit_bellman_ford_result(QWF) :: {found_goal, QWF} |
detected_negative_cycle |
no_goal.
-file("src/yog/pathfinding/bellman_ford.gleam", 84).
-spec relaxation_passes(
yog@model:graph(any(), QWM),
list(integer()),
gleam@dict:dict(integer(), QWM),
gleam@dict:dict(integer(), integer()),
integer(),
fun((QWM, QWM) -> QWM),
fun((QWM, QWM) -> gleam@order:order())
) -> {gleam@dict:dict(integer(), QWM), 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(), QWZ),
list(integer()),
gleam@dict:dict(integer(), QWZ),
fun((QWZ, QWZ) -> QWZ),
fun((QWZ, QWZ) -> 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(), QWH),
integer(),
integer(),
QWH,
fun((QWH, QWH) -> QWH),
fun((QWH, QWH) -> gleam@order:order())
) -> bellman_ford_result(QWH).
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(QXP),
gleam@dict:dict(QXP, QXR),
gleam@dict:dict(QXP, integer()),
gleam@set:set(QXP),
fun((QXP) -> list({QXP, QXR})),
fun((QXP) -> boolean()),
QXR,
fun((QXR, QXR) -> QXR),
fun((QXR, QXR) -> gleam@order:order())
) -> implicit_bellman_ford_result(QXR).
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(
QXL,
fun((QXL) -> list({QXL, QXM})),
fun((QXL) -> boolean()),
QXM,
fun((QXM, QXM) -> QXM),
fun((QXM, QXM) -> gleam@order:order())
) -> implicit_bellman_ford_result(QXM).
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(QYE),
gleam@dict:dict(QYG, {QYH, QYE}),
gleam@dict:dict(QYG, integer()),
gleam@set:set(QYE),
fun((QYE) -> list({QYE, QYH})),
fun((QYE) -> QYG),
fun((QYE) -> boolean()),
QYH,
fun((QYH, QYH) -> QYH),
fun((QYH, QYH) -> gleam@order:order())
) -> implicit_bellman_ford_result(QYH).
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(
QXZ,
fun((QXZ) -> list({QXZ, QYA})),
fun((QXZ) -> any()),
fun((QXZ) -> boolean()),
QYA,
fun((QYA, QYA) -> QYA),
fun((QYA, QYA) -> gleam@order:order())
) -> implicit_bellman_ford_result(QYA).
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
).