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/5]).

-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 chooses\n"
    " between Floyd-Warshall and multiple Dijkstra runs based on POI density.\n"
    "\n"
    " ## Algorithm Selection\n"
    "\n"
    " | Algorithm | When Selected | Complexity |\n"
    " |-----------|---------------|------------|\n"
    " | [Floyd-Warshall](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) | Many POIs (> V/3) | O(V³) then filter |\n"
    " | [Dijkstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) × P | Few POIs (≤ V/3) | O(P × (V + E) log V) |\n"
    "\n"
    " ## Heuristic\n"
    "\n"
    " The crossover point is P > V/3 where P is the number of points of interest:\n"
    " - **Dense POIs**: Floyd-Warshall computes all-pairs once, then filter\n"
    " - **Sparse POIs**: Run Dijkstra from each POI individually\n"
    "\n"
    " This heuristic balances the O(V³) Floyd-Warshall against the O(P(V+E) log V)\n"
    " cost of multiple Dijkstra runs.\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\n"
    " - See `yog/pathfinding/dijkstra` for single-source algorithm details\n"
).

-file("src/yog/pathfinding/matrix.gleam", 64).
?DOC(
    " Computes shortest distances between all pairs of points of interest.\n"
    "\n"
    " Automatically chooses between Floyd-Warshall and multiple Dijkstra runs\n"
    " based on the density of POIs relative to graph size.\n"
    "\n"
    " **Time Complexity:** O(V³) or O(P × (V + E) log V)\n"
).
-spec distance_matrix(
    yog@model:graph(any(), XDN),
    list(integer()),
    XDN,
    fun((XDN, XDN) -> XDN),
    fun((XDN, XDN) -> gleam@order:order())
) -> {ok, gleam@dict:dict({integer(), integer()}, XDN)} | {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 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;

        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.