yog

-module(yog@pathfinding@dijkstra).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/dijkstra.gleam").
-export([shortest_path/6, single_source_distances/5, implicit_dijkstra/6, implicit_dijkstra_by/7, fold/7, shortest_path_int/3, shortest_path_float/3, single_source_distances_int/2, single_source_distances_float/2]).

-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(
    " [Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) for \n"
    " single-source shortest paths in graphs with non-negative edge weights.\n"
    "\n"
    " Dijkstra's algorithm finds the shortest path from a source node to all other reachable\n"
    " nodes in a graph. It works by maintaining a priority queue of nodes to visit,\n"
    " always expanding the node with the smallest known distance.\n"
    "\n"
    " ## Algorithm\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) (single-target) | `shortest_path/6` | O((V + E) log V) | One-to-one shortest path |\n"
    " | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) (single-source) | `single_source_distances/5` | O((V + E) log V) | One-to-all shortest paths |\n"
    " | Implicit Dijkstra | `implicit_dijkstra/6` | O((V + E) log V) | Large/infinite graphs |\n"
    "\n"
    " ## Key Concepts\n"
    "\n"
    " - **Greedy Strategy**: Always expands the node with minimum tentative distance\n"
    " - **Priority Queue**: Min-heap ordered by current best distance\n"
    " - **Relaxation**: Update distances when a shorter path is found\n"
    " - **Non-Negative Weights**: Required for correctness (use Bellman-Ford for negative weights)\n"
    "\n"
    " ## Comparison with Other Algorithms\n"
    "\n"
    " | Algorithm | Handles Negative Weights | Complexity | Use Case |\n"
    " |-----------|-------------------------|------------|----------|\n"
    " | Dijkstra | ❌ No | O((V+E) log V) | General shortest paths |\n"
    " | A* | ❌ No | O((V+E) log V) | When good heuristic available |\n"
    " | Bellman-Ford | ✅ Yes | O(VE) | Negative weights, cycle detection |\n"
    " | Floyd-Warshall | ✅ Yes | O(V³) | All-pairs shortest paths |\n"
    "\n"
    " ## History\n"
    "\n"
    " Edsger W. Dijkstra published this algorithm in 1959. The original paper described\n"
    " it for finding the shortest path between two nodes, but it's commonly used for\n"
    " single-source shortest paths to all nodes.\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Network routing**: OSPF, IS-IS protocols use Dijkstra\n"
    " - **Map services**: Shortest driving directions\n"
    " - **Social networks**: Degrees of separation\n"
    " - **Game development**: Shortest path on weighted grids\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: Dijkstra's Algorithm](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm)\n"
    " - [Dijkstra's Original Paper (1959)](https://link.springer.com/article/10.1007/BF01386390)\n"
    " - [Red Blob Games: Dijkstra Introduction](https://www.redblobgames.com/pathfinding/a-star/introduction.html)\n"
    " - [CP-Algorithms: Dijkstra](https://cp-algorithms.com/graph/dijkstra.html)\n"
).

-file("src/yog/pathfinding/dijkstra.gleam", 90).
?DOC(
    " Finds the shortest path between two nodes using Dijkstra's algorithm.\n"
    "\n"
    " Works with non-negative edge weights only.\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"
    " dijkstra.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(), JNF),
    integer(),
    integer(),
    JNF,
    fun((JNF, JNF) -> JNF),
    fun((JNF, JNF) -> gleam@order:order())
) -> gleam@option:option(yog@pathfinding@path:path(JNF)).
shortest_path(Graph, Start, Goal, Zero, Add, Compare) ->
    yog@pathfinding@a_star:a_star(
        Graph,
        Start,
        Goal,
        Zero,
        Add,
        Compare,
        fun(_, _) -> Zero end
    ).

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

        {ok, {{Dist, Current}, Rest_frontier}} ->
            Should_explore = yog@internal@util: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,
                                yog@internal@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/dijkstra.gleam", 121).
?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"
    " **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"
).
-spec single_source_distances(
    yog@model:graph(any(), JNL),
    integer(),
    JNL,
    fun((JNL, JNL) -> JNL),
    fun((JNL, JNL) -> gleam@order:order())
) -> gleam@dict:dict(integer(), JNL).
single_source_distances(Graph, Source, Zero, Add, Compare) ->
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) ->
                yog@internal@util:compare_distance_frontier(A, B, Compare)
            end
        ),
        yog@internal@priority_queue:push(_pipe, {Zero, Source})
    end,
    do_single_source_dijkstra(Graph, Frontier, maps:new(), Add, Compare).

