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").

-file("src/yog/pathfinding/matrix.gleam", 17).
?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(), RJC),
    list(integer()),
    RJC,
    fun((RJC, RJC) -> RJC),
    fun((RJC, RJC) -> gleam@order:order())
) -> {ok, gleam@dict:dict({integer(), integer()}, RJC)} | {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.