yog

-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, 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(
    " Algorithms for Directed Acyclic Graphs (DAGs).\n"
    "\n"
    " This module provides efficient algorithms that leverage the acyclicity guarantee\n"
    " of the `Dag` type. These algorithms run in linear O(V+E) time, faster than\n"
    " their general-graph counterparts.\n"
    "\n"
    " ## Available Algorithms\n"
    "\n"
    " | Algorithm | Function | Use Case |\n"
    " |-----------|----------|----------|\n"
    " | Topological Sort | `topological_sort/1` | Task scheduling, build systems |\n"
    " | Longest Path | `longest_path/1` | Critical path analysis, project scheduling |\n"
    " | Shortest Path | `shortest_path/3` | Weighted DAG shortest paths |\n"
    " | Transitive Closure | `transitive_closure/2` | Reachability queries |\n"
    " | Transitive Reduction | `transitive_reduction/2` | Minimal graph representation |\n"
    " | LCA | `lowest_common_ancestors/3` | Dependency analysis, merge bases |\n"
    "\n"
    " ## Time Complexity\n"
    "\n"
    " Most algorithms run in **O(V + E)** linear time due to DP on topologically sorted nodes:\n"
    " - Path algorithms: O(V + E)\n"
    " - Transitive closure/reduction: O(V × E) worst case\n"
    " - LCA computation: O(V × (V + E))\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog/dag/algorithm as dag\n"
    "\n"
    " // Find critical path in a project schedule (weighted DAG)\n"
    " let critical_path = dag.longest_path(project_dag)\n"
    " ```\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: Directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph)\n"
    " - [Topological Sorting](https://en.wikipedia.org/wiki/Topological_sorting)\n"
    " - [Critical Path Method](https://en.wikipedia.org/wiki/Critical_path_method)\n"
).

-type direction() :: ancestors | descendants.

-file("src/yog/dag/algorithm.gleam", 72).
?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 => 75,
                        value => _assert_fail,
                        start => 2945,
                        'end' => 3002,
                        pattern_start => 2956,
                        pattern_end => 2966})
    end,
    Sorted@1.

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

        {error, _} ->
            New_path
    end.

-file("src/yog/dag/algorithm.gleam", 100).
?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} = begin
        gleam@list:fold(
            Sorted_nodes,
            {maps:new(), maps:new()},
            fun(_use0, Node) ->
                {Dist_acc, Pred_acc} = Acc = _use0,
                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(_use0@1, Target, Weight) ->
                                {D_acc, P_acc} = Inner_acc = _use0@1,
                                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
        )
    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, _}} ->
            do_reconstruct_path(End_node, Predecessors, [])
    end.

-file("src/yog/dag/algorithm.gleam", 207).
?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@path:path(integer())).
shortest_path(Dag, Start, Goal) ->
    Graph = yog@dag@model:to_graph(Dag),
    Sorted_nodes = topological_sort(Dag),
    {Distances, Predecessors} = begin
        gleam@list:fold(
            Sorted_nodes,
            {maps:new(), maps:new()},
            fun(_use0, Node) ->
                {Dist_acc, Pred_acc} = Acc = _use0,
                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(_use0@1, Target, Weight) ->
                                {D_acc, P_acc} = Inner_acc = _use0@1,
                                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
        )
    end,
    case gleam_stdlib:map_get(Distances, Goal) of
        {error, _} ->
            none;

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

-file("src/yog/dag/algorithm.gleam", 292).
?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),
            _pipe@1 = gleam@list:fold(
                Related,
                gleam@set:from_list(Related),
                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, _pipe@1)
        end
    ),
    gleam@dict:map_values(
        Reachability_sets,
        fun(_, Reachable) -> gleam@set:size(Reachable) end
    ).

-file("src/yog/dag/algorithm.gleam", 403).
-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 | _] when Current =:= Target ->
            true;

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

                false ->
                    _pipe = case gleam_stdlib:map_get(
                        erlang:element(4, Graph),
                        Current@1
                    ) of
                        {ok, Edges} ->
                            maps:keys(Edges);

                        {error, _} ->
                            []
                    end,
                    _pipe@1 = gleam@list:fold(
                        _pipe,
                        Rest,
                        fun(Acc, Child) -> [Child | Acc] end
                    ),
                    do_has_path(
                        Graph,
                        _pipe@1,
                        Target,
                        gleam@set:insert(Visited, Current@1)
                    )
            end
    end.

-file("src/yog/dag/algorithm.gleam", 396).
?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", 384).
-spec get_ancestors_set(yog@dag@model:dag(any(), any()), integer()) -> list(integer()).
get_ancestors_set(Dag, Node) ->
    _pipe = erlang:element(3, yog@dag@model:to_graph(Dag)),
    _pipe@1 = maps:keys(_pipe),
    gleam@list:filter(
        _pipe@1,
        fun(_capture) -> has_path(Dag, _capture, Node) end
    ).

-file("src/yog/dag/algorithm.gleam", 362).
?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(_capture) -> gleam@list:contains(Ancestors_counts_b, _capture) 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
    ).