-file("src/yog/pathfinding/dijkstra.gleam", 197).
?DOC(
    " Finds the shortest path in an implicit graph using Dijkstra's algorithm.\n"
    "\n"
    " Instead of a materialized `Graph`, this uses a `successors_with_cost` function\n"
    " to compute weighted neighbors on demand.\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"
).
-spec implicit_dijkstra(
    JNZ,
    fun((JNZ) -> list({JNZ, JOA})),
    fun((JNZ) -> boolean()),
    JOA,
    fun((JOA, JOA) -> JOA),
    fun((JOA, JOA) -> gleam@order:order())
) -> gleam@option:option(JOA).
implicit_dijkstra(Start, Successors, Is_goal, Zero, Add, Compare) ->
    yog@pathfinding@a_star:implicit_a_star(
        Start,
        Successors,
        Is_goal,
        fun(_) -> Zero end,
        Zero,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 222).
?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"
    " The `visited_by` function extracts the deduplication key from each state.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V) where V and E are measured in unique *keys*\n"
).
-spec implicit_dijkstra_by(
    JOD,
    fun((JOD) -> list({JOD, JOE})),
    fun((JOD) -> any()),
    fun((JOD) -> boolean()),
    JOE,
    fun((JOE, JOE) -> JOE),
    fun((JOE, JOE) -> gleam@order:order())
) -> gleam@option:option(JOE).
implicit_dijkstra_by(Start, Successors, Key_fn, Is_goal, Zero, Add, Compare) ->
    yog@pathfinding@a_star:implicit_a_star_by(
        Start,
        Successors,
        Key_fn,
        Is_goal,
        fun(_) -> Zero end,
        Zero,
        Add,
        Compare
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 265).
-spec do_fold(
    yog@internal@pairing_heap:heap({JSL, JSH}),
    gleam@dict:dict(JSH, JSL),
    JOT,
    fun((JSH) -> list({JSH, JSI})),
    fun((JSL, JSI) -> JSL),
    fun((JSL, JSL) -> gleam@order:order()),
    fun((JOT, JSH, JSL) -> {yog@traversal:walk_control(), JOT})
) -> JOT.
do_fold(Frontier, Best, Acc, Successors, Add, Compare, Folder) ->
    case yog@internal@priority_queue:pop(Frontier) of
        {error, nil} ->
            Acc;

        {ok, {{Cost, Node}, Rest}} ->
            Is_stale = case gleam_stdlib:map_get(Best, Node) of
                {ok, Prev} ->
                    Compare(Prev, Cost) /= gt;

                _ ->
                    false
            end,
            case Is_stale of
                true ->
                    do_fold(Rest, Best, Acc, Successors, Add, Compare, Folder);

                false ->
                    New_best = gleam@dict:insert(Best, Node, Cost),
                    {Control, New_acc} = Folder(Acc, Node, Cost),
                    case Control of
                        halt ->
                            New_acc;

                        stop ->
                            do_fold(
                                Rest,
                                New_best,
                                New_acc,
                                Successors,
                                Add,
                                Compare,
                                Folder
                            );

                        continue ->
                            Next_frontier = gleam@list:fold(
                                Successors(Node),
                                Rest,
                                fun(Q, Neighbor) ->
                                    {Nb_node, Edge_cost} = Neighbor,
                                    New_cost = Add(Cost, Edge_cost),
                                    Is_worse = case gleam_stdlib:map_get(
                                        New_best,
                                        Nb_node
                                    ) of
                                        {ok, Prev_cost} ->
                                            Compare(Prev_cost, New_cost) /= gt;

                                        _ ->
                                            false
                                    end,
                                    case Is_worse of
                                        true ->
                                            Q;

                                        false ->
                                            yog@internal@priority_queue:push(
                                                Q,
                                                {New_cost, Nb_node}
                                            )
                                    end
                                end
                            ),
                            do_fold(
                                Next_frontier,
                                New_best,
                                New_acc,
                                Successors,
                                Add,
                                Compare,
                                Folder
                            )
                    end
            end
    end.

