yog

-module(yog@connectivity).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/connectivity.gleam").
-export([analyze/1, strongly_connected_components/1, kosaraju/1]).
-export_type([connectivity_results/0, internal_state/0, tarjan_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(
    " Graph connectivity analysis - finding bridges, articulation points, and strongly connected components.\n"
    "\n"
    " This module provides algorithms for analyzing the connectivity structure of graphs,\n"
    " identifying critical components whose removal would disconnect the graph.\n"
    "\n"
    " ## Algorithms\n"
    "\n"
    " | Algorithm | Function | Use Case |\n"
    " |-----------|----------|----------|\n"
    " | [Tarjan's Bridge-Finding](https://en.wikipedia.org/wiki/Bridge_(graph_theory)) | `analyze/1` | Find bridges and articulation points |\n"
    " | [Tarjan's SCC](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) | `strongly_connected_components/1` | Find SCCs in one pass |\n"
    " | [Kosaraju's Algorithm](https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm) | `kosaraju/1` | Find SCCs using two DFS passes |\n"
    "\n"
    " ## Bridges vs Articulation Points\n"
    "\n"
    " - **Bridge** (cut edge): An edge whose removal increases the number of connected components.\n"
    "   In a network, this represents a single point of failure.\n"
    " - **Articulation Point** (cut vertex): A node whose removal increases the number of connected\n"
    "   components. These are critical nodes in the network.\n"
    "\n"
    " ## Strongly Connected Components\n"
    "\n"
    " A **strongly connected component** (SCC) is a maximal subgraph where every node is reachable\n"
    " from every other node. SCCs form a DAG when collapsed, useful for:\n"
    " - Identifying cycles in dependency graphs\n"
    " - Finding groups of mutually reachable web pages\n"
    " - Analyzing feedback loops in systems\n"
    "\n"
    " All algorithms run in **O(V + E)** linear time.\n"
).

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

-type internal_state() :: {internal_state,
        gleam@dict:dict(integer(), integer()),
        gleam@dict:dict(integer(), integer()),
        integer(),
        list({integer(), integer()}),
        gleam@set:set(integer()),
        gleam@set:set(integer())}.

-type tarjan_state() :: {tarjan_state,
        integer(),
        list(integer()),
        gleam@dict:dict(integer(), boolean()),
        gleam@dict:dict(integer(), integer()),
        gleam@dict:dict(integer(), integer()),
        list(list(integer()))}.

-file("src/yog/connectivity.gleam", 119).
-spec do_analyze(
    yog@model:graph(any(), any()),
    integer(),
    gleam@option:option(integer()),
    internal_state()
) -> internal_state().
do_analyze(Graph, V, Parent, State) ->
    Tin = gleam@dict:insert(
        erlang:element(2, State),
        V,
        erlang:element(4, State)
    ),
    Low = gleam@dict:insert(
        erlang:element(3, State),
        V,
        erlang:element(4, State)
    ),
    Visited = gleam@set:insert(erlang:element(7, State), V),
    Timer = erlang:element(4, State) + 1,
    State@1 = {internal_state,
        Tin,
        Low,
        Timer,
        erlang:element(5, State),
        erlang:element(6, State),
        Visited},
    Neighbors = yog@model:successor_ids(Graph, V),
    {Final_state, Children} = gleam@list:fold(
        Neighbors,
        {State@1, 0},
        fun(Acc, To) ->
            {Acc_state, Children_count} = Acc,
            case Parent of
                {some, Parent_id} when To =:= Parent_id ->
                    Acc;

                _ ->
                    case gleam@set:contains(erlang:element(7, Acc_state), To) of
                        true ->
                            V_low@1 = case gleam_stdlib:map_get(
                                erlang:element(3, Acc_state),
                                V
                            ) of
                                {ok, V_low} -> V_low;
                                _assert_fail ->
                                    erlang:error(#{gleam_error => let_assert,
                                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                                file => <<?FILEPATH/utf8>>,
                                                module => <<"yog/connectivity"/utf8>>,
                                                function => <<"do_analyze"/utf8>>,
                                                line => 141,
                                                value => _assert_fail,
                                                start => 4838,
                                                'end' => 4887,
                                                pattern_start => 4849,
                                                pattern_end => 4858})
                            end,
                            To_tin@1 = case gleam_stdlib:map_get(
                                erlang:element(2, Acc_state),
                                To
                            ) of
                                {ok, To_tin} -> To_tin;
                                _assert_fail@1 ->
                                    erlang:error(#{gleam_error => let_assert,
                                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                                file => <<?FILEPATH/utf8>>,
                                                module => <<"yog/connectivity"/utf8>>,
                                                function => <<"do_analyze"/utf8>>,
                                                line => 142,
                                                value => _assert_fail@1,
                                                start => 4902,
                                                'end' => 4953,
                                                pattern_start => 4913,
                                                pattern_end => 4923})
                            end,
                            New_low = gleam@int:min(V_low@1, To_tin@1),
                            {{internal_state,
                                    erlang:element(2, Acc_state),
                                    gleam@dict:insert(
                                        erlang:element(3, Acc_state),
                                        V,
                                        New_low
                                    ),
                                    erlang:element(4, Acc_state),
                                    erlang:element(5, Acc_state),
                                    erlang:element(6, Acc_state),
                                    erlang:element(7, Acc_state)},
                                Children_count};

                        false ->
                            Post_dfs_state = do_analyze(
                                Graph,
                                To,
                                {some, V},
                                Acc_state
                            ),
                            V_low@3 = case gleam_stdlib:map_get(
                                erlang:element(3, Post_dfs_state),
                                V
                            ) of
                                {ok, V_low@2} -> V_low@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/connectivity"/utf8>>,
                                                function => <<"do_analyze"/utf8>>,
                                                line => 155,
                                                value => _assert_fail@2,
                                                start => 5343,
                                                'end' => 5397,
                                                pattern_start => 5354,
                                                pattern_end => 5363})
                            end,
                            To_low@1 = case gleam_stdlib:map_get(
                                erlang:element(3, Post_dfs_state),
                                To
                            ) of
                                {ok, To_low} -> To_low;
                                _assert_fail@3 ->
                                    erlang:error(#{gleam_error => let_assert,
                                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                                file => <<?FILEPATH/utf8>>,
                                                module => <<"yog/connectivity"/utf8>>,
                                                function => <<"do_analyze"/utf8>>,
                                                line => 156,
                                                value => _assert_fail@3,
                                                start => 5412,
                                                'end' => 5468,
                                                pattern_start => 5423,
                                                pattern_end => 5433})
                            end,
                            New_v_low = gleam@int:min(V_low@3, To_low@1),
                            V_tin@1 = case gleam_stdlib:map_get(
                                erlang:element(2, Post_dfs_state),
                                V
                            ) of
                                {ok, V_tin} -> V_tin;
                                _assert_fail@4 ->
                                    erlang:error(#{gleam_error => let_assert,
                                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                                file => <<?FILEPATH/utf8>>,
                                                module => <<"yog/connectivity"/utf8>>,
                                                function => <<"do_analyze"/utf8>>,
                                                line => 159,
                                                value => _assert_fail@4,
                                                start => 5537,
                                                'end' => 5591,
                                                pattern_start => 5548,
                                                pattern_end => 5557})
                            end,
                            New_bridges = case To_low@1 > V_tin@1 of
                                true ->
                                    Bridge = case V < To of
                                        true ->
                                            {V, To};

                                        false ->
                                            {To, V}
                                    end,
                                    [Bridge | erlang:element(5, Post_dfs_state)];

                                false ->
                                    erlang:element(5, Post_dfs_state)
                            end,
                            New_points = case {Parent, To_low@1 >= V_tin@1} of
                                {{some, _}, true} ->
                                    gleam@set:insert(
                                        erlang:element(6, Post_dfs_state),
                                        V
                                    );

                                {_, _} ->
                                    erlang:element(6, Post_dfs_state)
                            end,
                            {{internal_state,
                                    erlang:element(2, Post_dfs_state),
                                    gleam@dict:insert(
                                        erlang:element(3, Post_dfs_state),
                                        V,
                                        New_v_low
                                    ),
                                    erlang:element(4, Post_dfs_state),
                                    New_bridges,
                                    New_points,
                                    erlang:element(7, Post_dfs_state)},
                                Children_count + 1}
                    end
            end
        end
    ),
    case {Parent, Children > 1} of
        {none, true} ->
            {internal_state,
                erlang:element(2, Final_state),
                erlang:element(3, Final_state),
                erlang:element(4, Final_state),
                erlang:element(5, Final_state),
                gleam@set:insert(erlang:element(6, Final_state), V),
                erlang:element(7, Final_state)};

        {_, _} ->
            Final_state
    end.

