yog

-module(yog@flow@network_simplex).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/flow/network_simplex.gleam").
-export([min_cost_flow/4]).
-export_type([min_cost_flow_result/0, network_simplex_error/0, omni_state/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(
    " Network Simplex algorithm for minimum cost flow optimization.\n"
    "\n"
    " This module solves the [minimum cost flow problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem):\n"
    " find the cheapest way to send a given amount of flow through a network where\n"
    " edges have both capacities and costs per unit of flow.\n"
    "\n"
    " ## Algorithm\n"
    "\n"
    " | Algorithm | Function | Complexity | Best For |\n"
    " |-----------|----------|------------|----------|\n"
    " | [Network Simplex](https://en.wikipedia.org/wiki/Network_simplex_algorithm) | `min_cost_flow/5` | O(V²E) practical | Large sparse networks |\n"
    "\n"
    " The Network Simplex is a specialized version of the [simplex algorithm](https://en.wikipedia.org/wiki/Simplex_algorithm)\n"
    " for network flow problems. It maintains a spanning tree of basic edges and\n"
    " iteratively pivots to improve the solution, similar to how the transportation\n"
    " simplex works for assignment problems.\n"
    "\n"
    " ## Key Concepts\n"
    "\n"
    " - **Minimum Cost Flow**: Route flow to satisfy demands at minimum total cost\n"
    " - **Node Demands**: Supply nodes (negative demand) and demand nodes (positive demand)\n"
    " - **Edge Costs**: Price per unit of flow on each edge\n"
    " - **Potentials (π)**: Dual variables for reduced cost computation\n"
    " - **Reduced Costs**: Modified costs ensuring optimality conditions\n"
    " - **Spanning Tree**: Basis for the simplex method on networks\n"
    "\n"
    " ## Problem Formulation\n"
    "\n"
    " Given:\n"
    " - Graph G = (V, E) with capacities u(e) and costs c(e)\n"
    " - Node demands b(v) where Σb(v) = 0 (conservation)\n"
    "\n"
    " Find flow f(e) that:\n"
    " - Minimizes: Σ c(e) × f(e)  (total cost)\n"
    " - Subject to: 0 ≤ f(e) ≤ u(e)  (capacity constraints)\n"
    " - And: flow conservation at each node\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Transportation planning**: Minimize shipping costs with vehicle capacities\n"
    " - **Supply chain**: Optimize distribution from warehouses to retailers\n"
    " - **Telecommunications**: Route calls at minimum cost with link capacities\n"
    " - **Workforce scheduling**: Assign workers to shifts minimizing total cost\n"
    " - **Circulation problems**: Fleet management and inventory routing\n"
    "\n"
    " ## Performance Notes\n"
    "\n"
    " > This implementation uses list-based data structures for the internal spanning\n"
    " > tree representation. While algorithmically correct, random access and updates\n"
    " > are O(n) rather than O(1). For large flow networks (1000+ nodes/edges), this\n"
    " > may impact performance. Consider using alternative approaches for very\n"
    " > large-scale problems:\n"
    " > - Erlang FFI to `:digraph` or optimized C libraries\n"
    " > - Specialized MCF solvers for production-scale optimization\n"
    "\n"
    " ## References\n"
    "\n"
    " - [Wikipedia: Minimum-Cost Flow Problem](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem)\n"
    " - [Wikipedia: Network Simplex Algorithm](https://en.wikipedia.org/wiki/Network_simplex_algorithm)\n"
    " - [Network Flows - Ahuja, Magnanti, Orlin](https://www.pearson.com/en-us/subject-catalog/p/network-flows/P200000005792)\n"
    " - [CP-Algorithms: Min-Cost Flow](https://cp-algorithms.com/graph/min_cost_flow.html)\n"
).

-type min_cost_flow_result() :: {min_cost_flow_result,
        integer(),
        list({integer(), integer(), integer()})}.

-type network_simplex_error() :: infeasible | unbounded | unbalanced_demands.

-type omni_state() :: {omni_state,
        integer(),
        integer(),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        list(integer()),
        integer(),
        integer()}.

-file("src/yog/flow/network_simplex.gleam", 130).
-spec wget(list(QTG), integer()) -> QTG.
wget(Collection, Index) ->
    Len = erlang:length(Collection),
    Mod_idx = case Len of
        0 -> 0;
        Gleam@denominator -> Index rem Gleam@denominator
    end,
    True_idx = case Mod_idx < 0 of
        true ->
            Mod_idx + Len;

        false ->
            Mod_idx
    end,
    Val@1 = case begin
        _pipe = Collection,
        _pipe@1 = gleam@list:drop(_pipe, True_idx),
        gleam@list:first(_pipe@1)
    end of
        {ok, Val} -> Val;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/flow/network_simplex"/utf8>>,
                        function => <<"wget"/utf8>>,
                        line => 137,
                        value => _assert_fail,
                        start => 5387,
                        'end' => 5457,
                        pattern_start => 5398,
                        pattern_end => 5405})
    end,
    Val@1.

-file("src/yog/flow/network_simplex.gleam", 141).
-spec wupdate(list(QTI), integer(), fun((QTI) -> QTI)) -> list(QTI).
wupdate(Collection, Index, Update) ->
    Len = erlang:length(Collection),
    Mod_idx = case Len of
        0 -> 0;
        Gleam@denominator -> Index rem Gleam@denominator
    end,
    True_idx = case Mod_idx < 0 of
        true ->
            Mod_idx + Len;

        false ->
            Mod_idx
    end,
    Before = gleam@list:take(Collection, True_idx),
    After = gleam@list:drop(Collection, True_idx + 1),
    Val@1 = case begin
        _pipe = Collection,
        _pipe@1 = gleam@list:drop(_pipe, True_idx),
        gleam@list:first(_pipe@1)
    end of
        {ok, Val} -> Val;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/flow/network_simplex"/utf8>>,
                        function => <<"wupdate"/utf8>>,
                        line => 150,
                        value => _assert_fail,
                        start => 5794,
                        'end' => 5864,
                        pattern_start => 5805,
                        pattern_end => 5812})
    end,
    lists:append([Before, [Update(Val@1)], After]).

