yog

-module(yog@dag@algorithms).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/dag/algorithms.gleam").
-export([topological_sort/1, longest_path/1, transitive_closure/2, transitive_reduction/2, shortest_path/3, count_reachability/2, lowest_common_ancestors/3]).
-export_type([direction/0]).

-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 direction() :: ancestors | descendants.

-file("src/yog/dag/algorithms.gleam", 13).
?DOC(
    " topological_sort(Dag(n, e)) -> List(NodeId)\n"
    " Unlike the general version, this version is total (cannot return an Error)\n"
    " because the DAG type guarantees acyclicity.\n"
).
-spec topological_sort(yog@dag@models:dag(any(), any())) -> list(integer()).
topological_sort(Dag) ->
    Graph = yog@dag@models:to_graph(Dag),
    Sorted@1 = case yog@traversal:topological_sort(Graph) of
        {ok, Sorted} -> Sorted;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/dag/algorithms"/utf8>>,
                        function => <<"topological_sort"/utf8>>,
                        line => 16,
                        value => _assert_fail,
                        start => 582,
                        'end' => 639,
                        pattern_start => 593,
                        pattern_end => 603})
    end,
    Sorted@1.

-file("src/yog/dag/algorithms.gleam", 84).
-spec reconstruct_path(
    integer(),
    gleam@dict:dict(integer(), integer()),
    list(integer())
) -> list(integer()).
reconstruct_path(Current, Predecessors, Path) ->
    New_path = [Current | Path],
    case gleam_stdlib:map_get(Predecessors, Current) of
        {ok, Prev} ->
            reconstruct_path(Prev, Predecessors, New_path);

        {error, _} ->
            New_path
    end.

-file("src/yog/dag/algorithms.gleam", 23).
?DOC(
    " longest_path(Dag(n, Int)) -> List(NodeId)\n"
    " Goal: Find the Critical Path in O(V+E).\n"
    " Returns the list of node IDs forming the longest path in the DAG.\n"
).
-spec longest_path(yog@dag@models:dag(any(), integer())) -> list(integer()).
longest_path(Dag) ->
    Graph = yog@dag@models:to_graph(Dag),
    Sorted_nodes = topological_sort(Dag),
    {Distances, Predecessors} = gleam@list:fold(
        Sorted_nodes,
        {maps:new(), maps:new()},
        fun(Acc, Node) ->
            {Dist_acc, Pred_acc} = Acc,
            Node_dist = case gleam_stdlib:map_get(Dist_acc, Node) of
                {ok, D} ->
                    D;

                {error, _} ->
                    0
            end,
            case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
                {ok, Edges} ->
                    gleam@dict:fold(
                        Edges,
                        {Dist_acc, Pred_acc},
                        fun(Inner_acc, Target, Weight) ->
                            {D_acc, P_acc} = Inner_acc,
                            Current_target_dist = gleam_stdlib:map_get(
                                D_acc,
                                Target
                            ),
                            New_dist = Node_dist + Weight,
                            Should_update = case Current_target_dist of
                                {ok, D@1} ->
                                    New_dist > D@1;

                                {error, _} ->
                                    true
                            end,
                            case Should_update of
                                true ->
                                    {gleam@dict:insert(D_acc, Target, New_dist),
                                        gleam@dict:insert(P_acc, Target, Node)};

                                false ->
                                    Inner_acc
                            end
                        end
                    );

                {error, _} ->
                    Acc
            end
        end
    ),
    Max_node_opt = gleam@dict:fold(
        Distances,
        none,
        fun(Acc@1, Node@1, Dist) -> case Acc@1 of
                none ->
                    {some, {Node@1, Dist}};

                {some, {_, Max_d}} when Dist > Max_d ->
                    {some, {Node@1, Dist}};

                _ ->
                    Acc@1
            end end
    ),
    case Max_node_opt of
        none ->
            [];

        {some, {End_node, _}} ->
            reconstruct_path(End_node, Predecessors, [])
    end.

