yog

-module(yog@mst).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/mst.gleam").
-export([wilson/3, wilson_with_seed/4, wilson_int/1, wilson_float/1, wilson_int_with_seed/2, wilson_float_with_seed/2, kruskal/4, boruvka/4, kruskal_int/1, kruskal_float/1, boruvka_int/1, boruvka_float/1, edmonds/6, edmonds_int/2, edmonds_float/2, prim/4, prim_int/1, prim_float/1]).
-export_type([algorithm/0, edge/1, mst_result/1, edmonds_graph/1, cycle_info/1]).

-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(
    " Minimum Spanning Tree (MST) algorithms for finding optimal network connections.\n"
    "\n"
    " A [Minimum Spanning Tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree) connects all nodes\n"
    " in a weighted undirected graph with the minimum possible total edge weight. MSTs have\n"
    " applications in network design, clustering, and optimization problems.\n"
    "\n"
    " ## Available Algorithms\n"
    "\n"
    " | Algorithm | Function | Best For |\n"
    " |-----------|----------|----------|\n"
    " | [Kruskal's](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) | `kruskal/4` | Sparse graphs, edge lists |\n"
    " | [Prim's](https://en.wikipedia.org/wiki/Prim%27s_algorithm) | `prim/4` | Dense graphs, adjacency-based |\n"
    " | [Borůvka's](https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm) | `boruvka/4` | Parallel/distributed MST |\n"
    " | [Chu-Liu/Edmonds](https://en.wikipedia.org/wiki/Edmonds%27_algorithm) | `edmonds/6` | Directed MSA (arborescence) |\n"
    " | Wilson's | `wilson/2` | Uniform random spanning tree |\n"
    "\n"
    " ## Properties of MSTs\n"
    "\n"
    " - Connects all nodes with exactly `V - 1` edges (for a graph with V nodes)\n"
    " - Contains no cycles\n"
    " - Minimizes the sum of edge weights\n"
    " - May not be unique if multiple edges have the same weight\n"
    "\n"
    " ## Maximum Spanning Trees\n"
    "\n"
    " While these functions are named for Minimum Spanning Trees, they are fully\n"
    " generic. To find a **Maximum Spanning Tree**, simply provide a comparator\n"
    " that reverses the natural order of your weights (e.g., using `order.reverse(int.compare)`).\n"
    " This will cause the algorithms to prioritize the largest weights first,\n"
    " yielding the maximum possible total weight.\n"
    "\n"
    " > [!TIP]\n"
    " > **Widest Path Problem**: In an undirected graph, the unique path between two nodes\n"
    " > in a Maximum Spanning Tree is also a **widest path** (or maximum capacity path).\n"
    " > If you need to find a path that maximizes the bottleneck capacity between two\n"
    " > nodes, you can calculate the MaxST and then find the path in that tree.\n"
    "\n"
    " ## Example Use Cases\n"
    "\n"
    " - **Network Design**: Minimizing cable length to connect buildings\n"
    " - **Cluster Analysis**: Hierarchical clustering via MST\n"
    " - **Approximation**: Traveling Salesman Problem approximations\n"
    " - **Image Segmentation**: Computer vision applications\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: Minimum Spanning Tree](https://en.wikipedia.org/wiki/Minimum_spanning_tree)\n"
    " - [CP-Algorithms: MST](https://cp-algorithms.com/graph/mst_kruskal.html)\n"
).

-type algorithm() :: kruskal | prim | boruvka | chu_liu_edmonds | wilson.

-type edge(TXC) :: {edge, integer(), integer(), TXC}.

-type mst_result(TXD) :: {mst_result,
        list(edge(TXD)),
        TXD,
        integer(),
        integer(),
        algorithm(),
        gleam@option:option(integer())}.

-type edmonds_graph(TXE) :: {edmonds_graph, list(integer()), list(edge(TXE))}.

-type cycle_info(TXF) :: {cycle_info,
        integer(),
        list(integer()),
        gleam@dict:dict({integer(), integer()}, edge(TXF))}.

-file("src/yog/mst.gleam", 110).
-spec do_kruskal(
    list(edge(TXL)),
    yog@disjoint_set:disjoint_set(integer()),
    list(edge(TXL))
) -> list(edge(TXL)).
do_kruskal(Edges, Disjoint_set_state, Acc) ->
    case Edges of
        [] ->
            lists:reverse(Acc);

        [Edge | Rest] ->
            {Disjoint_set1, Root_from} = begin
                _pipe = Disjoint_set_state,
                yog@disjoint_set:find(_pipe, erlang:element(2, Edge))
            end,
            {Disjoint_set2, Root_to} = begin
                _pipe@1 = Disjoint_set1,
                yog@disjoint_set:find(_pipe@1, erlang:element(3, Edge))
            end,
            case Root_from =:= Root_to of
                true ->
                    do_kruskal(Rest, Disjoint_set2, Acc);

                false ->
                    _pipe@2 = Disjoint_set2,
                    _pipe@3 = yog@disjoint_set:union(
                        _pipe@2,
                        erlang:element(2, Edge),
                        erlang:element(3, Edge)
                    ),
                    do_kruskal(Rest, _pipe@3, [Edge | Acc])
            end
    end.