-file("src/yog/flow/network_simplex.gleam", 154).
-spec wassoc(list(QTL), integer(), QTL) -> list(QTL).
wassoc(Collection, Index, Value) ->
    wupdate(Collection, Index, fun(_) -> Value end).

-file("src/yog/flow/network_simplex.gleam", 158).
-spec seq_do(integer(), integer(), list(integer())) -> list(integer()).
seq_do(Start, End, Acc) ->
    case Start > End of
        true ->
            lists:reverse(Acc);

        false ->
            seq_do(Start + 1, End, [Start | Acc])
    end.

-file("src/yog/flow/network_simplex.gleam", 165).
-spec seq(integer(), integer()) -> list(integer()).
seq(Start, End) ->
    seq_do(Start, End, []).

-file("src/yog/flow/network_simplex.gleam", 208).
-spec extract(
    yog@model:graph(QTX, QTY),
    fun((QTX) -> integer()),
    fun((QTY) -> integer()),
    fun((QTY) -> integer())
) -> {ok, omni_state()} | {error, network_simplex_error()}.
extract(Graph, Get_demand, Get_capacity, Get_cost) ->
    Nodes = yog@model:all_nodes(Graph),
    Nc = erlang:length(Nodes),
    _ = case Nc > 0 of
        true ->
            nil;

        false ->
            erlang:error(#{gleam_error => panic,
                    message => <<"Graph has no nodes"/utf8>>,
                    file => <<?FILEPATH/utf8>>,
                    module => <<"yog/flow/network_simplex"/utf8>>,
                    function => <<"extract"/utf8>>,
                    line => 218})
    end,
    _ = Nodes,
    Node_indices = begin
        _pipe = Nodes,
        _pipe@1 = gleam@list:index_map(_pipe, fun(N, I) -> {N, I} end),
        maps:from_list(_pipe@1)
    end,
    Demands = begin
        _pipe@2 = Nodes,
        gleam@list:map(
            _pipe@2,
            fun(N@1) ->
                Ndata@1 = case gleam_stdlib:map_get(
                    erlang:element(3, Graph),
                    N@1
                ) of
                    {ok, Ndata} -> Ndata;
                    _assert_fail ->
                        erlang:error(#{gleam_error => let_assert,
                                    message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                    file => <<?FILEPATH/utf8>>,
                                    module => <<"yog/flow/network_simplex"/utf8>>,
                                    function => <<"extract"/utf8>>,
                                    line => 231,
                                    value => _assert_fail,
                                    start => 7808,
                                    'end' => 7855,
                                    pattern_start => 7819,
                                    pattern_end => 7828})
                end,
                Get_demand(Ndata@1)
            end
        )
    end,
    Total_demand = gleam@list:fold(Demands, 0, fun gleam@int:add/2),
    case Total_demand =:= 0 of
        false ->
            {error, unbalanced_demands};

        true ->
            Edges = gleam@dict:fold(
                erlang:element(4, Graph),
                [],
                fun(Acc_out, Src, Targets) ->
                    gleam@dict:fold(
                        Targets,
                        Acc_out,
                        fun(Acc_in, Dst, Weight) ->
                            [{Src, Dst, Weight} | Acc_in]
                        end
                    )
                end
            ),
            Ec = erlang:length(Edges),
            Edge_sources = begin
                _pipe@3 = Edges,
                gleam@list:map(
                    _pipe@3,
                    fun(E_val) ->
                        {Src@1, _, _} = E_val,
                        Idx@1 = case gleam_stdlib:map_get(Node_indices, Src@1) of
                            {ok, Idx} -> Idx;
                            _assert_fail@1 ->
                                erlang:error(#{gleam_error => let_assert,
                                            message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                            file => <<?FILEPATH/utf8>>,
                                            module => <<"yog/flow/network_simplex"/utf8>>,
                                            function => <<"extract"/utf8>>,
                                            line => 254,
                                            value => _assert_fail@1,
                                            start => 8499,
                                            'end' => 8547,
                                            pattern_start => 8510,
                                            pattern_end => 8517})
                        end,
                        Idx@1
                    end
                )
            end,
            Edge_targets = begin
                _pipe@4 = Edges,
                gleam@list:map(
                    _pipe@4,
                    fun(E_val@1) ->
                        {_, Dst@1, _} = E_val@1,
                        Idx@3 = case gleam_stdlib:map_get(Node_indices, Dst@1) of
                            {ok, Idx@2} -> Idx@2;
                            _assert_fail@2 ->
                                erlang:error(#{gleam_error => let_assert,
                                            message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                            file => <<?FILEPATH/utf8>>,
                                            module => <<"yog/flow/network_simplex"/utf8>>,
                                            function => <<"extract"/utf8>>,
                                            line => 261,
                                            value => _assert_fail@2,
                                            start => 8693,
                                            'end' => 8741,
                                            pattern_start => 8704,
                                            pattern_end => 8711})
                        end,
                        Idx@3
                    end
                )
            end,
            Edge_costs = gleam@list:map(
                Edges,
                fun(E_val@2) ->
                    {_, _, W} = E_val@2,
                    Get_cost(W)
                end
            ),
            Edge_capacities = gleam@list:map(
                Edges,
                fun(E_val@3) ->
                    {_, _, W@1} = E_val@3,
                    Get_capacity(W@1)
                end
            ),
            Sum_cap = gleam@int:absolute_value(
                gleam@list:fold(Edge_capacities, 0, fun gleam@int:add/2)
            ),
            Sum_cost = gleam@list:fold(
                Edge_costs,
                0,
                fun(Acc, C) -> Acc + gleam@int:absolute_value(C) end
            ),
            Max_demand = gleam@list:fold(
                Demands,
                0,
                fun(Acc@1, D) ->
                    gleam@int:max(Acc@1, gleam@int:absolute_value(D))
                end
            ),
            Inf = begin
                _pipe@5 = (gleam@int:max(
                    gleam@int:max(Sum_cap, Sum_cost),
                    Max_demand
                )
                * 3),
                gleam@int:max(_pipe@5, 1)
            end,
            Invalid_caps = gleam@list:any(
                Edge_capacities,
                fun(C@1) -> C@1 < 0 end
            ),
            case Invalid_caps of
                true ->
                    erlang:error(#{gleam_error => panic,
                            message => <<"Negative capacity encountered"/utf8>>,
                            file => <<?FILEPATH/utf8>>,
                            module => <<"yog/flow/network_simplex"/utf8>>,
                            function => <<"extract"/utf8>>,
                            line => 289});

                false ->
                    nil
            end,
            {ok,
                {omni_state,
                    Nc,
                    Ec,
                    Nodes,
                    Demands,
                    Edge_sources,
                    Edge_targets,
                    Edge_capacities,
                    Edge_costs,
                    [],
                    [],
                    [],
                    [],
                    [],
                    [],
                    [],
                    [],
                    0,
                    Inf}}
    end.

