-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, to_directed/1, to_undirected/2, map_nodes/2, update_node/4, filter_nodes/2, map_edges/2, filter_edges/2, complement/2, merge/2, subgraph/2, contract/4, transitive_closure/2, transitive_reduction/2, update_edge/5]).

-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"
    " | Transitive Closure | `transitive_closure/2` | O(V × E) | Add all reachable edges |\n"
    " | Transitive Reduction | `transitive_reduction/2` | O(V × E) | Remove redundant 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", 76).
?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** that makes transposing large graphs extremely fast.\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(GHT, GHU)) -> yog@model:graph(GHT, GHU).
transpose(Graph) ->
    {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        erlang:element(5, Graph),
        erlang:element(4, Graph)}.

-file("src/yog/transform.gleam", 103).
?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(GHZ, GIA)) -> yog@model:graph(GHZ, GIA).
to_directed(Graph) ->
    {graph,
        directed,
        erlang:element(3, Graph),
        erlang:element(4, Graph),
        erlang:element(5, Graph)}.

-file("src/yog/transform.gleam", 141).
?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(GIF, GIG), fun((GIG, GIG) -> GIG)) -> yog@model:graph(GIF, GIG).
to_undirected(Graph, Resolve) ->
    case erlang:element(2, Graph) of
        undirected ->
            Graph;

        directed ->
            Symmetric_out = begin
                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
                )
            end,
            {graph,
                undirected,
                erlang:element(3, Graph),
                Symmetric_out,
                Symmetric_out}
    end.

-file("src/yog/transform.gleam", 205).
?DOC(
    " Transforms node data using a function, preserving graph structure.\n"
    "\n"
    " This is a functor-like operation that applies a function to every node's data\n"
    " while keeping all edges and the graph structure unchanged. The transformation\n"
    " function receives both the `NodeId` and the node data.\n"
    "\n"
    " **Time Complexity:** O(V) where V is the number of nodes\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, fn(_id, name) { string.uppercase(name) })\n"
    " // Nodes now contain \"ALICE\" and \"BOB\"\n"
    " ```\n"
    "\n"
    " ## Accessing Identifiers\n"
    "\n"
    " The function can use the node ID to calculate new values:\n"
    "\n"
    " ```gleam\n"
    " // Prefix node values with their IDs\n"
    " transform.map_nodes(graph, fn(id, name) {\n"
    "   int.to_string(id) <> \": \" <> name\n"
    " })\n"
    " ```\n"
).
-spec map_nodes(yog@model:graph(GIL, GIM), fun((integer(), GIL) -> GIP)) -> yog@model:graph(GIP, GIM).
map_nodes(Graph, Transform) ->
    New_nodes = gleam@dict:map_values(erlang:element(3, Graph), Transform),
    {graph,
        erlang:element(2, Graph),
        New_nodes,
        erlang:element(4, Graph),
        erlang:element(5, Graph)}.

-file("src/yog/transform.gleam", 227).
?DOC(
    " Updates a specific node's data using an updater function.\n"
    "\n"
    " Similar to `dict.upsert`, but specialized for graphs.\n"
    " If the node doesn't exist, it is created with the `default` value.\n"
    "\n"
    " **Time Complexity:** O(1)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " let graph = model.new(Directed) |> model.add_node(1, 100)\n"
    " let updated = transform.update_node(graph, 1, 0, fn(x) { x + 50 })\n"
    " // Node 1 now has data 150\n"
    " ```\n"
).
-spec update_node(yog@model:graph(GIS, GIT), integer(), GIS, fun((GIS) -> GIS)) -> yog@model:graph(GIS, GIT).
update_node(Graph, Id, Default, Fun) ->
    New_nodes = gleam@dict:upsert(
        erlang:element(3, Graph),
        Id,
        fun(Maybe_data) -> case Maybe_data of
                {some, Data} ->
                    Fun(Data);

                none ->
                    Default
            end end
    ),
    {graph,
        erlang:element(2, Graph),
        New_nodes,
        erlang:element(4, Graph),
        erlang:element(5, Graph)}.

