Current section
Files
Jump to
Current section
Files
src/yog@transform.erl
-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.