-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]).
-export_type([path/1, 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(GBC) :: {path, list(integer()), GBC}.

-type bellman_ford_result(GBD) :: {shortest_path, path(GBD)} |
    negative_cycle |
    no_path.

-file("src/yog/pathfinding.gleam", 104).
-spec compare_frontier(
    {GBU, list(integer())},
    {GBU, list(integer())},
    fun((GBU, GBU) -> 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", 114).
?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(), GBX),
    integer(),
    GBX,
    fun((GBX, GBX) -> 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(), GBL),
    integer(),
    yog@internal@heap:heap({GBL, list(integer())}),
    gleam@dict:dict(integer(), GBL),
    fun((GBL, GBL) -> GBL),
    fun((GBL, GBL) -> gleam@order:order())
) -> gleam@option:option(path(GBL)).
do_dijkstra(Graph, Goal, Frontier, Visited, Add, Compare) ->
    case yog@internal@heap:find_min(Frontier) of
        {error, nil} ->
            none;

        {ok, {Dist, [Current | _] = Path}} ->
            Rest_frontier = begin
                _pipe = yog@internal@heap:delete_min(
                    Frontier,
                    fun(A, B) -> compare_frontier(A, B, Compare) end
                ),
                gleam@result:unwrap(_pipe, yog@internal@heap:new())
            end,
            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@1 = yog@model:successors(Graph, Current),
                                gleam@list:fold(
                                    _pipe@1,
                                    Rest_frontier,
                                    fun(H, Neighbor) ->
                                        {Next_id, Weight} = Neighbor,
                                        yog@internal@heap:insert(
                                            H,
                                            {Add(Dist, Weight),
                                                [Next_id | Path]},
                                            fun(A@1, B@1) ->
                                                compare_frontier(
                                                    A@1,
                                                    B@1,
                                                    Compare
                                                )
                                            end
                                        )
                                    end
                                )
                            end,
                            do_dijkstra(
                                Graph,
                                Goal,
                                Next_frontier,
                                New_visited,
                                Add,
                                Compare
                            )
                    end
            end;

        {ok, _} ->
            none
    end.

-file("src/yog/pathfinding.gleam", 39).
?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(), GBF),
    integer(),
    integer(),
    GBF,
    fun((GBF, GBF) -> GBF),
    fun((GBF, GBF) -> gleam@order:order())
) -> gleam@option:option(path(GBF)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = yog@internal@heap:new(),
        yog@internal@heap:insert(
            _pipe,
            {Zero, [Start]},
            fun(A, B) -> compare_frontier(A, B, Compare) end
        )
    end,
    do_dijkstra(Graph, Goal, Frontier, maps:new(), Add, Compare).

-file("src/yog/pathfinding.gleam", 189).
-spec do_single_source_dijkstra(
    yog@model:graph(any(), GCH),
    yog@internal@heap:heap({GCH, integer()}),
    gleam@dict:dict(integer(), GCH),
    fun((GCH, GCH) -> GCH),
    fun((GCH, GCH) -> gleam@order:order())
) -> gleam@dict:dict(integer(), GCH).
do_single_source_dijkstra(Graph, Frontier, Distances, Add, Compare) ->
    case yog@internal@heap:find_min(Frontier) of
        {error, nil} ->
            Distances;

        {ok, {Dist, Current}} ->
            Rest_frontier = begin
                _pipe = yog@internal@heap:delete_min(
                    Frontier,
                    fun(A, B) ->
                        Compare(erlang:element(1, A), erlang:element(1, B))
                    end
                ),
                gleam@result:unwrap(_pipe, yog@internal@heap:new())
            end,
            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@1 = yog@model:successors(Graph, Current),
                        gleam@list:fold(
                            _pipe@1,
                            Rest_frontier,
                            fun(H, Neighbor) ->
                                {Next_id, Weight} = Neighbor,
                                yog@internal@heap:insert(
                                    H,
                                    {Add(Dist, Weight), Next_id},
                                    fun(A@1, B@1) ->
                                        Compare(
                                            erlang:element(1, A@1),
                                            erlang:element(1, B@1)
                                        )
                                    end
                                )
                            end
                        )
                    end,
                    do_single_source_dijkstra(
                        Graph,
                        Next_frontier,
                        New_distances,
                        Add,
                        Compare
                    )
            end
    end.

-file("src/yog/pathfinding.gleam", 175).
?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(), GCB),
    integer(),
    GCB,
    fun((GCB, GCB) -> GCB),
    fun((GCB, GCB) -> gleam@order:order())
) -> gleam@dict:dict(integer(), GCB).
single_source_distances(Graph, Source, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = yog@internal@heap:new(),
        yog@internal@heap:insert(
            _pipe,
            {Zero, Source},
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        )
    end,
    do_single_source_dijkstra(Graph, Frontier, maps:new(), Add, Compare).

-file("src/yog/pathfinding.gleam", 292).
-spec do_a_star(
    yog@model:graph(any(), GKM),
    integer(),
    yog@internal@heap:heap({GKJ, GKJ, list(integer())}),
    gleam@dict:dict(integer(), GKJ),
    fun((GKJ, GKM) -> GKJ),
    fun((GKJ, GKJ) -> gleam@order:order()),
    fun((integer(), integer()) -> GKM)
) -> gleam@option:option(path(GKJ)).
do_a_star(Graph, Goal, Frontier, Visited, Add, Compare, H) ->
    case yog@internal@heap:find_min(Frontier) of
        {error, nil} ->
            none;

        {ok, {_, Dist, [Current | _] = Path}} ->
            Rest_frontier = begin
                _pipe = yog@internal@heap:delete_min(
                    Frontier,
                    fun(A, B) ->
                        Compare(erlang:element(1, A), erlang:element(1, B))
                    end
                ),
                gleam@result:unwrap(_pipe, yog@internal@heap:new())
            end,
            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@1 = yog@model:successors(Graph, Current),
                                gleam@list:fold(
                                    _pipe@1,
                                    Rest_frontier,
                                    fun(Acc_h, Neighbor) ->
                                        {Next_id, Weight} = Neighbor,
                                        Next_dist = Add(Dist, Weight),
                                        F_score = Add(
                                            Next_dist,
                                            H(Next_id, Goal)
                                        ),
                                        yog@internal@heap:insert(
                                            Acc_h,
                                            {F_score,
                                                Next_dist,
                                                [Next_id | Path]},
                                            fun(A@1, B@1) ->
                                                Compare(
                                                    erlang:element(1, A@1),
                                                    erlang:element(1, B@1)
                                                )
                                            end
                                        )
                                    end
                                )
                            end,
                            do_a_star(
                                Graph,
                                Goal,
                                Next_frontier,
                                New_visited,
                                Add,
                                Compare,
                                H
                            )
                    end
            end;

        _ ->
            none
    end.

-file("src/yog/pathfinding.gleam", 274).
?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(), GCQ),
    integer(),
    integer(),
    GCQ,
    fun((GCQ, GCQ) -> GCQ),
    fun((GCQ, GCQ) -> gleam@order:order()),
    fun((integer(), integer()) -> GCQ)
) -> gleam@option:option(path(GCQ)).
a_star(Graph, Start, Goal, Zero, Add, Compare, H) ->
    Initial_f = H(Start, Goal),
    Frontier = begin
        _pipe = yog@internal@heap:new(),
        yog@internal@heap:insert(
            _pipe,
            {Initial_f, Zero, [Start]},
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        )
    end,
    do_a_star(Graph, Goal, Frontier, maps:new(), Add, Compare, H).