-file("src/yog/transform.gleam", 256).
?DOC(
    " Creates a new graph containing only the nodes that satisfy the predicate.\n"
    "\n"
    " Nodes are filtered based on both their ID and their associated data.\n"
    " Removing a node automatically removes all of its incident edges (both inbound\n"
    " and outbound).\n"
    "\n"
    " **Time Complexity:** O(V + E)\n"
    "\n"
    " ## Use Cases\n"
    "\n"
    " - Filter nodes by ID range or specific identifiers\n"
    " - Complex filtering requiring both identity and data\n"
    " - Efficiently removing common nodes between two graphs\n"
).
-spec filter_nodes(
    yog@model:graph(GIY, GIZ),
    fun((integer(), GIY) -> boolean())
) -> yog@model:graph(GIY, GIZ).
filter_nodes(Graph, Predicate) ->
    Kept_nodes = gleam@dict:filter(erlang:element(3, Graph), Predicate),
    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", 314).
?DOC(
    " Transforms edge weights using a function, preserving graph structure.\n"
    "\n"
    " This is a functor-like operation that applies a function to every edge's weight\n"
    " while keeping all nodes and the graph topology unchanged. The transformation\n"
    " function receives the source node ID, destination node ID, and the edge 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_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(_u, _v, w) { w * 2 })\n"
    " // Edges now have weights 20 and 40\n"
    " ```\n"
    "\n"
    " ## Accessing Identifiers\n"
    "\n"
    " The function can use endpoint identifiers to calculate new weights:\n"
    "\n"
    " ```gleam\n"
    " // Include path context in edge data\n"
    " let result = transform.map_edges(graph, fn(u, v, _w) {\n"
    "   int.to_string(u) <> \"->\" <> int.to_string(v)\n"
    " })\n"
    " ```\n"
).
-spec map_edges(
    yog@model:graph(GJE, GJF),
    fun((integer(), integer(), GJF) -> GJI)
) -> yog@model:graph(GJE, GJI).
map_edges(Graph, Transform) ->
    Map_outer = fun(Edge_map) ->
        gleam@dict:map_values(
            Edge_map,
            fun(Src, Inner_map) ->
                gleam@dict:map_values(
                    Inner_map,
                    fun(Dst, Weight) -> Transform(Src, Dst, Weight) end
                )
            end
        )
    end,
    {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        Map_outer(erlang:element(4, Graph)),
        Map_outer(erlang:element(5, Graph))}.

-file("src/yog/transform.gleam", 405).
?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(GJR, GJS),
    fun((integer(), integer(), GJS) -> boolean())
) -> yog@model:graph(GJR, GJS).
filter_edges(Graph, Predicate) ->
    Filter_out = 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,
    Filter_in = fun(Outer_map@1) -> _pipe@2 = Outer_map@1,
        _pipe@3 = gleam@dict:map_values(
            _pipe@2,
            fun(Dst@1, Inner_map@2) ->
                gleam@dict:filter(
                    Inner_map@2,
                    fun(Src@1, Weight@1) ->
                        Predicate(Src@1, Dst@1, Weight@1)
                    end
                )
            end
        ),
        gleam@dict:filter(
            _pipe@3,
            fun(_, Inner_map@3) -> maps:size(Inner_map@3) > 0 end
        ) end,
    {graph,
        erlang:element(2, Graph),
        erlang:element(3, Graph),
        Filter_out(erlang:element(4, Graph)),
        Filter_in(erlang:element(5, Graph))}.

-file("src/yog/transform.gleam", 466).
?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(GJX, GJY), GJY) -> yog@model:graph(GJX, GJY).
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()},
    gleam@list:fold(
        Node_ids,
        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 ->
                                    New_graph@1 = case yog@model:add_edge(
                                        Acc,
                                        Src,
                                        Dst,
                                        Default_weight
                                    ) of
                                        {ok, New_graph} -> New_graph;
                                        _assert_fail ->
                                            erlang:error(
                                                    #{gleam_error => let_assert,
                                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                                        file => <<?FILEPATH/utf8>>,
                                                        module => <<"yog/transform"/utf8>>,
                                                        function => <<"complement"/utf8>>,
                                                        line => 487,
                                                        value => _assert_fail,
                                                        start => 15238,
                                                        'end' => 15338,
                                                        pattern_start => 15249,
                                                        pattern_end => 15262}
                                                )
                                    end,
                                    New_graph@1
                            end
                    end end)
        end
    ).