-file("src/yog/mst.gleam", 264).
-spec update_best(
    gleam@dict:dict(integer(), edge(TZD)),
    integer(),
    edge(TZD),
    fun((TZD, TZD) -> gleam@order:order())
) -> gleam@dict:dict(integer(), edge(TZD)).
update_best(Best_map, Root, Edge, Compare) ->
    case gleam_stdlib:map_get(Best_map, Root) of
        {error, _} ->
            gleam@dict:insert(Best_map, Root, Edge);

        {ok, Existing} ->
            case Compare(erlang:element(4, Edge), erlang:element(4, Existing)) of
                lt ->
                    gleam@dict:insert(Best_map, Root, Edge);

                _ ->
                    Best_map
            end
    end.

-file("src/yog/mst.gleam", 245).
-spec find_best_edges_for_components(
    list(edge(TYW)),
    yog@disjoint_set:disjoint_set(integer()),
    fun((TYW, TYW) -> gleam@order:order())
) -> gleam@dict:dict(integer(), edge(TYW)).
find_best_edges_for_components(Edges, Dsu, Compare) ->
    gleam@list:fold(
        Edges,
        maps:new(),
        fun(Acc, Edge) ->
            {_, Root_u} = yog@disjoint_set:find(Dsu, erlang:element(2, Edge)),
            {_, Root_v} = yog@disjoint_set:find(Dsu, erlang:element(3, Edge)),
            case Root_u =:= Root_v of
                true ->
                    Acc;

                false ->
                    _pipe = Acc,
                    _pipe@1 = update_best(_pipe, Root_u, Edge, Compare),
                    update_best(_pipe@1, Root_v, Edge, Compare)
            end
        end
    ).

-file("src/yog/mst.gleam", 281).
-spec deduplicate_cheapest(list(edge(TZL))) -> list(edge(TZL)).
deduplicate_cheapest(Edges) ->
    {Result, _} = gleam@list:fold(
        Edges,
        {[], gleam@set:new()},
        fun(Acc, Edge) ->
            Key = case erlang:element(2, Edge) > erlang:element(3, Edge) of
                true ->
                    {erlang:element(3, Edge), erlang:element(2, Edge)};

                false ->
                    {erlang:element(2, Edge), erlang:element(3, Edge)}
            end,
            case gleam@set:contains(erlang:element(2, Acc), Key) of
                true ->
                    Acc;

                false ->
                    {[Edge | erlang:element(1, Acc)],
                        gleam@set:insert(erlang:element(2, Acc), Key)}
            end
        end
    ),
    lists:reverse(Result).

-file("src/yog/mst.gleam", 215).
-spec do_boruvka(
    list(edge(TYO)),
    yog@disjoint_set:disjoint_set(integer()),
    list(edge(TYO)),
    fun((TYO, TYO) -> gleam@order:order())
) -> list(edge(TYO)).
do_boruvka(All_edges, Dsu, Mst_edges, Compare) ->
    case yog@disjoint_set:count_sets(Dsu) =< 1 of
        true ->
            lists:reverse(Mst_edges);

        false ->
            Cheapest = find_best_edges_for_components(All_edges, Dsu, Compare),
            case maps:size(Cheapest) =:= 0 of
                true ->
                    lists:reverse(Mst_edges);

                false ->
                    Edges_to_add = deduplicate_cheapest(maps:values(Cheapest)),
                    {New_dsu, New_mst} = gleam@list:fold(
                        Edges_to_add,
                        {Dsu, Mst_edges},
                        fun(Acc, Edge) ->
                            {yog@disjoint_set:union(
                                    erlang:element(1, Acc),
                                    erlang:element(2, Edge),
                                    erlang:element(3, Edge)
                                ),
                                [Edge | erlang:element(2, Acc)]}
                        end
                    ),
                    Old_count = yog@disjoint_set:count_sets(Dsu),
                    New_count = yog@disjoint_set:count_sets(New_dsu),
                    case New_count =:= Old_count of
                        true ->
                            lists:reverse(Mst_edges);

                        false ->
                            do_boruvka(All_edges, New_dsu, New_mst, Compare)
                    end
            end
    end.