-file("src/yog/connectivity.gleam", 82).
?DOC(
    " Analyzes an **undirected graph** to find all bridges and articulation points\n"
    " using Tarjan's algorithm in a single DFS pass.\n"
    "\n"
    " **Important:** This algorithm is designed for undirected graphs. For directed\n"
    " graphs, use strongly connected components analysis instead.\n"
    "\n"
    " **Bridges** are edges whose removal increases the number of connected connectivity.\n"
    " **Articulation points** (cut vertices) are nodes whose removal increases the number\n"
    " of connected connectivity.\n"
    "\n"
    " **Bridge ordering:** Bridges are returned as `#(lower_id, higher_id)` for consistency.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog\n"
    " import yog/connectivity\n"
    "\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_edge(from: 1, to: 2, with: Nil)\n"
    "   |> yog.add_edge(from: 2, to: 3, with: Nil)\n"
    "\n"
    " let results = connectivity.analyze(in: graph)\n"
    " // results.bridges == [#(1, 2), #(2, 3)]\n"
    " // results.articulation_points == [2]\n"
    " ```\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
).
-spec analyze(yog@model:graph(any(), any())) -> connectivity_results().
analyze(Graph) ->
    Nodes = maps:keys(erlang:element(3, Graph)),
    Initial_state = {internal_state,
        maps:new(),
        maps:new(),
        0,
        [],
        gleam@set:new(),
        gleam@set:new()},
    Final_state = gleam@list:fold(
        Nodes,
        Initial_state,
        fun(State, Node) ->
            case gleam@set:contains(erlang:element(7, State), Node) of
                true ->
                    State;

                false ->
                    do_analyze(Graph, Node, none, State)
            end
        end
    ),
    {connectivity_results,
        erlang:element(5, Final_state),
        gleam@set:to_list(erlang:element(6, Final_state))}.