-file("src/yog/transform.gleam", 536).
?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(GKD, GKE), yog@model:graph(GKD, GKE)) -> yog@model:graph(GKD, GKE).
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", 590).
?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(GKL, GKM), list(integer())) -> yog@model:graph(GKL, GKM).
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", 669).
?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(GKS, GKT),
    integer(),
    integer(),
    fun((GKT, GKT) -> GKT)
) -> yog@model:graph(GKS, GKT).
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 ->
                    G@1 = case yog@model:add_edge_with_combine(
                        Acc_g,
                        A,
                        Neighbor,
                        Weight,
                        With_combine
                    ) of
                        {ok, G} -> G;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"yog/transform"/utf8>>,
                                        function => <<"contract"/utf8>>,
                                        line => 681,
                                        value => _assert_fail,
                                        start => 21569,
                                        'end' => 21754,
                                        pattern_start => 21580,
                                        pattern_end => 21585})
                    end,
                    G@1
            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 ->
                            G@3 = case yog@model:add_edge_with_combine(
                                Acc_g@1,
                                Neighbor@1,
                                A,
                                Weight@1,
                                With_combine
                            ) of
                                {ok, G@2} -> G@2;
                                _assert_fail@1 ->
                                    erlang:error(#{gleam_error => let_assert,
                                                message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                                file => <<?FILEPATH/utf8>>,
                                                module => <<"yog/transform"/utf8>>,
                                                function => <<"contract"/utf8>>,
                                                line => 702,
                                                value => _assert_fail@1,
                                                start => 22115,
                                                'end' => 22314,
                                                pattern_start => 22126,
                                                pattern_end => 22131})
                            end,
                            G@3
                    end
                end
            )
    end,
    yog@model:remove_node(Graph@2, B).

-file("src/yog/transform.gleam", 807).
-spec do_transitive_closure_dag(
    yog@model:graph(GLK, GLL),
    list(integer()),
    fun((GLL, GLL) -> GLL)
) -> yog@model:graph(GLK, GLL).
do_transitive_closure_dag(Graph, Sorted, Merge_fn) ->
    Reachability_map = begin
        gleam@list:fold(
            lists:reverse(Sorted),
            maps:new(),
            fun(Acc, Node) ->
                Edges = begin
                    _pipe = gleam_stdlib:map_get(erlang:element(4, Graph), Node),
                    gleam@result:unwrap(_pipe, maps:new())
                end,
                Reachable_from_node = begin
                    gleam@dict:fold(
                        Edges,
                        Edges,
                        fun(Reachable_acc, Child, W_node_child) ->
                            Child_reachable = begin
                                _pipe@1 = gleam_stdlib:map_get(Acc, Child),
                                gleam@result:unwrap(_pipe@1, maps:new())
                            end,
                            _pipe@2 = Child_reachable,
                            _pipe@3 = gleam@dict:map_values(
                                _pipe@2,
                                fun(_, W) -> Merge_fn(W_node_child, W) end
                            ),
                            gleam@dict:combine(_pipe@3, Reachable_acc, Merge_fn)
                        end
                    )
                end,
                gleam@dict:insert(Acc, Node, Reachable_from_node)
            end
        )
    end,
    gleam@dict:fold(
        Reachability_map,
        Graph,
        fun(G_acc, Src, Targets) ->
            gleam@dict:fold(
                Targets,
                G_acc,
                fun(G_inner, Dst, W@1) ->
                    G@1 = case yog@model:add_edge(G_inner, Src, Dst, W@1) of
                        {ok, G} -> G;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"yog/transform"/utf8>>,
                                        function => <<"do_transitive_closure_dag"/utf8>>,
                                        line => 829,
                                        value => _assert_fail,
                                        start => 25964,
                                        'end' => 26035,
                                        pattern_start => 25975,
                                        pattern_end => 25980})
                    end,
                    G@1
                end
            )
        end
    ).

-file("src/yog/transform.gleam", 864).
-spec do_weighted_reachability(
    yog@model:graph(any(), GME),
    list({integer(), GME}),
    gleam@dict:dict(integer(), GME),
    fun((GME, GME) -> GME)
) -> gleam@dict:dict(integer(), GME).
do_weighted_reachability(Graph, Queue, Visited, Merge_fn) ->
    case Queue of
        [] ->
            Visited;

        [{Current, Weight_to_current} | Rest] ->
            case gleam_stdlib:map_get(Visited, Current) of
                {ok, _} ->
                    do_weighted_reachability(Graph, Rest, Visited, Merge_fn);

                {error, _} ->
                    New_visited = gleam@dict:insert(
                        Visited,
                        Current,
                        Weight_to_current
                    ),
                    Neighbors = yog@model:successors(Graph, Current),
                    Next_steps = gleam@list:map(
                        Neighbors,
                        fun(Nb) ->
                            {erlang:element(1, Nb),
                                Merge_fn(
                                    Weight_to_current,
                                    erlang:element(2, Nb)
                                )}
                        end
                    ),
                    Next_queue = lists:append(Rest, Next_steps),
                    do_weighted_reachability(
                        Graph,
                        Next_queue,
                        New_visited,
                        Merge_fn
                    )
            end
    end.