-file("src/yog/dag/algorithms.gleam", 100).
?DOC(
    " transitive_closure(Dag(n, e), fn(e, e) -> e) -> Dag(n, e)\n"
    " Goal: Create a \"Reachability Map\" where an edge (u, v) exists if v is reachable from u.\n"
    " Returns a new Dag representing the transitive closure. The `merge_fn` combines edge weights\n"
    " when an indirect path dominates.\n"
).
-spec transitive_closure(yog@dag@models:dag(KIS, KIT), fun((KIT, KIT) -> KIT)) -> yog@dag@models:dag(KIS, KIT).
transitive_closure(Dag, Merge_fn) ->
    Graph = yog@dag@models:to_graph(Dag),
    Sorted_nodes = begin
        _pipe = topological_sort(Dag),
        lists:reverse(_pipe)
    end,
    Reachability_map = gleam@list:fold(
        Sorted_nodes,
        maps:new(),
        fun(Acc, Node) ->
            case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
                {ok, Edges} ->
                    Reachable_from_node = gleam@dict:fold(
                        Edges,
                        Edges,
                        fun(Reachable_acc, Child, W_node_child) ->
                            case gleam_stdlib:map_get(Acc, Child) of
                                {ok, Child_reachable} ->
                                    gleam@dict:fold(
                                        Child_reachable,
                                        Reachable_acc,
                                        fun(Inner_acc, Target, W_child_target) ->
                                            Combined_weight = Merge_fn(
                                                W_node_child,
                                                W_child_target
                                            ),
                                            case gleam_stdlib:map_get(
                                                Inner_acc,
                                                Target
                                            ) of
                                                {ok, Existing_weight} ->
                                                    gleam@dict:insert(
                                                        Inner_acc,
                                                        Target,
                                                        Merge_fn(
                                                            Existing_weight,
                                                            Combined_weight
                                                        )
                                                    );

                                                {error, _} ->
                                                    gleam@dict:insert(
                                                        Inner_acc,
                                                        Target,
                                                        Combined_weight
                                                    )
                                            end
                                        end
                                    );

                                {error, _} ->
                                    Reachable_acc
                            end
                        end
                    ),
                    gleam@dict:insert(Acc, Node, Reachable_from_node);

                {error, _} ->
                    gleam@dict:insert(Acc, Node, maps:new())
            end
        end
    ),
    New_graph = gleam@dict:fold(
        Reachability_map,
        Graph,
        fun(G_acc, Source_node, Targets) ->
            gleam@dict:fold(
                Targets,
                G_acc,
                fun(G_inner, Target_node, Weight) ->
                    yog@model:add_edge(
                        G_inner,
                        Source_node,
                        Target_node,
                        Weight
                    )
                end
            )
        end
    ),
    New_dag@1 = case yog@dag@models:from_graph(New_graph) of
        {ok, New_dag} -> New_dag;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/dag/algorithms"/utf8>>,
                        function => <<"transitive_closure"/utf8>>,
                        line => 163,
                        value => _assert_fail,
                        start => 5687,
                        'end' => 5740,
                        pattern_start => 5698,
                        pattern_end => 5709})
    end,
    New_dag@1.

-file("src/yog/dag/algorithms.gleam", 169).
?DOC(
    " transitive_reduction(Dag(n, e), fn(e, e) -> e) -> Dag(n, e)\n"
    " Goal: Remove redundant edges while preserving reachability.\n"
).
-spec transitive_reduction(yog@dag@models:dag(KIY, KIZ), fun((KIZ, KIZ) -> KIZ)) -> yog@dag@models:dag(KIY, KIZ).
transitive_reduction(Dag, Merge_fn) ->
    Graph = yog@dag@models:to_graph(Dag),
    Reach_dag = transitive_closure(Dag, Merge_fn),
    Reach_graph = yog@dag@models:to_graph(Reach_dag),
    Reduced_graph = gleam@dict:fold(
        erlang:element(4, Graph),
        Graph,
        fun(G_acc, U, Targets) ->
            gleam@dict:fold(
                Targets,
                G_acc,
                fun(G_inner, V, _) ->
                    Is_redundant = gleam@dict:fold(
                        Targets,
                        false,
                        fun(Found_redundant, W, _) ->
                            case {Found_redundant, W =:= V} of
                                {true, _} ->
                                    true;

                                {false, true} ->
                                    false;

                                {false, false} ->
                                    case gleam_stdlib:map_get(
                                        erlang:element(4, Reach_graph),
                                        W
                                    ) of
                                        {ok, W_targets} ->
                                            gleam@dict:has_key(W_targets, V);

                                        {error, _} ->
                                            false
                                    end
                            end
                        end
                    ),
                    case Is_redundant of
                        true ->
                            yog@model:remove_edge(G_inner, U, V);

                        false ->
                            G_inner
                    end
                end
            )
        end
    ),
    New_dag@1 = case yog@dag@models:from_graph(Reduced_graph) of
        {ok, New_dag} -> New_dag;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/dag/algorithms"/utf8>>,
                        function => <<"transitive_reduction"/utf8>>,
                        line => 205,
                        value => _assert_fail,
                        start => 7068,
                        'end' => 7125,
                        pattern_start => 7079,
                        pattern_end => 7090})
    end,
    New_dag@1.