-file("src/yog/mst.gleam", 397).
-spec find_best_in_edges(
    edmonds_graph(UAD),
    integer(),
    fun((UAD, UAD) -> gleam@order:order())
) -> gleam@dict:dict(integer(), edge(UAD)).
find_best_in_edges(Graph, Root, Compare) ->
    gleam@list:fold(
        erlang:element(2, Graph),
        maps:new(),
        fun(Acc, Node_id) -> case Node_id =:= Root of
                true ->
                    Acc;

                false ->
                    Incoming = gleam@list:filter(
                        erlang:element(3, Graph),
                        fun(E) -> erlang:element(3, E) =:= Node_id end
                    ),
                    case Incoming of
                        [] ->
                            Acc;

                        [First | Rest] ->
                            Best@1 = gleam@list:fold(
                                Rest,
                                First,
                                fun(Best, E@1) ->
                                    case Compare(
                                        erlang:element(4, E@1),
                                        erlang:element(4, Best)
                                    ) of
                                        lt ->
                                            E@1;

                                        _ ->
                                            Best
                                    end
                                end
                            ),
                            gleam@dict:insert(Acc, Node_id, Best@1)
                    end
            end end
    ).

-file("src/yog/mst.gleam", 434).
-spec find_cycle_dfs(
    integer(),
    gleam@dict:dict(integer(), edge(any())),
    gleam@dict:dict(integer(), binary()),
    list(integer())
) -> {ok, list(integer())} | {error, nil}.
find_cycle_dfs(Node, Best_in, Visited, Path) ->
    case gleam_stdlib:map_get(Visited, Node) of
        {ok, <<"visiting"/utf8>>} ->
            Cycle = [Node |
                gleam@list:take_while(Path, fun(X) -> X /= Node end)],
            {ok, lists:reverse(Cycle)};

        {ok, _} ->
            {error, nil};

        {error, _} ->
            case gleam_stdlib:map_get(Best_in, Node) of
                {error, _} ->
                    {error, nil};

                {ok, Edge} ->
                    find_cycle_dfs(
                        erlang:element(2, Edge),
                        Best_in,
                        gleam@dict:insert(Visited, Node, <<"visiting"/utf8>>),
                        [Node | Path]
                    )
            end
    end.

-file("src/yog/mst.gleam", 424).
-spec find_cycle_in_best_in(
    gleam@dict:dict(integer(), edge(any())),
    list(integer())
) -> list(integer()).
find_cycle_in_best_in(Best_in, Nodes) ->
    _pipe = gleam@list:find_map(
        Nodes,
        fun(Start_node) ->
            find_cycle_dfs(Start_node, Best_in, maps:new(), [])
        end
    ),
    gleam@result:unwrap(_pipe, []).

-file("src/yog/mst.gleam", 462).
-spec contract_cycle(
    edmonds_graph(UAY),
    list(integer()),
    gleam@dict:dict(integer(), edge(UAY)),
    fun((UAY, UAY) -> UAY),
    integer(),
    fun((UAY, UAY) -> gleam@order:order())
) -> {edmonds_graph(UAY), cycle_info(UAY)}.
contract_cycle(Graph, Cycle, Best_in, Subtract, Super_node, Compare) ->
    Cycle_set = gleam@set:from_list(Cycle),
    New_nodes = gleam@list:filter(
        erlang:element(2, Graph),
        fun(N) -> not gleam@set:contains(Cycle_set, N) end
    ),
    New_nodes@1 = [Super_node | New_nodes],
    Candidates = gleam@list:filter_map(
        erlang:element(3, Graph),
        fun(Edge) ->
            U_in = gleam@set:contains(Cycle_set, erlang:element(2, Edge)),
            V_in = gleam@set:contains(Cycle_set, erlang:element(3, Edge)),
            case {U_in, V_in} of
                {true, true} ->
                    {error, nil};

                {true, false} ->
                    {ok,
                        {{edge,
                                Super_node,
                                erlang:element(3, Edge),
                                erlang:element(4, Edge)},
                            Edge}};

                {false, true} ->
                    Best_in_v@1 = case gleam_stdlib:map_get(
                        Best_in,
                        erlang:element(3, Edge)
                    ) of
                        {ok, Best_in_v} -> Best_in_v;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"yog/mst"/utf8>>,
                                        function => <<"contract_cycle"/utf8>>,
                                        line => 483,
                                        value => _assert_fail,
                                        start => 14705,
                                        'end' => 14758,
                                        pattern_start => 14716,
                                        pattern_end => 14729})
                    end,
                    New_weight = Subtract(
                        erlang:element(4, Edge),
                        erlang:element(4, Best_in_v@1)
                    ),
                    {ok,
                        {{edge, erlang:element(2, Edge), Super_node, New_weight},
                            Edge}};

                {false, false} ->
                    {ok, {Edge, Edge}}
            end
        end
    ),
    Deduped = gleam@list:fold(
        Candidates,
        maps:new(),
        fun(Acc, Pair) ->
            {C_edge, Orig_edge} = Pair,
            Key = {erlang:element(2, C_edge), erlang:element(3, C_edge)},
            case gleam_stdlib:map_get(Acc, Key) of
                {ok, {Existing, _}} ->
                    case Compare(
                        erlang:element(4, C_edge),
                        erlang:element(4, Existing)
                    ) of
                        lt ->
                            gleam@dict:insert(Acc, Key, {C_edge, Orig_edge});

                        _ ->
                            Acc
                    end;

                {error, _} ->
                    gleam@dict:insert(Acc, Key, {C_edge, Orig_edge})
            end
        end
    ),
    New_edges = begin
        _pipe = maps:values(Deduped),
        gleam@list:map(_pipe, fun(P) -> erlang:element(1, P) end)
    end,
    Mapping = gleam@dict:map_values(
        Deduped,
        fun(_, Pair@1) -> erlang:element(2, Pair@1) end
    ),
    {{edmonds_graph, New_nodes@1, New_edges},
        {cycle_info, Super_node, Cycle, Mapping}}.