-file("src/yog/transform.gleam", 854).
-spec find_all_reachable_weighted(
    yog@model:graph(any(), GLY),
    integer(),
    fun((GLY, GLY) -> GLY)
) -> gleam@dict:dict(integer(), GLY).
find_all_reachable_weighted(Graph, Start, Merge_fn) ->
    Neighbors = yog@model:successors(Graph, Start),
    Initial_queue = gleam@list:map(
        Neighbors,
        fun(Nb) -> {erlang:element(1, Nb), erlang:element(2, Nb)} end
    ),
    do_weighted_reachability(Graph, Initial_queue, maps:new(), Merge_fn).

-file("src/yog/transform.gleam", 834).
-spec do_transitive_closure_general(
    yog@model:graph(GLR, GLS),
    fun((GLS, GLS) -> GLS)
) -> yog@model:graph(GLR, GLS).
do_transitive_closure_general(Graph, Merge_fn) ->
    _pipe = yog@model:all_nodes(Graph),
    gleam@list:fold(
        _pipe,
        Graph,
        fun(Acc_graph, Start_node) ->
            Reachable = find_all_reachable_weighted(Graph, Start_node, Merge_fn),
            gleam@dict:fold(
                Reachable,
                Acc_graph,
                fun(Inner_graph, Target_node, Weight) ->
                    G@1 = case yog@model:add_edge(
                        Inner_graph,
                        Start_node,
                        Target_node,
                        Weight
                    ) of
                        {ok, G} -> G;
                        _assert_fail ->
                            erlang:error(#{gleam_error => let_assert,
                                        message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
                                        file => <<?FILEPATH/utf8>>,
                                        module => <<"yog/transform"/utf8>>,
                                        function => <<"do_transitive_closure_general"/utf8>>,
                                        line => 842,
                                        value => _assert_fail,
                                        start => 26439,
                                        'end' => 26593,
                                        pattern_start => 26450,
                                        pattern_end => 26455})
                    end,
                    G@1
                end
            )
        end
    ).

-file("src/yog/transform.gleam", 744).
?DOC(
    " Computes the transitive closure of a graph.\n"
    "\n"
    " The transitive closure adds edges between all pairs of nodes where a path\n"
    " exists in the original graph. If `u` can reach `v` through any path, the\n"
    " closure will have a direct edge `u -> v`.\n"
    "\n"
    " The `merge_fn` is used to combine edge weights when multiple paths exist\n"
    " between the same pair of nodes.\n"
    "\n"
    " **Complexity:**\n"
    " - For DAGs: O(V × E) using topological sort\n"
    " - For general graphs: O(V × (V + E)) using multiple traversals\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Original edges: A->B (weight 2), B->C (weight 3)\n"
    " // Closure adds: A->C (weight 5 = 2+3)\n"
    " let closure = transform.transitive_closure(graph, int.add)\n"
    " ```\n"
).
-spec transitive_closure(yog@model:graph(GKY, GKZ), fun((GKZ, GKZ) -> GKZ)) -> yog@model:graph(GKY, GKZ).
transitive_closure(Graph, Merge_fn) ->
    case yog@traversal:topological_sort(Graph) of
        {ok, Sorted} ->
            do_transitive_closure_dag(Graph, Sorted, Merge_fn);

        {error, nil} ->
            do_transitive_closure_general(Graph, Merge_fn)
    end.

