-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, distance_matrix/5, implicit_dijkstra/6, implicit_dijkstra_by/7, implicit_a_star/7, implicit_a_star_by/8, implicit_bellman_ford/6, implicit_bellman_ford_by/7]). -export_type([path/1, 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. -type path(LXU) :: {path, list(integer()), LXU}. -type bellman_ford_result(LXV) :: {shortest_path, path(LXV)} | negative_cycle | no_path. -type implicit_bellman_ford_result(LXW) :: {found_goal, LXW} | detected_negative_cycle | no_goal. -file("src/yog/pathfinding.gleam", 99). -spec compare_frontier( {LYN, list(integer())}, {LYN, list(integer())}, fun((LYN, LYN) -> 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", 107). -spec compare_distance_frontier( {LYQ, integer()}, {LYQ, integer()}, fun((LYQ, LYQ) -> gleam@order:order()) ) -> gleam@order:order(). compare_distance_frontier(A, B, Cmp) -> Cmp(erlang:element(1, A), erlang:element(1, B)). -file("src/yog/pathfinding.gleam", 115). -spec compare_a_star_frontier( {LYR, LYR, list(integer())}, {LYR, LYR, list(integer())}, fun((LYR, LYR) -> gleam@order:order()) ) -> gleam@order:order(). compare_a_star_frontier(A, B, Cmp) -> Cmp(erlang:element(1, A), erlang:element(1, B)). -file("src/yog/pathfinding.gleam", 125). ?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(), LYU), integer(), LYU, fun((LYU, LYU) -> 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(), LYE), integer(), gleamy@pairing_heap:heap({LYE, list(integer())}), gleam@dict:dict(integer(), LYE), fun((LYE, LYE) -> LYE), fun((LYE, LYE) -> gleam@order:order()) ) -> gleam@option:option(path(LYE)). do_dijkstra(Graph, Goal, Frontier, Visited, Add, Compare) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> none; {ok, {{Dist, [Current | _] = Path}, Rest_frontier}} -> 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 = yog@model:successors(Graph, Current), gleam@list:fold( _pipe, Rest_frontier, fun(H, Neighbor) -> {Next_id, Weight} = Neighbor, gleamy@priority_queue:push( H, {Add(Dist, Weight), [Next_id | Path]} ) end ) end, do_dijkstra( Graph, Goal, Next_frontier, New_visited, Add, Compare ) end end; {ok, _} -> none end. -file("src/yog/pathfinding.gleam", 41). ?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(), LXY), integer(), integer(), LXY, fun((LXY, LXY) -> LXY), fun((LXY, LXY) -> gleam@order:order()) ) -> gleam@option:option(path(LXY)). shortest_path(Graph, Start, Goal, Zero, Add, Compare) -> Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> compare_frontier(A, B, Compare) end ), gleamy@priority_queue:push(_pipe, {Zero, [Start]}) end, do_dijkstra(Graph, Goal, Frontier, maps:new(), Add, Compare). -file("src/yog/pathfinding.gleam", 200). -spec do_single_source_dijkstra( yog@model:graph(any(), LZE), gleamy@pairing_heap:heap({LZE, integer()}), gleam@dict:dict(integer(), LZE), fun((LZE, LZE) -> LZE), fun((LZE, LZE) -> gleam@order:order()) ) -> gleam@dict:dict(integer(), LZE). do_single_source_dijkstra(Graph, Frontier, Distances, Add, Compare) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> Distances; {ok, {{Dist, Current}, Rest_frontier}} -> 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 = yog@model:successors(Graph, Current), gleam@list:fold( _pipe, Rest_frontier, fun(H, Neighbor) -> {Next_id, Weight} = Neighbor, gleamy@priority_queue:push( H, {Add(Dist, Weight), Next_id} ) end ) end, do_single_source_dijkstra( Graph, Next_frontier, New_distances, Add, Compare ) end end. -file("src/yog/pathfinding.gleam", 186). ?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(), LYY), integer(), LYY, fun((LYY, LYY) -> LYY), fun((LYY, LYY) -> gleam@order:order()) ) -> gleam@dict:dict(integer(), LYY). single_source_distances(Graph, Source, Zero, Add, Compare) -> Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> compare_distance_frontier(A, B, Compare) end ), gleamy@priority_queue:push(_pipe, {Zero, Source}) end, do_single_source_dijkstra(Graph, Frontier, maps:new(), Add, Compare). -file("src/yog/pathfinding.gleam", 295). -spec do_a_star( yog@model:graph(any(), MIY), integer(), gleamy@pairing_heap:heap({MIV, MIV, list(integer())}), gleam@dict:dict(integer(), MIV), fun((MIV, MIY) -> MIV), fun((MIV, MIV) -> gleam@order:order()), fun((integer(), integer()) -> MIY) ) -> gleam@option:option(path(MIV)). do_a_star(Graph, Goal, Frontier, Visited, Add, Compare, H) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> none; {ok, {{_, Dist, [Current | _] = Path}, Rest_frontier}} -> 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 = yog@model:successors(Graph, Current), gleam@list:fold( _pipe, Rest_frontier, fun(Acc_h, Neighbor) -> {Next_id, Weight} = Neighbor, Next_dist = Add(Dist, Weight), F_score = Add( Next_dist, H(Next_id, Goal) ), gleamy@priority_queue:push( Acc_h, {F_score, Next_dist, [Next_id | Path]} ) end ) end, do_a_star( Graph, Goal, Next_frontier, New_visited, Add, Compare, H ) end end; _ -> none end. -file("src/yog/pathfinding.gleam", 278). ?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(), LZN), integer(), integer(), LZN, fun((LZN, LZN) -> LZN), fun((LZN, LZN) -> gleam@order:order()), fun((integer(), integer()) -> LZN) ) -> gleam@option:option(path(LZN)). a_star(Graph, Start, Goal, Zero, Add, Compare, H) -> Initial_f = H(Start, Goal), Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> compare_a_star_frontier(A, B, Compare) end ), gleamy@priority_queue:push(_pipe, {Initial_f, Zero, [Start]}) end, do_a_star(Graph, Goal, Frontier, maps:new(), Add, Compare, H). -file("src/yog/pathfinding.gleam", 420). -spec relaxation_passes( yog@model:graph(any(), MAG), list(integer()), gleam@dict:dict(integer(), MAG), gleam@dict:dict(integer(), integer()), integer(), fun((MAG, MAG) -> MAG), fun((MAG, MAG) -> gleam@order:order()) ) -> {gleam@dict:dict(integer(), MAG), 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", 478). -spec has_negative_cycle( yog@model:graph(any(), MAT), list(integer()), gleam@dict:dict(integer(), MAT), fun((MAT, MAT) -> MAT), fun((MAT, MAT) -> 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", 508). -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", 379). ?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(), MAB), integer(), integer(), MAB, fun((MAB, MAB) -> MAB), fun((MAB, MAB) -> gleam@order:order()) ) -> bellman_ford_result(MAB). 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", 692). ?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(), integer()}, MBN), list(integer()), MBN, fun((MBN, MBN) -> gleam@order:order()) ) -> boolean(). detect_negative_cycle(Distances, Nodes, Zero, Compare) -> _pipe = Nodes, gleam@list:any( _pipe, fun(I) -> case gleam_stdlib:map_get(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", 611). ?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(), MBG), MBG, fun((MBG, MBG) -> MBG), fun((MBG, MBG) -> gleam@order:order()) ) -> {ok, gleam@dict:dict({integer(), integer()}, MBG)} | {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) -> _pipe@1 = Nodes, gleam@list:fold( _pipe@1, Distances, fun(Distances@1, 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( Distances@1, {I, J}, Weight ); _ -> gleam@dict:insert( Distances@1, {I, J}, Zero ) end; {error, nil} -> gleam@dict:insert( Distances@1, {I, J}, Zero ) end; {error, nil} -> gleam@dict:insert( Distances@1, {I, 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( Distances@1, {I, J}, Weight@1 ); {error, nil} -> Distances@1 end; {error, nil} -> Distances@1 end end end ) end) end, Final_distances = begin _pipe@2 = Nodes, gleam@list:fold( _pipe@2, Initial_distances, fun(Distances@2, K) -> _pipe@3 = Nodes, gleam@list:fold( _pipe@3, Distances@2, fun(Distances@3, I@1) -> _pipe@4 = Nodes, gleam@list:fold( _pipe@4, Distances@3, fun(Distances@4, J@1) -> case gleam_stdlib:map_get(Distances@4, {I@1, K}) of {error, nil} -> Distances@4; {ok, Dist_ik} -> case gleam_stdlib:map_get( Distances@4, {K, J@1} ) of {error, nil} -> Distances@4; {ok, Dist_kj} -> New_dist = Add(Dist_ik, Dist_kj), case gleam_stdlib:map_get( Distances@4, {I@1, J@1} ) of {error, nil} -> gleam@dict:insert( Distances@4, {I@1, J@1}, New_dist ); {ok, Current_dist} -> case Compare( New_dist, Current_dist ) of lt -> gleam@dict:insert( Distances@4, {I@1, J@1}, New_dist ); _ -> Distances@4 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. -file("src/yog/pathfinding.gleam", 778). ?DOC( " Computes shortest distances between all pairs of points of interest.\n" "\n" " Automatically chooses the most efficient algorithm based on the density\n" " of points of interest relative to the total graph size:\n" " - When POIs are dense (> 1/3 of nodes): Uses Floyd-Warshall O(V³)\n" " - When POIs are sparse (≤ 1/3 of nodes): Uses multiple single-source Dijkstra O(P × (V+E) log V)\n" "\n" " Returns only distances between the specified points of interest, not all node pairs.\n" "\n" " **Time Complexity:** Automatically optimized based on POI density\n" "\n" " ## Parameters\n" "\n" " - `between`: List of points of interest (POI) nodes\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" " ## Returns\n" "\n" " - `Ok(distances)`: Dictionary mapping POI pairs to their shortest distances\n" " - `Error(Nil)`: If a negative cycle is detected (only when using Floyd-Warshall)\n" "\n" " ## Example\n" "\n" " ```gleam\n" " import gleam/dict\n" " import yog\n" " import yog/pathfinding\n" "\n" " // Graph with many nodes, but only care about distances between a few POIs\n" " let graph = build_large_graph() // 1000 nodes\n" " let pois = [1, 5, 10, 42] // 4 points of interest\n" "\n" " // Efficiently computes only POI-to-POI distances\n" " case pathfinding.distance_matrix(\n" " in: graph,\n" " between: pois,\n" " with_zero: 0,\n" " with_add: int.add,\n" " with_compare: int.compare\n" " ) {\n" " Ok(distances) -> {\n" " // Get distance from POI 1 to POI 42\n" " dict.get(distances, #(1, 42))\n" " }\n" " Error(Nil) -> panic as \"Negative cycle detected\"\n" " }\n" " ```\n" "\n" " ## Use Cases\n" "\n" " - AoC 2016 Day 24: Computing distances between numbered locations\n" " - TSP-like problems: Finding optimal tour through specific landmarks\n" " - Network analysis: Distances between server hubs\n" " - Game pathfinding: Distances between quest objectives\n" "\n" " ## Algorithm Selection\n" "\n" " The function automatically chooses the optimal algorithm:\n" " - **Floyd-Warshall** when POIs are dense: Computes all-pairs shortest paths once,\n" " then filters to POIs. Efficient when you need distances for most nodes.\n" " - **Multiple Dijkstra** when POIs are sparse: Runs single-source shortest paths\n" " from each POI. Efficient when POIs are much fewer than total nodes.\n" ). -spec distance_matrix( yog@model:graph(any(), MBS), list(integer()), MBS, fun((MBS, MBS) -> MBS), fun((MBS, MBS) -> gleam@order:order()) ) -> {ok, gleam@dict:dict({integer(), integer()}, MBS)} | {error, nil}. distance_matrix(Graph, Points_of_interest, Zero, Add, Compare) -> Num_nodes = maps:size(erlang:element(3, Graph)), Num_pois = erlang:length(Points_of_interest), Poi_set = gleam@set:from_list(Points_of_interest), case (Num_pois * 3) > Num_nodes of true -> case floyd_warshall(Graph, Zero, Add, Compare) of {error, nil} -> {error, nil}; {ok, All_distances} -> Poi_distances = gleam@dict:filter( All_distances, fun(Key, _) -> {From_node, To_node} = Key, gleam@set:contains(Poi_set, From_node) andalso gleam@set:contains( Poi_set, To_node ) end ), {ok, Poi_distances} end; false -> Result = gleam@list:fold( Points_of_interest, maps:new(), fun(Acc, Source) -> Distances = single_source_distances( Graph, Source, Zero, Add, Compare ), gleam@list:fold( Points_of_interest, Acc, fun(Acc2, Target) -> case gleam_stdlib:map_get(Distances, Target) of {ok, Dist} -> gleam@dict:insert( Acc2, {Source, Target}, Dist ); {error, nil} -> Acc2 end end ) end ), {ok, Result} end. -file("src/yog/pathfinding.gleam", 918). -spec do_implicit_dijkstra( gleamy@pairing_heap:heap({MCE, MCF}), gleam@dict:dict(MCF, MCE), fun((MCF) -> list({MCF, MCE})), fun((MCF) -> boolean()), fun((MCE, MCE) -> MCE), fun((MCE, MCE) -> gleam@order:order()) ) -> gleam@option:option(MCE). do_implicit_dijkstra(Frontier, Distances, Successors, Is_goal, Add, Compare) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> none; {ok, {{Dist, Current}, Rest_frontier}} -> case Is_goal(Current) of true -> {some, Dist}; false -> Should_explore = case gleam_stdlib:map_get( Distances, Current ) of {ok, Prev_dist} -> case Compare(Dist, Prev_dist) of lt -> true; _ -> false end; {error, nil} -> true end, case Should_explore of false -> do_implicit_dijkstra( Rest_frontier, Distances, Successors, Is_goal, Add, Compare ); true -> New_distances = gleam@dict:insert( Distances, Current, Dist ), Next_frontier = begin _pipe = Successors(Current), gleam@list:fold( _pipe, Rest_frontier, fun(H, Neighbor) -> {Next_state, Cost} = Neighbor, gleamy@priority_queue:push( H, {Add(Dist, Cost), Next_state} ) end ) end, do_implicit_dijkstra( Next_frontier, New_distances, Successors, Is_goal, Add, Compare ) end end end. -file("src/yog/pathfinding.gleam", 901). ?DOC( " Finds the shortest path in an implicit graph using Dijkstra's algorithm.\n" "\n" " Unlike `shortest_path`, this does not require a materialized `Graph` value.\n" " Instead, you provide a `successors_with_cost` function that computes weighted\n" " neighbors on demand — ideal for state-space search, puzzles, or graphs too\n" " large to build upfront.\n" "\n" " Returns the shortest distance to any state satisfying `is_goal`, or `None`\n" " if no goal state is reachable.\n" "\n" " **Time Complexity:** O((V + E) log V) where V is visited states and E is explored transitions\n" "\n" " ## Parameters\n" "\n" " - `successors_with_cost`: Function that generates weighted successors for a state\n" " - `is_goal`: Predicate that identifies goal states\n" " - `zero`: The identity element for addition (e.g., 0 for integers)\n" " - `add`: Function to add two costs\n" " - `compare`: Function to compare two costs\n" "\n" " ## Example\n" "\n" " ```gleam\n" " // Find shortest path in a state-space where each state is (x, y, collected_keys)\n" " type State { State(x: Int, y: Int, keys: Int) }\n" "\n" " pathfinding.implicit_dijkstra(\n" " from: State(0, 0, 0),\n" " successors_with_cost: fn(state) {\n" " // Generate neighbor states with their costs\n" " [\n" " #(State(state.x + 1, state.y, state.keys), 1),\n" " #(State(state.x, state.y + 1, state.keys), 1),\n" " // ... more neighbors\n" " ]\n" " },\n" " is_goal: fn(state) { state.keys == all_keys_mask },\n" " with_zero: 0,\n" " with_add: int.add,\n" " with_compare: int.compare,\n" " )\n" " // => Some(42) // Shortest distance to goal\n" " ```\n" "\n" " ## Use Cases\n" "\n" " - Puzzle solving: State-space search for optimal solutions\n" " - Game AI: Pathfinding with complex state (position + inventory)\n" " - Planning problems: Finding cheapest action sequences\n" " - AoC problems: 2019 Day 18, 2021 Day 23, 2022 Day 16, etc.\n" "\n" " ## Notes\n" "\n" " - States are deduplicated by their full value (using `Dict(state, cost)`)\n" " - If your state carries extra data beyond identity, use `implicit_dijkstra_by`\n" " - First path to reach a state with minimal cost wins\n" " - Works with any cost type that supports addition and comparison\n" ). -spec implicit_dijkstra( MCA, fun((MCA) -> list({MCA, MCB})), fun((MCA) -> boolean()), MCB, fun((MCB, MCB) -> MCB), fun((MCB, MCB) -> gleam@order:order()) ) -> gleam@option:option(MCB). implicit_dijkstra(Start, Successors, Is_goal, Zero, Add, Compare) -> Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end ), gleamy@priority_queue:push(_pipe, {Zero, Start}) end, do_implicit_dijkstra( Frontier, maps:new(), Successors, Is_goal, Add, Compare ). -file("src/yog/pathfinding.gleam", 1056). -spec do_implicit_dijkstra_by( gleamy@pairing_heap:heap({MCQ, MCR}), gleam@dict:dict(MCT, MCQ), fun((MCR) -> list({MCR, MCQ})), fun((MCR) -> MCT), fun((MCR) -> boolean()), fun((MCQ, MCQ) -> MCQ), fun((MCQ, MCQ) -> gleam@order:order()) ) -> gleam@option:option(MCQ). do_implicit_dijkstra_by( Frontier, Distances, Successors, Key_fn, Is_goal, Add, Compare ) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> none; {ok, {{Dist, Current}, Rest_frontier}} -> case Is_goal(Current) of true -> {some, Dist}; false -> Current_key = Key_fn(Current), Should_explore = case gleam_stdlib:map_get( Distances, Current_key ) of {ok, Prev_dist} -> case Compare(Dist, Prev_dist) of lt -> true; _ -> false end; {error, nil} -> true end, case Should_explore of false -> do_implicit_dijkstra_by( Rest_frontier, Distances, Successors, Key_fn, Is_goal, Add, Compare ); true -> New_distances = gleam@dict:insert( Distances, Current_key, Dist ), Next_frontier = begin _pipe = Successors(Current), gleam@list:fold( _pipe, Rest_frontier, fun(H, Neighbor) -> {Next_state, Cost} = Neighbor, gleamy@priority_queue:push( H, {Add(Dist, Cost), Next_state} ) end ) end, do_implicit_dijkstra_by( Next_frontier, New_distances, Successors, Key_fn, Is_goal, Add, Compare ) end end end. -file("src/yog/pathfinding.gleam", 1030). ?DOC( " Like `implicit_dijkstra`, but deduplicates visited states by a custom key.\n" "\n" " Essential when your state carries extra data beyond what defines identity.\n" " For example, in state-space search you might have `#(Position, ExtraData)` states,\n" " but only want to visit each `Position` once — the `ExtraData` is carried state,\n" " not part of the identity.\n" "\n" " The `visited_by` function extracts the deduplication key from each state.\n" " Internally, a `Dict(key, cost)` tracks the best cost to each key, but the\n" " full state value is still passed to your successor function and goal predicate.\n" "\n" " **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n" "\n" " ## Parameters\n" "\n" " - `visited_by`: Function that extracts the deduplication key from a state\n" "\n" " ## Example\n" "\n" " ```gleam\n" " // State-space search where states carry metadata\n" " // Node is #(position, path_history) but we dedupe by position only\n" " pathfinding.implicit_dijkstra_by(\n" " from: #(start_pos, []),\n" " successors_with_cost: fn(state) {\n" " let #(pos, history) = state\n" " neighbors(pos)\n" " |> list.map(fn(next_pos) {\n" " #(#(next_pos, [pos, ..history]), move_cost(pos, next_pos))\n" " })\n" " },\n" " visited_by: fn(state) { state.0 }, // Dedupe by position only\n" " is_goal: fn(state) { state.0 == goal_pos },\n" " with_zero: 0,\n" " with_add: int.add,\n" " with_compare: int.compare,\n" " )\n" " ```\n" "\n" " ## Use Cases\n" "\n" " - AoC 2019 Day 18: `#(at_key, collected_mask)` → dedupe by both\n" " - Puzzle solving: `#(board_state, move_count)` → dedupe by `board_state`\n" " - Pathfinding with budget: `#(position, fuel_left)` → dedupe by `position`\n" " - A* with metadata: `#(node_id, came_from)` → dedupe by `node_id`\n" "\n" " ## Comparison to `implicit_dijkstra`\n" "\n" " - `implicit_dijkstra`: Deduplicates by the entire state value\n" " - `implicit_dijkstra_by`: Deduplicates by `visited_by(state)` but keeps full state\n" "\n" " Similar to SQL's `DISTINCT ON(key)` or Python's `key=` parameter.\n" ). -spec implicit_dijkstra_by( MCL, fun((MCL) -> list({MCL, MCM})), fun((MCL) -> any()), fun((MCL) -> boolean()), MCM, fun((MCM, MCM) -> MCM), fun((MCM, MCM) -> gleam@order:order()) ) -> gleam@option:option(MCM). implicit_dijkstra_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) -> Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end ), gleamy@priority_queue:push(_pipe, {Zero, Start}) end, do_implicit_dijkstra_by( Frontier, maps:new(), Successors, Key_fn, Is_goal, Add, Compare ). -file("src/yog/pathfinding.gleam", 1185). -spec do_implicit_a_star( gleamy@pairing_heap:heap({MDC, MDC, MDD}), gleam@dict:dict(MDD, MDC), fun((MDD) -> list({MDD, MDC})), fun((MDD) -> boolean()), fun((MDD) -> MDC), fun((MDC, MDC) -> MDC), fun((MDC, MDC) -> gleam@order:order()) ) -> gleam@option:option(MDC). do_implicit_a_star(Frontier, Distances, Successors, Is_goal, H, Add, Compare) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> none; {ok, {{_, Dist, Current}, Rest_frontier}} -> case Is_goal(Current) of true -> {some, Dist}; false -> Should_explore = case gleam_stdlib:map_get( Distances, Current ) of {ok, Prev_dist} -> case Compare(Dist, Prev_dist) of lt -> true; _ -> false end; {error, nil} -> true end, case Should_explore of false -> do_implicit_a_star( Rest_frontier, Distances, Successors, Is_goal, H, Add, Compare ); true -> New_distances = gleam@dict:insert( Distances, Current, Dist ), Next_frontier = begin _pipe = Successors(Current), gleam@list:fold( _pipe, Rest_frontier, fun(Frontier_acc, Neighbor) -> {Next_state, Edge_cost} = Neighbor, Next_dist = Add(Dist, Edge_cost), F_score = Add(Next_dist, H(Next_state)), gleamy@priority_queue:push( Frontier_acc, {F_score, Next_dist, Next_state} ) end ) end, do_implicit_a_star( Next_frontier, New_distances, Successors, Is_goal, H, Add, Compare ) end end end. -file("src/yog/pathfinding.gleam", 1166). ?DOC( " Finds the shortest path in an implicit graph using A* search with a heuristic.\n" "\n" " Like `implicit_dijkstra`, but uses a heuristic to guide the search toward the goal.\n" " The heuristic must be admissible (never overestimate the actual distance) to guarantee\n" " 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`: Function that estimates remaining cost from any state to goal.\n" " Must be admissible (h(state) ≤ actual cost) to guarantee shortest path.\n" "\n" " ## Example\n" "\n" " ```gleam\n" " // Grid pathfinding with Manhattan distance heuristic\n" " type Pos { Pos(x: Int, y: Int) }\n" "\n" " pathfinding.implicit_a_star(\n" " from: Pos(0, 0),\n" " successors_with_cost: fn(pos) {\n" " [\n" " #(Pos(pos.x + 1, pos.y), 1),\n" " #(Pos(pos.x, pos.y + 1), 1),\n" " ]\n" " },\n" " is_goal: fn(pos) { pos.x == 10 && pos.y == 10 },\n" " heuristic: fn(pos) {\n" " // Manhattan distance to goal\n" " int.absolute_value(10 - pos.x) + int.absolute_value(10 - pos.y)\n" " },\n" " with_zero: 0,\n" " with_add: int.add,\n" " with_compare: int.compare,\n" " )\n" " ```\n" "\n" " ## Use Cases\n" "\n" " - Grid pathfinding with spatial heuristics (Manhattan, Euclidean)\n" " - Puzzle solving where you can estimate \"distance to solution\"\n" " - Game AI pathfinding on maps\n" " - Any scenario where Dijkstra works but you have a good heuristic\n" ). -spec implicit_a_star( MCY, fun((MCY) -> list({MCY, MCZ})), fun((MCY) -> boolean()), fun((MCY) -> MCZ), MCZ, fun((MCZ, MCZ) -> MCZ), fun((MCZ, MCZ) -> gleam@order:order()) ) -> gleam@option:option(MCZ). implicit_a_star(Start, Successors, Is_goal, H, Zero, Add, Compare) -> Initial_f = H(Start), Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end ), gleamy@priority_queue:push(_pipe, {Initial_f, Zero, Start}) end, do_implicit_a_star( Frontier, maps:new(), Successors, Is_goal, H, Add, Compare ). -file("src/yog/pathfinding.gleam", 1310). -spec do_implicit_a_star_by( gleamy@pairing_heap:heap({MDO, MDO, MDP}), gleam@dict:dict(MDR, MDO), fun((MDP) -> list({MDP, MDO})), fun((MDP) -> MDR), fun((MDP) -> boolean()), fun((MDP) -> MDO), fun((MDO, MDO) -> MDO), fun((MDO, MDO) -> gleam@order:order()) ) -> gleam@option:option(MDO). do_implicit_a_star_by( Frontier, Distances, Successors, Key_fn, Is_goal, H, Add, Compare ) -> case gleamy@priority_queue:pop(Frontier) of {error, nil} -> none; {ok, {{_, Dist, Current}, Rest_frontier}} -> case Is_goal(Current) of true -> {some, Dist}; false -> Current_key = Key_fn(Current), Should_explore = case gleam_stdlib:map_get( Distances, Current_key ) of {ok, Prev_dist} -> case Compare(Dist, Prev_dist) of lt -> true; _ -> false end; {error, nil} -> true end, case Should_explore of false -> do_implicit_a_star_by( Rest_frontier, Distances, Successors, Key_fn, Is_goal, H, Add, Compare ); true -> New_distances = gleam@dict:insert( Distances, Current_key, Dist ), Next_frontier = begin _pipe = Successors(Current), gleam@list:fold( _pipe, Rest_frontier, fun(Frontier_acc, Neighbor) -> {Next_state, Edge_cost} = Neighbor, Next_dist = Add(Dist, Edge_cost), F_score = Add(Next_dist, H(Next_state)), gleamy@priority_queue:push( Frontier_acc, {F_score, Next_dist, Next_state} ) end ) end, do_implicit_a_star_by( Next_frontier, New_distances, Successors, Key_fn, Is_goal, H, Add, Compare ) end end end. -file("src/yog/pathfinding.gleam", 1281). ?DOC( " Like `implicit_a_star`, but deduplicates visited states by a custom key.\n" "\n" " Essential when your state carries extra data beyond what defines identity.\n" " The heuristic still operates on the full state, but deduplication uses only the key.\n" "\n" " **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n" "\n" " ## Example\n" "\n" " ```gleam\n" " // Grid with carried items, but dedupe by position only\n" " // Heuristic considers only position, not items\n" " pathfinding.implicit_a_star_by(\n" " from: #(Pos(0, 0), []),\n" " successors_with_cost: fn(state) {\n" " let #(pos, items) = state\n" " neighbors(pos)\n" " |> list.map(fn(next_pos) { #(#(next_pos, items), 1) })\n" " },\n" " visited_by: fn(state) { state.0 }, // Dedupe by position\n" " is_goal: fn(state) { state.0 == goal_pos },\n" " heuristic: fn(state) { manhattan_distance(state.0, goal_pos) },\n" " with_zero: 0,\n" " with_add: int.add,\n" " with_compare: int.compare,\n" " )\n" " ```\n" ). -spec implicit_a_star_by( MDJ, fun((MDJ) -> list({MDJ, MDK})), fun((MDJ) -> any()), fun((MDJ) -> boolean()), fun((MDJ) -> MDK), MDK, fun((MDK, MDK) -> MDK), fun((MDK, MDK) -> gleam@order:order()) ) -> gleam@option:option(MDK). implicit_a_star_by(Start, Successors, Key_fn, Is_goal, H, Zero, Add, Compare) -> Initial_f = H(Start), Frontier = begin _pipe = gleamy@priority_queue:new( fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end ), gleamy@priority_queue:push(_pipe, {Initial_f, Zero, Start}) end, do_implicit_a_star_by( Frontier, maps:new(), Successors, Key_fn, Is_goal, H, Add, Compare ). -file("src/yog/pathfinding.gleam", 1445). -spec do_implicit_bellman_ford( yog@internal@queue:queue(MEA), gleam@dict:dict(MEA, MEC), gleam@dict:dict(MEA, integer()), gleam@set:set(MEA), fun((MEA) -> list({MEA, MEC})), fun((MEA) -> boolean()), MEC, fun((MEC, MEC) -> MEC), fun((MEC, MEC) -> gleam@order:order()) ) -> implicit_bellman_ford_result(MEC). 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.gleam", 1424). ?DOC( " Finds shortest path in implicit graphs with support for negative edge weights.\n" "\n" " Uses SPFA (Shortest Path Faster Algorithm), a queue-based variant of Bellman-Ford\n" " that works naturally with implicit graphs. Detects negative cycles by counting\n" " relaxations per state.\n" "\n" " **Time Complexity:** O(VE) average case where V and E are discovered dynamically\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 before exhausting reachable states\n" "\n" " ## Example\n" "\n" " ```gleam\n" " pathfinding.implicit_bellman_ford(\n" " from: start_state,\n" " successors_with_cost: fn(state) {\n" " // Can include negative costs\n" " [#(next_state1, -5), #(next_state2, 10)]\n" " },\n" " is_goal: fn(state) { state == goal },\n" " with_zero: 0,\n" " with_add: int.add,\n" " with_compare: int.compare,\n" " )\n" " ```\n" ). -spec implicit_bellman_ford( MDW, fun((MDW) -> list({MDW, MDX})), fun((MDW) -> boolean()), MDX, fun((MDX, MDX) -> MDX), fun((MDX, MDX) -> gleam@order:order()) ) -> implicit_bellman_ford_result(MDX). 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.gleam", 1586). -spec do_implicit_bellman_ford_by( yog@internal@queue:queue(MEP), gleam@dict:dict(MER, {MES, MEP}), gleam@dict:dict(MER, integer()), gleam@set:set(MEP), fun((MEP) -> list({MEP, MES})), fun((MEP) -> MER), fun((MEP) -> boolean()), MES, fun((MES, MES) -> MES), fun((MES, MES) -> gleam@order:order()) ) -> implicit_bellman_ford_result(MES). 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), _pipe@7 = gleam@result:map( _pipe@6, fun(Pair) -> erlang:element(1, Pair) end ), gleam@result:unwrap(_pipe@7, Zero) end, {New_distances, New_counts, New_queue, New_in_q} = begin _pipe@8 = Successors(Current), gleam@list:fold( _pipe@8, {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@9 = gleam_stdlib:map_get( Counts, Next_key ), gleam@result:unwrap(_pipe@9, 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@10 = New_counts, _pipe@11 = maps:to_list(_pipe@10), gleam@list:any( _pipe@11, 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.gleam", 1562). ?DOC( " Like `implicit_bellman_ford`, but deduplicates visited states by a custom key.\n" "\n" " **Time Complexity:** O(VE) where V and E are measured in unique *keys*\n" ). -spec implicit_bellman_ford_by( MEK, fun((MEK) -> list({MEK, MEL})), fun((MEK) -> any()), fun((MEK) -> boolean()), MEL, fun((MEL, MEL) -> MEL), fun((MEL, MEL) -> gleam@order:order()) ) -> implicit_bellman_ford_result(MEL). 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 ).