-file("src/yog/mst.gleam", 516).
-spec expand_cycle(
    list(edge(UBG)),
    cycle_info(UBG),
    gleam@dict:dict(integer(), edge(UBG))
) -> list(edge(UBG)).
expand_cycle(Contracted_edges, Cycle_info, Best_in) ->
    {cycle_info, Super_node, Cycle, Mapping} = Cycle_info,
    Entry_edge_contracted = gleam@list:find(
        Contracted_edges,
        fun(E) -> erlang:element(3, E) =:= Super_node end
    ),
    Entry_orig = case Entry_edge_contracted of
        {ok, E@1} ->
            gleam_stdlib:map_get(Mapping, {erlang:element(2, E@1), Super_node});

        {error, _} ->
            {error, nil}
    end,
    Node_to_bypass = case Entry_orig of
        {ok, Orig} ->
            erlang:element(3, Orig);

        {error, _} ->
            -1
    end,
    Final_edges = gleam@list:flat_map(
        Contracted_edges,
        fun(E@2) ->
            case {erlang:element(3, E@2) =:= Super_node,
                erlang:element(2, E@2) =:= Super_node} of
                {true, _} ->
                    case Entry_orig of
                        {ok, Orig@1} ->
                            [Orig@1];

                        {error, _} ->
                            []
                    end;

                {_, true} ->
                    case gleam_stdlib:map_get(
                        Mapping,
                        {Super_node, erlang:element(3, E@2)}
                    ) of
                        {ok, Orig@2} ->
                            [Orig@2];

                        {error, _} ->
                            []
                    end;

                {_, _} ->
                    [E@2]
            end
        end
    ),
    Cycle_edges = gleam@list:filter_map(
        Cycle,
        fun(Node) -> case gleam_stdlib:map_get(Best_in, Node) of
                {ok, Edge} when erlang:element(3, Edge) =/= Node_to_bypass ->
                    {ok, Edge};

                _ ->
                    {error, nil}
            end end
    ),
    lists:append(Final_edges, Cycle_edges).

-file("src/yog/mst.gleam", 357).
-spec do_edmonds(
    edmonds_graph(TZX),
    integer(),
    fun((TZX, TZX) -> gleam@order:order()),
    fun((TZX, TZX) -> TZX),
    integer()
) -> {ok, list(edge(TZX))} | {error, binary()}.
do_edmonds(Graph, Root, Compare, Subtract, Super_counter) ->
    Nodes = erlang:element(2, Graph),
    Best_in = find_best_in_edges(Graph, Root, Compare),
    Unreachable = gleam@list:any(
        Nodes,
        fun(V) -> (V /= Root) andalso not gleam@dict:has_key(Best_in, V) end
    ),
    case Unreachable of
        true ->
            {error, <<"No arborescence exists"/utf8>>};

        false ->
            Cycle = find_cycle_in_best_in(Best_in, Nodes),
            case Cycle of
                [] ->
                    {ok, maps:values(Best_in)};

                Cycle_nodes ->
                    Super_node = Super_counter,
                    Next_counter = Super_counter - 1,
                    {Contracted, Cycle_info} = contract_cycle(
                        Graph,
                        Cycle_nodes,
                        Best_in,
                        Subtract,
                        Super_node,
                        Compare
                    ),
                    case do_edmonds(
                        Contracted,
                        Root,
                        Compare,
                        Subtract,
                        Next_counter
                    ) of
                        {ok, Contracted_edges} ->
                            {ok,
                                expand_cycle(
                                    Contracted_edges,
                                    Cycle_info,
                                    Best_in
                                )};

                        {error, Msg} ->
                            {error, Msg}
                    end
            end
    end.

