Current section
Files
Jump to
Current section
Files
src/yog@pathfinding@bidirectional.erl
-module(yog@pathfinding@bidirectional).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/bidirectional.gleam").
-export([shortest_path_unweighted/3, shortest_path/6, shortest_path_int/3, shortest_path_float/3]).
-export_type([bi_search_state/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(
" [Bidirectional search](https://en.wikipedia.org/wiki/Bidirectional_search) algorithms\n"
" that meet in the middle for dramatic speedup.\n"
"\n"
" These algorithms start two simultaneous searches - one from the source\n"
" and one from the target - that meet in the middle. This can dramatically\n"
" reduce the search space compared to single-direction search.\n"
"\n"
" ## Performance Benefits\n"
"\n"
" For a graph with branching factor b and depth d:\n"
" - **Standard BFS**: O(b^d) nodes explored\n"
" - **Bidirectional BFS**: O(2 × b^(d/2)) nodes explored\n"
"\n"
" **Example** with b=10, d=6:\n"
" - Standard: 10^6 = 1,000,000 nodes\n"
" - Bidirectional: 2 × 10^3 = 2,000 nodes (500× faster!)\n"
"\n"
" ## Algorithms\n"
"\n"
" | Algorithm | Function | Complexity | Best For |\n"
" |-----------|----------|------------|----------|\n"
" | Bidirectional BFS | `shortest_path_unweighted/3` | O(b^(d/2)) | Unweighted graphs |\n"
" | Bidirectional Dijkstra | `shortest_path/6` | O(b^(d/2) log b) | Weighted graphs |\n"
"\n"
" ## Requirements\n"
"\n"
" - Graph must be connected (otherwise no path exists)\n"
" - For directed graphs: needs efficient reverse edge lookup (yog's `in_edges` structure is perfect!)\n"
" - Target node must be known in advance\n"
"\n"
" ## Termination\n"
"\n"
" The tricky part of bidirectional search is knowing when to stop:\n"
" - **BFS**: Can stop as soon as frontiers touch\n"
" - **Dijkstra**: Must continue until minimum distances from both sides exceed best path found\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Bidirectional Search](https://en.wikipedia.org/wiki/Bidirectional_search)\n"
" - [Red Blob Games: Meeting in the Middle](https://www.redblobgames.com/pathfinding/a-star/introduction.html#bidirectional-search)\n"
" - [Ira Pohl (1971): Bi-directional Search](https://api.semanticscholar.org/CorpusID:60374980)\n"
).
-type bi_search_state(VVW) :: {bi_search_state,
gleam@dict:dict(integer(), VVW),
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), VVW),
gleam@dict:dict(integer(), integer()),
gleam@option:option(integer()),
gleam@option:option(VVW)}.
-file("src/yog/pathfinding/bidirectional.gleam", 135).
-spec do_bidirectional_bfs(
yog@model:graph(any(), any()),
yog@internal@queue:queue(integer()),
yog@internal@queue:queue(integer()),
bi_search_state(integer())
) -> gleam@option:option(bi_search_state(integer())).
do_bidirectional_bfs(Graph, Forward_queue, Backward_queue, State) ->
case erlang:element(6, State) of
{some, _} ->
{some, State};
none ->
Forward_size = maps:size(erlang:element(2, State)),
Backward_size = maps:size(erlang:element(4, State)),
case Forward_size =< Backward_size of
true ->
case yog@internal@queue:pop(Forward_queue) of
{error, nil} ->
none;
{ok, {Current, Rest_queue}} ->
Current_dist = begin
_pipe = gleam_stdlib:map_get(
erlang:element(2, State),
Current
),
_pipe@1 = gleam@option:from_result(_pipe),
gleam@option:unwrap(_pipe@1, 0)
end,
New_state = case gleam@dict:has_key(
erlang:element(4, State),
Current
) of
true ->
Back_dist = begin
_pipe@2 = gleam_stdlib:map_get(
erlang:element(4, State),
Current
),
_pipe@3 = gleam@option:from_result(
_pipe@2
),
gleam@option:unwrap(_pipe@3, 0)
end,
Total = Current_dist + Back_dist,
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current},
{some, Total}};
false ->
State
end,
Neighbors = yog@model:successor_ids(Graph, Current),
{Next_state, Next_queue} = gleam@list:fold(
Neighbors,
{New_state, Rest_queue},
fun(Acc, Neighbor) ->
{S, Q} = Acc,
case gleam@dict:has_key(
erlang:element(2, S),
Neighbor
) of
true ->
{S, Q};
false ->
Updated_state = {bi_search_state,
gleam@dict:insert(
erlang:element(2, S),
Neighbor,
Current_dist + 1
),
gleam@dict:insert(
erlang:element(3, S),
Neighbor,
Current
),
erlang:element(4, S),
erlang:element(5, S),
erlang:element(6, S),
erlang:element(7, S)},
Updated_queue = yog@internal@queue:push(
Q,
Neighbor
),
case gleam@dict:has_key(
erlang:element(4, S),
Neighbor
) of
true ->
Back_dist@1 = begin
_pipe@4 = gleam_stdlib:map_get(
erlang:element(4, S),
Neighbor
),
_pipe@5 = gleam@option:from_result(
_pipe@4
),
gleam@option:unwrap(
_pipe@5,
0
)
end,
Total@1 = (Current_dist + 1)
+ Back_dist@1,
{{bi_search_state,
erlang:element(
2,
Updated_state
),
erlang:element(
3,
Updated_state
),
erlang:element(
4,
Updated_state
),
erlang:element(
5,
Updated_state
),
{some, Neighbor},
{some, Total@1}},
Updated_queue};
false ->
{Updated_state,
Updated_queue}
end
end
end
),
do_bidirectional_bfs(
Graph,
Next_queue,
Backward_queue,
Next_state
)
end;
false ->
case yog@internal@queue:pop(Backward_queue) of
{error, nil} ->
none;
{ok, {Current@1, Rest_queue@1}} ->
Current_dist@1 = begin
_pipe@6 = gleam_stdlib:map_get(
erlang:element(4, State),
Current@1
),
_pipe@7 = gleam@option:from_result(_pipe@6),
gleam@option:unwrap(_pipe@7, 0)
end,
New_state@1 = case gleam@dict:has_key(
erlang:element(2, State),
Current@1
) of
true ->
Fwd_dist = begin
_pipe@8 = gleam_stdlib:map_get(
erlang:element(2, State),
Current@1
),
_pipe@9 = gleam@option:from_result(
_pipe@8
),
gleam@option:unwrap(_pipe@9, 0)
end,
Total@2 = Fwd_dist + Current_dist@1,
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current@1},
{some, Total@2}};
false ->
State
end,
Predecessors = begin
_pipe@10 = yog@model:predecessors(
Graph,
Current@1
),
gleam@list:map(
_pipe@10,
fun(P) -> erlang:element(1, P) end
)
end,
{Next_state@1, Next_queue@1} = gleam@list:fold(
Predecessors,
{New_state@1, Rest_queue@1},
fun(Acc@1, Pred) ->
{S@1, Q@1} = Acc@1,
case gleam@dict:has_key(
erlang:element(4, S@1),
Pred
) of
true ->
{S@1, Q@1};
false ->
Updated_state@1 = {bi_search_state,
erlang:element(2, S@1),
erlang:element(3, S@1),
gleam@dict:insert(
erlang:element(4, S@1),
Pred,
Current_dist@1 + 1
),
gleam@dict:insert(
erlang:element(5, S@1),
Pred,
Current@1
),
erlang:element(6, S@1),
erlang:element(7, S@1)},
Updated_queue@1 = yog@internal@queue:push(
Q@1,
Pred
),
case gleam@dict:has_key(
erlang:element(2, S@1),
Pred
) of
true ->
Fwd_dist@1 = begin
_pipe@11 = gleam_stdlib:map_get(
erlang:element(
2,
S@1
),
Pred
),
_pipe@12 = gleam@option:from_result(
_pipe@11
),
gleam@option:unwrap(
_pipe@12,
0
)
end,
Total@3 = (Fwd_dist@1 + Current_dist@1)
+ 1,
{{bi_search_state,
erlang:element(
2,
Updated_state@1
),
erlang:element(
3,
Updated_state@1
),
erlang:element(
4,
Updated_state@1
),
erlang:element(
5,
Updated_state@1
),
{some, Pred},
{some, Total@3}},
Updated_queue@1};
false ->
{Updated_state@1,
Updated_queue@1}
end
end
end
),
do_bidirectional_bfs(
Graph,
Forward_queue,
Next_queue@1,
Next_state@1
)
end
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 342).
-spec build_path_to_meeting(
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
list(integer())
) -> list(integer()).
build_path_to_meeting(Parent_map, Start, Current, Acc) ->
case Current =:= Start of
true ->
[Start | Acc];
false ->
case gleam_stdlib:map_get(Parent_map, Current) of
{ok, Parent} ->
build_path_to_meeting(
Parent_map,
Start,
Parent,
[Current | Acc]
);
{error, nil} ->
[Current | Acc]
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 360).
-spec build_path_from_meeting(
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
list(integer())
) -> list(integer()).
build_path_from_meeting(Parent_map, Current, Goal, Acc) ->
case Current =:= Goal of
true ->
lists:reverse(Acc);
false ->
case gleam_stdlib:map_get(Parent_map, Current) of
{ok, Child} ->
build_path_from_meeting(
Parent_map,
Child,
Goal,
[Child | Acc]
);
{error, nil} ->
lists:reverse(Acc)
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 324).
?DOC(" Reconstructs the path from bidirectional search by combining forward and backward paths\n").
-spec reconstruct_bidirectional_path(
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
integer()
) -> list(integer()).
reconstruct_bidirectional_path(
Forward_parent,
Backward_parent,
Start,
Goal,
Meeting
) ->
Forward_path = build_path_to_meeting(Forward_parent, Start, Meeting, []),
Backward_path = build_path_from_meeting(Backward_parent, Meeting, Goal, []),
lists:append(Forward_path, Backward_path).
-file("src/yog/pathfinding/bidirectional.gleam", 88).
?DOC(
" Finds the shortest path in an unweighted graph using bidirectional BFS.\n"
"\n"
" This runs BFS from both source and target simultaneously, stopping when\n"
" the frontiers meet. Much faster than single-direction BFS for long paths.\n"
"\n"
" **Time Complexity:** O(b^(d/2)) where b is branching factor and d is depth\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" bidirectional.shortest_path_unweighted(\n"
" in: graph,\n"
" from: 1,\n"
" to: 100\n"
" )\n"
" // => Some(Path([1, 5, 20, 100], 3))\n"
" ```\n"
).
-spec shortest_path_unweighted(
yog@model:graph(any(), any()),
integer(),
integer()
) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path_unweighted(Graph, Start, Goal) ->
case Start =:= Goal of
true ->
{some, {path, [Start], 0}};
false ->
Initial_state = {bi_search_state,
begin
_pipe = maps:new(),
gleam@dict:insert(_pipe, Start, 0)
end,
maps:new(),
begin
_pipe@1 = maps:new(),
gleam@dict:insert(_pipe@1, Goal, 0)
end,
maps:new(),
none,
none},
Forward_queue = begin
_pipe@2 = yog@internal@queue:new(),
yog@internal@queue:push(_pipe@2, Start)
end,
Backward_queue = begin
_pipe@3 = yog@internal@queue:new(),
yog@internal@queue:push(_pipe@3, Goal)
end,
_pipe@4 = do_bidirectional_bfs(
Graph,
Forward_queue,
Backward_queue,
Initial_state
),
gleam@option:map(
_pipe@4,
fun(State) -> case erlang:element(6, State) of
{some, Meeting} ->
Path = reconstruct_bidirectional_path(
erlang:element(3, State),
erlang:element(5, State),
Start,
Goal,
Meeting
),
Length = case erlang:element(7, State) of
{some, Len} ->
Len;
none ->
erlang:length(Path) - 1
end,
{path, Path, Length};
none ->
{path, [], 0}
end end
)
end.
-file("src/yog/pathfinding/bidirectional.gleam", 627).
-spec expand_forward(
yog@model:graph(any(), VYC),
gleamy@pairing_heap:heap({VYC, integer()}),
gleamy@pairing_heap:heap({VYC, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(VYC),
VYC,
fun((VYC, VYC) -> VYC),
fun((VYC, VYC) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(VYC)).
expand_forward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case gleamy@priority_queue:pop(Forward_frontier) of
{error, nil} ->
do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
{ok, {{Dist, Current}, Rest_frontier}} ->
case gleam@set:contains(Forward_settled, Current) of
true ->
do_bidirectional_dijkstra(
Graph,
Rest_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
false ->
New_settled = gleam@set:insert(Forward_settled, Current),
Updated_state = case gleam_stdlib:map_get(
erlang:element(4, State),
Current
) of
{ok, Back_dist} ->
Total = Add(Dist, Back_dist),
case erlang:element(7, State) of
{some, Best} ->
case Compare(Total, Best) of
lt ->
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current},
{some, Total}};
_ ->
State
end;
none ->
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current},
{some, Total}}
end;
{error, nil} ->
State
end,
Neighbors = yog@model:successors(Graph, Current),
{Next_state, Next_frontier} = gleam@list:fold(
Neighbors,
{Updated_state, Rest_frontier},
fun(Acc, Neighbor) ->
{S, Frontier} = Acc,
{Next_id, Weight} = Neighbor,
New_dist = Add(Dist, Weight),
case yog@pathfinding@utils:should_explore_node(
erlang:element(2, S),
Next_id,
New_dist,
Compare
) of
true ->
New_s = {bi_search_state,
gleam@dict:insert(
erlang:element(2, S),
Next_id,
New_dist
),
gleam@dict:insert(
erlang:element(3, S),
Next_id,
Current
),
erlang:element(4, S),
erlang:element(5, S),
erlang:element(6, S),
erlang:element(7, S)},
New_frontier = gleamy@priority_queue:push(
Frontier,
{New_dist, Next_id}
),
{New_s, New_frontier};
false ->
{S, Frontier}
end
end
),
do_bidirectional_dijkstra(
Graph,
Next_frontier,
Backward_frontier,
New_settled,
Backward_settled,
Next_state,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 468).
-spec do_bidirectional_dijkstra(
yog@model:graph(any(), VXG),
gleamy@pairing_heap:heap({VXG, integer()}),
gleamy@pairing_heap:heap({VXG, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(VXG),
VXG,
fun((VXG, VXG) -> VXG),
fun((VXG, VXG) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(VXG)).
do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case {gleamy@priority_queue:is_empty(Forward_frontier),
gleamy@priority_queue:is_empty(Backward_frontier)} of
{true, true} ->
case erlang:element(6, State) of
{some, _} ->
{some, State};
none ->
none
end;
{_, _} ->
case erlang:element(7, State) of
{some, Best} ->
Fwd_min = gleamy@priority_queue:peek(Forward_frontier),
Back_min = gleamy@priority_queue:peek(Backward_frontier),
case {Fwd_min, Back_min} of
{{ok, {Fd, _}}, {ok, {Bd, _}}} ->
Sum = Add(Fd, Bd),
case Compare(Sum, Best) of
lt ->
expand_bidirectional(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
eq ->
expand_bidirectional(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
gt ->
{some, State}
end;
{_, _} ->
expand_bidirectional(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
)
end;
none ->
expand_bidirectional(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 549).
-spec expand_bidirectional(
yog@model:graph(any(), VXR),
gleamy@pairing_heap:heap({VXR, integer()}),
gleamy@pairing_heap:heap({VXR, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(VXR),
VXR,
fun((VXR, VXR) -> VXR),
fun((VXR, VXR) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(VXR)).
expand_bidirectional(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case {gleamy@priority_queue:peek(Forward_frontier),
gleamy@priority_queue:peek(Backward_frontier)} of
{{ok, {Fwd_dist, _}}, {ok, {Back_dist, _}}} ->
case Compare(Fwd_dist, Back_dist) of
lt ->
expand_forward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
eq ->
expand_forward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
gt ->
expand_backward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
)
end;
{{ok, _}, {error, nil}} ->
expand_forward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
{{error, nil}, {ok, _}} ->
expand_backward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
{{error, nil}, {error, nil}} ->
case erlang:element(6, State) of
{some, _} ->
{some, State};
none ->
none
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 404).
?DOC(
" Finds the shortest path in a weighted graph using bidirectional Dijkstra.\n"
"\n"
" This is trickier than bidirectional BFS because we can't stop as soon\n"
" as the frontiers meet - we must continue until we can prove optimality.\n"
"\n"
" **Time Complexity:** O((V + E) log V / 2) - approximately 2x faster than standard Dijkstra\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"
" bidirectional.shortest_path(\n"
" in: graph,\n"
" from: 1,\n"
" to: 100,\n"
" with_zero: 0,\n"
" with_add: int.add,\n"
" with_compare: int.compare\n"
" )\n"
" // => Some(Path([1, 5, 20, 100], 42))\n"
" ```\n"
).
-spec shortest_path(
yog@model:graph(any(), VXA),
integer(),
integer(),
VXA,
fun((VXA, VXA) -> VXA),
fun((VXA, VXA) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@utils:path(VXA)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
case Start =:= Goal of
true ->
{some, {path, [Start], Zero}};
false ->
Initial_state = {bi_search_state,
begin
_pipe = maps:new(),
gleam@dict:insert(_pipe, Start, Zero)
end,
maps:new(),
begin
_pipe@1 = maps:new(),
gleam@dict:insert(_pipe@1, Goal, Zero)
end,
maps:new(),
none,
none},
Forward_frontier = begin
_pipe@2 = gleamy@priority_queue:new(
fun(A, B) ->
Compare(erlang:element(1, A), erlang:element(1, B))
end
),
gleamy@priority_queue:push(_pipe@2, {Zero, Start})
end,
Backward_frontier = begin
_pipe@3 = gleamy@priority_queue:new(
fun(A@1, B@1) ->
Compare(erlang:element(1, A@1), erlang:element(1, B@1))
end
),
gleamy@priority_queue:push(_pipe@3, {Zero, Goal})
end,
_pipe@4 = do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Backward_frontier,
gleam@set:new(),
gleam@set:new(),
Initial_state,
Zero,
Add,
Compare
),
gleam@option:map(
_pipe@4,
fun(State) ->
case {erlang:element(6, State), erlang:element(7, State)} of
{{some, Meeting}, {some, Length}} ->
Path = reconstruct_bidirectional_path(
erlang:element(3, State),
erlang:element(5, State),
Start,
Goal,
Meeting
),
{path, Path, Length};
{_, _} ->
{path, [], Zero}
end
end
)
end.
-file("src/yog/pathfinding/bidirectional.gleam", 754).
-spec expand_backward(
yog@model:graph(any(), VYN),
gleamy@pairing_heap:heap({VYN, integer()}),
gleamy@pairing_heap:heap({VYN, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(VYN),
VYN,
fun((VYN, VYN) -> VYN),
fun((VYN, VYN) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(VYN)).
expand_backward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case gleamy@priority_queue:pop(Backward_frontier) of
{error, nil} ->
do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
{ok, {{Dist, Current}, Rest_frontier}} ->
case gleam@set:contains(Backward_settled, Current) of
true ->
do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Rest_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
);
false ->
New_settled = gleam@set:insert(Backward_settled, Current),
Updated_state = case gleam_stdlib:map_get(
erlang:element(2, State),
Current
) of
{ok, Fwd_dist} ->
Total = Add(Fwd_dist, Dist),
case erlang:element(7, State) of
{some, Best} ->
case Compare(Total, Best) of
lt ->
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current},
{some, Total}};
_ ->
State
end;
none ->
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current},
{some, Total}}
end;
{error, nil} ->
State
end,
Predecessors = yog@model:predecessors(Graph, Current),
{Next_state, Next_frontier} = gleam@list:fold(
Predecessors,
{Updated_state, Rest_frontier},
fun(Acc, Pred) ->
{S, Frontier} = Acc,
{Pred_id, Weight} = Pred,
New_dist = Add(Dist, Weight),
case yog@pathfinding@utils:should_explore_node(
erlang:element(4, S),
Pred_id,
New_dist,
Compare
) of
true ->
New_s = {bi_search_state,
erlang:element(2, S),
erlang:element(3, S),
gleam@dict:insert(
erlang:element(4, S),
Pred_id,
New_dist
),
gleam@dict:insert(
erlang:element(5, S),
Pred_id,
Current
),
erlang:element(6, S),
erlang:element(7, S)},
New_frontier = gleamy@priority_queue:push(
Frontier,
{New_dist, Pred_id}
),
{New_s, New_frontier};
false ->
{S, Frontier}
end
end
),
do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Next_frontier,
Forward_settled,
New_settled,
Next_state,
Zero,
Add,
Compare
)
end
end.
-file("src/yog/pathfinding/bidirectional.gleam", 891).
?DOC(
" Finds the shortest path using bidirectional Dijkstra with **integer weights**.\n"
"\n"
" Convenience wrapper that uses:\n"
" - `0` as the zero element\n"
" - `int.add` for addition\n"
" - `int.compare` for comparison\n"
).
-spec shortest_path_int(yog@model:graph(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path_int(Graph, Start, Goal) ->
shortest_path(
Graph,
Start,
Goal,
0,
fun gleam@int:add/2,
fun gleam@int:compare/2
).
-file("src/yog/pathfinding/bidirectional.gleam", 912).
?DOC(
" Finds the shortest path using bidirectional Dijkstra with **float weights**.\n"
"\n"
" Convenience wrapper that uses:\n"
" - `0.0` as the zero element\n"
" - `float.add` for addition\n"
" - `float.compare` for comparison\n"
).
-spec shortest_path_float(yog@model:graph(any(), float()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(float())).
shortest_path_float(Graph, Start, Goal) ->
shortest_path(
Graph,
Start,
Goal,
+0.0,
fun gleam@float:add/2,
fun gleam@float:compare/2
).