-file("src/yog/flow/network_simplex.gleam", 318).
-spec add_super_source(omni_state()) -> omni_state().
add_super_source(Omni) ->
    Nc = erlang:element(2, Omni),
    Ss_edges = begin
        _pipe = erlang:element(5, Omni),
        gleam@list:index_map(_pipe, fun(D, P) -> case D > 0 of
                    true ->
                        {P, Nc};

                    false ->
                        {Nc, P}
                end end)
    end,
    New_sources = lists:append(
        [erlang:element(6, Omni),
            gleam@list:map(Ss_edges, fun(E) -> erlang:element(1, E) end)]
    ),
    New_targets = lists:append(
        [erlang:element(7, Omni),
            gleam@list:map(Ss_edges, fun(E@1) -> erlang:element(2, E@1) end)]
    ),
    New_costs = lists:append(
        [erlang:element(9, Omni),
            gleam@list:repeat(erlang:element(19, Omni), Nc)]
    ),
    New_caps = lists:append(
        [erlang:element(8, Omni),
            gleam@list:repeat(erlang:element(19, Omni), Nc)]
    ),
    New_demands = lists:append(erlang:element(5, Omni), [0]),
    {omni_state,
        Nc + 1,
        erlang:element(3, Omni) + Nc,
        erlang:element(4, Omni),
        New_demands,
        New_sources,
        New_targets,
        New_caps,
        New_costs,
        erlang:element(10, Omni),
        erlang:element(11, Omni),
        erlang:element(12, Omni),
        erlang:element(13, Omni),
        erlang:element(14, Omni),
        erlang:element(15, Omni),
        erlang:element(16, Omni),
        erlang:element(17, Omni),
        erlang:element(18, Omni),
        erlang:element(19, Omni)}.

-file("src/yog/flow/network_simplex.gleam", 356).
-spec init_spanning_tree(omni_state()) -> omni_state().
init_spanning_tree(Omni) ->
    Nc = erlang:element(2, Omni),
    Ec = erlang:element(3, Omni),
    Old_nc = Nc - 1,
    Old_ec = Ec - Old_nc,
    Flows_base = gleam@list:repeat(0, Old_ec),
    Flows_demands = gleam@list:map(
        gleam@list:take(erlang:element(5, Omni), Old_nc),
        fun gleam@int:absolute_value/1
    ),
    Flows = lists:append([Flows_base, Flows_demands]),
    Phis_base = gleam@list:map(
        gleam@list:take(erlang:element(5, Omni), Old_nc),
        fun(D) -> case D > 0 of
                true ->
                    - erlang:element(19, Omni);

                false ->
                    erlang:element(19, Omni)
            end end
    ),
    Phis = lists:append([Phis_base, [0]]),
    Edges = lists:append([seq(Old_ec, Ec - 1), [-1]]),
    Parents = lists:append([gleam@list:repeat(Old_nc, Old_nc), [-1]]),
    Sizes = lists:append([gleam@list:repeat(1, Old_nc), [Nc]]),
    Nexts = lists:append([seq(1, Old_nc - 1), [-1, 0]]),
    Prevs = lists:append([[Old_nc], seq(0, Old_nc - 2), [-1]]),
    Lasts = lists:append([seq(0, Old_nc - 1), [Old_nc - 1]]),
    {omni_state,
        erlang:element(2, Omni),
        erlang:element(3, Omni),
        erlang:element(4, Omni),
        erlang:element(5, Omni),
        erlang:element(6, Omni),
        erlang:element(7, Omni),
        erlang:element(8, Omni),
        erlang:element(9, Omni),
        Flows,
        Phis,
        Parents,
        Edges,
        Sizes,
        Nexts,
        Prevs,
        Lasts,
        erlang:element(18, Omni),
        erlang:element(19, Omni)}.

-file("src/yog/flow/network_simplex.gleam", 413).
-spec reduced_cost(omni_state(), integer()) -> integer().
reduced_cost(Omni, I) ->
    C = wget(erlang:element(9, Omni), I),
    S = wget(erlang:element(6, Omni), I),
    T = wget(erlang:element(7, Omni), I),
    Phi_s = wget(erlang:element(11, Omni), S),
    Phi_t = wget(erlang:element(11, Omni), T),
    Base_cost = (C + Phi_s) - Phi_t,
    case wget(erlang:element(10, Omni), I) =:= 0 of
        true ->
            Base_cost;

        false ->
            - Base_cost
    end.

