yog

-module(yog@model).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/model.gleam").
-export([new/1, add_node/3, successors/2, predecessors/2, neighbors/2, all_nodes/1, order/1, node_count/1, edge_count/1, successor_ids/2, add_edge/4, add_edge_ensured/5, remove_node/2, remove_edge/3, add_edge_with_combine/5]).
-export_type([graph_type/0, graph/2]).

-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(
    " Core graph data structures and basic operations for the yog library.\n"
    "\n"
    " This module defines the fundamental `Graph` type and provides all basic operations\n"
    " for creating and manipulating graphs. The graph uses an adjacency list representation\n"
    " with dual indexing (both outgoing and incoming edges) for efficient traversal in both\n"
    " directions.\n"
    "\n"
    " ## Graph Types\n"
    "\n"
    " - **Directed Graph**: Edges have a direction (one-way relationships)\n"
    " - **Undirected Graph**: Edges are bidirectional (mutual relationships)\n"
    "\n"
    " ## Type Parameters\n"
    "\n"
    " - `node_data`: The type of data stored at each node (e.g., `String`, `City`, `Task`)\n"
    " - `edge_data`: The type of data stored on edges, typically weights (e.g., `Int`, `Float`)\n"
    "\n"
    " ## Quick Start\n"
    "\n"
    " ```gleam\n"
    " import yog/model\n"
    "\n"
    " let graph =\n"
    "   model.new(model.Undirected)\n"
    "   |> model.add_node(1, \"Alice\")\n"
    "   |> model.add_node(2, \"Bob\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)  // weight = 10\n"
    " ```\n"
    "\n"
    " ## Design Notes\n"
    "\n"
    " The dual-map representation enables O(1) edge existence checks and O(1) transpose\n"
    " operations, at the cost of increased memory usage and slightly more complex edge\n"
    " updates.\n"
).

-type graph_type() :: directed | undirected.

-type graph(KBI, KBJ) :: {graph,
        graph_type(),
        gleam@dict:dict(integer(), KBI),
        gleam@dict:dict(integer(), gleam@dict:dict(integer(), KBJ)),
        gleam@dict:dict(integer(), gleam@dict:dict(integer(), KBJ))}.

-file("src/yog/model.gleam", 76).
?DOC(
    " Creates a new empty graph of the specified type.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = model.new(Directed)\n"
    " ```\n"
).
-spec new(graph_type()) -> graph(any(), any()).
new(Graph_type) ->
    {graph, Graph_type, maps:new(), maps:new(), maps:new()}.

-file("src/yog/model.gleam", 95).
?DOC(
    " Adds a node to the graph with the given ID and data.\n"
    " If a node with this ID already exists, its data will be replaced.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " graph\n"
    " |> model.add_node(1, \"Node A\")\n"
    " |> model.add_node(2, \"Node B\")\n"
    " ```\n"
).
-spec add_node(graph(KBO, KBP), integer(), KBO) -> graph(KBO, KBP).
add_node(Graph, Id, Data) ->
    New_nodes = gleam@dict:insert(erlang:element(3, Graph), Id, Data),
    {graph,
        erlang:element(2, Graph),
        New_nodes,
        erlang:element(4, Graph),
        erlang:element(5, Graph)}.

-file("src/yog/model.gleam", 171).
?DOC(" Adds a node only if it doesn't already exist.\n").
-spec ensure_node(graph(KCG, KCH), integer(), KCG) -> graph(KCG, KCH).
ensure_node(Graph, Id, Data) ->
    case gleam@dict:has_key(erlang:element(3, Graph), Id) of
        true ->
            Graph;

        false ->
            add_node(Graph, Id, Data)
    end.

-file("src/yog/model.gleam", 179).
?DOC(" Gets nodes you can travel TO (Successors).\n").
-spec successors(graph(any(), KCN), integer()) -> list({integer(), KCN}).
successors(Graph, Id) ->
    _pipe = erlang:element(4, Graph),
    _pipe@1 = gleam_stdlib:map_get(_pipe, Id),
    _pipe@2 = gleam@result:map(_pipe@1, fun maps:to_list/1),
    gleam@result:unwrap(_pipe@2, []).

-file("src/yog/model.gleam", 187).
?DOC(" Gets nodes you came FROM (Predecessors).\n").
-spec predecessors(graph(any(), KCS), integer()) -> list({integer(), KCS}).
predecessors(Graph, Id) ->
    _pipe = erlang:element(5, Graph),
    _pipe@1 = gleam_stdlib:map_get(_pipe, Id),
    _pipe@2 = gleam@result:map(_pipe@1, fun maps:to_list/1),
    gleam@result:unwrap(_pipe@2, []).