-file("src/yog/connectivity.gleam", 296).
-spec pop_stack_until(integer(), tarjan_state(), list(integer())) -> tarjan_state().
pop_stack_until(U, State, Component) ->
    case erlang:element(3, State) of
        [] ->
            State;

        [Head | Tail] ->
            New_component = [Head | Component],
            New_on_stack = gleam@dict:insert(
                erlang:element(4, State),
                Head,
                false
            ),
            Next_state = {tarjan_state,
                erlang:element(2, State),
                Tail,
                New_on_stack,
                erlang:element(5, State),
                erlang:element(6, State),
                erlang:element(7, State)},
            case Head =:= U of
                true ->
                    {tarjan_state,
                        erlang:element(2, Next_state),
                        erlang:element(3, Next_state),
                        erlang:element(4, Next_state),
                        erlang:element(5, Next_state),
                        erlang:element(6, Next_state),
                        [New_component | erlang:element(7, State)]};

                false ->
                    pop_stack_until(U, Next_state, New_component)
            end
    end.

-file("src/yog/connectivity.gleam", 237).
-spec strong_connect(yog@model:graph(any(), any()), integer(), tarjan_state()) -> tarjan_state().
strong_connect(Graph, U, State) ->
    State@1 = {tarjan_state,
        erlang:element(2, State) + 1,
        [U | erlang:element(3, State)],
        gleam@dict:insert(erlang:element(4, State), U, true),
        gleam@dict:insert(erlang:element(5, State), U, erlang:element(2, State)),
        gleam@dict:insert(erlang:element(6, State), U, erlang:element(2, State)),
        erlang:element(7, State)},
    Successors = yog@model:successor_ids(Graph, U),
    State@2 = gleam@list:fold(
        Successors,
        State@1,
        fun(St, V) -> case gleam@dict:has_key(erlang:element(5, St), V) of
                false ->
                    St@1 = strong_connect(Graph, V, St),
                    U_low = begin
                        _pipe = gleam_stdlib:map_get(erlang:element(6, St@1), U),
                        gleam@result:unwrap(_pipe, 0)
                    end,
                    V_low = begin
                        _pipe@1 = gleam_stdlib:map_get(
                            erlang:element(6, St@1),
                            V
                        ),
                        gleam@result:unwrap(_pipe@1, 0)
                    end,
                    {tarjan_state,
                        erlang:element(2, St@1),
                        erlang:element(3, St@1),
                        erlang:element(4, St@1),
                        erlang:element(5, St@1),
                        gleam@dict:insert(
                            erlang:element(6, St@1),
                            U,
                            gleam@int:min(U_low, V_low)
                        ),
                        erlang:element(7, St@1)};

                true ->
                    case begin
                        _pipe@2 = gleam_stdlib:map_get(erlang:element(4, St), V),
                        gleam@result:unwrap(_pipe@2, false)
                    end of
                        true ->
                            U_low@1 = begin
                                _pipe@3 = gleam_stdlib:map_get(
                                    erlang:element(6, St),
                                    U
                                ),
                                gleam@result:unwrap(_pipe@3, 0)
                            end,
                            V_index = begin
                                _pipe@4 = gleam_stdlib:map_get(
                                    erlang:element(5, St),
                                    V
                                ),
                                gleam@result:unwrap(_pipe@4, 0)
                            end,
                            {tarjan_state,
                                erlang:element(2, St),
                                erlang:element(3, St),
                                erlang:element(4, St),
                                erlang:element(5, St),
                                gleam@dict:insert(
                                    erlang:element(6, St),
                                    U,
                                    gleam@int:min(U_low@1, V_index)
                                ),
                                erlang:element(7, St)};

                        false ->
                            St
                    end
            end end
    ),
    U_index = begin
        _pipe@5 = gleam_stdlib:map_get(erlang:element(5, State@2), U),
        gleam@result:unwrap(_pipe@5, 0)
    end,
    U_low@2 = begin
        _pipe@6 = gleam_stdlib:map_get(erlang:element(6, State@2), U),
        gleam@result:unwrap(_pipe@6, 0)
    end,
    case U_low@2 =:= U_index of
        true ->
            pop_stack_until(U, State@2, []);

        false ->
            State@2
    end.