-file("src/yog/mst.gleam", 638).
-spec perform_lerw(
    yog@model:graph(any(), any()),
    integer(),
    gleam@set:set(integer()),
    gleam@dict:dict(integer(), integer()),
    yog@internal@random:rng()
) -> {gleam@dict:dict(integer(), integer()), yog@internal@random:rng()}.
perform_lerw(Graph, Current, Tree, Path_map, Rng) ->
    case gleam@set:contains(Tree, Current) of
        true ->
            {Path_map, Rng};

        false ->
            Neighbors = yog@model:successor_ids(Graph, Current),
            case Neighbors of
                [] ->
                    {Path_map, Rng};

                _ ->
                    {Idx, Next_rng} = yog@internal@random:next_int(
                        Rng,
                        erlang:length(Neighbors)
                    ),
                    Next_node@1 = case yog@internal@util:list_at(Neighbors, Idx) of
                        {ok, Next_node} -> Next_node;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"yog/mst"/utf8>>,
                                        function => <<"perform_lerw"/utf8>>,
                                        line => 653,
                                        value => _assert_fail,
                                        start => 19515,
                                        'end' => 19570,
                                        pattern_start => 19526,
                                        pattern_end => 19539})
                    end,
                    perform_lerw(
                        Graph,
                        Next_node@1,
                        Tree,
                        gleam@dict:insert(Path_map, Current, Next_node@1),
                        Next_rng
                    )
            end
    end.

-file("src/yog/mst.gleam", 667).
-spec add_path_to_tree(
    yog@model:graph(any(), UCY),
    integer(),
    gleam@dict:dict(integer(), integer()),
    gleam@set:set(integer()),
    gleam@set:set(integer())
) -> {gleam@set:set(integer()), gleam@set:set(integer()), list(edge(UCY))}.
add_path_to_tree(Graph, Current, Path_map, Tree, Unvisited) ->
    case gleam@set:contains(Tree, Current) of
        true ->
            {Tree, Unvisited, []};

        false ->
            Next_node@1 = case gleam_stdlib:map_get(Path_map, Current) of
                {ok, Next_node} -> Next_node;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/mst"/utf8>>,
                                function => <<"add_path_to_tree"/utf8>>,
                                line => 677,
                                value => _assert_fail,
                                start => 20061,
                                'end' => 20115,
                                pattern_start => 20072,
                                pattern_end => 20085})
            end,
            Weight@1 = case yog@model:edge_data(Graph, Current, Next_node@1) of
                {ok, Weight} -> Weight;
                _assert_fail@1 ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/mst"/utf8>>,
                                function => <<"add_path_to_tree"/utf8>>,
                                line => 678,
                                value => _assert_fail@1,
                                start => 20122,
                                'end' => 20188,
                                pattern_start => 20133,
                                pattern_end => 20143})
            end,
            Edge = {edge, Current, Next_node@1, Weight@1},
            New_tree = gleam@set:insert(Tree, Current),
            New_unvisited = gleam@set:delete(Unvisited, Current),
            {Final_tree, Final_unvisited, Rest_edges} = add_path_to_tree(
                Graph,
                Next_node@1,
                Path_map,
                New_tree,
                New_unvisited
            ),
            {Final_tree, Final_unvisited, [Edge | Rest_edges]}
    end.

-file("src/yog/mst.gleam", 608).
-spec do_wilson_loop(
    yog@model:graph(any(), UCF),
    gleam@set:set(integer()),
    gleam@set:set(integer()),
    list(edge(UCF)),
    yog@internal@random:rng()
) -> {list(edge(UCF)), yog@internal@random:rng()}.
do_wilson_loop(Graph, Unvisited, Tree, Acc_edges, Rng) ->
    case gleam@set:size(Unvisited) of
        0 ->
            {lists:reverse(Acc_edges), Rng};

        _ ->
            Unvisited_list = gleam@set:to_list(Unvisited),
            {Idx, Next_rng} = yog@internal@random:next_int(
                Rng,
                erlang:length(Unvisited_list)
            ),
            Start_node@1 = case yog@internal@util:list_at(Unvisited_list, Idx) of
                {ok, Start_node} -> Start_node;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/mst"/utf8>>,
                                function => <<"do_wilson_loop"/utf8>>,
                                line => 620,
                                value => _assert_fail,
                                start => 18593,
                                'end' => 18654,
                                pattern_start => 18604,
                                pattern_end => 18618})
            end,
            {Path_map, Next_rng2} = perform_lerw(
                Graph,
                Start_node@1,
                Tree,
                maps:new(),
                Next_rng
            ),
            {New_tree, New_unvisited, Path_edges} = add_path_to_tree(
                Graph,
                Start_node@1,
                Path_map,
                Tree,
                Unvisited
            ),
            do_wilson_loop(
                Graph,
                New_unvisited,
                New_tree,
                lists:append(Acc_edges, Path_edges),
                Next_rng2
            )
    end.

-file("src/yog/mst.gleam", 795).
-spec make_result(
    list(edge(UFJ)),
    algorithm(),
    integer(),
    gleam@option:option(integer()),
    fun((UFJ, UFJ) -> UFJ),
    UFJ
) -> mst_result(UFJ).
make_result(Edges, Algorithm, Node_count, Root, Add, Zero) ->
    Total_weight = gleam@list:fold(
        Edges,
        Zero,
        fun(Acc, Edge) -> Add(Acc, erlang:element(4, Edge)) end
    ),
    {mst_result,
        Edges,
        Total_weight,
        Node_count,
        erlang:length(Edges),
        Algorithm,
        Root}.

