yog

-module(yog@pathfinding@matrix).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/pathfinding/matrix.gleam").
-export([distance_matrix/6]).

-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(
    " Optimized distance matrix computation for subsets of nodes.\n"
    "\n"
    " This module provides an auto-selecting algorithm for computing shortest path\n"
    " distances between specified \"points of interest\" (POIs) in a graph. It intelligently\n"
    " chooses between Floyd-Warshall, Johnson's, and multiple Dijkstra runs based on\n"
    " graph characteristics and POI density.\n"
    "\n"
    " ## Algorithm Selection\n"
    "\n"
    " **With negative weights support** (when `with_subtract` is provided):\n"
    "\n"
    " | Algorithm | When Selected | Complexity |\n"
    " |-----------|---------------|------------|\n"
    " | [Johnson's](https://en.wikipedia.org/wiki/Johnson%27s_algorithm) | Sparse graphs (E < V²/4) | O(V² log V + VE) then filter |\n"
    " | [Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) | Dense graphs (E ≥ V²/4) | O(V³) then filter |\n"
    "\n"
    " **Without negative weights** (when `with_subtract` is `None`):\n"
    "\n"
    " | Algorithm | When Selected | Complexity |\n"
    " |-----------|---------------|------------|\n"
    " | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) × P | Few POIs (P ≤ V/3) | O(P × (V + E) log V) |\n"
    " | [Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) | Many POIs (P > V/3) | O(V³) then filter |\n"
    "\n"
    " ## Heuristics\n"
    "\n"
    " **For graphs with potential negative weights:**\n"
    " - Johnson's algorithm is preferred for sparse graphs where E < V²/4\n"
    " - Floyd-Warshall is preferred for denser graphs\n"
    "\n"
    " **For non-negative weights only:**\n"
    " - Multiple Dijkstra runs when P ≤ V/3 (few POIs)\n"
    " - Floyd-Warshall when P > V/3 (many POIs)\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Game AI**: Pathfinding between key locations (not all nodes)\n"
    " - **Logistics**: Distance matrix for delivery stops\n"
    " - **Facility location**: Distances between candidate sites\n"
    " - **Network analysis**: Selected node pairwise distances\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Compute distances only between important waypoints\n"
    " let pois = [start, waypoint_a, waypoint_b, goal]\n"
    " let distances = matrix.distance_matrix(\n"
    "   in: graph,\n"
    "   between: pois,\n"
    "   with_zero: 0,\n"
    "   with_add: int.add,\n"
    "   with_compare: int.compare,\n"
    " )\n"
    " // Result contains only 4×4 = 16 distances, not full V×V matrix\n"
    " ```\n"
    "\n"
    " ## References\n"
    "\n"
    " - See `yog/pathfinding/floyd_warshall` for all-pairs algorithm details (O(V³))\n"
    " - See `yog/pathfinding/johnson` for sparse all-pairs with negative weights (O(V² log V + VE))\n"
    " - See `yog/pathfinding/dijkstra` for single-source algorithm details (O((V+E) log V))\n"
).

-file("src/yog/pathfinding/matrix.gleam", 201).
?DOC(" Helper function to run Floyd-Warshall and filter results to POIs\n").
-spec use_floyd_warshall(
    yog@model:graph(any(), VEX),
    gleam@set:set(integer()),
    VEX,
    fun((VEX, VEX) -> VEX),
    fun((VEX, VEX) -> gleam@order:order())
) -> {ok, gleam@dict:dict({integer(), integer()}, VEX)} | {error, nil}.
use_floyd_warshall(Graph, Poi_set, Zero, Add, Compare) ->
    case yog@pathfinding@floyd_warshall: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.

-file("src/yog/pathfinding/matrix.gleam", 110).
?DOC(
    " Computes shortest distances between all pairs of points of interest.\n"
    "\n"
    " Automatically chooses the best algorithm based on:\n"
    " - Whether negative weights are possible (presence of `with_subtract`)\n"
    " - Graph sparsity (E relative to V²)\n"
    " - POI density (P relative to V)\n"
    "\n"
    " **Time Complexity:** O(V³), O(V² log V + VE), or O(P × (V + E) log V)\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `with_subtract`: Optional subtraction function for negative weight support.\n"
    "   If provided, enables Johnson's algorithm for sparse graphs with negative weights.\n"
    "   If `None`, assumes non-negative weights and may use Dijkstra.\n"
    "\n"
    " ## Examples\n"
    "\n"
    " ```gleam\n"
    " // Non-negative weights only (uses Dijkstra or Floyd-Warshall)\n"
    " matrix.distance_matrix(\n"
    "   in: graph,\n"
    "   between: pois,\n"
    "   with_zero: 0,\n"
    "   with_add: int.add,\n"
    "   with_subtract: None,\n"
    "   with_compare: int.compare,\n"
    " )\n"
    "\n"
    " // Support negative weights (uses Johnson's or Floyd-Warshall)\n"
    " matrix.distance_matrix(\n"
    "   in: graph,\n"
    "   between: pois,\n"
    "   with_zero: 0,\n"
    "   with_add: int.add,\n"
    "   with_subtract: Some(int.subtract),\n"
    "   with_compare: int.compare,\n"
    " )\n"
    " ```\n"
).
-spec distance_matrix(
    yog@model:graph(any(), VEN),
    list(integer()),
    VEN,
    fun((VEN, VEN) -> VEN),
    gleam@option:option(fun((VEN, VEN) -> VEN)),
    fun((VEN, VEN) -> gleam@order:order())
) -> {ok, gleam@dict:dict({integer(), integer()}, VEN)} | {error, nil}.
distance_matrix(Graph, Points_of_interest, Zero, Add, Subtract, Compare) ->
    Num_nodes = maps:size(erlang:element(3, Graph)),
    Num_edges = yog@model:edge_count(Graph),
    Num_pois = erlang:length(Points_of_interest),
    Poi_set = gleam@set:from_list(Points_of_interest),
    case Subtract of
        {some, Sub_fn} ->
            Is_sparse = (Num_edges * 4) < (Num_nodes * Num_nodes),
            case Is_sparse of
                true ->
                    case yog@pathfinding@johnson:johnson(
                        Graph,
                        Zero,
                        Add,
                        Sub_fn,
                        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 ->
                    use_floyd_warshall(Graph, Poi_set, Zero, Add, Compare)
            end;

        none ->
            case (Num_pois * 3) > Num_nodes of
                true ->
                    use_floyd_warshall(Graph, Poi_set, Zero, Add, Compare);

                false ->
                    Result = gleam@list:fold(
                        Points_of_interest,
                        maps:new(),
                        fun(Acc, Source) ->
                            Distances = yog@pathfinding@dijkstra: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
    end.