-file("src/yog/connectivity.gleam", 213).
?DOC(
    " Finds Strongly Connected Components (SCC) using Tarjan's Algorithm.\n"
    " Returns a list of components, where each component is a list of NodeIds.\n"
).
-spec strongly_connected_components(yog@model:graph(any(), any())) -> list(list(integer())).
strongly_connected_components(Graph) ->
    Nodes = yog@model:all_nodes(Graph),
    Initial_state = {tarjan_state,
        0,
        [],
        maps:new(),
        maps:new(),
        maps:new(),
        []},
    Final_state = gleam@list:fold(
        Nodes,
        Initial_state,
        fun(State, Node) ->
            case gleam@dict:has_key(erlang:element(5, State), Node) of
                true ->
                    State;

                false ->
                    strong_connect(Graph, Node, State)
            end
        end
    ),
    erlang:element(7, Final_state).

-file("src/yog/connectivity.gleam", 387).
-spec first_dfs(
    yog@model:graph(any(), any()),
    integer(),
    gleam@set:set(integer()),
    list(integer())
) -> {list(integer()), gleam@set:set(integer())}.
first_dfs(Graph, Node, Visited, Stack) ->
    case gleam@set:contains(Visited, Node) of
        true ->
            {Stack, Visited};

        false ->
            New_visited = gleam@set:insert(Visited, Node),
            Successors = yog@model:successor_ids(Graph, Node),
            {New_stack, Final_visited} = gleam@list:fold(
                Successors,
                {Stack, New_visited},
                fun(Acc, Succ) ->
                    {S, V} = Acc,
                    first_dfs(Graph, Succ, V, S)
                end
            ),
            {[Node | New_stack], Final_visited}
    end.

