yog

-module(yog@multi@eulerian).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/multi/eulerian.gleam").
-export([has_eulerian_circuit/1, has_eulerian_path/1, find_eulerian_circuit/1, find_eulerian_path/1]).

-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.

-file("src/yog/multi/eulerian.gleam", 147).
-spec pick_edge(
    yog@multi@model:multi_graph(any(), any()),
    integer(),
    gleam@set:set(integer())
) -> gleam@option:option({integer(), integer()}).
pick_edge(Graph, Current, Available) ->
    _pipe = yog@multi@model:successors(Graph, Current),
    _pipe@1 = gleam@list:find_map(
        _pipe,
        fun(S) ->
            {Dst, Eid, _} = S,
            case gleam@set:contains(Available, Eid) of
                true ->
                    {ok, {Dst, Eid}};

                false ->
                    {error, nil}
            end
        end
    ),
    gleam@option:from_result(_pipe@1).

-file("src/yog/multi/eulerian.gleam", 131).
-spec do_hierholzer(
    yog@multi@model:multi_graph(any(), any()),
    integer(),
    gleam@set:set(integer()),
    list(integer())
) -> {gleam@set:set(integer()), list(integer())}.
do_hierholzer(Graph, Current, Available, Path) ->
    case pick_edge(Graph, Current, Available) of
        none ->
            {Available, Path};

        {some, {Next_node, Eid}} ->
            Available2 = gleam@set:delete(Available, Eid),
            {Av3, Built} = do_hierholzer(Graph, Next_node, Available2, Path),
            {Av3, [Eid | Built]}
    end.

-file("src/yog/multi/eulerian.gleam", 119).
-spec run_hierholzer(yog@multi@model:multi_graph(any(), any()), integer()) -> gleam@option:option(list(integer())).
run_hierholzer(Graph, Start) ->
    All_ids = begin
        _pipe = yog@multi@model:all_edge_ids(Graph),
        gleam@set:from_list(_pipe)
    end,
    {_, Path} = do_hierholzer(Graph, Start, All_ids, []),
    case gleam@list:is_empty(Path) of
        true ->
            none;

        false ->
            {some, Path}
    end.

-file("src/yog/multi/eulerian.gleam", 167).
-spec all_even_degree(yog@multi@model:multi_graph(any(), any())) -> boolean().
all_even_degree(Graph) ->
    _pipe = maps:keys(erlang:element(3, Graph)),
    gleam@list:all(
        _pipe,
        fun(N) -> (yog@multi@model:out_degree(Graph, N) rem 2) =:= 0 end
    ).

-file("src/yog/multi/eulerian.gleam", 172).
-spec all_balanced_degree(yog@multi@model:multi_graph(any(), any())) -> boolean().
all_balanced_degree(Graph) ->
    _pipe = maps:keys(erlang:element(3, Graph)),
    gleam@list:all(
        _pipe,
        fun(N) ->
            yog@multi@model:out_degree(Graph, N) =:= yog@multi@model:in_degree(
                Graph,
                N
            )
        end
    ).

-file("src/yog/multi/eulerian.gleam", 187).
-spec bfs_node_set(
    yog@multi@model:multi_graph(any(), any()),
    integer(),
    gleam@set:set(integer())
) -> gleam@set:set(integer()).
bfs_node_set(Graph, Current, Visited) ->
    case gleam@set:contains(Visited, Current) of
        true ->
            Visited;

        false ->
            Visited2 = gleam@set:insert(Visited, Current),
            Neighbors = begin
                _pipe@2 = lists:append(
                    begin
                        _pipe = yog@multi@model:successors(Graph, Current),
                        gleam@list:map(
                            _pipe,
                            fun(S) -> erlang:element(1, S) end
                        )
                    end,
                    begin
                        _pipe@1 = yog@multi@model:predecessors(Graph, Current),
                        gleam@list:map(
                            _pipe@1,
                            fun(P) -> erlang:element(1, P) end
                        )
                    end
                ),
                gleam@list:unique(_pipe@2)
            end,
            gleam@list:fold(
                Neighbors,
                Visited2,
                fun(Acc, Neighbor) -> bfs_node_set(Graph, Neighbor, Acc) end
            )
    end.

-file("src/yog/multi/eulerian.gleam", 177).
-spec is_connected(yog@multi@model:multi_graph(any(), any())) -> boolean().
is_connected(Graph) ->
    case begin
        _pipe = maps:keys(erlang:element(3, Graph)),
        gleam@list:first(_pipe)
    end of
        {error, _} ->
            true;

        {ok, Start} ->
            Visited = bfs_node_set(Graph, Start, gleam@set:new()),
            gleam@set:size(Visited) =:= maps:size(erlang:element(3, Graph))
    end.