-file("src/yog/mst.gleam", 590).
-spec do_wilson_generic(
    yog@model:graph(any(), UCA),
    yog@internal@random:rng(),
    fun((UCA, UCA) -> UCA),
    UCA
) -> mst_result(UCA).
do_wilson_generic(Graph, Rng, Add, Zero) ->
    Nodes = maps:keys(erlang:element(3, Graph)),
    case Nodes of
        [] ->
            make_result([], wilson, 0, none, Add, Zero);

        [First | _] ->
            Tree = gleam@set:from_list([First]),
            Unvisited = gleam@set:difference(gleam@set:from_list(Nodes), Tree),
            {Edges, _} = do_wilson_loop(Graph, Unvisited, Tree, [], Rng),
            make_result(Edges, wilson, erlang:length(Nodes), none, Add, Zero)
    end.

-file("src/yog/mst.gleam", 572).
?DOC(
    " Generates a Uniform Spanning Tree (UST) using Wilson's algorithm.\n"
    "\n"
    " Uses a random seed for non-deterministic sampling.\n"
).
-spec wilson(yog@model:graph(any(), UBQ), fun((UBQ, UBQ) -> UBQ), UBQ) -> mst_result(UBQ).
wilson(Graph, Add, Zero) ->
    do_wilson_generic(Graph, yog@internal@random:new(none), Add, Zero).

-file("src/yog/mst.gleam", 581).
?DOC(" Generates a Uniform Spanning Tree with a fixed seed for reproducibility.\n").
-spec wilson_with_seed(
    yog@model:graph(any(), UBV),
    integer(),
    fun((UBV, UBV) -> UBV),
    UBV
) -> mst_result(UBV).
wilson_with_seed(Graph, Seed, Add, Zero) ->
    do_wilson_generic(Graph, yog@internal@random:new({some, Seed}), Add, Zero).

-file("src/yog/mst.gleam", 766).
?DOC(" Wilson for `Int` weights.\n").
-spec wilson_int(yog@model:graph(any(), integer())) -> mst_result(integer()).
wilson_int(Graph) ->
    wilson(Graph, fun gleam@int:add/2, 0).

-file("src/yog/mst.gleam", 771).
?DOC(" Wilson for `Float` weights.\n").
-spec wilson_float(yog@model:graph(any(), float())) -> mst_result(float()).
wilson_float(Graph) ->
    wilson(Graph, fun gleam@float:add/2, +0.0).

-file("src/yog/mst.gleam", 776).
?DOC(" Wilson with fixed seed for `Int` weights.\n").
-spec wilson_int_with_seed(yog@model:graph(any(), integer()), integer()) -> mst_result(integer()).
wilson_int_with_seed(Graph, Seed) ->
    wilson_with_seed(Graph, Seed, fun gleam@int:add/2, 0).

-file("src/yog/mst.gleam", 784).
?DOC(" Wilson with fixed seed for `Float` weights.\n").
-spec wilson_float_with_seed(yog@model:graph(any(), float()), integer()) -> mst_result(float()).
wilson_float_with_seed(Graph, Seed) ->
    wilson_with_seed(Graph, Seed, fun gleam@float:add/2, +0.0).

-file("src/yog/mst.gleam", 815).
-spec extract_undirected_edges(yog@model:graph(any(), UFP)) -> list(edge(UFP)).
extract_undirected_edges(Graph) ->
    gleam@dict:fold(
        erlang:element(4, Graph),
        [],
        fun(Acc, From_id, Targets) ->
            gleam@dict:fold(
                Targets,
                Acc,
                fun(Inner_acc, To_id, Weight) ->
                    case (erlang:element(2, Graph) =:= undirected) andalso (From_id
                    > To_id) of
                        true ->
                            Inner_acc;

                        false ->
                            [{edge, From_id, To_id, Weight} | Inner_acc]
                    end
                end
            )
        end
    ).

-file("src/yog/mst.gleam", 97).
?DOC(
    " Finds the Minimum Spanning Tree (MST) using Kruskal's algorithm.\n"
    "\n"
    " **Time Complexity:** O(E log E)\n"
).
-spec kruskal(
    yog@model:graph(any(), TXH),
    fun((TXH, TXH) -> gleam@order:order()),
    fun((TXH, TXH) -> TXH),
    TXH
) -> mst_result(TXH).
kruskal(Graph, Compare, Add, Zero) ->
    Edges = begin
        _pipe = extract_undirected_edges(Graph),
        gleam@list:sort(
            _pipe,
            fun(A, B) -> Compare(erlang:element(4, A), erlang:element(4, B)) end
        )
    end,
    Mst_edges = do_kruskal(Edges, yog@disjoint_set:new(), []),
    make_result(
        Mst_edges,
        kruskal,
        maps:size(erlang:element(3, Graph)),
        none,
        Add,
        Zero
    ).