-file("src/yog/dag/algorithms.gleam", 283).
-spec reconstruct_path_backward(
    integer(),
    integer(),
    gleam@dict:dict(integer(), integer()),
    list(integer())
) -> list(integer()).
reconstruct_path_backward(Current, Start, Predecessors, Path) ->
    New_path = [Current | Path],
    case Current =:= Start of
        true ->
            New_path;

        false ->
            case gleam_stdlib:map_get(Predecessors, Current) of
                {ok, Prev} ->
                    reconstruct_path_backward(
                        Prev,
                        Start,
                        Predecessors,
                        New_path
                    );

                {error, _} ->
                    New_path
            end
    end.

-file("src/yog/dag/algorithms.gleam", 221).
?DOC(
    " shortest_path(Dag(n, Int), NodeId, NodeId) -> Option(Path(e))\n"
    " Finds the shortest path between two nodes in a DAG using O(V+E) dynamic programming.\n"
    " \n"
    " Unlike Dijkstra's algorithm which works on general graphs in O((V+E) log V),\n"
    " this leverages the DAG property for linear time complexity.\n"
    "\n"
    " Returns `None` if no path exists from `from` to `to`.\n"
).
-spec shortest_path(yog@dag@models:dag(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path(Dag, Start, Goal) ->
    Graph = yog@dag@models:to_graph(Dag),
    Sorted_nodes = topological_sort(Dag),
    {Distances, Predecessors} = gleam@list:fold(
        Sorted_nodes,
        {maps:new(), maps:new()},
        fun(Acc, Node) ->
            {Dist_acc, Pred_acc} = Acc,
            Dist_acc@1 = case Node =:= Start of
                true ->
                    gleam@dict:insert(Dist_acc, Node, 0);

                false ->
                    Dist_acc
            end,
            Node_dist = case gleam_stdlib:map_get(Dist_acc@1, Node) of
                {ok, D} ->
                    D;

                {error, _} ->
                    0
            end,
            case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
                {ok, Edges} ->
                    gleam@dict:fold(
                        Edges,
                        {Dist_acc@1, Pred_acc},
                        fun(Inner_acc, Target, Weight) ->
                            {D_acc, P_acc} = Inner_acc,
                            Current_target_dist = gleam_stdlib:map_get(
                                D_acc,
                                Target
                            ),
                            New_dist = Node_dist + Weight,
                            Should_update = case Current_target_dist of
                                {ok, D@1} ->
                                    New_dist < D@1;

                                {error, _} ->
                                    true
                            end,
                            case Should_update of
                                true ->
                                    {gleam@dict:insert(D_acc, Target, New_dist),
                                        gleam@dict:insert(P_acc, Target, Node)};

                                false ->
                                    Inner_acc
                            end
                        end
                    );

                {error, _} ->
                    Acc
            end
        end
    ),
    case gleam_stdlib:map_get(Distances, Goal) of
        {error, _} ->
            none;

        {ok, Total_dist} ->
            Path = reconstruct_path_backward(Goal, Start, Predecessors, []),
            {some, {path, Path, Total_dist}}
    end.

-file("src/yog/dag/algorithms.gleam", 308).
?DOC(
    " count_reachability(Dag(n, e), Direction) -> Dict(NodeId, Int)\n"
    " Goal: Efficiently count total descendants/ancestors for every node.\n"
    "\n"
    " Uses sets internally to handle diamond patterns efficiently - a node with\n"
    " multiple paths to the same descendant is only counted once.\n"
).
-spec count_reachability(yog@dag@models:dag(any(), any()), direction()) -> gleam@dict:dict(integer(), integer()).
count_reachability(Dag, Direction) ->
    Graph = yog@dag@models:to_graph(Dag),
    Nodes_to_process = case Direction of
        descendants ->
            _pipe = topological_sort(Dag),
            lists:reverse(_pipe);

        ancestors ->
            topological_sort(Dag)
    end,
    Get_related = fun(Node) -> case Direction of
            descendants ->
                case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
                    {ok, Targets} ->
                        maps:keys(Targets);

                    {error, _} ->
                        []
                end;

            ancestors ->
                case gleam_stdlib:map_get(erlang:element(5, Graph), Node) of
                    {ok, Sources} ->
                        maps:keys(Sources);

                    {error, _} ->
                        []
                end
        end end,
    Reachability_sets = gleam@list:fold(
        Nodes_to_process,
        maps:new(),
        fun(Acc, Node@1) ->
            Related = Get_related(Node@1),
            Related_set = gleam@set:from_list(Related),
            All_reachable = gleam@list:fold(
                Related,
                Related_set,
                fun(Set_acc, Child) -> case gleam_stdlib:map_get(Acc, Child) of
                        {ok, Child_set} ->
                            gleam@set:union(Set_acc, Child_set);

                        {error, _} ->
                            Set_acc
                    end end
            ),
            gleam@dict:insert(Acc, Node@1, All_reachable)
        end
    ),
    gleam@dict:map_values(
        Reachability_sets,
        fun(_, Reachable) -> gleam@set:size(Reachable) end
    ).

-file("src/yog/dag/algorithms.gleam", 407).
-spec do_has_path(
    yog@model:graph(any(), any()),
    list(integer()),
    integer(),
    gleam@set:set(integer())
) -> boolean().
do_has_path(Graph, Stack, Target, Visited) ->
    case Stack of
        [] ->
            false;

        [Current | Rest] ->
            case Current =:= Target of
                true ->
                    true;

                false ->
                    case gleam@set:contains(Visited, Current) of
                        true ->
                            do_has_path(Graph, Rest, Target, Visited);

                        false ->
                            New_visited = gleam@set:insert(Visited, Current),
                            Children = case gleam_stdlib:map_get(
                                erlang:element(4, Graph),
                                Current
                            ) of
                                {ok, Edges} ->
                                    maps:keys(Edges);

                                {error, _} ->
                                    []
                            end,
                            New_stack = gleam@list:fold(
                                Children,
                                Rest,
                                fun(Acc, Child) -> [Child | Acc] end
                            ),
                            do_has_path(Graph, New_stack, Target, New_visited)
                    end
            end
    end.

-file("src/yog/dag/algorithms.gleam", 399).
?DOC(" Helper: does a path exist from `start` to `target`?\n").
-spec has_path(yog@dag@models:dag(any(), any()), integer(), integer()) -> boolean().
has_path(Dag, Start, Target) ->
    Graph = yog@dag@models:to_graph(Dag),
    do_has_path(Graph, [Start], Target, gleam@set:new()).

-file("src/yog/dag/algorithms.gleam", 390).
-spec get_ancestors_set(yog@dag@models:dag(any(), any()), integer()) -> list(integer()).
get_ancestors_set(Dag, Node) ->
    Graph = yog@dag@models:to_graph(Dag),
    All_nodes = maps:keys(erlang:element(3, Graph)),
    gleam@list:filter(All_nodes, fun(N) -> has_path(Dag, N, Node) end).

-file("src/yog/dag/algorithms.gleam", 361).
?DOC(
    " lowest_common_ancestors(Dag(n, e), NodeId, NodeId) -> List(NodeId)\n"
    " Goal: Find the immediate common dependencies of two nodes.\n"
).
-spec lowest_common_ancestors(
    yog@dag@models:dag(any(), any()),
    integer(),
    integer()
) -> list(integer()).
lowest_common_ancestors(Dag, Node_a, Node_b) ->
    Ancestors_counts_a = get_ancestors_set(Dag, Node_a),
    Ancestors_counts_b = get_ancestors_set(Dag, Node_b),
    Common_ancestors = gleam@list:filter(
        Ancestors_counts_a,
        fun(A) -> gleam@list:contains(Ancestors_counts_b, A) end
    ),
    gleam@list:filter(
        Common_ancestors,
        fun(Candidate) ->
            Is_ancestor_of_another = gleam@list:any(
                Common_ancestors,
                fun(Other) -> case Candidate =:= Other of
                        true ->
                            false;

                        false ->
                            has_path(Dag, Candidate, Other)
                    end end
            ),
            not Is_ancestor_of_another
        end
    ).