yog

-module(yog@flow@max_flow).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/flow/max_flow.gleam").
-export([edmonds_karp/8, min_cut/3, edmonds_karp_int/3]).
-export_type([max_flow_result/1, 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.

?MODULEDOC(
    " Maximum flow algorithms and min-cut extraction.\n"
    "\n"
    " This module implements the Edmonds-Karp algorithm for finding the maximum\n"
    " flow in a network and extracting the corresponding minimum cut.\n"
).

-type max_flow_result(MLX) :: {max_flow_result,
        MLX,
        yog@model:graph(nil, MLX),
        integer(),
        integer()}.

-type min_cut() :: {min_cut, gleam@set:set(integer()), gleam@set:set(integer())}.

-file("src/yog/flow/max_flow.gleam", 203).
-spec build_adjacency_list(gleam@dict:dict({integer(), integer()}, any())) -> gleam@dict:dict(integer(), list(integer())).
build_adjacency_list(Residuals) ->
    gleam@dict:fold(
        Residuals,
        maps:new(),
        fun(Adj, Edge, _) ->
            {From, To} = Edge,
            gleam@dict:upsert(Adj, From, fun(Existing) -> case Existing of
                        {some, Neighbors} ->
                            [To | Neighbors];

                        none ->
                            [To]
                    end end)
        end
    ).

-file("src/yog/flow/max_flow.gleam", 363).
-spec do_reconstruct_path(
    gleam@dict:dict(integer(), {integer(), MNN}),
    integer(),
    list(integer()),
    MNN,
    boolean(),
    fun((MNN, MNN) -> MNN)
) -> {list(integer()), MNN}.
do_reconstruct_path(Parents, Current, Path, Bottleneck, Is_first, Min) ->
    New_path = [Current | Path],
    case gleam_stdlib:map_get(Parents, Current) of
        {error, nil} ->
            {New_path, Bottleneck};

        {ok, {Parent, Capacity}} ->
            case Parent of
                -1 ->
                    {New_path, Bottleneck};

                _ ->
                    New_bottleneck = case Is_first of
                        true ->
                            Capacity;

                        false ->
                            Min(Capacity, Bottleneck)
                    end,
                    do_reconstruct_path(
                        Parents,
                        Parent,
                        New_path,
                        New_bottleneck,
                        false,
                        Min
                    )
            end
    end.

-file("src/yog/flow/max_flow.gleam", 354).
-spec reconstruct_path(
    gleam@dict:dict(integer(), {integer(), MNJ}),
    integer(),
    MNJ,
    fun((MNJ, MNJ) -> MNJ)
) -> {list(integer()), MNJ}.
reconstruct_path(Parents, Sink, Zero, Min) ->
    do_reconstruct_path(Parents, Sink, [], Zero, true, Min).

-file("src/yog/flow/max_flow.gleam", 288).
-spec do_bfs(
    gleam@dict:dict({integer(), integer()}, MNB),
    gleam@dict:dict(integer(), list(integer())),
    yog@internal@queue:queue(integer()),
    gleam@dict:dict(integer(), {integer(), MNB}),
    integer(),
    MNB,
    fun((MNB, MNB) -> gleam@order:order()),
    fun((MNB, MNB) -> MNB)
) -> {ok, {list(integer()), MNB}} | {error, nil}.
do_bfs(Residuals, Adj_list, Q, Parents, Sink, Zero, Compare, Min) ->
    case yog@internal@queue:pop(Q) of
        {error, nil} ->
            {error, nil};

        {ok, {Current, Rest}} ->
            case Current =:= Sink of
                true ->
                    {Path, Bottleneck} = reconstruct_path(
                        Parents,
                        Sink,
                        Zero,
                        Min
                    ),
                    {ok, {Path, Bottleneck}};

                false ->
                    Neighbors = begin
                        _pipe = gleam_stdlib:map_get(Adj_list, Current),
                        gleam@result:unwrap(_pipe, [])
                    end,
                    {New_neighbors, New_parents} = gleam@list:fold(
                        Neighbors,
                        {[], Parents},
                        fun(Acc, Neighbor) ->
                            {Neighbors_acc, Parents_acc} = Acc,
                            Cap = begin
                                _pipe@1 = gleam_stdlib:map_get(
                                    Residuals,
                                    {Current, Neighbor}
                                ),
                                gleam@result:unwrap(_pipe@1, Zero)
                            end,
                            Already_visited = gleam@dict:has_key(
                                Parents_acc,
                                Neighbor
                            ),
                            Has_capacity = Compare(Cap, Zero) =:= gt,
                            case Already_visited orelse not Has_capacity of
                                true ->
                                    Acc;

                                false ->
                                    Updated_parents = gleam@dict:insert(
                                        Parents_acc,
                                        Neighbor,
                                        {Current, Cap}
                                    ),
                                    {[Neighbor | Neighbors_acc],
                                        Updated_parents}
                            end
                        end
                    ),
                    New_queue = yog@internal@queue:push_list(
                        Rest,
                        New_neighbors
                    ),
                    do_bfs(
                        Residuals,
                        Adj_list,
                        New_queue,
                        New_parents,
                        Sink,
                        Zero,
                        Compare,
                        Min
                    )
            end
    end.

-file("src/yog/flow/max_flow.gleam", 265).
-spec find_augmenting_path_bfs(
    gleam@dict:dict({integer(), integer()}, MMW),
    gleam@dict:dict(integer(), list(integer())),
    integer(),
    integer(),
    MMW,
    fun((MMW, MMW) -> gleam@order:order()),
    fun((MMW, MMW) -> MMW)
) -> {ok, {list(integer()), MMW}} | {error, nil}.
find_augmenting_path_bfs(Residuals, Adj_list, Source, Sink, Zero, Compare, Min) ->
    Initial_queue = begin
        _pipe = yog@internal@queue:new(),
        yog@internal@queue:push(_pipe, Source)
    end,
    do_bfs(
        Residuals,
        Adj_list,
        Initial_queue,
        maps:from_list([{Source, {-1, Zero}}]),
        Sink,
        Zero,
        Compare,
        Min
    ).

-file("src/yog/flow/max_flow.gleam", 409).
-spec do_augment_path(
    gleam@dict:dict({integer(), integer()}, MNW),
    list(integer()),
    MNW,
    fun((MNW, MNW) -> MNW),
    fun((MNW, MNW) -> MNW)
) -> gleam@dict:dict({integer(), integer()}, MNW).
do_augment_path(Residuals, Path, Bottleneck, Add, Subtract) ->
    case Path of
        [] ->
            Residuals;

        [_] ->
            Residuals;

        [From, To | Rest] ->
            Forward_key = {From, To},
            Backward_key = {To, From},
            Forward_cap = begin
                _pipe = gleam_stdlib:map_get(Residuals, Forward_key),
                gleam@result:unwrap(_pipe, Bottleneck)
            end,
            Backward_cap = begin
                _pipe@1 = gleam_stdlib:map_get(Residuals, Backward_key),
                gleam@result:unwrap(_pipe@1, Bottleneck)
            end,
            New_residuals = begin
                _pipe@2 = Residuals,
                _pipe@3 = gleam@dict:insert(
                    _pipe@2,
                    Forward_key,
                    Subtract(Forward_cap, Bottleneck)
                ),
                gleam@dict:insert(
                    _pipe@3,
                    Backward_key,
                    Add(Backward_cap, Bottleneck)
                )
            end,
            do_augment_path(
                New_residuals,
                [To | Rest],
                Bottleneck,
                Add,
                Subtract
            )
    end.

-file("src/yog/flow/max_flow.gleam", 399).
-spec augment_path(
    gleam@dict:dict({integer(), integer()}, MNS),
    list(integer()),
    MNS,
    fun((MNS, MNS) -> MNS),
    fun((MNS, MNS) -> MNS)
) -> gleam@dict:dict({integer(), integer()}, MNS).
augment_path(Residuals, Path, Bottleneck, Add, Subtract) ->
    do_augment_path(Residuals, Path, Bottleneck, Add, Subtract).

-file("src/yog/flow/max_flow.gleam", 216).
-spec ford_fulkerson(
    gleam@dict:dict({integer(), integer()}, MMT),
    gleam@dict:dict(integer(), list(integer())),
    integer(),
    integer(),
    MMT,
    MMT,
    fun((MMT, MMT) -> MMT),
    fun((MMT, MMT) -> MMT),
    fun((MMT, MMT) -> gleam@order:order()),
    fun((MMT, MMT) -> MMT)
) -> {gleam@dict:dict({integer(), integer()}, MMT), MMT}.
ford_fulkerson(
    Residuals,
    Adj_list,
    Source,
    Sink,
    Total_flow,
    Zero,
    Add,
    Subtract,
    Compare,
    Min
) ->
    case find_augmenting_path_bfs(
        Residuals,
        Adj_list,
        Source,
        Sink,
        Zero,
        Compare,
        Min
    ) of
        {error, nil} ->
            {Residuals, Total_flow};

        {ok, {Path, Bottleneck}} ->
            New_residuals = augment_path(
                Residuals,
                Path,
                Bottleneck,
                Add,
                Subtract
            ),
            ford_fulkerson(
                New_residuals,
                Adj_list,
                Source,
                Sink,
                Add(Total_flow, Bottleneck),
                Zero,
                Add,
                Subtract,
                Compare,
                Min
            )
    end.

-file("src/yog/flow/max_flow.gleam", 440).
-spec residuals_to_graph(
    gleam@dict:dict({integer(), integer()}, MOA),
    gleam@set:set(integer())
) -> yog@model:graph(nil, MOA).
residuals_to_graph(Residuals, All_nodes) ->
    Graph = gleam@set:fold(
        All_nodes,
        yog@model:new(directed),
        fun(G, Node) -> yog@model:add_node(G, Node, nil) end
    ),
    gleam@dict:fold(
        Residuals,
        Graph,
        fun(G@1, Edge, Capacity) ->
            {From, To} = Edge,
            yog@model:add_edge(G@1, From, To, Capacity)
        end
    ).

-file("src/yog/flow/max_flow.gleam", 458).
-spec extract_all_nodes_from_edges(yog@model:graph(any(), any())) -> gleam@set:set(integer()).
extract_all_nodes_from_edges(Graph) ->
    Source_nodes = gleam@set:from_list(maps:keys(erlang:element(4, Graph))),
    Dest_nodes = begin
        _pipe = maps:values(erlang:element(4, Graph)),
        _pipe@1 = gleam@list:flat_map(
            _pipe,
            fun(Edge_dict) -> maps:keys(Edge_dict) end
        ),
        gleam@set:from_list(_pipe@1)
    end,
    gleam@set:union(Source_nodes, Dest_nodes).

-file("src/yog/flow/max_flow.gleam", 175).
-spec build_residuals(yog@model:graph(any(), MMM), MMM) -> {gleam@dict:dict({integer(),
        integer()}, MMM),
    gleam@set:set(integer())}.
build_residuals(Graph, Zero) ->
    Nodes_set = begin
        _pipe = extract_all_nodes_from_edges(Graph),
        gleam@set:union(_pipe, gleam@set:from_list(yog@model:all_nodes(Graph)))
    end,
    All_nodes_list = gleam@set:to_list(Nodes_set),
    Residuals = gleam@list:fold(
        All_nodes_list,
        maps:new(),
        fun(Caps, Node_id) ->
            Successors = yog@model:successors(Graph, Node_id),
            gleam@list:fold(
                Successors,
                Caps,
                fun(Acc, Edge) ->
                    {Neighbor, Capacity} = Edge,
                    With_forward = gleam@dict:insert(
                        Acc,
                        {Node_id, Neighbor},
                        Capacity
                    ),
                    case gleam@dict:has_key(With_forward, {Neighbor, Node_id}) of
                        true ->
                            With_forward;

                        false ->
                            gleam@dict:insert(
                                With_forward,
                                {Neighbor, Node_id},
                                Zero
                            )
                    end
                end
            )
        end
    ),
    {Residuals, Nodes_set}.

-file("src/yog/flow/max_flow.gleam", 92).
?DOC(
    " Finds the maximum flow using the Edmonds-Karp algorithm.\n"
    "\n"
    " Edmonds-Karp is a specific implementation of the Ford-Fulkerson method\n"
    " that uses BFS to find the shortest augmenting path. This guarantees\n"
    " O(VE²) time complexity.\n"
    "\n"
    " **Time Complexity:** O(VE²)\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `in` - The flow network (directed graph where edge weights are capacities)\n"
    " - `from` - The source node\n"
    " - `to` - The sink node\n"
    " - `with_zero` - The zero element for the capacity type\n"
    " - `with_add` - Function to add two capacity values\n"
    " - `with_subtract` - Function to subtract capacity values\n"
    " - `with_compare` - Function to compare capacity values\n"
    " - `with_min` - Function to find minimum of two capacity values\n"
    "\n"
    " ## Returns\n"
    "\n"
    " A `MaxFlowResult` containing the max flow value and residual graph.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let result = max_flow.edmonds_karp(\n"
    "   in: network,\n"
    "   from: 0,\n"
    "   to: 5,\n"
    "   with_zero: 0,\n"
    "   with_add: int.add,\n"
    "   with_subtract: int.subtract,\n"
    "   with_compare: int.compare,\n"
    "   with_min: int.min,\n"
    " )\n"
    " ```\n"
).
-spec edmonds_karp(
    yog@model:graph(any(), MMF),
    integer(),
    integer(),
    MMF,
    fun((MMF, MMF) -> MMF),
    fun((MMF, MMF) -> MMF),
    fun((MMF, MMF) -> gleam@order:order()),
    fun((MMF, MMF) -> MMF)
) -> max_flow_result(MMF).
edmonds_karp(Graph, Source, Sink, Zero, Add, Subtract, Compare, Min) ->
    case Source =:= Sink of
        true ->
            Empty_graph = yog@model:new(directed),
            {max_flow_result, Zero, Empty_graph, Source, Sink};

        false ->
            {Residuals, All_nodes} = build_residuals(Graph, Zero),
            Adj_list = build_adjacency_list(Residuals),
            {Final_residuals, Total_flow} = ford_fulkerson(
                Residuals,
                Adj_list,
                Source,
                Sink,
                Zero,
                Zero,
                Add,
                Subtract,
                Compare,
                Min
            ),
            Residual_graph = residuals_to_graph(Final_residuals, All_nodes),
            {max_flow_result, Total_flow, Residual_graph, Source, Sink}
    end.

-file("src/yog/flow/max_flow.gleam", 482).
-spec do_dfs_reachable(
    yog@model:graph(nil, MOO),
    list(integer()),
    gleam@set:set(integer()),
    MOO,
    fun((MOO, MOO) -> gleam@order:order())
) -> gleam@set:set(integer()).
do_dfs_reachable(Residual, Stack, Visited, Zero, Compare) ->
    case Stack of
        [] ->
            Visited;

        [Current | Rest] ->
            case gleam@set:contains(Visited, Current) of
                true ->
                    do_dfs_reachable(Residual, Rest, Visited, Zero, Compare);

                false ->
                    New_visited = gleam@set:insert(Visited, Current),
                    New_stack = begin
                        _pipe = yog@model:successors(Residual, Current),
                        gleam@list:fold(
                            _pipe,
                            Rest,
                            fun(Stack_acc, Edge) ->
                                {Node, Capacity} = Edge,
                                case not gleam@set:contains(New_visited, Node)
                                andalso (Compare(Capacity, Zero) =:= gt) of
                                    true ->
                                        [Node | Stack_acc];

                                    false ->
                                        Stack_acc
                                end
                            end
                        )
                    end,
                    do_dfs_reachable(
                        Residual,
                        New_stack,
                        New_visited,
                        Zero,
                        Compare
                    )
            end
    end.

-file("src/yog/flow/max_flow.gleam", 473).
-spec find_reachable_nodes(
    yog@model:graph(nil, MOK),
    integer(),
    MOK,
    fun((MOK, MOK) -> gleam@order:order())
) -> gleam@set:set(integer()).
find_reachable_nodes(Residual, Source, Zero, Compare) ->
    do_dfs_reachable(Residual, [Source], gleam@set:new(), Zero, Compare).

-file("src/yog/flow/max_flow.gleam", 158).
?DOC(
    " Extracts the minimum cut from a max flow result.\n"
    "\n"
    " Uses the max-flow min-cut theorem identifying nodes reachable from source\n"
    " in the final residual graph.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let cut = max_flow.min_cut(result, with_zero: 0, with_compare: int.compare)\n"
    " ```\n"
).
-spec min_cut(max_flow_result(MMJ), MMJ, fun((MMJ, MMJ) -> gleam@order:order())) -> min_cut().
min_cut(Result, Zero, Compare) ->
    Reachable = find_reachable_nodes(
        erlang:element(3, Result),
        erlang:element(4, Result),
        Zero,
        Compare
    ),
    All_nodes = begin
        _pipe = yog@model:all_nodes(erlang:element(3, Result)),
        gleam@set:from_list(_pipe)
    end,
    Sink_side = gleam@set:difference(All_nodes, Reachable),
    {min_cut, Reachable, Sink_side}.

-file("src/yog/flow/max_flow.gleam", 543).
?DOC(
    " Finds maximum flow with **integer capacities**.\n"
    "\n"
    " This is a convenience wrapper around `edmonds_karp` that uses:\n"
    " - `0` as the zero element\n"
    " - `int.add` for addition\n"
    " - `int.subtract` for subtraction\n"
    " - `int.compare` for comparison\n"
    " - `int.min` for minimum\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let result = max_flow.edmonds_karp_int(network, from: 0, to: 5)\n"
    " // => MaxFlowResult(max_flow: 25, ...)\n"
    " ```\n"
    "\n"
    " ## When to Use\n"
    "\n"
    " Use this for flow networks with integer capacities (bandwidth in Mbps,\n"
    " vehicle capacity, number of lanes, etc.). This is the most common case\n"
    " for network flow problems.\n"
).
-spec edmonds_karp_int(yog@model:graph(any(), integer()), integer(), integer()) -> max_flow_result(integer()).
edmonds_karp_int(Graph, Source, Sink) ->
    edmonds_karp(
        Graph,
        Source,
        Sink,
        0,
        fun gleam@int:add/2,
        fun gleam@int:subtract/2,
        fun gleam@int:compare/2,
        fun gleam@int:min/2
    ).