yog

-module(yog@bipartite).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/bipartite.gleam").
-export([partition/1, is_bipartite/1, maximum_matching/2]).
-export_type([partition/0, matching/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 partition() :: {partition,
        gleam@set:set(integer()),
        gleam@set:set(integer())}.

-type matching() :: {matching,
        gleam@dict:dict(integer(), integer()),
        gleam@dict:dict(integer(), integer())}.

-file("src/yog/bipartite.gleam", 219).
-spec get_neighbors(yog@model:graph(any(), any()), integer()) -> list(integer()).
get_neighbors(Graph, Node) ->
    case erlang:element(2, Graph) of
        undirected ->
            case gleam_stdlib:map_get(erlang:element(4, Graph), Node) of
                {error, _} ->
                    [];

                {ok, Neighbors} ->
                    maps:keys(Neighbors)
            end;

        directed ->
            Out_neighbors = case gleam_stdlib:map_get(
                erlang:element(4, Graph),
                Node
            ) of
                {error, _} ->
                    [];

                {ok, Neighbors@1} ->
                    maps:keys(Neighbors@1)
            end,
            In_neighbors = case gleam_stdlib:map_get(
                erlang:element(5, Graph),
                Node
            ) of
                {error, _} ->
                    [];

                {ok, Neighbors@2} ->
                    maps:keys(Neighbors@2)
            end,
            _pipe = lists:append(Out_neighbors, In_neighbors),
            gleam@list:unique(_pipe)
    end.

-file("src/yog/bipartite.gleam", 187).
-spec do_bfs_color(
    yog@model:graph(any(), any()),
    list({integer(), boolean()}),
    gleam@dict:dict(integer(), boolean())
) -> gleam@option:option(gleam@dict:dict(integer(), boolean())).
do_bfs_color(Graph, Queue, Colors) ->
    case Queue of
        [] ->
            {some, Colors};

        [{Node, Color} | Rest] ->
            case gleam_stdlib:map_get(Colors, Node) of
                {ok, Existing_color} ->
                    case Existing_color =:= Color of
                        true ->
                            do_bfs_color(Graph, Rest, Colors);

                        false ->
                            none
                    end;

                {error, _} ->
                    New_colors = gleam@dict:insert(Colors, Node, Color),
                    Neighbors = get_neighbors(Graph, Node),
                    Next_color = not Color,
                    New_queue = gleam@list:fold(
                        Neighbors,
                        Rest,
                        fun(Q, Neighbor) -> [{Neighbor, Next_color} | Q] end
                    ),
                    do_bfs_color(Graph, New_queue, New_colors)
            end
    end.

-file("src/yog/bipartite.gleam", 177).
-spec bfs_color(
    yog@model:graph(any(), any()),
    integer(),
    boolean(),
    gleam@dict:dict(integer(), boolean())
) -> gleam@option:option(gleam@dict:dict(integer(), boolean())).
bfs_color(Graph, Start, Start_color, Colors) ->
    Queue = [{Start, Start_color}],
    do_bfs_color(Graph, Queue, Colors).

-file("src/yog/bipartite.gleam", 155).
-spec color_graph(
    yog@model:graph(any(), any()),
    list(integer()),
    gleam@dict:dict(integer(), boolean())
) -> gleam@option:option(gleam@dict:dict(integer(), boolean())).
color_graph(Graph, Remaining_nodes, Colors) ->
    case Remaining_nodes of
        [] ->
            {some, Colors};

        [Node | Rest] ->
            case gleam@dict:has_key(Colors, Node) of
                true ->
                    color_graph(Graph, Rest, Colors);

                false ->
                    case bfs_color(Graph, Node, true, Colors) of
                        none ->
                            none;

                        {some, Updated_colors} ->
                            color_graph(Graph, Rest, Updated_colors)
                    end
            end
    end.

-file("src/yog/bipartite.gleam", 59).
?DOC(
    " Returns the two partitions of a bipartite graph, or None if the graph is not bipartite.\n"
    "\n"
    " Uses BFS with 2-coloring to detect bipartiteness and construct the partitions.\n"
    " Handles disconnected graphs by checking all components.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " case bipartite.partition(graph) {\n"
    "   Some(Partition(left, right)) -> {\n"
    "     // left and right are the two independent sets\n"
    "     io.println(\"Graph is bipartite!\")\n"
    "   }\n"
    "   None -> io.println(\"Graph is not bipartite\")\n"
    " }\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec partition(yog@model:graph(any(), any())) -> gleam@option:option(partition()).
partition(Graph) ->
    Nodes = maps:keys(erlang:element(3, Graph)),
    Initial_colors = maps:new(),
    case color_graph(Graph, Nodes, Initial_colors) of
        none ->
            none;

        {some, Colors} ->
            {Left, Right} = gleam@dict:fold(
                Colors,
                {gleam@set:new(), gleam@set:new()},
                fun(Acc, Node, Color) ->
                    {Left_set, Right_set} = Acc,
                    case Color of
                        true ->
                            {gleam@set:insert(Left_set, Node), Right_set};

                        false ->
                            {Left_set, gleam@set:insert(Right_set, Node)}
                    end
                end
            ),
            {some, {partition, Left, Right}}
    end.

-file("src/yog/bipartite.gleam", 35).
?DOC(
    " Checks if a graph is bipartite (2-colorable).\n"
    "\n"
    " A graph is bipartite if its vertices can be divided into two disjoint sets\n"
    " such that every edge connects a vertex in one set to a vertex in the other set.\n"
    "\n"
    " ## Example\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"
    "\n"
    " bipartite.is_bipartite(graph)  // => True (can color as: 1,3 vs 2,4)\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec is_bipartite(yog@model:graph(any(), any())) -> boolean().
is_bipartite(Graph) ->
    case partition(Graph) of
        {some, _} ->
            true;

        none ->
            false
    end.

-file("src/yog/bipartite.gleam", 270).
-spec try_neighbors(
    yog@model:graph(any(), any()),
    integer(),
    list(integer()),
    partition(),
    matching(),
    gleam@set:set(integer())
) -> gleam@option:option(matching()).
try_neighbors(Graph, Left_node, Right_neighbors, Partition, Matching, Visited) ->
    case Right_neighbors of
        [] ->
            none;

        [Right_node | Rest] ->
            case gleam@set:contains(Visited, Right_node) of
                true ->
                    try_neighbors(
                        Graph,
                        Left_node,
                        Rest,
                        Partition,
                        Matching,
                        Visited
                    );

                false ->
                    New_visited = gleam@set:insert(Visited, Right_node),
                    case gleam_stdlib:map_get(
                        erlang:element(3, Matching),
                        Right_node
                    ) of
                        {error, _} ->
                            {some,
                                {matching,
                                    gleam@dict:insert(
                                        erlang:element(2, Matching),
                                        Left_node,
                                        Right_node
                                    ),
                                    gleam@dict:insert(
                                        erlang:element(3, Matching),
                                        Right_node,
                                        Left_node
                                    )}};

                        {ok, Matched_left} ->
                            case find_augmenting_path(
                                Graph,
                                Matched_left,
                                Partition,
                                {matching,
                                    gleam@dict:delete(
                                        erlang:element(2, Matching),
                                        Matched_left
                                    ),
                                    gleam@dict:delete(
                                        erlang:element(3, Matching),
                                        Right_node
                                    )},
                                New_visited
                            ) of
                                none ->
                                    try_neighbors(
                                        Graph,
                                        Left_node,
                                        Rest,
                                        Partition,
                                        Matching,
                                        Visited
                                    );

                                {some, Updated_matching} ->
                                    {some,
                                        {matching,
                                            gleam@dict:insert(
                                                erlang:element(
                                                    2,
                                                    Updated_matching
                                                ),
                                                Left_node,
                                                Right_node
                                            ),
                                            gleam@dict:insert(
                                                erlang:element(
                                                    3,
                                                    Updated_matching
                                                ),
                                                Right_node,
                                                Left_node
                                            )}}
                            end
                    end
            end
    end.

-file("src/yog/bipartite.gleam", 244).
-spec find_augmenting_path(
    yog@model:graph(any(), any()),
    integer(),
    partition(),
    matching(),
    gleam@set:set(integer())
) -> gleam@option:option(matching()).
find_augmenting_path(Graph, Left_node, Partition, Matching, Visited) ->
    case gleam@dict:has_key(erlang:element(2, Matching), Left_node) of
        true ->
            none;

        false ->
            Right_neighbors = begin
                _pipe = get_neighbors(Graph, Left_node),
                gleam@list:filter(
                    _pipe,
                    fun(N) ->
                        gleam@set:contains(erlang:element(3, Partition), N)
                    end
                )
            end,
            try_neighbors(
                Graph,
                Left_node,
                Right_neighbors,
                Partition,
                Matching,
                Visited
            )
    end.

-file("src/yog/bipartite.gleam", 114).
?DOC(
    " Finds a maximum matching in a bipartite graph.\n"
    "\n"
    " A matching is a set of edges with no common vertices. A maximum matching\n"
    " has the largest possible number of edges.\n"
    "\n"
    " Uses the augmenting path algorithm (also known as the Hungarian algorithm\n"
    " for unweighted bipartite matching).\n"
    "\n"
    " Returns a list of matched pairs `#(left_node, right_node)`.\n"
    "\n"
    " ## Example\n"
    " ```gleam\n"
    " let graph =\n"
    "   yog.undirected()\n"
    "   |> yog.add_node(1, Nil)  // left\n"
    "   |> yog.add_node(2, Nil)  // left\n"
    "   |> yog.add_node(3, Nil)  // right\n"
    "   |> yog.add_node(4, Nil)  // right\n"
    "   |> yog.add_edge(from: 1, to: 3, with: 1)\n"
    "   |> yog.add_edge(from: 1, to: 4, with: 1)\n"
    "   |> yog.add_edge(from: 2, to: 3, with: 1)\n"
    "\n"
    " case bipartite.partition(graph) {\n"
    "   Some(p) -> {\n"
    "     let matching = bipartite.maximum_matching(graph, p)\n"
    "     // => [#(1, 3), #(2, 4)] or [#(1, 4), #(2, 3)]\n"
    "   }\n"
    "   None -> panic as \"Not bipartite\"\n"
    " }\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(V * E)\n"
).
-spec maximum_matching(yog@model:graph(any(), any()), partition()) -> list({integer(),
    integer()}).
maximum_matching(Graph, Partition) ->
    Matching = {matching, maps:new(), maps:new()},
    Left_list = gleam@set:to_list(erlang:element(2, Partition)),
    Final_matching = gleam@list:fold(
        Left_list,
        Matching,
        fun(Current_matching, Left_node) ->
            Visited = gleam@set:new(),
            case find_augmenting_path(
                Graph,
                Left_node,
                Partition,
                Current_matching,
                Visited
            ) of
                none ->
                    Current_matching;

                {some, Updated_matching} ->
                    Updated_matching
            end
        end
    ),
    gleam@dict:fold(
        erlang:element(2, Final_matching),
        [],
        fun(Acc, Left, Right) -> [{Left, Right} | Acc] end
    ).