yog

-module(yog@transform).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/transform.gleam").
-export([transpose/1, map_nodes/2, map_edges/2, filter_nodes/2, filter_edges/2, complement/2, merge/2, subgraph/2, contract/4, to_directed/1, to_undirected/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(
    " Graph transformations and mappings - functor operations on graphs.\n"
    "\n"
    " This module provides operations that transform graphs while preserving their structure.\n"
    " These are useful for adapting graph data types, creating derived graphs, and\n"
    " preparing graphs for specific algorithms.\n"
    "\n"
    " ## Available Transformations\n"
    "\n"
    " | Transformation | Function | Complexity | Use Case |\n"
    " |----------------|----------|------------|----------|\n"
    " | Transpose | `transpose/1` | O(1) | Reverse edge directions |\n"
    " | Map Nodes | `map_nodes/2` | O(V) | Transform node data |\n"
    " | Map Edges | `map_edges/2` | O(E) | Transform edge weights |\n"
    " | Filter Nodes | `filter_nodes/2` | O(V) | Subgraph extraction |\n"
    " | Filter Edges | `filter_edges/2` | O(E) | Remove unwanted edges |\n"
    "\n"
    " ## The O(1) Transpose Operation\n"
    "\n"
    " Due to yog's dual-map representation (storing both outgoing and incoming edges),\n"
    " transposing a graph is a single pointer swap - dramatically faster than O(E)\n"
    " implementations in traditional adjacency list libraries.\n"
    "\n"
    " ## Functor Laws\n"
    "\n"
    " The mapping operations satisfy functor laws:\n"
    " - Identity: `map_nodes(g, fn(x) { x }) == g`\n"
    " - Composition: `map_nodes(map_nodes(g, f), h) == map_nodes(g, fn(x) { h(f(x)) })`\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Kosaraju's Algorithm**: Requires transposed graph for SCC finding\n"
    " - **Type Conversion**: Changing node/edge data types for algorithm requirements\n"
    " - **Subgraph Extraction**: Working with portions of large graphs\n"
    " - **Weight Normalization**: Preprocessing edge weights\n"
).

-file("src/yog/transform.gleam", 69).
?DOC(
    " Reverses the direction of every edge in the graph (graph transpose).\n"
    "\n"
    " Due to the dual-map representation (storing both out_edges and in_edges),\n"
    " this is an **O(1) operation** - just a pointer swap! This is dramatically\n"
    " faster than most graph libraries where transpose is O(E).\n"
    "\n"
    " **Time Complexity:** O(1)\n"
    "\n"
    " **Property:** `transpose(transpose(G)) = G`\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Directed)\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 20)\n"
    "\n"
    " let reversed = transform.transpose(graph)\n"
    " // Now has edges: 2->1 and 3->2\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Computing strongly connected components (Kosaraju's algorithm)\n"
    " - Finding all nodes that can reach a target node\n"
    " - Reversing dependencies in a DAG\n"
).
-spec transpose(yog@model:graph(KRA, KRB)) -> yog@model:graph(KRA, KRB).
transpose(Graph) ->
    {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        erlang:element(5, Graph),
        erlang:element(4, Graph)}.

-file("src/yog/transform.gleam", 107).
?DOC(
    " Transforms node data using a function, preserving graph structure.\n"
    "\n"
    " This is a functor operation - it applies a function to every node's data\n"
    " while keeping all edges and the graph structure unchanged.\n"
    "\n"
    " **Time Complexity:** O(V) where V is the number of nodes\n"
    "\n"
    " **Functor Law:** `map_nodes(map_nodes(g, f), h) = map_nodes(g, fn(x) { h(f(x)) })`\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Directed)\n"
    "   |> model.add_node(1, \"alice\")\n"
    "   |> model.add_node(2, \"bob\")\n"
    "\n"
    " let uppercased = transform.map_nodes(graph, string.uppercase)\n"
    " // Nodes now contain \"ALICE\" and \"BOB\"\n"
    " ```\n"
    "\n"
    " ## Type Changes\n"
    "\n"
    " Can change the node data type:\n"
    "\n"
    " ```gleam\n"
    " // Convert string node data to integers\n"
    " transform.map_nodes(graph, fn(s) {\n"
    "   case int.parse(s) {\n"
    "     Ok(n) -> n\n"
    "     Error(_) -> 0\n"
    "   }\n"
    " })\n"
    " ```\n"
).
-spec map_nodes(yog@model:graph(KRG, KRH), fun((KRG) -> KRK)) -> yog@model:graph(KRK, KRH).
map_nodes(Graph, Fun) ->
    New_nodes = gleam@dict:map_values(
        erlang:element(3, Graph),
        fun(_, Data) -> Fun(Data) end
    ),
    {graph,
        erlang:element(2, Graph),
        New_nodes,
        erlang:element(4, Graph),
        erlang:element(5, Graph)}.

-file("src/yog/transform.gleam", 151).
?DOC(
    " Transforms edge weights using a function, preserving graph structure.\n"
    "\n"
    " This is a functor operation - it applies a function to every edge's weight/data\n"
    " while keeping all nodes and the graph topology unchanged.\n"
    "\n"
    " **Time Complexity:** O(E) where E is the number of edges\n"
    "\n"
    " **Functor Law:** `map_edges(map_edges(g, f), h) = map_edges(g, fn(x) { h(f(x)) })`\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Directed)\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 20)\n"
    "\n"
    " // Double all weights\n"
    " let doubled = transform.map_edges(graph, fn(w) { w * 2 })\n"
    " // Edges now have weights 20 and 40\n"
    " ```\n"
    "\n"
    " ## Type Changes\n"
    "\n"
    " Can change the edge weight type:\n"
    "\n"
    " ```gleam\n"
    " // Convert integer weights to floats\n"
    " transform.map_edges(graph, int.to_float)\n"
    "\n"
    " // Convert weights to labels\n"
    " transform.map_edges(graph, fn(w) {\n"
    "   case w < 10 {\n"
    "     True -> \"short\"\n"
    "     False -> \"long\"\n"
    "   }\n"
    " })\n"
    " ```\n"
).
-spec map_edges(yog@model:graph(KRN, KRO), fun((KRO) -> KRR)) -> yog@model:graph(KRN, KRR).
map_edges(Graph, Fun) ->
    Transform_inner = fun(_capture) ->
        gleam@dict:map_values(_capture, fun(_, Weight) -> Fun(Weight) end)
    end,
    Transform_outer = fun(_capture@1) ->
        gleam@dict:map_values(
            _capture@1,
            fun(_, Inner_map) -> Transform_inner(Inner_map) end
        )
    end,
    {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        Transform_outer(erlang:element(4, Graph)),
        Transform_outer(erlang:element(5, Graph))}.

-file("src/yog/transform.gleam", 196).
?DOC(
    " Filters nodes by a predicate, automatically pruning connected edges.\n"
    "\n"
    " Returns a new graph containing only nodes whose data satisfies the predicate.\n"
    " All edges connected to removed nodes (both incoming and outgoing) are\n"
    " automatically removed to maintain graph consistency.\n"
    "\n"
    " **Time Complexity:** O(V + E) where V is nodes and E is edges\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Directed)\n"
    "   |> model.add_node(1, \"apple\")\n"
    "   |> model.add_node(2, \"banana\")\n"
    "   |> model.add_node(3, \"apricot\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 1)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 2)\n"
    "\n"
    " // Keep only nodes starting with 'a'\n"
    " let filtered = transform.filter_nodes(graph, fn(s) {\n"
    "   string.starts_with(s, \"a\")\n"
    " })\n"
    " // Result has nodes 1 and 3, edge 1->2 is removed (node 2 gone)\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Extract subgraphs based on node properties\n"
    " - Remove inactive/disabled nodes from a network\n"
    " - Filter by node importance/centrality\n"
).
-spec filter_nodes(yog@model:graph(KRU, KRV), fun((KRU) -> boolean())) -> yog@model:graph(KRU, KRV).
filter_nodes(Graph, Predicate) ->
    Kept_nodes = gleam@dict:filter(
        erlang:element(3, Graph),
        fun(_, Data) -> Predicate(Data) end
    ),
    Kept_ids = gleam@set:from_list(maps:keys(Kept_nodes)),
    Prune_edges = fun(Outer_map) -> _pipe = Outer_map,
        _pipe@1 = gleam@dict:filter(
            _pipe,
            fun(Src, _) -> gleam@set:contains(Kept_ids, Src) end
        ),
        gleam@dict:map_values(
            _pipe@1,
            fun(_, Inner_map) ->
                gleam@dict:filter(
                    Inner_map,
                    fun(Dst, _) -> gleam@set:contains(Kept_ids, Dst) end
                )
            end
        ) end,
    {graph,
        erlang:element(2, Graph),
        Kept_nodes,
        Prune_edges(erlang:element(4, Graph)),
        Prune_edges(erlang:element(5, Graph))}.

-file("src/yog/transform.gleam", 248).
?DOC(
    " Filters edges by a predicate, preserving all nodes.\n"
    "\n"
    " Returns a new graph with the same nodes but only the edges where the\n"
    " predicate returns `True`. The predicate receives `(src, dst, weight)`.\n"
    "\n"
    " **Time Complexity:** O(E) where E is the number of edges\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: 5)\n"
    "   |> model.add_edge(from: 1, to: 3, with: 15)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 3)\n"
    "\n"
    " // Keep only edges with weight >= 10\n"
    " let heavy = transform.filter_edges(graph, fn(_src, _dst, w) { w >= 10 })\n"
    " // Result: edges [1->3 (15)], edges 1->2 and 2->3 removed\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Pruning low-weight edges in weighted networks\n"
    " - Removing self-loops: `filter_edges(g, fn(s, d, _) { s != d })`\n"
    " - Threshold-based graph sparsification\n"
).
-spec filter_edges(
    yog@model:graph(KSA, KSB),
    fun((integer(), integer(), KSB) -> boolean())
) -> yog@model:graph(KSA, KSB).
filter_edges(Graph, Predicate) ->
    Filter_outer = fun(Outer_map) -> _pipe = Outer_map,
        _pipe@1 = gleam@dict:map_values(
            _pipe,
            fun(Src, Inner_map) ->
                gleam@dict:filter(
                    Inner_map,
                    fun(Dst, Weight) -> Predicate(Src, Dst, Weight) end
                )
            end
        ),
        gleam@dict:filter(
            _pipe@1,
            fun(_, Inner_map@1) -> maps:size(Inner_map@1) > 0 end
        ) end,
    {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        Filter_outer(erlang:element(4, Graph)),
        Filter_outer(erlang:element(5, Graph))}.

-file("src/yog/transform.gleam", 297).
?DOC(
    " Creates the complement of a graph.\n"
    "\n"
    " The complement contains the same nodes but connects all pairs of nodes\n"
    " that are **not** connected in the original graph, and removes all edges\n"
    " that **are** present. Each new edge gets the supplied `default_weight`.\n"
    "\n"
    " Self-loops are never added in the complement.\n"
    "\n"
    " **Time Complexity:** O(V² + E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Undirected)\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"
    "\n"
    " let comp = transform.complement(graph, default_weight: 1)\n"
    " // Original: 1-2 connected, 1-3 and 2-3 not\n"
    " // Complement: 1-3 and 2-3 connected, 1-2 not\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Finding independent sets (cliques in the complement)\n"
    " - Graph coloring via complement analysis\n"
    " - Testing graph density (sparse ↔ dense complement)\n"
).
-spec complement(yog@model:graph(KSG, KSH), KSH) -> yog@model:graph(KSG, KSH).
complement(Graph, Default_weight) ->
    Node_ids = maps:keys(erlang:element(3, Graph)),
    Init_graph = {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        maps:new(),
        maps:new()},
    _pipe = Node_ids,
    gleam@list:fold(
        _pipe,
        Init_graph,
        fun(G, Src) ->
            gleam@list:fold(Node_ids, G, fun(Acc, Dst) -> case Src =:= Dst of
                        true ->
                            Acc;

                        false ->
                            Has_edge = case gleam_stdlib:map_get(
                                erlang:element(4, Graph),
                                Src
                            ) of
                                {ok, Inner} ->
                                    gleam@dict:has_key(Inner, Dst);

                                {error, _} ->
                                    false
                            end,
                            case Has_edge of
                                true ->
                                    Acc;

                                false ->
                                    yog@model:add_edge(
                                        Acc,
                                        Src,
                                        Dst,
                                        Default_weight
                                    )
                            end
                    end end)
        end
    ).

-file("src/yog/transform.gleam", 365).
?DOC(
    " Combines two graphs, with the second graph's data taking precedence on conflicts.\n"
    "\n"
    " Merges nodes, out_edges, and in_edges from both graphs. When a node exists in\n"
    " both graphs, the node data from `other` overwrites `base`. When the same edge\n"
    " exists in both graphs, the edge weight from `other` overwrites `base`.\n"
    "\n"
    " Importantly, edges from different nodes are combined - if `base` has edges\n"
    " 1->2 and 1->3, and `other` has edges 1->4 and 1->5, the result will have\n"
    " all four edges from node 1.\n"
    "\n"
    " The resulting graph uses the `kind` (Directed/Undirected) from the base graph.\n"
    "\n"
    " **Time Complexity:** O(V + E) for both graphs combined\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let base =\n"
    "   model.new(Directed)\n"
    "   |> model.add_node(1, \"Original\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.add_edge(from: 1, to: 3, with: 15)\n"
    "\n"
    " let other =\n"
    "   model.new(Directed)\n"
    "   |> model.add_node(1, \"Updated\")\n"
    "   |> model.add_edge(from: 1, to: 4, with: 20)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 25)\n"
    "\n"
    " let merged = transform.merge(base, other)\n"
    " // Node 1 has \"Updated\" (from other)\n"
    " // Node 1 has edges to: 2, 3, and 4 (all edges combined)\n"
    " // Node 2 has edge to: 3\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Combining disjoint subgraphs\n"
    " - Applying updates/patches to a graph\n"
    " - Building graphs incrementally from multiple sources\n"
).
-spec merge(yog@model:graph(KSM, KSN), yog@model:graph(KSM, KSN)) -> yog@model:graph(KSM, KSN).
merge(Base, Other) ->
    Merge_inner = fun(M1, M2) -> maps:merge(M1, M2) end,
    Merge_outer = fun(Outer1, Outer2) ->
        gleam@dict:combine(Outer1, Outer2, Merge_inner)
    end,
    {graph,
        erlang:element(2, Base),
        maps:merge(erlang:element(3, Base), erlang:element(3, Other)),
        Merge_outer(erlang:element(4, Base), erlang:element(4, Other)),
        Merge_outer(erlang:element(5, Base), erlang:element(5, Other))}.

-file("src/yog/transform.gleam", 419).
?DOC(
    " Extracts a subgraph containing only the specified nodes and their connecting edges.\n"
    "\n"
    " Returns a new graph with only the nodes whose IDs are in the provided list,\n"
    " along with any edges that connect nodes within this subset. Nodes not in the\n"
    " list are removed, and all edges touching removed nodes are pruned.\n"
    "\n"
    " **Time Complexity:** O(V + E) where V is nodes and E is edges\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_node(4, \"D\")\n"
    "   |> model.add_edge(from: 1, to: 2, with: 10)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 20)\n"
    "   |> model.add_edge(from: 3, to: 4, with: 30)\n"
    "\n"
    " // Extract only nodes 2 and 3\n"
    " let sub = transform.subgraph(graph, keeping: [2, 3])\n"
    " // Result has nodes 2, 3 and edge 2->3\n"
    " // Edges 1->2 and 3->4 are removed (endpoints outside subgraph)\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Extracting connected components found by algorithms\n"
    " - Analyzing k-hop neighborhoods around specific nodes\n"
    " - Working with strongly connected components (extract each SCC)\n"
    " - Removing nodes found by some criteria (keep the inverse set)\n"
    " - Visualizing specific portions of large graphs\n"
    "\n"
    " ## Comparison with `filter_nodes()`\n"
    "\n"
    " - `filter_nodes()` - Filters by predicate on node data (e.g., \"keep active users\")\n"
    " - `subgraph()` - Filters by explicit node IDs (e.g., \"keep nodes [1, 5, 7]\")\n"
).
-spec subgraph(yog@model:graph(KSU, KSV), list(integer())) -> yog@model:graph(KSU, KSV).
subgraph(Graph, Ids) ->
    Id_set = gleam@set:from_list(Ids),
    Nodes = gleam@dict:filter(
        erlang:element(3, Graph),
        fun(Id, _) -> gleam@set:contains(Id_set, Id) end
    ),
    Prune = fun(Outer) ->
        _pipe = gleam@dict:filter(
            Outer,
            fun(Src, _) -> gleam@set:contains(Id_set, Src) end
        ),
        gleam@dict:map_values(
            _pipe,
            fun(_, Inner) ->
                gleam@dict:filter(
                    Inner,
                    fun(Dst, _) -> gleam@set:contains(Id_set, Dst) end
                )
            end
        )
    end,
    {graph,
        erlang:element(2, Graph),
        Nodes,
        Prune(erlang:element(4, Graph)),
        Prune(erlang:element(5, Graph))}.

-file("src/yog/transform.gleam", 498).
?DOC(
    " Contracts an edge by merging node `b` into node `a`.\n"
    "\n"
    " Node `b` is removed from the graph, and all edges connected to `b` are\n"
    " redirected to `a`. If both `a` and `b` had edges to the same neighbor,\n"
    " their weights are combined using `with_combine`.\n"
    "\n"
    " Self-loops (edges from a node to itself) are removed during contraction.\n"
    "\n"
    " **Important for undirected graphs:** Since undirected edges are stored\n"
    " bidirectionally, each logical edge is processed twice during contraction,\n"
    " causing weights to be combined twice. For example, if edge weights represent\n"
    " capacities, this effectively doubles them. Consider dividing weights by 2\n"
    " or using a custom combine function if this behavior is undesired.\n"
    "\n"
    " **Time Complexity:** O(deg(a) + deg(b)) - proportional to the combined\n"
    " degree of both nodes.\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph =\n"
    "   model.new(Undirected)\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: 5)\n"
    "   |> model.add_edge(from: 2, to: 3, with: 10)\n"
    "\n"
    " let contracted = transform.contract(\n"
    "   in: graph,\n"
    "   merge: 1,\n"
    "   with: 2,\n"
    "   combine_weights: int.add,\n"
    " )\n"
    " // Result: nodes [1, 3], edge 1-3 with weight 10\n"
    " // Node 2 is merged into node 1\n"
    " ```\n"
    "\n"
    " ## Combining Weights\n"
    "\n"
    " When both `a` and `b` have edges to the same neighbor `c`:\n"
    "\n"
    " ```gleam\n"
    " // Before: a-[5]->c, b-[10]->c\n"
    " let contracted = transform.contract(\n"
    "   in: graph,\n"
    "   merge: a,\n"
    "   with: b,\n"
    "   combine_weights: int.add,\n"
    " )\n"
    " // After: a-[15]->c (5 + 10)\n"
    " ```\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - **Stoer-Wagner algorithm** for minimum cut\n"
    " - **Graph simplification** by merging strongly connected nodes\n"
    " - **Community detection** by contracting nodes in the same community\n"
    " - **Karger's algorithm** for minimum cut (randomized)\n"
).
-spec contract(
    yog@model:graph(KTB, KTC),
    integer(),
    integer(),
    fun((KTC, KTC) -> KTC)
) -> yog@model:graph(KTB, KTC).
contract(Graph, A, B, With_combine) ->
    B_out = begin
        _pipe = gleam_stdlib:map_get(erlang:element(4, Graph), B),
        gleam@result:unwrap(_pipe, maps:new())
    end,
    Graph@1 = gleam@dict:fold(
        B_out,
        Graph,
        fun(Acc_g, Neighbor, Weight) ->
            case (Neighbor =:= A) orelse (Neighbor =:= B) of
                true ->
                    Acc_g;

                false ->
                    yog@model:add_edge_with_combine(
                        Acc_g,
                        A,
                        Neighbor,
                        Weight,
                        With_combine
                    )
            end
        end
    ),
    Graph@2 = case erlang:element(2, Graph@1) of
        undirected ->
            Graph@1;

        directed ->
            B_in = begin
                _pipe@1 = gleam_stdlib:map_get(erlang:element(5, Graph@1), B),
                gleam@result:unwrap(_pipe@1, maps:new())
            end,
            gleam@dict:fold(
                B_in,
                Graph@1,
                fun(Acc_g@1, Neighbor@1, Weight@1) ->
                    case (Neighbor@1 =:= A) orelse (Neighbor@1 =:= B) of
                        true ->
                            Acc_g@1;

                        false ->
                            yog@model:add_edge_with_combine(
                                Acc_g@1,
                                Neighbor@1,
                                A,
                                Weight@1,
                                With_combine
                            )
                    end
                end
            )
    end,
    yog@model:remove_node(Graph@2, B).

-file("src/yog/transform.gleam", 560).
?DOC(
    " Converts an undirected graph to a directed graph.\n"
    "\n"
    " Since yog internally stores undirected edges as bidirectional directed edges,\n"
    " this is essentially free — it just changes the `kind` flag. The resulting\n"
    " directed graph has two directed edges (A→B and B→A) for each original\n"
    " undirected edge.\n"
    "\n"
    " If the graph is already directed, it is returned unchanged.\n"
    "\n"
    " **Time Complexity:** O(1)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let undirected =\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"
    "\n"
    " let directed = transform.to_directed(undirected)\n"
    " // Has edges: 1->2 and 2->1 (both with weight 10)\n"
    " ```\n"
).
-spec to_directed(yog@model:graph(KTH, KTI)) -> yog@model:graph(KTH, KTI).
to_directed(Graph) ->
    {graph,
        directed,
        erlang:element(3, Graph),
        erlang:element(4, Graph),
        erlang:element(5, Graph)}.

-file("src/yog/transform.gleam", 598).
?DOC(
    " Converts a directed graph to an undirected graph.\n"
    "\n"
    " For each directed edge A→B, ensures B→A also exists. If both A→B and B→A\n"
    " already exist with different weights, the `resolve` function decides which\n"
    " weight to keep.\n"
    "\n"
    " If the graph is already undirected, it is returned unchanged.\n"
    "\n"
    " **Time Complexity:** O(E) where E is the number of edges\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let directed =\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(from: 2, to: 1, with: 20)\n"
    "\n"
    " // When both directions exist, keep the smaller weight\n"
    " let undirected = transform.to_undirected(directed, resolve: int.min)\n"
    " // Edge 1-2 has weight 10 (min of 10 and 20)\n"
    " ```\n"
    "\n"
    " ```gleam\n"
    " // One-directional edges get mirrored automatically\n"
    " let directed =\n"
    "   model.new(Directed)\n"
    "   |> model.add_edge(from: 1, to: 2, with: 5)\n"
    "\n"
    " let undirected = transform.to_undirected(directed, resolve: int.min)\n"
    " // Edge exists in both directions with weight 5\n"
    " ```\n"
).
-spec to_undirected(yog@model:graph(KTN, KTO), fun((KTO, KTO) -> KTO)) -> yog@model:graph(KTN, KTO).
to_undirected(Graph, Resolve) ->
    case erlang:element(2, Graph) of
        undirected ->
            Graph;

        directed ->
            Symmetric_out = gleam@dict:fold(
                erlang:element(4, Graph),
                erlang:element(4, Graph),
                fun(Acc_outer, Src, Inner) ->
                    gleam@dict:fold(
                        Inner,
                        Acc_outer,
                        fun(Acc, Dst, Weight) ->
                            Dst_inner = case gleam_stdlib:map_get(Acc, Dst) of
                                {ok, M} ->
                                    M;

                                {error, _} ->
                                    maps:new()
                            end,
                            Updated_inner = case gleam_stdlib:map_get(
                                Dst_inner,
                                Src
                            ) of
                                {ok, Existing} ->
                                    gleam@dict:insert(
                                        Dst_inner,
                                        Src,
                                        Resolve(Existing, Weight)
                                    );

                                {error, _} ->
                                    gleam@dict:insert(Dst_inner, Src, Weight)
                            end,
                            gleam@dict:insert(Acc, Dst, Updated_inner)
                        end
                    )
                end
            ),
            {graph,
                undirected,
                erlang:element(3, Graph),
                Symmetric_out,
                Symmetric_out}
    end.