Current section
Files
Jump to
Current section
Files
src/yog@operation.erl
-module(yog@operation).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/operation.gleam").
-export([union/2, cartesian_product/4, compose/2, disjoint_union/2, intersection/2, difference/2, symmetric_difference/2, power/3, is_subgraph/2, is_isomorphic/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 operations - Set-theoretic operations, composition, and structural comparison.\n"
"\n"
" This module implements binary operations that treat graphs as sets of nodes and edges,\n"
" following NetworkX's \"Graph as a Set\" philosophy. These operations allow you to combine,\n"
" compare, and analyze structural differences between graphs.\n"
"\n"
" ## Set-Theoretic Operations\n"
"\n"
" | Function | Description | Use Case |\n"
" |----------|-------------|----------|\n"
" | `union/2` | All nodes and edges from both graphs | Combine graph data |\n"
" | `intersection/2` | Only nodes and edges common to both | Find common structure |\n"
" | `difference/2` | Nodes/edges in first but not second | Find unique structure |\n"
" | `symmetric_difference/2` | Edges in exactly one graph | Find differing structure |\n"
"\n"
" ## Composition & Joins\n"
"\n"
" | Function | Description | Use Case |\n"
" |----------|-------------|----------|\n"
" | `disjoint_union/2` | Combine with automatic ID re-indexing | Safe graph combination |\n"
" | `cartesian_product/2` | Multiply graphs (grids, hypercubes) | Generate complex structures |\n"
" | `compose/2` | Merge overlapping graphs with combined edges | Layered systems |\n"
" | `power/2` | k-th power (connect nodes within distance k) | Reachability analysis |\n"
"\n"
" ## Structural Comparison\n"
"\n"
" | Function | Description | Use Case |\n"
" |----------|-------------|----------|\n"
" | `is_subgraph/2` | Check if first is subset of second | Validation, pattern matching |\n"
" | `is_isomorphic/2` | Check if graphs are structurally identical | Graph comparison |\n"
"\n"
" ## Example: Combining Graphs Safely\n"
"\n"
" ```gleam\n"
" import yog\n"
" import yog/operation\n"
"\n"
" // Two triangle graphs with overlapping IDs\n"
" let triangle1 = yog.from_simple_edges(Directed, [#(0, 1), #(1, 2), #(2, 0)])\n"
" let triangle2 = yog.from_simple_edges(Directed, [#(0, 1), #(1, 2), #(2, 0)])\n"
"\n"
" // disjoint_union re-indexes the second graph automatically\n"
" let combined = operation.disjoint_union(triangle1, triangle2)\n"
" // Result: 6 nodes (0-5), two separate triangles\n"
" ```\n"
"\n"
" ## Example: Finding Common Structure\n"
"\n"
" ```gleam\n"
" let common = operation.intersection(graph_a, graph_b)\n"
" // Returns only nodes and edges present in both graphs\n"
" ```\n"
).
-file("src/yog/operation.gleam", 81).
?DOC(
" Returns a graph containing all nodes and edges from both input graphs.\n"
"\n"
" If a node or edge exists in both graphs, the one from `other` takes\n"
" precedence for data/weights.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let g1 = yog.from_simple_edges(Directed, [#(1, 2)])\n"
" let g2 = yog.from_simple_edges(Directed, [#(2, 3)])\n"
" let result = operation.union(g1, g2)\n"
" // order(result) == 3, edge_count(result) == 2\n"
" ```\n"
).
-spec union(yog@model:graph(WJN, WJO), yog@model:graph(WJN, WJO)) -> yog@model:graph(WJN, WJO).
union(Base, Other) ->
yog@transform:merge(Base, Other).
-file("src/yog/operation.gleam", 189).
?DOC(
" Returns the Cartesian product of two graphs.\n"
"\n"
" Every node in the result is a pair `#(u, v)` where `u` is from the first graph\n"
" and `v` is from the second graph. Node IDs in the result are integers\n"
" calculated as `u_index * order(second) + v_index`.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Product of two paths of length 1 (single edge) is a 2x2 grid\n"
" let path = yog.from_simple_edges(Undirected, [#(0, 1)])\n"
" let grid = operation.cartesian_product(path, path, 0, 0)\n"
" // order(grid) == 4, edge_count(grid) == 4\n"
" ```\n"
).
-spec cartesian_product(
yog@model:graph(WLB, WLC),
yog@model:graph(WLF, WLG),
WLG,
WLC
) -> yog@model:graph({WLB, WLF}, {WLC, WLG}).
cartesian_product(First, Second, Default_first, Default_second) ->
First_nodes = maps:to_list(erlang:element(3, First)),
Second_nodes = maps:to_list(erlang:element(3, Second)),
Second_order = yog@model:order(Second),
Graph_with_nodes = begin
gleam@list:fold(
First_nodes,
yog@model:new(erlang:element(2, First)),
fun(G_acc, _use1) ->
{U, U_data} = _use1,
gleam@list:fold(
Second_nodes,
G_acc,
fun(G, _use1@1) ->
{V, V_data} = _use1@1,
yog@model:add_node(
G,
(U * Second_order) + V,
{U_data, V_data}
)
end
)
end
)
end,
Graph_with_second_edges = begin
Second_edges = yog@model:all_edges(Second),
gleam@list:fold(
First_nodes,
Graph_with_nodes,
fun(G_acc@1, _use1@2) ->
{U@1, _} = _use1@2,
gleam@list:fold(
Second_edges,
G_acc@1,
fun(G@1, _use1@3) ->
{V_src, V_dst, Weight} = _use1@3,
Src_id = (U@1 * Second_order) + V_src,
Dst_id = (U@1 * Second_order) + V_dst,
Weight@1 = {Default_second, Weight},
case yog@model:add_edge(G@1, Src_id, Dst_id, Weight@1) of
{ok, New_g} ->
New_g;
{error, _} ->
G@1
end
end
)
end
)
end,
begin
First_edges = yog@model:all_edges(First),
gleam@list:fold(
Second_nodes,
Graph_with_second_edges,
fun(G_acc@2, _use1@4) ->
{V@1, _} = _use1@4,
gleam@list:fold(
First_edges,
G_acc@2,
fun(G@2, _use1@5) ->
{U_src, U_dst, Weight@2} = _use1@5,
Src_id@1 = (U_src * Second_order) + V@1,
Dst_id@1 = (U_dst * Second_order) + V@1,
Weight@3 = {Weight@2, Default_first},
case yog@model:add_edge(
G@2,
Src_id@1,
Dst_id@1,
Weight@3
) of
{ok, New_g@1} ->
New_g@1;
{error, _} ->
G@2
end
end
)
end
)
end.
-file("src/yog/operation.gleam", 244).
?DOC(
" Composes two graphs by merging overlapping nodes and combining their edges.\n"
"\n"
" This is a simple merge where nodes with the same ID are identified.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let composed = operation.compose(g1, g2)\n"
" ```\n"
).
-spec compose(yog@model:graph(WLL, WLM), yog@model:graph(WLL, WLM)) -> yog@model:graph(WLL, WLM).
compose(First, Second) ->
union(First, Second).
-file("src/yog/operation.gleam", 338).
?DOC(" Shifts all node IDs in a graph by a given offset.\n").
-spec shift_node_ids(yog@model:graph(WML, WMM), integer()) -> yog@model:graph(WML, WMM).
shift_node_ids(Graph, Offset) ->
Map_id = fun(Id) -> Id + Offset end,
New_nodes = gleam@dict:fold(
erlang:element(3, Graph),
maps:new(),
fun(Acc, Id@1, Data) -> gleam@dict:insert(Acc, Map_id(Id@1), Data) end
),
Map_edges = fun(Edge_map) ->
gleam@dict:fold(
Edge_map,
maps:new(),
fun(Acc@1, Src, Targets) ->
New_targets = gleam@dict:fold(
Targets,
maps:new(),
fun(Inner_acc, Dst, Weight) ->
gleam@dict:insert(Inner_acc, Map_id(Dst), Weight)
end
),
gleam@dict:insert(Acc@1, Map_id(Src), New_targets)
end
)
end,
{graph,
erlang:element(2, Graph),
New_nodes,
Map_edges(erlang:element(4, Graph)),
Map_edges(erlang:element(5, Graph))}.
-file("src/yog/operation.gleam", 169).
?DOC(
" Combines two graphs assuming they are separate entities with automatic re-indexing.\n"
"\n"
" The second graph's node IDs are shifted by `order(base)` to ensure they\n"
" do not collide with IDs in the first graph.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let g1 = yog.from_simple_edges(Directed, [#(0, 1)])\n"
" let g2 = yog.from_simple_edges(Directed, [#(0, 1)])\n"
" let result = operation.disjoint_union(g1, g2)\n"
" // Result has nodes 0, 1, 2, 3 and edges 0->1, 2->3\n"
" ```\n"
).
-spec disjoint_union(yog@model:graph(WKT, WKU), yog@model:graph(WKT, WKU)) -> yog@model:graph(WKT, WKU).
disjoint_union(Base, Other) ->
Offset = yog@model:order(Base),
Reindexed_other = shift_node_ids(Other, Offset),
union(Base, Reindexed_other).
-file("src/yog/operation.gleam", 365).
?DOC(" Computes the degree sequence of a graph.\n").
-spec degree_sequence(yog@model:graph(any(), any())) -> list({integer(),
integer()}).
degree_sequence(Graph) ->
_pipe = maps:keys(erlang:element(3, Graph)),
gleam@list:map(
_pipe,
fun(Node) ->
Out_deg = begin
_pipe@1 = gleam_stdlib:map_get(erlang:element(4, Graph), Node),
_pipe@2 = gleam@result:map(_pipe@1, fun maps:size/1),
gleam@result:unwrap(_pipe@2, 0)
end,
In_deg = begin
_pipe@3 = gleam_stdlib:map_get(erlang:element(5, Graph), Node),
_pipe@4 = gleam@result:map(_pipe@3, fun maps:size/1),
gleam@result:unwrap(_pipe@4, 0)
end,
{In_deg, Out_deg}
end
).
-file("src/yog/operation.gleam", 380).
-spec compare_degrees({integer(), integer()}, {integer(), integer()}) -> gleam@order:order().
compare_degrees(A, B) ->
case gleam@int:compare(erlang:element(1, A), erlang:element(1, B)) of
eq ->
gleam@int:compare(erlang:element(2, A), erlang:element(2, B));
Other ->
Other
end.
-file("src/yog/operation.gleam", 450).
-spec out_degree(yog@model:graph(any(), any()), integer()) -> integer().
out_degree(Graph, Id) ->
_pipe = gleam_stdlib:map_get(erlang:element(4, Graph), Id),
_pipe@1 = gleam@result:map(_pipe, fun maps:size/1),
gleam@result:unwrap(_pipe@1, 0).
-file("src/yog/operation.gleam", 454).
-spec in_degree(yog@model:graph(any(), any()), integer()) -> integer().
in_degree(Graph, Id) ->
_pipe = gleam_stdlib:map_get(erlang:element(5, Graph), Id),
_pipe@1 = gleam@result:map(_pipe, fun maps:size/1),
gleam@result:unwrap(_pipe@1, 0).
-file("src/yog/operation.gleam", 459).
?DOC(" Finds all nodes within distance k using BFS.\n").
-spec nodes_within_distance(yog@model:graph(any(), any()), integer(), integer()) -> list(integer()).
nodes_within_distance(Graph, Src, Max_dist) ->
yog@traversal:fold_walk(
Graph,
Src,
breadth_first,
[],
fun(Acc, Node_id, Meta) ->
case {erlang:element(2, Meta) > 0,
erlang:element(2, Meta) =< Max_dist} of
{true, true} ->
{continue, [Node_id | Acc]};
{false, _} ->
{continue, Acc};
{_, false} ->
{stop, Acc}
end
end
).
-file("src/yog/operation.gleam", 480).
?DOC(" Efficient edge existence check.\n").
-spec has_edge(yog@model:graph(any(), any()), integer(), integer()) -> boolean().
has_edge(Graph, U, V) ->
case gleam_stdlib:map_get(erlang:element(4, Graph), U) of
{ok, Targets} ->
gleam@dict:has_key(Targets, V);
{error, _} ->
false
end.
-file("src/yog/operation.gleam", 98).
?DOC(
" Returns a graph containing only nodes and edges that exist in both input graphs.\n"
"\n"
" For an edge to be present in the intersection, it must exist between the\n"
" same nodes in both graphs.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let g1 = yog.from_simple_edges(Directed, [#(1, 2), #(2, 3)])\n"
" let g2 = yog.from_simple_edges(Directed, [#(2, 3), #(3, 4)])\n"
" let result = operation.intersection(g1, g2)\n"
" // Result contains node 2, 3 and edge 2->3\n"
" ```\n"
).
-spec intersection(yog@model:graph(WJV, WJW), yog@model:graph(WJV, WJW)) -> yog@model:graph(WJV, WJW).
intersection(First, Second) ->
_pipe = First,
_pipe@1 = yog@transform:filter_nodes(
_pipe,
fun(Id, _) -> gleam@dict:has_key(erlang:element(3, Second), Id) end
),
yog@transform:filter_edges(
_pipe@1,
fun(U, V, _) -> has_edge(Second, U, V) end
).
-file("src/yog/operation.gleam", 119).
?DOC(
" Returns a graph containing nodes and edges that exist in the first graph\n"
" but not in the second.\n"
"\n"
" An edge is removed if it exists in both graphs. A node is removed if it\n"
" exists in both graphs AND it has no remaining unique edges incident to it.\n"
" If a node exists in the first graph but not the second, it is always kept.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let g1 = yog.from_simple_edges(Directed, [#(1, 2), #(2, 3)])\n"
" let g2 = yog.from_simple_edges(Directed, [#(1, 2)])\n"
" let result = operation.difference(g1, g2)\n"
" // Result retains node 2, 3 and edge 2->3. Node 1 is removed.\n"
" ```\n"
).
-spec difference(yog@model:graph(WKD, WKE), yog@model:graph(WKD, WKE)) -> yog@model:graph(WKD, WKE).
difference(First, Second) ->
Filtered_edges_graph = begin
_pipe = First,
yog@transform:filter_edges(
_pipe,
fun(U, V, _) -> not has_edge(Second, U, V) end
)
end,
_pipe@1 = Filtered_edges_graph,
yog@transform:filter_nodes(
_pipe@1,
fun(Id, _) ->
not gleam@dict:has_key(erlang:element(3, Second), Id) orelse (yog@model:degree(
Filtered_edges_graph,
Id
)
> 0)
end
).
-file("src/yog/operation.gleam", 144).
?DOC(
" Returns a graph containing edges that exist in exactly one of the input graphs.\n"
"\n"
" Also includes all nodes that are incident to these unique edges, or nodes\n"
" that exist in only one of the graphs.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let g1 = yog.from_simple_edges(Directed, [#(1, 2)])\n"
" let g2 = yog.from_simple_edges(Directed, [#(2, 3)])\n"
" let result = operation.symmetric_difference(g1, g2)\n"
" // Result contains edges 1->2 and 2->3\n"
" ```\n"
).
-spec symmetric_difference(yog@model:graph(WKL, WKM), yog@model:graph(WKL, WKM)) -> yog@model:graph(WKL, WKM).
symmetric_difference(First, Second) ->
_pipe = difference(First, Second),
union(_pipe, difference(Second, First)).
-file("src/yog/operation.gleam", 256).
?DOC(
" Returns the k-th power of a graph.\n"
"\n"
" The k-th power of a graph G, denoted G^k, is a graph where two nodes are\n"
" adjacent if and only if their distance in G is at most k.\n"
"\n"
" New edges are created with the provided `default_weight`.\n"
"\n"
" **Time Complexity:** O(V * (V + E))\n"
).
-spec power(yog@model:graph(WLT, WLU), integer(), WLU) -> yog@model:graph(WLT, WLU).
power(Graph, K, Default_weight) ->
gleam@list:fold(
yog@model:all_nodes(Graph),
Graph,
fun(G_acc, U) ->
Reachable = nodes_within_distance(Graph, U, K),
gleam@list:fold(
Reachable,
G_acc,
fun(G, V) -> case (U =:= V) orelse has_edge(G, U, V) of
true ->
G;
false ->
New_g@1 = case yog@model:add_edge(
G,
U,
V,
Default_weight
) of
{ok, New_g} -> New_g;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/operation"/utf8>>,
function => <<"power"/utf8>>,
line => 263,
value => _assert_fail,
start => 9539,
'end' => 9625,
pattern_start => 9550,
pattern_end => 9559})
end,
New_g@1
end end
)
end
).
-file("src/yog/operation.gleam", 286).
?DOC(
" Checks if the first graph is a subgraph of the second graph.\n"
"\n"
" Returns true if every node in the first graph exists in the second, and\n"
" every edge in the first graph also exists in the second.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let g1 = yog.from_simple_edges(Directed, [#(1, 2)])\n"
" let g2 = yog.from_simple_edges(Directed, [#(1, 2), #(2, 3)])\n"
" operation.is_subgraph(g1, g2) // True\n"
" ```\n"
).
-spec is_subgraph(yog@model:graph(WLZ, WMA), yog@model:graph(WLZ, WMA)) -> boolean().
is_subgraph(Potential, Container) ->
Potential_nodes = maps:keys(erlang:element(3, Potential)),
gleam@bool:guard(
not gleam@list:all(
Potential_nodes,
fun(Node) -> yog@model:has_node(Container, Node) end
),
false,
fun() ->
gleam@list:all(
Potential_nodes,
fun(Src) ->
Successors = begin
_pipe = gleam_stdlib:map_get(
erlang:element(4, Potential),
Src
),
gleam@result:unwrap(_pipe, maps:new())
end,
gleam@list:all(
maps:to_list(Successors),
fun(_use0) ->
{Dst, _} = _use0,
has_edge(Container, Src, Dst)
end
)
end
)
end
).
-file("src/yog/operation.gleam", 431).
-spec is_mapping_valid(
yog@model:graph(WNM, WNN),
yog@model:graph(WNM, WNN),
integer(),
integer(),
gleam@dict:dict(integer(), integer())
) -> boolean().
is_mapping_valid(Graph1, Graph2, Src, Cand, Mapping) ->
gleam@list:all(
maps:to_list(Mapping),
fun(_use0) ->
{Src_prev, Cand_prev} = _use0,
G1_forward = has_edge(Graph1, Src_prev, Src),
G2_forward = has_edge(Graph2, Cand_prev, Cand),
gleam@bool:guard(
G1_forward /= G2_forward,
false,
fun() ->
G1_backward = has_edge(Graph1, Src, Src_prev),
G2_backward = has_edge(Graph2, Cand, Cand_prev),
gleam@bool:guard(
G1_backward /= G2_backward,
false,
fun() -> true end
)
end
)
end
).
-file("src/yog/operation.gleam", 399).
-spec try_mapping(
yog@model:graph(WNC, WND),
yog@model:graph(WNC, WND),
list(integer()),
list(integer()),
gleam@dict:dict(integer(), integer())
) -> boolean().
try_mapping(First, Second, Remaining_first, Available_second, Mapping) ->
case Remaining_first of
[] ->
true;
[Src | Rest] ->
Src_out = out_degree(First, Src),
Src_in = in_degree(First, Src),
Candidates = gleam@list:filter(
Available_second,
fun(Cand) ->
(out_degree(Second, Cand) =:= Src_out) andalso (in_degree(
Second,
Cand
)
=:= Src_in)
end
),
gleam@list:any(
Candidates,
fun(Cand@1) ->
case is_mapping_valid(First, Second, Src, Cand@1, Mapping) of
false ->
false;
true ->
New_mapping = gleam@dict:insert(
Mapping,
Src,
Cand@1
),
New_available = gleam@list:filter(
Available_second,
fun(N) -> N /= Cand@1 end
),
try_mapping(
First,
Second,
Rest,
New_available,
New_mapping
)
end
end
)
end.
-file("src/yog/operation.gleam", 388).
?DOC(" Attempts backtracking isomorphism check.\n").
-spec attempt_isomorphism(yog@model:graph(WMW, WMX), yog@model:graph(WMW, WMX)) -> boolean().
attempt_isomorphism(First, Second) ->
First_nodes = begin
_pipe = maps:keys(erlang:element(3, First)),
gleam@list:sort(
_pipe,
fun(A, B) ->
gleam@int:compare(
yog@model:degree(First, B),
yog@model:degree(First, A)
)
end
)
end,
Second_nodes = maps:keys(erlang:element(3, Second)),
try_mapping(First, Second, First_nodes, Second_nodes, maps:new()).
-file("src/yog/operation.gleam", 318).
?DOC(
" Checks if two graphs are isomorphic (structurally identical).\n"
"\n"
" Two graphs are isomorphic if there exists a bijection between their vertices\n"
" that preserves adjacency. This function uses a backtracking algorithm\n"
" with degree-sequence pruning.\n"
"\n"
" **Note:** Graph isomorphism is a computationally hard problem. This\n"
" implementation is suitable for small to medium-sized graphs.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Triangle (0-1-2) is isomorphic to (10-20-30)\n"
" let g1 = yog.from_simple_edges(Undirected, [#(0, 1), #(1, 2), #(2, 0)])\n"
" let g2 = yog.from_simple_edges(Undirected, [#(10, 20), #(20, 30), #(30, 10)])\n"
" operation.is_isomorphic(g1, g2) // True\n"
" ```\n"
).
-spec is_isomorphic(yog@model:graph(WMF, WMG), yog@model:graph(WMF, WMG)) -> boolean().
is_isomorphic(First, Second) ->
First_order = yog@model:order(First),
Second_order = yog@model:order(Second),
gleam@bool:guard(
First_order /= Second_order,
false,
fun() ->
gleam@bool:guard(
yog@model:edge_count(First) /= yog@model:edge_count(Second),
false,
fun() ->
First_degrees = begin
_pipe = degree_sequence(First),
gleam@list:sort(_pipe, fun compare_degrees/2)
end,
Second_degrees = begin
_pipe@1 = degree_sequence(Second),
gleam@list:sort(_pipe@1, fun compare_degrees/2)
end,
gleam@bool:guard(
First_degrees /= Second_degrees,
false,
fun() -> attempt_isomorphism(First, Second) end
)
end
)
end
).