-file("src/yog/flow/network_simplex.gleam", 426).
-spec residual_capacity(omni_state(), integer(), integer()) -> integer().
residual_capacity(Omni, I, P) ->
    S = wget(erlang:element(6, Omni), I),
    U = wget(erlang:element(8, Omni), I),
    F = wget(erlang:element(10, Omni), I),
    case S =:= P of
        true ->
            U - F;

        false ->
            F
    end.

-file("src/yog/flow/network_simplex.gleam", 440).
-spec do_find_apex(omni_state(), integer(), integer(), integer()) -> integer().
do_find_apex(Omni, P, Q, Max) ->
    case (P =:= Q) orelse (Max =< 0) of
        true ->
            P;

        false ->
            Next_p = case wget(erlang:element(14, Omni), P) >= wget(
                erlang:element(14, Omni),
                Q
            ) of
                true ->
                    P;

                false ->
                    wget(erlang:element(12, Omni), P)
            end,
            Next_q = case wget(erlang:element(14, Omni), Q) >= wget(
                erlang:element(14, Omni),
                P
            ) of
                true ->
                    Q;

                false ->
                    wget(erlang:element(12, Omni), Q)
            end,
            Final_p = case (Next_p /= Next_q) andalso (wget(
                erlang:element(14, Omni),
                Next_p
            )
            =:= wget(erlang:element(14, Omni), Next_q)) of
                true ->
                    wget(erlang:element(12, Omni), Next_p);

                false ->
                    Next_p
            end,
            Final_q = case (Next_p /= Next_q) andalso (wget(
                erlang:element(14, Omni),
                Next_p
            )
            =:= wget(erlang:element(14, Omni), Next_q)) of
                true ->
                    wget(erlang:element(12, Omni), Next_q);

                false ->
                    Next_q
            end,
            do_find_apex(Omni, Final_p, Final_q, Max - 1)
    end.

-file("src/yog/flow/network_simplex.gleam", 436).
-spec find_apex(omni_state(), integer(), integer()) -> integer().
find_apex(Omni, P, Q) ->
    do_find_apex(Omni, P, Q, erlang:element(2, Omni)).

-file("src/yog/flow/network_simplex.gleam", 474).
-spec do_trace_path(
    omni_state(),
    integer(),
    integer(),
    list(integer()),
    list(integer()),
    integer()
) -> {list(integer()), list(integer())}.
do_trace_path(Omni, P, W, Wn, We, Max) ->
    case (P =:= W) orelse (Max =< 0) of
        true ->
            {Wn, We};

        false ->
            Next_p = wget(erlang:element(12, Omni), P),
            do_trace_path(
                Omni,
                Next_p,
                W,
                lists:append(Wn, [Next_p]),
                lists:append(We, [wget(erlang:element(13, Omni), P)]),
                Max - 1
            )
    end.

-file("src/yog/flow/network_simplex.gleam", 470).
-spec trace_path(omni_state(), integer(), integer()) -> {list(integer()),
    list(integer())}.
trace_path(Omni, P, W) ->
    do_trace_path(Omni, P, W, [P], [], erlang:element(2, Omni)).

-file("src/yog/flow/network_simplex.gleam", 498).
-spec find_cycle(omni_state(), integer(), integer(), integer()) -> {list(integer()),
    list(integer()),
    integer()}.
find_cycle(Omni, I, P, Q) ->
    W = find_apex(Omni, P, Q),
    {Wn_p, We_p} = trace_path(Omni, P, W),
    Wn_p_rev = lists:reverse(Wn_p),
    We_p_rev = lists:append(lists:reverse(We_p), [I]),
    {Wn_q, We_q} = trace_path(Omni, Q, W),
    Wn_q_rev = gleam@list:take(Wn_q, erlang:length(Wn_q) - 1),
    {lists:append(Wn_p_rev, Wn_q_rev),
        lists:append(We_p_rev, We_q),
        erlang:length(Wn_p)}.

-file("src/yog/flow/network_simplex.gleam", 520).
-spec find_leaving_edge(omni_state(), list(integer()), list(integer())) -> {integer(),
    integer()}.
find_leaving_edge(Omni, Wn, We) ->
    Zipped = gleam@list:zip(We, Wn),
    Min_edge = gleam@list:fold(
        Zipped,
        none,
        fun(Acc, Ew) ->
            {I, Cycle_source_node} = Ew,
            Rc = residual_capacity(Omni, I, Cycle_source_node),
            case Acc of
                none ->
                    {some, {I, Rc}};

                {some, {Min_i, Min_rc}} ->
                    case (Rc < Min_rc) orelse ((Rc =:= Min_rc) andalso (I < Min_i)) of
                        true ->
                            {some, {I, Rc}};

                        false ->
                            Acc
                    end
            end
        end
    ),
    {J@1, Rc@2} = case Min_edge of
        {some, {J, Rc@1}} -> {J, Rc@1};
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/flow/network_simplex"/utf8>>,
                        function => <<"find_leaving_edge"/utf8>>,
                        line => 541,
                        value => _assert_fail,
                        start => 15780,
                        'end' => 15823,
                        pattern_start => 15791,
                        pattern_end => 15812})
    end,
    {J@1, Rc@2}.

-file("src/yog/flow/network_simplex.gleam", 545).
-spec augment_flow(omni_state(), list(integer()), list(integer()), integer()) -> omni_state().
augment_flow(Omni, Wn, We, F) ->
    Zipped = gleam@list:zip(We, Wn),
    gleam@list:fold(
        Zipped,
        Omni,
        fun(Acc, Ew) ->
            {I, P} = Ew,
            S = wget(erlang:element(6, Acc), I),
            Update_amt = case S =:= P of
                true ->
                    F;

                false ->
                    - F
            end,
            {omni_state,
                erlang:element(2, Acc),
                erlang:element(3, Acc),
                erlang:element(4, Acc),
                erlang:element(5, Acc),
                erlang:element(6, Acc),
                erlang:element(7, Acc),
                erlang:element(8, Acc),
                erlang:element(9, Acc),
                wupdate(
                    erlang:element(10, Acc),
                    I,
                    fun(Curr) -> Curr + Update_amt end
                ),
                erlang:element(11, Acc),
                erlang:element(12, Acc),
                erlang:element(13, Acc),
                erlang:element(14, Acc),
                erlang:element(15, Acc),
                erlang:element(16, Acc),
                erlang:element(17, Acc),
                erlang:element(18, Acc),
                erlang:element(19, Acc)}
        end
    ).

