yog

-module(yog@min_cut).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/min_cut.gleam").
-export([global_min_cut/1]).
-export_type([min_cut/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 min_cut() :: {min_cut, integer(), integer(), integer()}.

-file("src/yog/min_cut.gleam", 117).
?DOC(" Builds the MAS ordering by greedily adding the most tightly connected node.\n").
-spec build_mas_order(
    yog@model:graph(integer(), integer()),
    list(integer()),
    gleam@set:set(integer())
) -> list(integer()).
build_mas_order(Graph, Current_order, Remaining) ->
    case gleam@set:size(Remaining) of
        0 ->
            Current_order;

        _ ->
            Next_node = begin
                _pipe = Remaining,
                _pipe@1 = gleam@set:to_list(_pipe),
                _pipe@4 = gleam@list:map(
                    _pipe@1,
                    fun(Node) ->
                        Weight = begin
                            _pipe@2 = yog@model:neighbors(Graph, Node),
                            _pipe@3 = gleam@list:filter(
                                _pipe@2,
                                fun(Edge) ->
                                    {Neighbor, _} = Edge,
                                    gleam@list:contains(Current_order, Neighbor)
                                end
                            ),
                            gleam@list:fold(
                                _pipe@3,
                                0,
                                fun(Sum, Edge@1) ->
                                    {_, W} = Edge@1,
                                    Sum + W
                                end
                            )
                        end,
                        {Node, Weight}
                    end
                ),
                _pipe@5 = gleam@list:sort(
                    _pipe@4,
                    fun(A, B) ->
                        {_, Weight_a} = A,
                        {_, Weight_b} = B,
                        gleam@int:compare(Weight_b, Weight_a)
                    end
                ),
                gleam@list:first(_pipe@5)
            end,
            Node@2 = case Next_node of
                {ok, {Node@1, _}} -> Node@1;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/min_cut"/utf8>>,
                                function => <<"build_mas_order"/utf8>>,
                                line => 148,
                                value => _assert_fail,
                                start => 4312,
                                'end' => 4349,
                                pattern_start => 4323,
                                pattern_end => 4337})
            end,
            build_mas_order(
                Graph,
                [Node@2 | Current_order],
                gleam@set:delete(Remaining, Node@2)
            )
    end.

-file("src/yog/min_cut.gleam", 95).
?DOC(
    " Maximum Adjacency Search (MAS): finds the two most tightly connected nodes.\n"
    "\n"
    " Returns #(s, t, cut_weight) where:\n"
    " - s: second-to-last node added\n"
    " - t: last node added\n"
    " - cut_weight: sum of edge weights connecting t to the rest of the graph\n"
    "\n"
    " This is similar to Prim's algorithm but picks nodes by maximum total\n"
    " connection weight to the current set, not minimum edge weight.\n"
).
-spec maximum_adjacency_search(yog@model:graph(integer(), integer())) -> {integer(),
    integer(),
    integer()}.
maximum_adjacency_search(Graph) ->
    All_nodes = yog@model:all_nodes(Graph),
    Start@1 = case gleam@list:first(All_nodes) of
        {ok, Start} -> Start;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/min_cut"/utf8>>,
                        function => <<"maximum_adjacency_search"/utf8>>,
                        line => 98,
                        value => _assert_fail,
                        start => 2977,
                        'end' => 3021,
                        pattern_start => 2988,
                        pattern_end => 2997})
    end,
    Initial_order = [Start@1],
    Remaining = begin
        _pipe = gleam@set:from_list(All_nodes),
        gleam@set:delete(_pipe, Start@1)
    end,
    Final_order = build_mas_order(Graph, Initial_order, Remaining),
    {T@1, S@1} = case lists:reverse(Final_order) of
        [T, S | _] -> {T, S};
        _assert_fail@1 ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/min_cut"/utf8>>,
                        function => <<"maximum_adjacency_search"/utf8>>,
                        line => 104,
                        value => _assert_fail@1,
                        start => 3189,
                        'end' => 3238,
                        pattern_start => 3200,
                        pattern_end => 3210})
    end,
    Cut_weight = begin
        _pipe@1 = yog@model:neighbors(Graph, T@1),
        gleam@list:fold(
            _pipe@1,
            0,
            fun(Sum, Edge) ->
                {_, Weight} = Edge,
                Sum + Weight
            end
        )
    end,
    {S@1, T@1, Cut_weight}.