-file("src/yog/transform.gleam", 774).
?DOC(
    " Computes the transitive reduction of a graph.\n"
    "\n"
    " The transitive reduction removes all edges that are redundant - i.e., edges\n"
    " `u -> v` where there exists an indirect path from `u` to `v` through other\n"
    " nodes.\n"
    "\n"
    " **Note:** For graphs with cycles (non-DAGs), the transitive reduction\n"
    " is not always unique and can be more complex to compute. This implementation\n"
    " focuses on the DAG case.\n"
    "\n"
    " **Time Complexity:** O(V × E)\n"
    "\n"
    " ## Example\n"
    "\n"
    " ```gleam\n"
    " // Original: A->B, B->C, A->C (A->C is implied by A->B->C)\n"
    " // Reduction removes: A->C\n"
    " // Result: A->B, B->C\n"
    " let minimal = transform.transitive_reduction(graph, int.add)\n"
    " ```\n"
).
-spec transitive_reduction(yog@model:graph(GLE, GLF), fun((GLF, GLF) -> GLF)) -> yog@model:graph(GLE, GLF).
transitive_reduction(Graph, Merge_fn) ->
    Reach_graph = transitive_closure(Graph, Merge_fn),
    gleam@dict:fold(
        erlang:element(4, Graph),
        Graph,
        fun(G_acc, U, Targets) ->
            gleam@dict:fold(
                Targets,
                G_acc,
                fun(G_inner, V, _) ->
                    Is_redundant = begin
                        gleam@dict:fold(
                            Targets,
                            false,
                            fun(Found_redundant, W, _) ->
                                case {Found_redundant, W =:= V} of
                                    {true, _} ->
                                        true;

                                    {false, true} ->
                                        false;

                                    {false, false} ->
                                        case gleam_stdlib:map_get(
                                            erlang:element(4, Reach_graph),
                                            W
                                        ) of
                                            {ok, W_targets} ->
                                                gleam@dict:has_key(W_targets, V);

                                            {error, _} ->
                                                false
                                        end
                                end
                            end
                        )
                    end,
                    case Is_redundant of
                        true ->
                            yog@model:remove_edge(G_inner, U, V);

                        false ->
                            G_inner
                    end
                end
            )
        end
    ).

-file("src/yog/transform.gleam", 890).
-spec do_update_directed_edge(
    yog@model:graph(GMM, GMN),
    integer(),
    integer(),
    GMN,
    fun((GMN) -> GMN)
) -> yog@model:graph(GMM, GMN).
do_update_directed_edge(Graph, Src, Dst, Default, Fun) ->
    Update_fn = fun(Maybe_inner) -> case Maybe_inner of
            {some, M} ->
                gleam@dict:upsert(M, Dst, fun(Maybe_w) -> case Maybe_w of
                            {some, W} ->
                                Fun(W);

                            none ->
                                Default
                        end end);

            none ->
                maps:from_list([{Dst, Default}])
        end end,
    New_out = gleam@dict:upsert(erlang:element(4, Graph), Src, Update_fn),
    Update_in_fn = fun(Maybe_inner@1) -> case Maybe_inner@1 of
            {some, M@1} ->
                gleam@dict:upsert(M@1, Src, fun(Maybe_w@1) -> case Maybe_w@1 of
                            {some, W@1} ->
                                Fun(W@1);

                            none ->
                                Default
                        end end);

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

-file("src/yog/transform.gleam", 352).
?DOC(
    " Updates a specific edge's weight/metadata safely.\n"
    "\n"
    " Ensures both `in_edges` and `out_edges` stay in sync. Properly handles\n"
    " undirected graphs by updating both directions.\n"
    "\n"
    " If either node `src` or `dst` does not exist, the graph is returned unchanged.\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(1, 2, 10)\n"
    "\n"
    " let updated = transform.update_edge(graph, 1, 2, 0, fn(w) { w + 5 })\n"
    " // Edge 1->2 now has weight 15\n"
    " ```\n"
).
-spec update_edge(
    yog@model:graph(GJL, GJM),
    integer(),
    integer(),
    GJM,
    fun((GJM) -> GJM)
) -> yog@model:graph(GJL, GJM).
update_edge(Graph, Src, Dst, Default, Fun) ->
    case {gleam@dict:has_key(erlang:element(3, Graph), Src),
        gleam@dict:has_key(erlang:element(3, Graph), Dst)} of
        {true, true} ->
            Graph@1 = do_update_directed_edge(Graph, Src, Dst, Default, Fun),
            case erlang:element(2, Graph@1) of
                directed ->
                    Graph@1;

                undirected ->
                    case Src =:= Dst of
                        true ->
                            Graph@1;

                        false ->
                            do_update_directed_edge(
                                Graph@1,
                                Dst,
                                Src,
                                Default,
                                Fun
                            )
                    end
            end;

        {false, _} ->
            Graph;

        {_, false} ->
            Graph
    end.