-file("src/yog/model.gleam", 196).
?DOC(
    " Gets everyone connected to the node, regardless of direction.\n"
    " Useful for algorithms like finding \"connected connectivity.\"\n"
).
-spec neighbors(graph(any(), KCX), integer()) -> list({integer(), KCX}).
neighbors(Graph, Id) ->
    case erlang:element(2, Graph) of
        undirected ->
            successors(Graph, Id);

        directed ->
            Outgoing = successors(Graph, Id),
            Incoming = predecessors(Graph, Id),
            Out_ids = gleam@set:from_list(
                gleam@list:map(Outgoing, fun gleam@pair:first/1)
            ),
            gleam@list:fold(
                Incoming,
                Outgoing,
                fun(Acc, _use1) ->
                    {In_id, _} = Incoming@1 = _use1,
                    case gleam@set:contains(Out_ids, In_id) of
                        true ->
                            Acc;

                        false ->
                            [Incoming@1 | Acc]
                    end
                end
            )
    end.

-file("src/yog/model.gleam", 215).
?DOC(
    " Returns all node IDs in the graph.\n"
    " This includes all nodes, even isolated nodes with no edges.\n"
).
-spec all_nodes(graph(any(), any())) -> list(integer()).
all_nodes(Graph) ->
    maps:keys(erlang:element(3, Graph)).

-file("src/yog/model.gleam", 222).
?DOC(
    " Returns the number of nodes in the graph (graph order).\n"
    "\n"
    " **Time Complexity:** O(1)\n"
).
-spec order(graph(any(), any())) -> integer().
order(Graph) ->
    maps:size(erlang:element(3, Graph)).

-file("src/yog/model.gleam", 230).
?DOC(
    " Returns the number of nodes in the graph.\n"
    " Equivalent to `order(graph)`.\n"
    "\n"
    " **Time Complexity:** O(1)\n"
).
-spec node_count(graph(any(), any())) -> integer().
node_count(Graph) ->
    order(Graph).

-file("src/yog/model.gleam", 240).
?DOC(
    " Returns the number of edges in the graph.\n"
    "\n"
    " For undirected graphs, each edge is counted once (the pair {u, v}).\n"
    " For directed graphs, each directed edge (u -> v) is counted once.\n"
    "\n"
    " **Time Complexity:** O(V)\n"
).
-spec edge_count(graph(any(), any())) -> integer().
edge_count(Graph) ->
    _pipe = gleam@dict:fold(
        erlang:element(4, Graph),
        0,
        fun(Acc, _, Targets) -> Acc + maps:size(Targets) end
    ),
    (fun(Count) -> case erlang:element(2, Graph) of
            directed ->
                Count;

            undirected ->
                Count div 2
        end end)(_pipe).

-file("src/yog/model.gleam", 254).
?DOC(
    " Returns just the NodeIds of successors (without edge weights).\n"
    " Convenient for traversal algorithms that only need the IDs.\n"
).
-spec successor_ids(graph(any(), any()), integer()) -> list(integer()).
successor_ids(Graph, Id) ->
    _pipe = successors(Graph, Id),
    gleam@list:map(_pipe, fun(Edge) -> erlang:element(1, Edge) end).

-file("src/yog/model.gleam", 259).
-spec do_add_directed_edge(graph(KDX, KDY), integer(), integer(), KDY) -> graph(KDX, KDY).
do_add_directed_edge(Graph, Src, Dst, Weight) ->
    Out_update_fn = fun(Maybe_inner_map) -> case Maybe_inner_map of
            {some, M} ->
                gleam@dict:insert(M, Dst, Weight);

            none ->
                maps:from_list([{Dst, Weight}])
        end end,
    In_update_fn = fun(Maybe_inner_map@1) -> case Maybe_inner_map@1 of
            {some, M@1} ->
                gleam@dict:insert(M@1, Src, Weight);

            none ->
                maps:from_list([{Src, Weight}])
        end end,
    New_out = gleam@dict:upsert(erlang:element(4, Graph), Src, Out_update_fn),
    New_in = gleam@dict:upsert(erlang:element(5, Graph), Dst, In_update_fn),
    {graph, erlang:element(2, Graph), erlang:element(3, Graph), New_out, New_in}.