-file("src/yog/mst.gleam", 199).
?DOC(
    " Finds the Minimum Spanning Tree (MST) using Borůvka's algorithm.\n"
    "\n"
    " **Time Complexity:** O(E log V)\n"
).
-spec boruvka(
    yog@model:graph(any(), TYK),
    fun((TYK, TYK) -> gleam@order:order()),
    fun((TYK, TYK) -> TYK),
    TYK
) -> mst_result(TYK).
boruvka(Graph, Compare, Add, Zero) ->
    Nodes = maps:keys(erlang:element(3, Graph)),
    Dsu = gleam@list:fold(
        Nodes,
        yog@disjoint_set:new(),
        fun(Acc, Node) -> yog@disjoint_set:add(Acc, Node) end
    ),
    All_edges = extract_undirected_edges(Graph),
    Mst_edges = do_boruvka(All_edges, Dsu, [], Compare),
    make_result(Mst_edges, boruvka, erlang:length(Nodes), none, Add, Zero).

-file("src/yog/mst.gleam", 696).
?DOC(" Kruskal for `Int` weights.\n").
-spec kruskal_int(yog@model:graph(any(), integer())) -> mst_result(integer()).
kruskal_int(Graph) ->
    kruskal(Graph, fun gleam@int:compare/2, fun gleam@int:add/2, 0).

-file("src/yog/mst.gleam", 701).
?DOC(" Kruskal for `Float` weights.\n").
-spec kruskal_float(yog@model:graph(any(), float())) -> mst_result(float()).
kruskal_float(Graph) ->
    kruskal(Graph, fun gleam@float:compare/2, fun gleam@float:add/2, +0.0).

-file("src/yog/mst.gleam", 721).
?DOC(" Borůvka for `Int` weights.\n").
-spec boruvka_int(yog@model:graph(any(), integer())) -> mst_result(integer()).
boruvka_int(Graph) ->
    boruvka(Graph, fun gleam@int:compare/2, fun gleam@int:add/2, 0).

-file("src/yog/mst.gleam", 726).
?DOC(" Borůvka for `Float` weights.\n").
-spec boruvka_float(yog@model:graph(any(), float())) -> mst_result(float()).
boruvka_float(Graph) ->
    boruvka(Graph, fun gleam@float:compare/2, fun gleam@float:add/2, +0.0).

-file("src/yog/mst.gleam", 826).
-spec extract_all_edges(yog@model:graph(any(), UFV)) -> list(edge(UFV)).
extract_all_edges(Graph) ->
    gleam@dict:fold(
        erlang:element(4, Graph),
        [],
        fun(Acc, From_id, Targets) ->
            gleam@dict:fold(
                Targets,
                Acc,
                fun(Inner_acc, To_id, Weight) ->
                    [{edge, From_id, To_id, Weight} | Inner_acc]
                end
            )
        end
    ).

-file("src/yog/mst.gleam", 307).
?DOC(
    " Finds the Minimum Spanning Arborescence (MSA) of a directed graph.\n"
    "\n"
    " An arborescence is a directed spanning tree rooted at `root`. This algorithm\n"
    " finds the minimum-weight set of edges that connects all reachable nodes to\n"
    " the root.\n"
    "\n"
    " **Time Complexity:** O(VE)\n"
).
-spec edmonds(
    yog@model:graph(any(), TZR),
    integer(),
    fun((TZR, TZR) -> gleam@order:order()),
    fun((TZR, TZR) -> TZR),
    fun((TZR, TZR) -> TZR),
    TZR
) -> {ok, mst_result(TZR)} | {error, binary()}.
edmonds(Graph, Root, Compare, Add, Subtract, Zero) ->
    case erlang:element(2, Graph) of
        directed ->
            Nodes = maps:keys(erlang:element(3, Graph)),
            Edges = extract_all_edges(Graph),
            Min_id = gleam@list:fold(Nodes, 0, fun gleam@int:min/2),
            case do_edmonds(
                {edmonds_graph, Nodes, Edges},
                Root,
                Compare,
                Subtract,
                Min_id - 1
            ) of
                {ok, Mst_edges} ->
                    {ok,
                        make_result(
                            Mst_edges,
                            chu_liu_edmonds,
                            erlang:length(Nodes),
                            {some, Root},
                            Add,
                            Zero
                        )};

                {error, Msg} ->
                    {error, Msg}
            end;

        undirected ->
            {error, <<"Edmonds algorithm requires a directed graph"/utf8>>}
    end.

-file("src/yog/mst.gleam", 736).
?DOC(" Edmonds for `Int` weights.\n").
-spec edmonds_int(yog@model:graph(any(), integer()), integer()) -> {ok,
        mst_result(integer())} |
    {error, binary()}.