-file("src/yog/pathfinding.gleam", 428).
-spec relaxation_passes(
    yog@model:graph(any(), GDJ),
    list(integer()),
    gleam@dict:dict(integer(), GDJ),
    gleam@dict:dict(integer(), integer()),
    integer(),
    fun((GDJ, GDJ) -> GDJ),
    fun((GDJ, GDJ) -> gleam@order:order())
) -> {gleam@dict:dict(integer(), GDJ), 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", 492).
-spec has_negative_cycle(
    yog@model:graph(any(), GDW),
    list(integer()),
    gleam@dict:dict(integer(), GDW),
    fun((GDW, GDW) -> GDW),
    fun((GDW, GDW) -> 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", 524).
-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", 382).
?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(), GDE),
    integer(),
    integer(),
    GDE,
    fun((GDE, GDE) -> GDE),
    fun((GDE, GDE) -> gleam@order:order())
) -> bellman_ford_result(GDE).
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", 722).
?DOC(" Helper to get distance from the nested dictionary structure\n").
-spec get_distance(
    gleam@dict:dict(integer(), gleam@dict:dict(integer(), GES)),
    integer(),
    integer()
) -> {ok, GES} | {error, nil}.
get_distance(Distances, I, J) ->
    case gleam_stdlib:map_get(Distances, I) of
        {ok, Row} ->
            gleam_stdlib:map_get(Row, J);

        {error, nil} ->
            {error, nil}
    end.

-file("src/yog/pathfinding.gleam", 734).
?DOC(" Helper to update distance in the nested dictionary structure\n").
-spec update_distance(
    gleam@dict:dict(integer(), gleam@dict:dict(integer(), GEZ)),
    integer(),
    integer(),
    GEZ
) -> gleam@dict:dict(integer(), gleam@dict:dict(integer(), GEZ)).
update_distance(Distances, I, J, Dist) ->
    case gleam_stdlib:map_get(Distances, I) of
        {ok, Row} ->
            New_row = gleam@dict:insert(Row, J, Dist),
            gleam@dict:insert(Distances, I, New_row);

        {error, nil} ->
            New_row@1 = begin
                _pipe = maps:new(),
                gleam@dict:insert(_pipe, J, Dist)
            end,
            gleam@dict:insert(Distances, I, New_row@1)
    end.

-file("src/yog/pathfinding.gleam", 754).
?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(), gleam@dict:dict(integer(), GFI)),
    list(integer()),
    GFI,
    fun((GFI, GFI) -> gleam@order:order())
) -> boolean().
detect_negative_cycle(Distances, Nodes, Zero, Compare) ->
    _pipe = Nodes,
    gleam@list:any(_pipe, fun(I) -> case get_distance(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", 627).
?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(), GEJ),
    GEJ,
    fun((GEJ, GEJ) -> GEJ),
    fun((GEJ, GEJ) -> gleam@order:order())
) -> {ok, gleam@dict:dict(integer(), gleam@dict:dict(integer(), GEJ))} |
    {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) ->
                Row@1 = begin
                    _pipe@1 = Nodes,
                    gleam@list:fold(
                        _pipe@1,
                        maps:new(),
                        fun(Row, 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(
                                                                Row,
                                                                J,
                                                                Weight
                                                            );

                                                        _ ->
                                                            gleam@dict:insert(
                                                                Row,
                                                                J,
                                                                Zero
                                                            )
                                                    end;

                                                {error, nil} ->
                                                    gleam@dict:insert(
                                                        Row,
                                                        J,
                                                        Zero
                                                    )
                                            end;

                                        {error, nil} ->
                                            gleam@dict:insert(Row, 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(
                                                        Row,
                                                        J,
                                                        Weight@1
                                                    );

                                                {error, nil} ->
                                                    Row
                                            end;

                                        {error, nil} ->
                                            Row
                                    end
                            end end
                    )
                end,
                gleam@dict:insert(Distances, I, Row@1)
            end
        )
    end,
    Final_distances = begin
        _pipe@2 = Nodes,
        gleam@list:fold(
            _pipe@2,
            Initial_distances,
            fun(Distances@1, K) -> _pipe@3 = Nodes,
                gleam@list:fold(
                    _pipe@3,
                    Distances@1,
                    fun(Distances@2, I@1) -> _pipe@4 = Nodes,
                        gleam@list:fold(
                            _pipe@4,
                            Distances@2,
                            fun(Distances@3, J@1) ->
                                case get_distance(Distances@3, I@1, K) of
                                    {error, nil} ->
                                        Distances@3;

                                    {ok, Dist_ik} ->
                                        case get_distance(Distances@3, K, J@1) of
                                            {error, nil} ->
                                                Distances@3;

                                            {ok, Dist_kj} ->
                                                New_dist = Add(Dist_ik, Dist_kj),
                                                case get_distance(
                                                    Distances@3,
                                                    I@1,
                                                    J@1
                                                ) of
                                                    {error, nil} ->
                                                        update_distance(
                                                            Distances@3,
                                                            I@1,
                                                            J@1,
                                                            New_dist
                                                        );

                                                    {ok, Current_dist} ->
                                                        case Compare(
                                                            New_dist,
                                                            Current_dist
                                                        ) of
                                                            lt ->
                                                                update_distance(
                                                                    Distances@3,
                                                                    I@1,
                                                                    J@1,
                                                                    New_dist
                                                                );

                                                            _ ->
                                                                Distances@3
                                                        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.