-file("src/yog/connectivity.gleam", 413).
-spec second_dfs(
    yog@model:graph(any(), any()),
    integer(),
    gleam@set:set(integer()),
    list(integer())
) -> {list(integer()), gleam@set:set(integer())}.
second_dfs(Transposed, Node, Visited, Component) ->
    case gleam@set:contains(Visited, Node) of
        true ->
            {Component, Visited};

        false ->
            New_visited = gleam@set:insert(Visited, Node),
            New_component = [Node | Component],
            Successors = yog@model:successor_ids(Transposed, Node),
            gleam@list:fold(
                Successors,
                {New_component, New_visited},
                fun(Acc, Succ) ->
                    {Comp, Vis} = Acc,
                    second_dfs(Transposed, Succ, Vis, Comp)
                end
            )
    end.

-file("src/yog/connectivity.gleam", 356).
?DOC(
    " Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.\n"
    "\n"
    " Returns a list of components, where each component is a list of NodeIds.\n"
    " Kosaraju's algorithm uses two DFS passes and graph transposition:\n"
    "\n"
    " 1. First DFS: Compute finishing times (nodes added to stack when DFS completes)\n"
    " 2. Transpose the graph (reverse all edges) - O(1) operation!\n"
    " 3. Second DFS: Process nodes in reverse finishing time order on transposed graph\n"
    "\n"
    " **Time Complexity:** O(V + E) where V is vertices and E is edges\n"
    " **Space Complexity:** O(V) for the visited set and finish stack\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Directed)\n"
    "   |> model.add_node(1, \"A\")\n"
    "   |> model.add_node(2, \"B\")\n"
    "   |> model.add_node(3, \"C\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 1)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 1)\n"
    "   |> model.add_edge(from: 3, to: 1, with: 1)\n"
    "\n"
    " let sccs = connectivity.kosaraju(graph)\n"
    " // => [[1, 2, 3]]  // All nodes form one SCC (cycle)\n"
    " ```\n"
    "\n"
    " ## Comparison with Tarjan's Algorithm\n"
    "\n"
    " - **Kosaraju:** Two DFS passes, requires graph transposition, simpler to understand\n"
    " - **Tarjan:** Single DFS pass, no transposition needed, uses low-link values\n"
    "\n"
    " Both have the same O(V + E) time complexity, but Kosaraju may be preferred when:\n"
    " - The graph is already stored in a format supporting fast transposition\n"
    " - Simplicity and clarity are prioritized over single-pass execution\n"
).
-spec kosaraju(yog@model:graph(any(), any())) -> list(list(integer())).
kosaraju(Graph) ->
    Nodes = yog@model:all_nodes(Graph),
    {Finish_stack, _} = gleam@list:fold(
        Nodes,
        {[], gleam@set:new()},
        fun(Acc, Node) ->
            {Stack, Visited} = Acc,
            first_dfs(Graph, Node, Visited, Stack)
        end
    ),
    Transposed = yog@transform:transpose(Graph),
    {Components@1, _} = gleam@list:fold(
        Finish_stack,
        {[], gleam@set:new()},
        fun(Acc@1, Node@1) ->
            {Components, Visited@1} = Acc@1,
            case gleam@set:contains(Visited@1, Node@1) of
                true ->
                    Acc@1;

                false ->
                    {Component, New_visited} = second_dfs(
                        Transposed,
                        Node@1,
                        Visited@1,
                        []
                    ),
                    {[Component | Components], New_visited}
            end
        end
    ),
    Components@1.