yog

-module(yog@community).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/community.gleam").
-export([communities_to_dict/1, community_sizes/1, largest_community/1, merge_communities/3]).
-export_type([communities/0, dendrogram/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(
    " Community detection and clustering algorithms.\n"
    "\n"
    " Provides types and utility functions for working with community structures\n"
    " in graphs. Community detection algorithms identify groups of nodes that\n"
    " are more densely connected internally than with the rest of the graph.\n"
    "\n"
    " ## Algorithms\n"
    "\n"
    " | Algorithm | Module | Best For |\n"
    " |-----------|--------|----------|\n"
    " | [Louvain](https://en.wikipedia.org/wiki/Louvain_method) | `yog/community/louvain` | Large graphs, modularity optimization |\n"
    " | [Leiden](https://en.wikipedia.org/wiki/Leiden_algorithm) | `yog/community/leiden` | Quality guarantee, well-connected communities |\n"
    " | [Label Propagation](https://en.wikipedia.org/wiki/Label_propagation_algorithm) | `yog/community/label_propagation` | Speed, near-linear time |\n"
    " | [Girvan-Newman](https://en.wikipedia.org/wiki/Girvan%E2%80%93Newman_algorithm) | `yog/community/girvan_newman` | Hierarchical structure, edge betweenness |\n"
    " | [Infomap](https://www.mapequation.org/) | `yog/community/infomap` | Information-theoretic, flow-based |\n"
    " | [Clique Percolation](https://en.wikipedia.org/wiki/Clique_percolation_method) | `yog/community/clique_percolation` | Overlapping communities |\n"
    " | [Walktrap](https://doi.org/10.1080/15427951.2007.10129237) | `yog/community/walktrap` | Random walk-based distances |\n"
    " | [Local Community](https://en.wikipedia.org/wiki/Community_structure#Local_communities) | `yog/community/local_community` | Massive graphs, seed expansion |\n"
    " | [Fluid Communities](https://arxiv.org/abs/1703.09307) | `yog/community/fluid_communities` | Exact `k` partitions, fast |\n"
    "\n"
    " ## Core Types\n"
    "\n"
    " - **`Communities`** - Community assignment mapping nodes to community IDs\n"
    " - **`Dendrogram`** - Hierarchical community structure with multiple levels\n"
    " - **`CommunityId`** - Integer identifier for a community\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " import yog\n"
    " import yog/community\n"
    " import yog/community/louvain\n"
    "\n"
    " let graph = // ... build your graph\n"
    "\n"
    " // Detect communities\n"
    " let communities = louvain.detect(graph)\n"
    " io.debug(communities.num_communities)  // => 4\n"
    "\n"
    " // Get nodes in each community\n"
    " let communities_dict = community.communities_to_dict(communities)\n"
    " // => dict.from_list([#(0, set.from_list([1, 2, 3])), #(1, set.from_list([4, 5]))])\n"
    "\n"
    " // Find largest community\n"
    " case community.largest_community(communities) {\n"
    "   Some(community_id) -> io.debug(community_id)\n"
    "   None -> io.println(\"No communities found\")\n"
    " }\n"
    " ```\n"
    "\n"
    " ## Choosing an Algorithm\n"
    "\n"
    " - **Louvain**: Fast and widely used, good for most cases\n"
    " - **Leiden**: Better quality than Louvain, guarantees well-connected communities\n"
    " - **Label Propagation**: Fastest option for very large graphs\n"
    " - **Girvan-Newman**: When you need hierarchical structure\n"
    " - **Infomap**: When flow/random walk structure matters\n"
    " - **Clique Percolation**: When nodes may belong to multiple communities\n"
    " - **Walktrap**: Good for capturing local structure via random walks\n"
    " - **Local Community**: When the graph is massive/infinite and you only care about the immediate community around specific seeds\n"
    " - **Fluid Communities**: Fast and allows finding exactly `k` communities\n"
).

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

-type dendrogram() :: {dendrogram,
        list(communities()),
        list({integer(), integer()})}.

-file("src/yog/community.gleam", 133).
?DOC(
    " Converts community assignments to a dictionary mapping community IDs to sets of node IDs.\n"
    "\n"
    " This is useful when you need to iterate over all nodes in each community\n"
    " rather than looking up the community for each node.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let communities = Communities(\n"
    "   assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1)]),\n"
    "   num_communities: 2\n"
    " )\n"
    "\n"
    " community.communities_to_dict(communities)\n"
    " // => dict.from_list([\n"
    " //      #(0, set.from_list([1, 2])),\n"
    " //      #(1, set.from_list([3]))\n"
    " //    ])\n"
    " ```\n"
).
-spec communities_to_dict(communities()) -> gleam@dict:dict(integer(), gleam@set:set(integer())).
communities_to_dict(Communities) ->
    gleam@dict:fold(
        erlang:element(2, Communities),
        maps:new(),
        fun(Acc, Node, Community) ->
            Current_set = begin
                _pipe = gleam_stdlib:map_get(Acc, Community),
                _pipe@1 = gleam@option:from_result(_pipe),
                gleam@option:unwrap(_pipe@1, gleam@set:new())
            end,
            gleam@dict:insert(
                Acc,
                Community,
                gleam@set:insert(Current_set, Node)
            )
        end
    ).

-file("src/yog/community.gleam", 186).
?DOC(
    " Returns a dictionary mapping community IDs to their sizes (number of nodes).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let communities = Communities(\n"
    "   assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1), #(4, 1), #(5, 1)]),\n"
    "   num_communities: 2\n"
    " )\n"
    "\n"
    " community.community_sizes(communities)\n"
    " // => dict.from_list([#(0, 2), #(1, 3)])\n"
    " ```\n"
).
-spec community_sizes(communities()) -> gleam@dict:dict(integer(), integer()).
community_sizes(Communities) ->
    gleam@dict:fold(
        erlang:element(2, Communities),
        maps:new(),
        fun(Acc, _, Community) ->
            Current_size = begin
                _pipe = gleam_stdlib:map_get(Acc, Community),
                _pipe@1 = gleam@option:from_result(_pipe),
                gleam@option:unwrap(_pipe@1, 0)
            end,
            gleam@dict:insert(Acc, Community, Current_size + 1)
        end
    ).

-file("src/yog/community.gleam", 164).
?DOC(
    " Returns the community ID with the largest number of nodes.\n"
    "\n"
    " Returns `None` if there are no communities (empty graph or no assignments).\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let communities = Communities(\n"
    "   assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 0), #(4, 1)]),\n"
    "   num_communities: 2\n"
    " )\n"
    "\n"
    " community.largest_community(communities)\n"
    " // => Some(0)  // Community 0 has 3 nodes vs 1 for community 1\n"
    " ```\n"
).
-spec largest_community(communities()) -> gleam@option:option(integer()).
largest_community(Communities) ->
    _pipe = community_sizes(Communities),
    _pipe@1 = maps:to_list(_pipe),
    _pipe@2 = gleam@list:sort(
        _pipe@1,
        fun(A, B) ->
            gleam@int:compare(erlang:element(2, B), erlang:element(2, A))
        end
    ),
    _pipe@3 = gleam@list:first(_pipe@2),
    _pipe@4 = gleam@option:from_result(_pipe@3),
    gleam@option:map(_pipe@4, fun(Pair) -> erlang:element(1, Pair) end).

-file("src/yog/community.gleam", 224).
?DOC(
    " Merges two communities into one.\n"
    "\n"
    " All nodes from the source community are reassigned to the target community.\n"
    " The source community ID is effectively removed.\n"
    "\n"
    " ## Parameters\n"
    "\n"
    " - `communities`: The current community partition\n"
    " - `source`: The community ID to merge from (will be removed)\n"
    " - `target`: The community ID to merge into (will be kept)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let communities = Communities(\n"
    "   assignments: dict.from_list([#(1, 0), #(2, 0), #(3, 1), #(4, 1)]),\n"
    "   num_communities: 2\n"
    " )\n"
    "\n"
    " // Merge community 1 into community 0\n"
    " let merged = community.merge_communities(communities, source: 1, target: 0)\n"
    " // merged.assignments => dict.from_list([#(1, 0), #(2, 0), #(3, 0), #(4, 0)])\n"
    " // merged.num_communities => 1\n"
    " ```\n"
).
-spec merge_communities(communities(), integer(), integer()) -> communities().
merge_communities(Communities, Source, Target) ->
    New_assignments = gleam@dict:fold(
        erlang:element(2, Communities),
        erlang:element(2, Communities),
        fun(Acc, Node, Community) -> case Community =:= Source of
                true ->
                    gleam@dict:insert(Acc, Node, Target);

                false ->
                    Acc
            end end
    ),
    Num_communities = case Source =:= Target of
        true ->
            erlang:element(3, Communities);

        false ->
            erlang:element(3, Communities) - 1
    end,
    {communities, New_assignments, Num_communities}.