-file("src/yog/flow/network_simplex.gleam", 571).
-spec do_trace_subtree(omni_state(), integer(), integer(), integer()) -> list(integer()).
do_trace_subtree(Omni, P, L, Max) ->
    case (P =:= L) orelse (Max =< 0) of
        true ->
            [P];

        false ->
            [P |
                do_trace_subtree(
                    Omni,
                    wget(erlang:element(15, Omni), P),
                    L,
                    Max - 1
                )]
    end.

-file("src/yog/flow/network_simplex.gleam", 566).
-spec trace_subtree(omni_state(), integer()) -> list(integer()).
trace_subtree(Omni, P) ->
    L = wget(erlang:element(17, Omni), P),
    do_trace_subtree(Omni, P, L, erlang:element(2, Omni)).

-file("src/yog/flow/network_simplex.gleam", 605).
-spec do_remove_tree_edge_ancestors(
    omni_state(),
    integer(),
    integer(),
    integer(),
    integer(),
    integer()
) -> omni_state().
do_remove_tree_edge_ancestors(Omni, S, Size_t, Last_t, Prev_t, Max) ->
    case (S < 0) orelse (Max =< 0) of
        true ->
            Omni;

        false ->
            Next_s = wget(erlang:element(12, Omni), S),
            O1 = {omni_state,
                erlang:element(2, Omni),
                erlang:element(3, Omni),
                erlang:element(4, Omni),
                erlang:element(5, Omni),
                erlang:element(6, Omni),
                erlang:element(7, Omni),
                erlang:element(8, Omni),
                erlang:element(9, Omni),
                erlang:element(10, Omni),
                erlang:element(11, Omni),
                erlang:element(12, Omni),
                erlang:element(13, Omni),
                wupdate(
                    erlang:element(14, Omni),
                    S,
                    fun(Curr) -> Curr - Size_t end
                ),
                erlang:element(15, Omni),
                erlang:element(16, Omni),
                wupdate(
                    erlang:element(17, Omni),
                    S,
                    fun(Curr@1) -> case Curr@1 =:= Last_t of
                            true ->
                                Prev_t;

                            false ->
                                Curr@1
                        end end
                ),
                erlang:element(18, Omni),
                erlang:element(19, Omni)},
            do_remove_tree_edge_ancestors(
                O1,
                Next_s,
                Size_t,
                Last_t,
                Prev_t,
                Max - 1
            )
    end.

-file("src/yog/flow/network_simplex.gleam", 578).
-spec remove_tree_edge(omni_state(), integer(), integer()) -> omni_state().
remove_tree_edge(Omni, S, T) ->
    case S =:= wget(erlang:element(12, Omni), T) of
        true -> nil;
        _assert_fail ->
            erlang:error(#{gleam_error => let_assert,
                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                        file => <<?FILEPATH/utf8>>,
                        module => <<"yog/flow/network_simplex"/utf8>>,
                        function => <<"remove_tree_edge"/utf8>>,
                        line => 579,
                        value => _assert_fail,
                        start => 16664,
                        'end' => 16708,
                        pattern_start => 16675,
                        pattern_end => 16679})
    end,
    Size_t = wget(erlang:element(14, Omni), T),
    Prev_t = wget(erlang:element(16, Omni), T),
    Last_t = wget(erlang:element(17, Omni), T),
    Next_last_t = wget(erlang:element(15, Omni), Last_t),
    O1 = {omni_state,
        erlang:element(2, Omni),
        erlang:element(3, Omni),
        erlang:element(4, Omni),
        erlang:element(5, Omni),
        erlang:element(6, Omni),
        erlang:element(7, Omni),
        erlang:element(8, Omni),
        erlang:element(9, Omni),
        erlang:element(10, Omni),
        erlang:element(11, Omni),
        wassoc(erlang:element(12, Omni), T, -1),
        wassoc(erlang:element(13, Omni), T, -1),
        erlang:element(14, Omni),
        wassoc(erlang:element(15, Omni), Prev_t, Next_last_t),
        wassoc(erlang:element(16, Omni), Next_last_t, Prev_t),
        erlang:element(17, Omni),
        erlang:element(18, Omni),
        erlang:element(19, Omni)},
    O2 = {omni_state,
        erlang:element(2, O1),
        erlang:element(3, O1),
        erlang:element(4, O1),
        erlang:element(5, O1),
        erlang:element(6, O1),
        erlang:element(7, O1),
        erlang:element(8, O1),
        erlang:element(9, O1),
        erlang:element(10, O1),
        erlang:element(11, O1),
        erlang:element(12, O1),
        erlang:element(13, O1),
        erlang:element(14, O1),
        wassoc(erlang:element(15, O1), Last_t, T),
        wassoc(erlang:element(16, O1), T, Last_t),
        erlang:element(17, O1),
        erlang:element(18, O1),
        erlang:element(19, O1)},
    do_remove_tree_edge_ancestors(
        O2,
        S,
        Size_t,
        Last_t,
        Prev_t,
        erlang:element(2, Omni)
    ).

-file("src/yog/flow/network_simplex.gleam", 675).
-spec do_get_ancestors(omni_state(), integer(), list(integer()), integer()) -> {list(integer()),
    integer()}.