-file("src/yog/min_cut.gleam", 49).
-spec do_min_cut(yog@model:graph(integer(), integer()), min_cut()) -> min_cut().
do_min_cut(Graph, Best) ->
    case yog@model:order(Graph) =< 1 of
        true ->
            Best;

        false ->
            {S, T, Cut_weight} = maximum_adjacency_search(Graph),
            T_size@1 = case gleam_stdlib:map_get(erlang:element(3, Graph), T) of
                {ok, T_size} -> T_size;
                _assert_fail ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/min_cut"/utf8>>,
                                function => <<"do_min_cut"/utf8>>,
                                line => 55,
                                value => _assert_fail,
                                start => 1721,
                                'end' => 1769,
                                pattern_start => 1732,
                                pattern_end => 1742})
            end,
            S_size@1 = case gleam_stdlib:map_get(erlang:element(3, Graph), S) of
                {ok, S_size} -> S_size;
                _assert_fail@1 ->
                    erlang:error(#{gleam_error => let_assert,
                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                file => <<?FILEPATH/utf8>>,
                                module => <<"yog/min_cut"/utf8>>,
                                function => <<"do_min_cut"/utf8>>,
                                line => 56,
                                value => _assert_fail@1,
                                start => 1776,
                                'end' => 1824,
                                pattern_start => 1787,
                                pattern_end => 1797})
            end,
            Total_nodes = gleam@list:fold(
                maps:values(erlang:element(3, Graph)),
                0,
                fun gleam@int:add/2
            ),
            Current_cut = {min_cut,
                Cut_weight,
                T_size@1,
                Total_nodes - T_size@1},
            Best@1 = case erlang:element(2, Current_cut) < erlang:element(
                2,
                Best
            ) of
                true ->
                    Current_cut;

                false ->
                    Best
            end,
            Next_graph = yog@transform:contract(
                Graph,
                S,
                T,
                fun gleam@int:add/2
            ),
            Next_graph@1 = yog@model:add_node(
                Next_graph,
                S,
                S_size@1 + T_size@1
            ),
            do_min_cut(Next_graph@1, Best@1)
    end.

-file("src/yog/min_cut.gleam", 39).
?DOC(
    " Finds the global minimum cut of an undirected weighted graph using the\n"
    " Stoer-Wagner algorithm.\n"
    "\n"
    " Returns the minimum cut weight and the sizes of the two partitions.\n"
    " Perfect for AoC 2023 Day 25, where you need to find the cut of weight 3\n"
    " and compute the product of partition sizes.\n"
    "\n"
    " **Time Complexity:** O(V³) or O(VE + V² log V) with a good priority queue\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   yog.undirected()\n"
    "   |> yog.add_node(1, Nil)\n"
    "   |> yog.add_node(2, Nil)\n"
    "   |> yog.add_node(3, Nil)\n"
    "   |> yog.add_node(4, Nil)\n"
    "   |> yog.add_edge(from: 1, to: 2, with: 1)\n"
    "   |> yog.add_edge(from: 2, to: 3, with: 1)\n"
    "   |> yog.add_edge(from: 3, to: 4, with: 1)\n"
    "   |> yog.add_edge(from: 1, to: 4, with: 1)\n"
    "\n"
    " let result = min_cut.global_min_cut(in: graph)\n"
    " // result.weight == 2 (minimum cut)\n"
    " // result.group_a_size * result.group_b_size == product of partition sizes\n"
    " ```\n"
).
-spec global_min_cut(yog@model:graph(any(), integer())) -> min_cut().
global_min_cut(Graph) ->
    Graph@1 = yog@transform:map_nodes(Graph, fun(_) -> 1 end),
    do_min_cut(Graph@1, {min_cut, 999999999, 0, 0}).