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(XOK) :: {bi_search_state,
gleam@dict:dict(integer(), XOK),
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), XOK),
gleam@dict:dict(integer(), integer()),
gleam@option:option(integer()),
gleam@option:option(XOK)}.
-file("src/yog/pathfinding/bidirectional.gleam", 137).
-spec get_queue_min_dist(
yog@internal@queue:queue(integer()),
gleam@dict:dict(integer(), integer())
) -> gleam@option:option(integer()).
get_queue_min_dist(Q, Dists) ->
case yog@internal@queue:peek(Q) of
{ok, Node} ->
_pipe = gleam_stdlib:map_get(Dists, Node),
gleam@option:from_result(_pipe);
{error, nil} ->
none
end.
-file("src/yog/pathfinding/bidirectional.gleam", 149).
-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) ->
Can_terminate = case erlang:element(7, State) of
{some, Best} ->
F_min = get_queue_min_dist(Forward_queue, erlang:element(2, State)),
B_min = get_queue_min_dist(Backward_queue, erlang:element(4, State)),
case {F_min, B_min} of
{{some, F}, {some, B}} ->
((F + B) + 1) >= Best;
{_, _} ->
false
end;
none ->
false
end,
case Can_terminate of
true ->
{some, State};
false ->
F_empty = begin
_pipe = yog@internal@queue:pop(Forward_queue),
gleam@result:is_error(_pipe)
end,
B_empty = begin
_pipe@1 = yog@internal@queue:pop(Backward_queue),
gleam@result:is_error(_pipe@1)
end,
case {F_empty, B_empty} of
{true, true} ->
case erlang:element(6, State) of
{some, _} ->
{some, State};
none ->
none
end;
{_, _} ->
Forward_size = maps:size(erlang:element(2, State)),
Backward_size = maps:size(erlang:element(4, State)),
case ((Forward_size =< Backward_size) andalso not F_empty)
orelse B_empty of
true ->
case yog@internal@queue:pop(Forward_queue) of
{error, nil} ->
none;
{ok, {Current, Rest_queue}} ->
Current_dist = begin
_pipe@2 = gleam_stdlib:map_get(
erlang:element(2, State),
Current
),
_pipe@3 = gleam@option:from_result(
_pipe@2
),
gleam@option:unwrap(_pipe@3, 0)
end,
New_state = case gleam@dict:has_key(
erlang:element(4, State),
Current
) of
true ->
Back_dist = begin
_pipe@4 = gleam_stdlib:map_get(
erlang:element(4, State),
Current
),
_pipe@5 = gleam@option:from_result(
_pipe@4
),
gleam@option:unwrap(_pipe@5, 0)
end,
Total = Current_dist + Back_dist,
case erlang:element(7, State) of
{some, Best@1} when Total >= Best@1 ->
State;
_ ->
{bi_search_state,
erlang:element(2, State),
erlang:element(3, State),
erlang:element(4, State),
erlang:element(5, State),
{some, Current},
{some, Total}}
end;
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@6 = gleam_stdlib:map_get(
erlang:element(
4,
S
),
Neighbor
),
_pipe@7 = gleam@option:from_result(
_pipe@6
),
gleam@option:unwrap(
_pipe@7,
0
)
end,
Total@1 = (Current_dist
+ 1)
+ Back_dist@1,
case erlang:element(
7,
S
) of
{some, Best@2} when Total@1 >= Best@2 ->
{Updated_state,
Updated_queue};
_ ->
{{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}
end;
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@8 = gleam_stdlib:map_get(
erlang:element(4, State),
Current@1
),
_pipe@9 = gleam@option:from_result(
_pipe@8
),
gleam@option:unwrap(_pipe@9, 0)
end,
New_state@1 = case gleam@dict:has_key(
erlang:element(2, State),
Current@1
) of
true ->
Fwd_dist = begin
_pipe@10 = gleam_stdlib:map_get(
erlang:element(2, State),
Current@1
),
_pipe@11 = gleam@option:from_result(
_pipe@10
),
gleam@option:unwrap(_pipe@11, 0)
end,
Total@2 = Fwd_dist + Current_dist@1,
case erlang:element(7, State) of
{some, Best@3} when Total@2 >= Best@3 ->
State;
_ ->
{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}}
end;
false ->
State
end,
Predecessors = begin
_pipe@12 = yog@model:predecessors(
Graph,
Current@1
),
gleam@list:map(
_pipe@12,
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@13 = gleam_stdlib:map_get(
erlang:element(
2,
S@1
),
Pred
),
_pipe@14 = gleam@option:from_result(
_pipe@13
),
gleam@option:unwrap(
_pipe@14,
0
)
end,
Total@3 = (Fwd_dist@1
+ Current_dist@1)
+ 1,
case erlang:element(
7,
S@1
) of
{some, Best@4} when Total@3 >= Best@4 ->
{Updated_state@1,
Updated_queue@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}
end;
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
end.
-file("src/yog/pathfinding/bidirectional.gleam", 412).
-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", 430).
-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", 394).
?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", 90).
?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@path: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", 697).
-spec expand_forward(
yog@model:graph(any(), XQU),
yog@internal@pairing_heap:heap({XQU, integer()}),
yog@internal@pairing_heap:heap({XQU, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(XQU),
XQU,
fun((XQU, XQU) -> XQU),
fun((XQU, XQU) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XQU)).
expand_forward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case yog@internal@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@internal@util: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 = yog@internal@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", 538).
-spec do_bidirectional_dijkstra(
yog@model:graph(any(), XPY),
yog@internal@pairing_heap:heap({XPY, integer()}),
yog@internal@pairing_heap:heap({XPY, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(XPY),
XPY,
fun((XPY, XPY) -> XPY),
fun((XPY, XPY) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XPY)).
do_bidirectional_dijkstra(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case {yog@internal@priority_queue:is_empty(Forward_frontier),
yog@internal@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 = yog@internal@priority_queue:peek(Forward_frontier),
Back_min = yog@internal@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", 619).
-spec expand_bidirectional(
yog@model:graph(any(), XQJ),
yog@internal@pairing_heap:heap({XQJ, integer()}),
yog@internal@pairing_heap:heap({XQJ, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(XQJ),
XQJ,
fun((XQJ, XQJ) -> XQJ),
fun((XQJ, XQJ) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XQJ)).
expand_bidirectional(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case {yog@internal@priority_queue:peek(Forward_frontier),
yog@internal@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", 474).
?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(), XPS),
integer(),
integer(),
XPS,
fun((XPS, XPS) -> XPS),
fun((XPS, XPS) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@path:path(XPS)).
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 = yog@internal@priority_queue:new(
fun(A, B) ->
Compare(erlang:element(1, A), erlang:element(1, B))
end
),
yog@internal@priority_queue:push(_pipe@2, {Zero, Start})
end,
Backward_frontier = begin
_pipe@3 = yog@internal@priority_queue:new(
fun(A@1, B@1) ->
Compare(erlang:element(1, A@1), erlang:element(1, B@1))
end
),
yog@internal@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", 824).
-spec expand_backward(
yog@model:graph(any(), XRF),
yog@internal@pairing_heap:heap({XRF, integer()}),
yog@internal@pairing_heap:heap({XRF, integer()}),
gleam@set:set(integer()),
gleam@set:set(integer()),
bi_search_state(XRF),
XRF,
fun((XRF, XRF) -> XRF),
fun((XRF, XRF) -> gleam@order:order())
) -> gleam@option:option(bi_search_state(XRF)).
expand_backward(
Graph,
Forward_frontier,
Backward_frontier,
Forward_settled,
Backward_settled,
State,
Zero,
Add,
Compare
) ->
case yog@internal@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@internal@util: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 = yog@internal@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", 961).
?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@path: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", 982).
?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@path: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
).