do_get_ancestors(Omni, Q, Acc, Max) ->
    case (Q < 0) orelse (Max =< 0) of
        true ->
            {Acc, Q};

        false ->
            do_get_ancestors(
                Omni,
                wget(erlang:element(12, Omni), Q),
                lists:append(Acc, [Q]),
                Max - 1
            )
    end.

-file("src/yog/flow/network_simplex.gleam", 633).
-spec make_root(omni_state(), integer()) -> omni_state().
make_root(Omni, Q) ->
    {Ancestors, _} = do_get_ancestors(Omni, Q, [], erlang:element(2, Omni)),
    Reversed_ancestors = lists:reverse(Ancestors),
    Zipped = gleam@list:zip(
        Reversed_ancestors,
        gleam@list:drop(Reversed_ancestors, 1)
    ),
    gleam@list:fold(
        Zipped,
        Omni,
        fun(Acc, Pq) ->
            {P, Q_curr} = Pq,
            Size_p = wget(erlang:element(14, Acc), P),
            Last_p = wget(erlang:element(17, Acc), P),
            Prev_q = wget(erlang:element(16, Acc), Q_curr),
            Last_q = wget(erlang:element(17, Acc), Q_curr),
            Next_last_q = wget(erlang:element(15, Acc), Last_q),
            Size_q = wget(erlang:element(14, Acc), Q_curr),
            E_q = wget(erlang:element(13, Acc), Q_curr),
            O1 = {omni_state,
                erlang:element(2, Acc),
                erlang:element(3, Acc),
                erlang:element(4, Acc),
                erlang:element(5, Acc),
                erlang:element(6, Acc),
                erlang:element(7, Acc),
                erlang:element(8, Acc),
                erlang:element(9, Acc),
                erlang:element(10, Acc),
                erlang:element(11, Acc),
                wassoc(wassoc(erlang:element(12, Acc), P, Q_curr), Q_curr, -1),
                wassoc(wassoc(erlang:element(13, Acc), P, E_q), Q_curr, -1),
                wassoc(
                    wassoc(erlang:element(14, Acc), P, Size_p - Size_q),
                    Q_curr,
                    Size_p
                ),
                wassoc(
                    wassoc(erlang:element(15, Acc), Prev_q, Next_last_q),
                    Last_q,
                    Q_curr
                ),
                wassoc(
                    wassoc(erlang:element(16, Acc), Next_last_q, Prev_q),
                    Q_curr,
                    Last_q
                ),
                erlang:element(17, Acc),
                erlang:element(18, Acc),
                erlang:element(19, Acc)},
            O2 = case Last_p =:= Last_q of
                true ->
                    {omni_state,
                        erlang:element(2, O1),
                        erlang:element(3, O1),
                        erlang:element(4, O1),
                        erlang:element(5, O1),
                        erlang:element(6, O1),
                        erlang:element(7, O1),
                        erlang:element(8, O1),
                        erlang:element(9, O1),
                        erlang:element(10, O1),
                        erlang:element(11, O1),
                        erlang:element(12, O1),
                        erlang:element(13, O1),
                        erlang:element(14, O1),
                        erlang:element(15, O1),
                        erlang:element(16, O1),
                        wassoc(erlang:element(17, O1), P, Prev_q),
                        erlang:element(18, O1),
                        erlang:element(19, O1)};

                false ->
                    O1
            end,
            Last_p_new = wget(erlang:element(17, O2), P),
            {omni_state,
                erlang:element(2, O2),
                erlang:element(3, O2),
                erlang:element(4, O2),
                erlang:element(5, O2),
                erlang:element(6, O2),
                erlang:element(7, O2),
                erlang:element(8, O2),
                erlang:element(9, O2),
                erlang:element(10, O2),
                erlang:element(11, O2),
                erlang:element(12, O2),
                erlang:element(13, O2),
                erlang:element(14, O2),
                wassoc(
                    wassoc(erlang:element(15, O2), Last_q, P),
                    Last_p_new,
                    Q_curr
                ),
                wassoc(
                    wassoc(erlang:element(16, O2), P, Last_q),
                    Q_curr,
                    Last_p_new
                ),
                wassoc(erlang:element(17, O2), Q_curr, Last_p_new),
                erlang:element(18, O2),
                erlang:element(19, O2)}
        end
    ).

-file("src/yog/flow/network_simplex.gleam", 693).
-spec update_potentials(omni_state(), integer(), integer(), integer()) -> omni_state().
update_potentials(Omni, I, P, Q) ->
    C = wget(erlang:element(9, Omni), I),
    S = wget(erlang:element(6, Omni), I),
    T = wget(erlang:element(7, Omni), I),
    Phi_s = wget(erlang:element(11, Omni), S),
    Phi_t = wget(erlang:element(11, Omni), T),
    _ = wget(erlang:element(11, Omni), Q),
    _ = wget(erlang:element(11, Omni), P),
    Delta = case P =:= S of
        true ->
            (Phi_s + C) - Phi_t;

        false ->
            (Phi_t - C) - Phi_s
    end,
    Subtree_nodes = trace_subtree(Omni, Q),
    gleam@list:fold(
        Subtree_nodes,
        Omni,
        fun(Acc, N) ->
            {omni_state,
                erlang:element(2, Acc),
                erlang:element(3, Acc),
                erlang:element(4, Acc),
                erlang:element(5, Acc),
                erlang:element(6, Acc),
                erlang:element(7, Acc),
                erlang:element(8, Acc),
                erlang:element(9, Acc),
                erlang:element(10, Acc),
                wupdate(
                    erlang:element(11, Acc),
                    N,
                    fun(Curr) -> Curr + Delta end
                ),
                erlang:element(12, Acc),
                erlang:element(13, Acc),
                erlang:element(14, Acc),
                erlang:element(15, Acc),
                erlang:element(16, Acc),
                erlang:element(17, Acc),
                erlang:element(18, Acc),
                erlang:element(19, Acc)}
        end
    ).