-file("src/yog/model.gleam", 118).
?DOC(
    " Adds an edge to the graph with the given weight.\n"
    "\n"
    " For directed graphs, adds a single edge from `src` to `dst`.\n"
    " For undirected graphs, adds edges in both directions.\n"
    "\n"
    " > **Note:** If `src` or `dst` have not been added via `add_node`,\n"
    " > the edge will still be created in the edge dictionaries but the\n"
    " > nodes will be missing from `graph.nodes`. This creates \"ghost nodes\"\n"
    " > that are traversable but invisible to functions that iterate over\n"
    " > nodes (e.g. `order`, `filter_nodes`). Use `add_edge_ensured` to\n"
    " > auto-create missing endpoints with a default value.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " graph\n"
    " |> model.add_edge(from: 1, to: 2, with: 10)\n"
    " ```\n"
).
-spec add_edge(graph(KBU, KBV), integer(), integer(), KBV) -> graph(KBU, KBV).
add_edge(Graph, Src, Dst, Weight) ->
    Graph@1 = do_add_directed_edge(Graph, Src, Dst, Weight),
    case erlang:element(2, Graph@1) of
        directed ->
            Graph@1;

        undirected ->
            do_add_directed_edge(Graph@1, Dst, Src, Weight)
    end.

-file("src/yog/model.gleam", 158).
?DOC(
    " Like `add_edge`, but ensures both endpoint nodes exist first.\n"
    "\n"
    " If `src` or `dst` is not already in the graph, it is created with\n"
    " the supplied `default` node data before the edge is added. Nodes\n"
    " that already exist are left unchanged.\n"
    " \n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Nodes 1 and 2 are created automatically with data \"unknown\"\n"
    " model.new(model.Directed)\n"
    " |> model.add_edge_ensured(from: 1, to: 2, with: 10, default: \"unknown\")\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " // Existing nodes keep their data; only missing ones get the default\n"
    " model.new(model.Directed)\n"
    " |> model.add_node(1, \"Alice\")\n"
    " |> model.add_edge_ensured(from: 1, to: 2, with: 5, default: \"anon\")\n"
    " // Node 1 is still \"Alice\", node 2 is \"anon\"\n"
    " ```\n"
    " ## Future Improvements\n"
    "\n"
    " A future version may support separate defaults for each endpoint\n"
    " (`default_from` and `default_to`). If you need this feature, please\n"
    " [open an issue](https://github.com/code-shoily/yog/issues).\n"
).
-spec add_edge_ensured(graph(KCA, KCB), integer(), integer(), KCB, KCA) -> graph(KCA, KCB).
add_edge_ensured(Graph, Src, Dst, Weight, Default) ->
    Graph@1 = ensure_node(Graph, Src, Default),
    Graph@2 = ensure_node(Graph@1, Dst, Default),
    add_edge(Graph@2, Src, Dst, Weight).

-file("src/yog/model.gleam", 304).
?DOC(
    " Removes a node and all its connected edges (incoming and outgoing).\n"
    "\n"
    " **Time Complexity:** O(deg(v)) - proportional to the number of edges\n"
    " connected to the node, not the whole graph.\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: 10)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 20)\n"
    "\n"
    " let graph = model.remove_node(graph, 2)\n"
    " // Node 2 is removed, along with edges 1->2 and 2->3\n"
    " ```\n"
).
-spec remove_node(graph(KED, KEE), integer()) -> graph(KED, KEE).
remove_node(Graph, Id) ->
    Targets = successors(Graph, Id),
    Sources = predecessors(Graph, Id),
    New_nodes = gleam@dict:delete(erlang:element(3, Graph), Id),
    New_out = gleam@dict:delete(erlang:element(4, Graph), Id),
    New_in_cleaned = begin
        gleam@list:fold(
            Targets,
            erlang:element(5, Graph),
            fun(Acc_in, _use1) ->
                {Target_id, _} = _use1,
                yog@internal@utils:dict_update_inner(
                    Acc_in,
                    Target_id,
                    Id,
                    fun gleam@dict:delete/2
                )
            end
        )
    end,
    New_in = gleam@dict:delete(New_in_cleaned, Id),
    New_out_cleaned = begin
        gleam@list:fold(
            Sources,
            New_out,
            fun(Acc_out, _use1@1) ->
                {Source_id, _} = _use1@1,
                yog@internal@utils:dict_update_inner(
                    Acc_out,
                    Source_id,
                    Id,
                    fun gleam@dict:delete/2
                )
            end
        )
    end,
    {graph, erlang:element(2, Graph), New_nodes, New_out_cleaned, New_in}.

-file("src/yog/model.gleam", 369).
-spec do_remove_directed_edge(graph(KEP, KEQ), integer(), integer()) -> graph(KEP, KEQ).
do_remove_directed_edge(Graph, Src, Dst) ->
    New_out = case gleam_stdlib:map_get(erlang:element(4, Graph), Src) of
        {ok, Targets} ->
            gleam@dict:insert(
                erlang:element(4, Graph),
                Src,
                gleam@dict:delete(Targets, Dst)
            );

        {error, _} ->
            erlang:element(4, Graph)
    end,
    New_in = case gleam_stdlib:map_get(erlang:element(5, Graph), Dst) of
        {ok, Sources} ->
            gleam@dict:insert(
                erlang:element(5, Graph),
                Dst,
                gleam@dict:delete(Sources, Src)
            );

        {error, _} ->
            erlang:element(5, Graph)
    end,
    {graph, erlang:element(2, Graph), erlang:element(3, Graph), New_out, New_in}.