edmonds_int(Graph, Root) ->
    edmonds(
        Graph,
        Root,
        fun gleam@int:compare/2,
        fun gleam@int:add/2,
        fun gleam@int:subtract/2,
        0
    ).

-file("src/yog/mst.gleam", 751).
?DOC(" Edmonds for `Float` weights.\n").
-spec edmonds_float(yog@model:graph(any(), float()), integer()) -> {ok,
        mst_result(float())} |
    {error, binary()}.
edmonds_float(Graph, Root) ->
    edmonds(
        Graph,
        Root,
        fun gleam@float:compare/2,
        fun gleam@float:add/2,
        fun gleam@float:subtract/2,
        +0.0
    ).

-file("src/yog/mst.gleam", 834).
-spec get_all_edges_from_node(yog@model:graph(any(), UGB), integer()) -> list(edge(UGB)).
get_all_edges_from_node(Graph, From) ->
    case gleam_stdlib:map_get(erlang:element(4, Graph), From) of
        {ok, Targets} ->
            gleam@dict:fold(
                Targets,
                [],
                fun(Acc, To_id, Weight) ->
                    [{edge, From, To_id, Weight} | Acc]
                end
            );

        {error, nil} ->
            []
    end.

-file("src/yog/mst.gleam", 168).
-spec do_prim(
    yog@model:graph(any(), TXZ),
    yog@internal@pairing_heap:heap(edge(TXZ)),
    gleam@set:set(integer()),
    list(edge(TXZ))
) -> list(edge(TXZ)).
do_prim(Graph, Pq, Visited, Acc) ->
    case yog@internal@priority_queue:pop(Pq) of
        {error, nil} ->
            lists:reverse(Acc);

        {ok, {Edge, Rest_pq}} ->
            case gleam@set:contains(Visited, erlang:element(3, Edge)) of
                true ->
                    do_prim(Graph, Rest_pq, Visited, Acc);

                false ->
                    New_visited = gleam@set:insert(
                        Visited,
                        erlang:element(3, Edge)
                    ),
                    _pipe = Graph,
                    _pipe@1 = get_all_edges_from_node(
                        _pipe,
                        erlang:element(3, Edge)
                    ),
                    _pipe@2 = gleam@list:filter(
                        _pipe@1,
                        fun(E) ->
                            not gleam@set:contains(
                                New_visited,
                                erlang:element(3, E)
                            )
                        end
                    ),
                    _pipe@3 = gleam@list:fold(
                        _pipe@2,
                        Rest_pq,
                        fun(Pq@1, E@1) ->
                            yog@internal@priority_queue:push(Pq@1, E@1)
                        end
                    ),
                    do_prim(Graph, _pipe@3, New_visited, [Edge | Acc])
            end
    end.

-file("src/yog/mst.gleam", 146).
?DOC(
    " Finds the Minimum Spanning Tree (MST) using Prim's algorithm.\n"
    "\n"
    " **Time Complexity:** O(E log V)\n"
    "\n"
    " **Disconnected Graphs:** For disconnected graphs, Prim's only returns edges\n"
    " for the connected component containing the starting node.\n"
).
-spec prim(
    yog@model:graph(any(), TXU),
    fun((TXU, TXU) -> gleam@order:order()),
    fun((TXU, TXU) -> TXU),
    TXU
) -> mst_result(TXU).
prim(Graph, Compare, Add, Zero) ->
    Mst_edges = case maps:keys(erlang:element(3, Graph)) of
        [] ->
            [];

        [Start | _] ->
            Initial_pq = yog@internal@priority_queue:new(
                fun(A, B) ->
                    Compare(erlang:element(4, A), erlang:element(4, B))
                end
            ),
            _pipe = Graph,
            _pipe@1 = get_all_edges_from_node(_pipe, Start),
            _pipe@2 = gleam@list:fold(
                _pipe@1,
                Initial_pq,
                fun(Pq, Edge) -> yog@internal@priority_queue:push(Pq, Edge) end
            ),
            do_prim(Graph, _pipe@2, gleam@set:from_list([Start]), [])
    end,
    make_result(
        Mst_edges,
        prim,
        maps:size(erlang:element(3, Graph)),
        none,
        Add,
        Zero
    ).

-file("src/yog/mst.gleam", 711).
?DOC(" Prim for `Int` weights.\n").
-spec prim_int(yog@model:graph(any(), integer())) -> mst_result(integer()).
prim_int(Graph) ->
    prim(Graph, fun gleam@int:compare/2, fun gleam@int:add/2, 0).

-file("src/yog/mst.gleam", 716).
?DOC(" Prim for `Float` weights.\n").
-spec prim_float(yog@model:graph(any(), float())) -> mst_result(float()).
prim_float(Graph) ->
    prim(Graph, fun gleam@float:compare/2, fun gleam@float:add/2, +0.0).