-module(yog@dag@algorithm).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/dag/algorithm.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.

?MODULEDOC(
    " # ⚠️ Experimental Module\n"
    "\n"
    " This module is experimental and provides minimal, working functionality.\n"
    " The implementation is functional but may not be fully optimized for performance.\n"
    "\n"
    " **Expected changes:**\n"
    " - Additional features and algorithms will be added\n"
    " - Performance enhancements and optimizations\n"
    " - API may be subject to change in future versions\n"
    "\n"
    " Use with caution in production environments.\n"
).

-type direction() :: ancestors | descendants.

-file("src/yog/dag/algorithm.gleam", 45).
?DOC(
    " Returns a topological ordering of all nodes in the DAG.\n"
    "\n"
    " Unlike `traversal.topological_sort()` which returns `Result` (since general\n"
    " graphs may contain cycles), this version is **total** - it always returns\n"
    " a valid ordering because the `Dag` type guarantees acyclicity.\n"
    "\n"
    " In a topological ordering, every node appears before all nodes it has edges to.\n"
    " This is useful for scheduling tasks with dependencies, build systems, etc.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Given edges: 1->2, 1->3, 2->4, 3->4\n"
    " // Valid topological sorts include: [1, 2, 3, 4] or [1, 3, 2, 4]\n"
    " let sorted = dag.algorithms.topological_sort(my_dag)\n"
    " // sorted == [1, 2, 3, 4]  // or another valid ordering\n"
    " ```\n"
).
-spec topological_sort(yog@dag@model:dag(any(), any())) -> list(integer()).
topological_sort(Dag) ->
    Graph = yog@dag@model: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/algorithm"/utf8>>,
                        function => <<"topological_sort"/utf8>>,
                        line => 48,
                        value => _assert_fail,
                        start => 1774,
                        'end' => 1831,
                        pattern_start => 1785,
                        pattern_end => 1795})
    end,
    Sorted@1.

-file("src/yog/dag/algorithm.gleam", 134).
-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/algorithm.gleam", 73).
?DOC(
    " Finds the longest path (critical path) in a weighted DAG.\n"
    "\n"
    " The longest path is the path with maximum total edge weight from any source\n"
    " node to any sink node. This is the dual of shortest path and is useful for:\n"
    " - Project scheduling (finding the critical path)\n"
    " - Dependency chains with durations\n"
    " - Determining minimum time to complete all tasks\n"
    "\n"
    " **Time Complexity:** O(V + E) - linear via dynamic programming on the\n"
    " topologically sorted DAG.\n"
    "\n"
    " **Note:** For unweighted graphs, this finds the path with most edges.\n"
    " Weights must be non-negative for meaningful results.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Find the critical path in a project schedule\n"
    " let critical_path = dag.algorithms.longest_path(project_dag)\n"
    " // critical_path == [start, task_a, task_b, end]\n"
    " ```\n"
).
-spec longest_path(yog@dag@model:dag(any(), integer())) -> list(integer()).
longest_path(Dag) ->
    Graph = yog@dag@model: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/algorithm.gleam", 169).
?DOC(
    " Computes the transitive closure of a DAG.\n"
    "\n"
    " The transitive closure adds edges between all pairs of nodes where a path\n"
    " exists in the original graph. If `u` can reach `v` through any path, the\n"
    " closure will have a direct edge `u -> v`.\n"
    "\n"
    " The `merge_fn` is used to combine edge weights when multiple paths exist\n"
    " between the same pair of nodes.\n"
    "\n"
    " **Use cases:**\n"
    " - Reachability queries (is A reachable from B?)\n"
    " - Precomputing path relationships\n"
    " - Dependency analysis (what indirectly depends on what?)\n"
    "\n"
    " **Time Complexity:** O(V × E) in the worst case\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Original edges: A->B (weight 2), B->C (weight 3)\n"
    " // Closure adds: A->C (weight 5 = 2+3)\n"
    " let closure = dag.algorithms.transitive_closure(dag, int.add)\n"
    " ```\n"
).
-spec transitive_closure(yog@dag@model:dag(PMO, PMP), fun((PMP, PMP) -> PMP)) -> yog@dag@model:dag(PMO, PMP).
transitive_closure(Dag, Merge_fn) ->
    Graph = yog@dag@model: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) ->
                    G@1 = case yog@model:add_edge(
                        G_inner,
                        Source_node,
                        Target_node,
                        Weight
                    ) of
                        {ok, G} -> G;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"yog/dag/algorithm"/utf8>>,
                                        function => <<"transitive_closure"/utf8>>,
                                        line => 229,
                                        value => _assert_fail,
                                        start => 8079,
                                        'end' => 8242,
                                        pattern_start => 8090,
                                        pattern_end => 8095})
                    end,
                    G@1
                end
            )
        end
    ),
    New_dag@1 = case yog@dag@model:from_graph(New_graph) of
        {ok, New_dag} -> New_dag;
        _assert_fail@1 ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/dag/algorithm"/utf8>>,
                        function => <<"transitive_closure"/utf8>>,
                        line => 240,
                        value => _assert_fail@1,
                        start => 8272,
                        'end' => 8364,
                        pattern_start => 8283,
                        pattern_end => 8294})
    end,
    New_dag@1.