-file("src/yog/model.gleam", 356).
?DOC(
    " Removes a directed edge from `src` to `dst`.\n"
    "\n"
    " For **directed graphs**, this removes the single directed edge from `src` to `dst`.\n"
    " For **undirected graphs**, this removes the edges in both directions\n"
    " (from `src` to `dst` and from `dst` to `src`).\n"
    "\n"
    " **Time Complexity:** O(1)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Directed graph - removes single directed edge\n"
    " let graph =\n"
    "   model.new(Directed)\n"
    "   |> model.add_node(1, \"A\")\n"
    "   |> model.add_node(2, \"B\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.remove_edge(1, 2)\n"
    " // Edge 1->2 is removed\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " // Undirected graph - removes both directions\n"
    " let graph =\n"
    "   model.new(Undirected)\n"
    "   |> model.add_node(1, \"A\")\n"
    "   |> model.add_node(2, \"B\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.remove_edge(1, 2)\n"
    " // Edge between 1 and 2 is fully removed\n"
    " ```\n"
).
-spec remove_edge(graph(KEJ, KEK), integer(), integer()) -> graph(KEJ, KEK).
remove_edge(Graph, Src, Dst) ->
    Graph@1 = do_remove_directed_edge(Graph, Src, Dst),
    case erlang:element(2, Graph@1) of
        directed ->
            Graph@1;

        undirected ->
            do_remove_directed_edge(Graph@1, Dst, Src)
    end.

-file("src/yog/model.gleam", 425).
-spec do_add_directed_combine(
    graph(KFB, KFC),
    integer(),
    integer(),
    KFC,
    fun((KFC, KFC) -> KFC)
) -> graph(KFB, KFC).
do_add_directed_combine(Graph, Src, Dst, Weight, With_combine) ->
    Update_fn = fun(Maybe_inner_map) -> case Maybe_inner_map of
            {some, M} ->
                New_weight = case gleam_stdlib:map_get(M, Dst) of
                    {ok, Existing} ->
                        With_combine(Existing, Weight);

                    {error, _} ->
                        Weight
                end,
                gleam@dict:insert(M, Dst, New_weight);

            none ->
                maps:from_list([{Dst, Weight}])
        end end,
    New_out = gleam@dict:upsert(erlang:element(4, Graph), Src, Update_fn),
    New_in = gleam@dict:upsert(
        erlang:element(5, Graph),
        Dst,
        fun(Maybe_m) -> case Maybe_m of
                {some, M@1} ->
                    New_weight@1 = case gleam_stdlib:map_get(M@1, Src) of
                        {ok, Existing@1} ->
                            With_combine(Existing@1, Weight);

                        {error, _} ->
                            Weight
                    end,
                    gleam@dict:insert(M@1, Src, New_weight@1);

                none ->
                    maps:from_list([{Src, Weight}])
            end end
    ),
    {graph, erlang:element(2, Graph), erlang:element(3, Graph), New_out, New_in}.

-file("src/yog/model.gleam", 410).
?DOC(
    " Adds an edge, but if an edge already exists between `src` and `dst`,\n"
    " it combines the new weight with the existing one using `with_combine`.\n"
    "\n"
    " The combine function receives `(existing_weight, new_weight)` and should\n"
    " return the combined weight.\n"
    "\n"
    " **Time Complexity:** O(1)\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_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.add_edge_with_combine(from: 1, to: 2, with: 5, using: int.add)\n"
    " // Edge 1->2 now has weight 15 (10 + 5)\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Edge contraction** in graph algorithms (Stoer-Wagner min-cut)\n"
    " - **Multi-graph support** (adding parallel edges with combined weights)\n"
    " - **Incremental graph building** (accumulating weights from multiple sources)\n"
).
-spec add_edge_with_combine(
    graph(KEV, KEW),
    integer(),
    integer(),
    KEW,
    fun((KEW, KEW) -> KEW)
) -> graph(KEV, KEW).
add_edge_with_combine(Graph, Src, Dst, Weight, With_combine) ->
    Graph@1 = do_add_directed_combine(Graph, Src, Dst, Weight, With_combine),
    case erlang:element(2, Graph@1) of
        directed ->
            Graph@1;

        undirected ->
            do_add_directed_combine(Graph@1, Dst, Src, Weight, With_combine)
    end.