-file("src/yog/pathfinding/dijkstra.gleam", 249).
?DOC(
    " Folds over an implicit weighted graph using Dijkstra's algorithm.\n"
    "\n"
    " Like `implicit_dijkstra` but visits nodes in order of increasing cost and\n"
    " accumulates state. Provides control over traversal via `WalkControl`.\n"
    "\n"
    " **Time Complexity:** O((V + E) log V)\n"
).
-spec fold(
    JOI,
    JOJ,
    fun((JOI) -> list({JOI, JOK})),
    JOK,
    fun((JOK, JOK) -> JOK),
    fun((JOK, JOK) -> gleam@order:order()),
    fun((JOJ, JOI, JOK) -> {yog@traversal:walk_control(), JOJ})
) -> JOJ.
fold(Start, Acc, Successors, Zero, Add, Compare, Folder) ->
    Frontier = begin
        _pipe = yog@internal@priority_queue:new(
            fun(A, B) -> Compare(erlang:element(1, A), erlang:element(1, B)) end
        ),
        yog@internal@priority_queue:push(_pipe, {Zero, Start})
    end,
    do_fold(Frontier, maps:new(), Acc, Successors, Add, Compare, Folder).

-file("src/yog/pathfinding/dijkstra.gleam", 346).
?DOC(
    " Finds the shortest path using **integer weights**.\n"
    "\n"
    " This is a convenience wrapper around `shortest_path` that uses:\n"
    " - `0` as the zero element\n"
    " - `int.add` for addition\n"
    " - `int.compare` for comparison\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Much cleaner than the full explicit version\n"
    " dijkstra.shortest_path_int(graph, from: 1, to: 5)\n"
    " // => Some(Path([1, 2, 5], 15))\n"
    "\n"
    " // Equivalent explicit call:\n"
    " // dijkstra.shortest_path(\n"
    " //   graph, from: 1, to: 5,\n"
    " //   with_zero: 0,\n"
    " //   with_add: int.add,\n"
    " //   with_compare: int.compare\n"
    " // )\n"
    " ```\n"
    "\n"
    " ## When to Use\n"
    "\n"
    " Use this for graphs with `Int` edge weights (hop counts, distances in meters,\n"
    " costs in cents, etc.). For custom weight types (Money, Distance, etc.), use\n"
    " the full `shortest_path` function with your own semiring operations.\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/dijkstra.gleam", 381).
?DOC(
    " Finds the shortest path using **float weights**.\n"
    "\n"
    " This is a convenience wrapper around `shortest_path` that uses:\n"
    " - `0.0` as the zero element\n"
    " - `float.add` for addition\n"
    " - `float.compare` for comparison\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " dijkstra.shortest_path_float(graph, from: 1, to: 5)\n"
    " // => Some(Path([1, 2, 5], 15.5))\n"
    " ```\n"
    "\n"
    " ## When to Use\n"
    "\n"
    " Use this for graphs with `Float` edge weights (probabilities, distances in\n"
    " kilometers with decimal precision, continuous costs, etc.). Note that float\n"
    " arithmetic has precision limitations - for exact calculations, prefer `Int`\n"
    " weights (e.g., store cents instead of dollars).\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
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 399).
?DOC(
    " Computes shortest distances using **integer weights**.\n"
    "\n"
    " Convenience wrapper for `single_source_distances` with `Int` weights.\n"
).
-spec single_source_distances_int(yog@model:graph(any(), integer()), integer()) -> gleam@dict:dict(integer(), integer()).
single_source_distances_int(Graph, Source) ->
    single_source_distances(
        Graph,
        Source,
        0,
        fun gleam@int:add/2,
        fun gleam@int:compare/2
    ).

-file("src/yog/pathfinding/dijkstra.gleam", 415).
?DOC(
    " Computes shortest distances using **float weights**.\n"
    "\n"
    " Convenience wrapper for `single_source_distances` with `Float` weights.\n"
).
-spec single_source_distances_float(yog@model:graph(any(), float()), integer()) -> gleam@dict:dict(integer(), float()).
single_source_distances_float(Graph, Source) ->
    single_source_distances(
        Graph,
        Source,
        +0.0,
        fun gleam@float:add/2,
        fun gleam@float:compare/2
    ).