-file("src/yog/dag/algorithm.gleam", 267).
?DOC(
    " Computes the transitive reduction of a DAG.\n"
    "\n"
    " The transitive reduction removes all edges that are redundant - i.e., edges\n"
    " `u -> v` where there exists an indirect path from `u` to `v` through other\n"
    " nodes. The result has the minimum number of edges while preserving all\n"
    " reachability relationships.\n"
    "\n"
    " This is the inverse of transitive closure. It's useful for:\n"
    " - Simplifying dependency graphs\n"
    " - Removing implied dependencies\n"
    " - Creating minimal representations\n"
    "\n"
    " **Time Complexity:** O(V × E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Original: A->B, B->C, A->C (A->C is implied by A->B->C)\n"
    " // Reduction removes: A->C\n"
    " // Result: A->B, B->C\n"
    " let minimal = dag.algorithms.transitive_reduction(dag, int.add)\n"
    " ```\n"
).
-spec transitive_reduction(yog@dag@model:dag(PMU, PMV), fun((PMV, PMV) -> PMV)) -> yog@dag@model:dag(PMU, PMV).
transitive_reduction(Dag, Merge_fn) ->
    Graph = yog@dag@model:to_graph(Dag),
    Reach_dag = transitive_closure(Dag, Merge_fn),
    Reach_graph = yog@dag@model: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@model: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/algorithm"/utf8>>,
                        function => <<"transitive_reduction"/utf8>>,
                        line => 303,
                        value => _assert_fail,
                        start => 10338,
                        'end' => 10434,
                        pattern_start => 10349,
                        pattern_end => 10360})
    end,
    New_dag@1.

-file("src/yog/dag/algorithm.gleam", 404).
-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/algorithm.gleam", 342).
?DOC(
    " Finds the shortest path between two specific nodes in a weighted DAG.\n"
    "\n"
    " Uses dynamic programming on the topologically sorted DAG to find the minimum\n"
    " weight path from `from` to `to`. Unlike Dijkstra's algorithm which works on\n"
    " general graphs in O((V+E) log V), this leverages the DAG property for linear\n"
    " time complexity.\n"
    "\n"
    " Returns `None` if no path exists from `from` to `to`.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Find shortest path in a weighted DAG\n"
    " case dag.algorithms.shortest_path(my_dag, from: start_node, to: end_node) {\n"
    "   Some(path) -> {\n"
    "     // path.nodes contains the node sequence\n"
    "     // path.total_weight is the path length\n"
    "   }\n"
    "   None -> // No path exists\n"
    " }\n"
    " ```\n"
).
-spec shortest_path(yog@dag@model:dag(any(), integer()), integer(), integer()) -> gleam@option:option(yog@pathfinding@utils:path(integer())).
shortest_path(Dag, Start, Goal) ->
    Graph = yog@dag@model: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/algorithm.gleam", 445).
?DOC(
    " Counts the number of ancestors or descendants for every node.\n"
    "\n"
    " For each node, returns how many other nodes are reachable from it\n"
    " (`Descendants`) or can reach it (`Ancestors`).\n"
    "\n"
    " Uses dynamic programming on the topologically sorted DAG for efficiency.\n"
    " Properly handles diamond patterns where a node is reachable through multiple\n"
    " paths - each node is only counted once.\n"
    "\n"
    " **Time Complexity:** O(V × E) in the worst case (sparse graphs),\n"
    " optimized with set operations for common cases.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Given: A->B, A->C, B->D, C->D (diamond pattern)\n"
    " // D has 3 ancestors (A, B, C)\n"
    " // A has 3 descendants (B, C, D) - D counted once despite 2 paths\n"
    " let descendant_counts = dag.algorithms.count_reachability(dag, Descendants)\n"
    " // dict.get(descendant_counts, a) == Ok(3)\n"
    " ```\n"
).
-spec count_reachability(yog@dag@model:dag(any(), any()), direction()) -> gleam@dict:dict(integer(), integer()).
count_reachability(Dag, Direction) ->
    Graph = yog@dag@model: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/algorithm.gleam", 568).
-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/algorithm.gleam", 560).
?DOC(
    " Checks if a path exists from `start` to `target` in the DAG.\n"
    "\n"
    " Performs a simple DFS traversal. Since the graph is a DAG, no cycle\n"
    " detection is needed.\n"
    "\n"
    " **Time Complexity:** O(V + E) in the worst case\n"
).
-spec has_path(yog@dag@model:dag(any(), any()), integer(), integer()) -> boolean().
has_path(Dag, Start, Target) ->
    Graph = yog@dag@model:to_graph(Dag),
    do_has_path(Graph, [Start], Target, gleam@set:new()).

-file("src/yog/dag/algorithm.gleam", 546).
-spec get_ancestors_set(yog@dag@model:dag(any(), any()), integer()) -> list(integer()).
get_ancestors_set(Dag, Node) ->
    Graph = yog@dag@model: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/algorithm.gleam", 517).
?DOC(
    " Finds the lowest common ancestors (LCAs) of two nodes.\n"
    "\n"
    " A common ancestor of nodes A and B is any node that has paths to both A and B.\n"
    " The \"lowest\" common ancestors are those that are not ancestors of any other\n"
    " common ancestor - they are the \"closest\" shared dependencies.\n"
    "\n"
    " This is useful for:\n"
    " - Finding merge bases in version control\n"
    " - Identifying shared dependencies\n"
    " - Computing dominators in control flow graphs\n"
    "\n"
    " **Time Complexity:** O(V × (V + E))\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Given: X->A, X->B, Y->A, Z->B\n"
    " // LCAs of A and B are [X] - the most specific shared ancestor\n"
    " let lcas = dag.algorithms.lowest_common_ancestors(dag, a, b)\n"
    " // lcas == [x]\n"
    " ```\n"
).
-spec lowest_common_ancestors(
    yog@dag@model: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
    ).