-file("src/yog/flow/network_simplex.gleam", 723).
-spec find_entering_edges(omni_state()) -> gleam@option:option({integer(),
    integer(),
    integer(),
    integer()}).
find_entering_edges(Omni) ->
    Search_space = seq(0, erlang:element(3, Omni) - 1),
    Result = gleam@list:fold_until(
        Search_space,
        none,
        fun(Acc, Idx) ->
            Offset = case erlang:element(3, Omni) of
                0 -> 0;
                Gleam@denominator -> (erlang:element(18, Omni) + Idx) rem Gleam@denominator
            end,
            Is_tree_edge = gleam@list:contains(erlang:element(13, Omni), Offset),
            case Is_tree_edge of
                true ->
                    {continue, Acc};

                false ->
                    Rc = reduced_cost(Omni, Offset),
                    case Rc < 0 of
                        false ->
                            {continue, Acc};

                        true ->
                            S = wget(erlang:element(6, Omni), Offset),
                            T = wget(erlang:element(7, Omni), Offset),
                            F = wget(erlang:element(10, Omni), Offset),
                            {P, Q} = case F =:= 0 of
                                true ->
                                    {S, T};

                                false ->
                                    {T, S}
                            end,
                            {stop, {some, {Offset, P, Q, F}}}
                    end
            end
        end
    ),
    case Result of
        {some, {_, _, _, _}} ->
            Result;

        none ->
            none
    end.

-file("src/yog/flow/network_simplex.gleam", 818).
-spec do_add_tree_edge_ancestors(omni_state(), integer(), integer(), integer()) -> omni_state().
do_add_tree_edge_ancestors(Omni, P, Size_q, Max) ->
    case (P < 0) orelse (Max =< 0) of
        true ->
            Omni;

        false ->
            O1 = {omni_state,
                erlang:element(2, Omni),
                erlang:element(3, Omni),
                erlang:element(4, Omni),
                erlang:element(5, Omni),
                erlang:element(6, Omni),
                erlang:element(7, Omni),
                erlang:element(8, Omni),
                erlang:element(9, Omni),
                erlang:element(10, Omni),
                erlang:element(11, Omni),
                erlang:element(12, Omni),
                erlang:element(13, Omni),
                wupdate(
                    erlang:element(14, Omni),
                    P,
                    fun(Curr) -> Curr + Size_q end
                ),
                erlang:element(15, Omni),
                erlang:element(16, Omni),
                erlang:element(17, Omni),
                erlang:element(18, Omni),
                erlang:element(19, Omni)},
            do_add_tree_edge_ancestors(
                O1,
                wget(erlang:element(12, Omni), P),
                Size_q,
                Max - 1
            )
    end.

-file("src/yog/flow/network_simplex.gleam", 837).
-spec do_update_lasts_ancestors(
    omni_state(),
    integer(),
    integer(),
    integer(),
    integer()
) -> omni_state().
do_update_lasts_ancestors(Omni, S, Last_s, Last_t, Max) ->
    case (S < 0) orelse (Max =< 0) of
        true ->
            Omni;

        false ->
            O1 = {omni_state,
                erlang:element(2, Omni),
                erlang:element(3, Omni),
                erlang:element(4, Omni),
                erlang:element(5, Omni),
                erlang:element(6, Omni),
                erlang:element(7, Omni),
                erlang:element(8, Omni),
                erlang:element(9, Omni),
                erlang:element(10, Omni),
                erlang:element(11, Omni),
                erlang:element(12, Omni),
                erlang:element(13, Omni),
                erlang:element(14, Omni),
                erlang:element(15, Omni),
                erlang:element(16, Omni),
                wupdate(
                    erlang:element(17, Omni),
                    S,
                    fun(Curr) -> case Curr =:= Last_s of
                            true ->
                                Last_t;

                            false ->
                                Curr
                        end end
                ),
                erlang:element(18, Omni),
                erlang:element(19, Omni)},
            Next_s = wget(erlang:element(12, O1), S),
            do_update_lasts_ancestors(O1, Next_s, Last_s, Last_t, Max - 1)
    end.

-file("src/yog/flow/network_simplex.gleam", 863).
-spec do_add_tree_edge_thread(omni_state(), integer(), integer()) -> omni_state().
do_add_tree_edge_thread(Omni, T, S) ->
    Last_s = wget(erlang:element(17, Omni), S),
    Next_last_s = wget(erlang:element(15, Omni), Last_s),
    Last_t = wget(erlang:element(17, Omni), T),
    O1 = do_update_lasts_ancestors(
        Omni,
        S,
        Last_s,
        Last_t,
        erlang:element(2, Omni)
    ),
    {omni_state,
        erlang:element(2, O1),
        erlang:element(3, O1),
        erlang:element(4, O1),
        erlang:element(5, O1),
        erlang:element(6, O1),
        erlang:element(7, O1),
        erlang:element(8, O1),
        erlang:element(9, O1),
        erlang:element(10, O1),
        erlang:element(11, O1),
        erlang:element(12, O1),
        erlang:element(13, O1),
        erlang:element(14, O1),
        wassoc(wassoc(erlang:element(15, O1), Last_s, T), Last_t, Next_last_s),
        wassoc(wassoc(erlang:element(16, O1), T, Last_s), Next_last_s, Last_t),
        erlang:element(17, O1),
        erlang:element(18, O1),
        erlang:element(19, O1)}.