-file("src/yog/multi/eulerian.gleam", 29).
?DOC(
    " Returns `True` if the multigraph has an Eulerian circuit — a closed walk\n"
    " that traverses every edge exactly once.\n"
    "\n"
    " Conditions:\n"
    " - **Undirected:** all nodes have even degree and the graph is connected.\n"
    " - **Directed:** every node has equal in-degree and out-degree and the\n"
    "   graph is (weakly) connected.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec has_eulerian_circuit(yog@multi@model:multi_graph(any(), any())) -> boolean().
has_eulerian_circuit(Graph) ->
    case maps:size(erlang:element(3, Graph)) of
        0 ->
            false;

        _ ->
            case erlang:element(2, Graph) of
                undirected ->
                    all_even_degree(Graph) andalso is_connected(Graph);

                directed ->
                    all_balanced_degree(Graph) andalso is_connected(Graph)
            end
    end.

-file("src/yog/multi/eulerian.gleam", 49).
?DOC(
    " Returns `True` if the multigraph has an Eulerian path — an open walk that\n"
    " traverses every edge exactly once.\n"
    "\n"
    " Conditions:\n"
    " - **Undirected:** exactly 0 or 2 nodes have odd degree and the graph is connected.\n"
    " - **Directed:** at most one node with (out − in = 1), at most one with\n"
    "   (in − out = 1), all others balanced; graph must be connected.\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec has_eulerian_path(yog@multi@model:multi_graph(any(), any())) -> boolean().
has_eulerian_path(Graph) ->
    case maps:size(erlang:element(3, Graph)) of
        0 ->
            false;

        _ ->
            case erlang:element(2, Graph) of
                undirected ->
                    Odd_count = begin
                        _pipe = maps:keys(erlang:element(3, Graph)),
                        _pipe@1 = gleam@list:filter(
                            _pipe,
                            fun(N) ->
                                (yog@multi@model:out_degree(Graph, N) rem 2) =:= 1
                            end
                        ),
                        erlang:length(_pipe@1)
                    end,
                    ((Odd_count =:= 0) orelse (Odd_count =:= 2)) andalso is_connected(
                        Graph
                    );

                directed ->
                    {Starts, Ends, Balanced} = begin
                        _pipe@2 = maps:keys(erlang:element(3, Graph)),
                        gleam@list:fold(
                            _pipe@2,
                            {0, 0, true},
                            fun(Acc, N@1) ->
                                {S, E, Ok} = Acc,
                                Diff = yog@multi@model:out_degree(Graph, N@1) - yog@multi@model:in_degree(
                                    Graph,
                                    N@1
                                ),
                                case Diff of
                                    1 ->
                                        {S + 1, E, Ok};

                                    -1 ->
                                        {S, E + 1, Ok};

                                    0 ->
                                        Acc;

                                    _ ->
                                        {S, E, false}
                                end
                            end
                        )
                    end,
                    (Balanced andalso (((Starts =:= 0) andalso (Ends =:= 0))
                    orelse ((Starts =:= 1) andalso (Ends =:= 1))))
                    andalso is_connected(Graph)
            end
    end.

-file("src/yog/multi/eulerian.gleam", 89).
?DOC(
    " Finds an Eulerian circuit using Hierholzer's algorithm adapted for\n"
    " multigraphs.  The circuit is returned as a list of **`EdgeId`s** rather\n"
    " than node IDs, which avoids ambiguity when parallel edges exist.\n"
    "\n"
    " Returns `None` if no Eulerian circuit exists.\n"
    "\n"
    " **Time Complexity:** O(E)\n"
).
-spec find_eulerian_circuit(yog@multi@model:multi_graph(any(), any())) -> gleam@option:option(list(integer())).
find_eulerian_circuit(Graph) ->
    case has_eulerian_circuit(Graph) of
        false ->
            none;

        true ->
            case begin
                _pipe = maps:keys(erlang:element(3, Graph)),
                gleam@list:first(_pipe)
            end of
                {error, _} ->
                    none;

                {ok, Start} ->
                    run_hierholzer(Graph, Start)
            end
    end.

-file("src/yog/multi/eulerian.gleam", 209).
-spec find_path_start(yog@multi@model:multi_graph(any(), any())) -> gleam@option:option(integer()).
find_path_start(Graph) ->
    case erlang:element(2, Graph) of
        undirected ->
            _pipe = maps:keys(erlang:element(3, Graph)),
            _pipe@1 = gleam@list:find(
                _pipe,
                fun(N) -> (yog@multi@model:out_degree(Graph, N) rem 2) =:= 1 end
            ),
            _pipe@3 = gleam@result:'or'(
                _pipe@1,
                begin
                    _pipe@2 = maps:keys(erlang:element(3, Graph)),
                    gleam@list:find(
                        _pipe@2,
                        fun(N@1) ->
                            yog@multi@model:out_degree(Graph, N@1) > 0
                        end
                    )
                end
            ),
            gleam@option:from_result(_pipe@3);

        directed ->
            _pipe@4 = maps:keys(erlang:element(3, Graph)),
            _pipe@5 = gleam@list:find(
                _pipe@4,
                fun(N@2) ->
                    yog@multi@model:out_degree(Graph, N@2) > yog@multi@model:in_degree(
                        Graph,
                        N@2
                    )
                end
            ),
            _pipe@7 = gleam@result:'or'(
                _pipe@5,
                begin
                    _pipe@6 = maps:keys(erlang:element(3, Graph)),
                    gleam@list:find(
                        _pipe@6,
                        fun(N@3) ->
                            yog@multi@model:out_degree(Graph, N@3) > 0
                        end
                    )
                end
            ),
            gleam@option:from_result(_pipe@7)
    end.

-file("src/yog/multi/eulerian.gleam", 104).
?DOC(
    " Finds an Eulerian path using Hierholzer's algorithm adapted for multigraphs.\n"
    " Returns the path as a list of **`EdgeId`s**.  Returns `None` if no path exists.\n"
    "\n"
    " **Time Complexity:** O(E)\n"
).
-spec find_eulerian_path(yog@multi@model:multi_graph(any(), any())) -> gleam@option:option(list(integer())).
find_eulerian_path(Graph) ->
    case has_eulerian_path(Graph) of
        false ->
            none;

        true ->
            case find_path_start(Graph) of
                none ->
                    none;

                {some, S} ->
                    run_hierholzer(Graph, S)
            end
    end.