-file("src/yog/flow/network_simplex.gleam", 765).
-spec pivot(omni_state(), {integer(), integer(), integer(), integer()}) -> omni_state().
pivot(Omni, Ee) ->
    {I, P, Q, _} = Ee,
    {Wn, We, Len_p} = find_cycle(Omni, I, P, Q),
    {J, Rc} = find_leaving_edge(Omni, Wn, We),
    J_on_p_side = begin
        _pipe = gleam@list:take(We, Len_p),
        gleam@list:contains(_pipe, J)
    end,
    {P_val, Q_val} = case J_on_p_side of
        true ->
            {Q, P};

        false ->
            {P, Q}
    end,
    Omni@1 = augment_flow(Omni, Wn, We, Rc),
    case I =:= J of
        true ->
            Omni@1;

        false ->
            J_src = wget(erlang:element(6, Omni@1), J),
            J_tgt = wget(erlang:element(7, Omni@1), J),
            Leaving_child = case wget(erlang:element(12, Omni@1), J_src) =:= J_tgt of
                true ->
                    J_src;

                false ->
                    J_tgt
            end,
            Leaving_parent = wget(erlang:element(12, Omni@1), Leaving_child),
            Omni@2 = remove_tree_edge(Omni@1, Leaving_parent, Leaving_child),
            Omni@3 = make_root(Omni@2, Q_val),
            Omni@4 = {omni_state,
                erlang:element(2, Omni@3),
                erlang:element(3, Omni@3),
                erlang:element(4, Omni@3),
                erlang:element(5, Omni@3),
                erlang:element(6, Omni@3),
                erlang:element(7, Omni@3),
                erlang:element(8, Omni@3),
                erlang:element(9, Omni@3),
                erlang:element(10, Omni@3),
                erlang:element(11, Omni@3),
                wassoc(erlang:element(12, Omni@3), Q_val, P_val),
                wassoc(erlang:element(13, Omni@3), Q_val, I),
                erlang:element(14, Omni@3),
                erlang:element(15, Omni@3),
                erlang:element(16, Omni@3),
                erlang:element(17, Omni@3),
                erlang:element(18, Omni@3),
                erlang:element(19, Omni@3)},
            O1 = do_add_tree_edge_ancestors(
                Omni@4,
                P_val,
                wget(erlang:element(14, Omni@4), Q_val),
                erlang:element(2, Omni@4)
            ),
            O2 = do_add_tree_edge_thread(O1, Q_val, P_val),
            update_potentials(O2, I, P_val, Q_val)
    end.

-file("src/yog/flow/network_simplex.gleam", 877).
-spec pivot_loop(omni_state(), integer()) -> omni_state().
pivot_loop(Omni, Max_iter) ->
    case Max_iter =< 0 of
        true ->
            erlang:error(#{gleam_error => panic,
                    message => <<"Network Simplex Cycle Timeout Error!"/utf8>>,
                    file => <<?FILEPATH/utf8>>,
                    module => <<"yog/flow/network_simplex"/utf8>>,
                    function => <<"pivot_loop"/utf8>>,
                    line => 879});

        false ->
            case find_entering_edges(Omni) of
                none ->
                    Omni;

                {some, Ee} ->
                    Next_omni = pivot(Omni, Ee),
                    pivot_loop(Next_omni, Max_iter - 1)
            end
    end.

-file("src/yog/flow/network_simplex.gleam", 892).
-spec summarize(omni_state(), yog@model:graph(any(), any())) -> {ok,
        min_cost_flow_result()} |
    {error, network_simplex_error()}.
summarize(Omni, _) ->
    Onc = erlang:element(2, Omni) - 1,
    Oec = erlang:element(3, Omni) - Onc,
    Artificial_edges = seq(Oec, (Oec + Onc) - 1),
    Is_infeasible = gleam@list:any(
        Artificial_edges,
        fun(I) -> wget(erlang:element(10, Omni), I) > 0 end
    ),
    case Is_infeasible of
        true ->
            {error, infeasible};

        false ->
            Flow_list = seq(0, Oec - 1),
            {Flow_map, Total_cost} = gleam@list:fold(
                Flow_list,
                {[], 0},
                fun(Acc, I@1) ->
                    {Current_map, Current_cost} = Acc,
                    F = wget(erlang:element(10, Omni), I@1),
                    case F > 0 of
                        false ->
                            Acc;

                        true ->
                            S_idx = wget(erlang:element(6, Omni), I@1),
                            T_idx = wget(erlang:element(7, Omni), I@1),
                            C = wget(erlang:element(9, Omni), I@1),
                            S = wget(erlang:element(4, Omni), S_idx),
                            T = wget(erlang:element(4, Omni), T_idx),
                            {[{S, T, F} | Current_map], Current_cost + (F * C)}
                    end
                end
            ),
            {ok, {min_cost_flow_result, Total_cost, Flow_map}}
    end.

-file("src/yog/flow/network_simplex.gleam", 185).
?DOC(
    " Solves the Minimum Cost Flow problem using the Network Simplex algorithm.\n"
    "\n"
    " Returns either the optimal flow assignment or an error.\n"
    "\n"
    " **Time Complexity:** O(V²E) worst case.\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `graph`: The flow network\n"
    " - `get_demand`: Node demand mapping\n"
    " - `get_capacity`: Edge capacity mapping\n"
    " - `get_cost`: Edge unit cost mapping\n"
).
-spec min_cost_flow(
    yog@model:graph(QTR, QTS),
    fun((QTR) -> integer()),
    fun((QTS) -> integer()),
    fun((QTS) -> integer())
) -> {ok, min_cost_flow_result()} | {error, network_simplex_error()}.
min_cost_flow(Graph, Get_demand, Get_capacity, Get_cost) ->
    Extract_res = extract(Graph, Get_demand, Get_capacity, Get_cost),
    case Extract_res of
        {error, Err} ->
            {error, Err};

        {ok, Omni} ->
            Max_pivots = gleam@int:max(500, erlang:element(3, Omni) * 5),
            Ans = begin
                _pipe = Omni,
                _pipe@1 = add_super_source(_pipe),
                _pipe@2 = init_spanning_tree(_pipe@1),
                pivot_loop(_pipe@2, Max_pivots)
            end,
            summarize(Ans, Graph)
    end.