Current section
Files
Jump to
Current section
Files
src/yog@property@structure.erl
-module(yog@property@structure).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/property/structure.gleam").
-export([is_arborescence/1, arborescence_root/1, is_regular/2, is_planar/1, is_chordal/1, is_complete/1, is_strongly_connected/1, is_connected/1, is_tree/1, is_weakly_connected/1]).
-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(
" Structural properties of graphs.\n"
"\n"
" This module provides checks for various graph classes and regularities.\n"
"\n"
" ## Algorithms\n"
"\n"
" | Problem | Function | Complexity |\n"
" |---------|----------|------------|\n"
" | Tree check | `is_tree/1` | O(V + E) |\n"
" | Arborescence check | `is_arborescence/1` | O(V + E) |\n"
" | Complete graph check | `is_complete/1` | O(V) |\n"
" | Regular graph check | `is_regular/2` | O(V) |\n"
" | Connected check | `is_connected/1` | O(V + E) |\n"
" | Strongly connected check | `is_strongly_connected/1` | O(V + E) |\n"
" | Weakly connected check | `is_weakly_connected/1` | O(V + E) |\n"
" | Planar check | `is_planar/1` | O(V + E) |\n"
" | Chordal check | `is_chordal/1` | O(V + E) |\n"
"\n"
" ## Key Concepts\n"
"\n"
" - **Tree**: Connected acyclic undirected graph.\n"
" - **Arborescence**: Directed tree with a unique root.\n"
" - **Complete Graph (Kn)**: Every pair of distinct vertices is connected by an edge.\n"
" - **Regular Graph**: Every vertex has the same degree k.\n"
).
-file("src/yog/property/structure.gleam", 58).
?DOC(
" Checks if the graph is an arborescence (directed tree with a single root).\n"
"\n"
" A directed graph is an arborescence iff:\n"
" - It has n nodes and n-1 edges\n"
" - Exactly one node has in-degree 0 (the root)\n"
" - All other nodes have in-degree 1\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_arborescence(yog@model:graph(any(), any())) -> boolean().
is_arborescence(Graph) ->
case erlang:element(2, Graph) of
directed ->
N = yog@model:node_count(Graph),
case (N > 0) andalso (yog@model:edge_count(Graph) =:= (N - 1)) of
false ->
false;
true ->
Nodes = yog@model:all_nodes(Graph),
{Roots@1, Valid_non_roots} = begin
gleam@list:fold(
Nodes,
{[], 0},
fun(_use0, Node) ->
{Roots, Valid} = _use0,
case yog@model:in_degree(Graph, Node) of
0 ->
{[Node | Roots], Valid};
1 ->
{Roots, Valid + 1};
_ ->
{Roots, Valid}
end
end
)
end,
(erlang:length(Roots@1) =:= 1) andalso (Valid_non_roots =:= (N
- 1))
end;
undirected ->
false
end.
-file("src/yog/property/structure.gleam", 85).
?DOC(
" Finds the root of an arborescence.\n"
"\n"
" Returns `Some(root)` if the graph is an arborescence, `None` otherwise.\n"
).
-spec arborescence_root(yog@model:graph(any(), any())) -> gleam@option:option(integer()).
arborescence_root(Graph) ->
case is_arborescence(Graph) of
false ->
none;
true ->
_pipe = yog@model:all_nodes(Graph),
_pipe@1 = gleam@list:find(
_pipe,
fun(Node) ->
gleam@list:is_empty(yog@model:predecessors(Graph, Node))
end
),
gleam@option:from_result(_pipe@1)
end.
-file("src/yog/property/structure.gleam", 119).
?DOC(
" Checks if the graph is k-regular (every node has degree exactly k).\n"
"\n"
" For directed graphs, both in-degree and out-degree must equal k.\n"
"\n"
" **Time Complexity:** O(V)\n"
).
-spec is_regular(yog@model:graph(any(), any()), integer()) -> boolean().
is_regular(Graph, K) ->
Nodes = yog@model:all_nodes(Graph),
case gleam@list:is_empty(Nodes) of
true ->
true;
false ->
case erlang:element(2, Graph) of
undirected ->
gleam@list:all(
Nodes,
fun(U) -> yog@model:degree(Graph, U) =:= K end
);
directed ->
gleam@list:all(
Nodes,
fun(U@1) ->
(yog@model:out_degree(Graph, U@1) =:= K) andalso (yog@model:in_degree(
Graph,
U@1
)
=:= K)
end
)
end
end.
-file("src/yog/property/structure.gleam", 188).
?DOC(
" Checks if the graph is planar (necessary conditions only).\n"
"\n"
" Implements necessary checks: |E| ≤ 3|V| - 6 and bipartite |E| ≤ 2|V| - 4.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_planar(yog@model:graph(any(), any())) -> boolean().
is_planar(Graph) ->
N = yog@model:node_count(Graph),
E = yog@model:edge_count(Graph),
case N =< 4 of
true ->
true;
false ->
case E > ((3 * N) - 6) of
true ->
false;
false ->
case yog@property@bipartite:is_bipartite(Graph) andalso (E > ((2
* N)
- 4)) of
true ->
false;
false ->
true
end
end
end.
-file("src/yog/property/structure.gleam", 299).
-spec pop_max_weight_node(
gleam@dict:dict(integer(), gleam@set:set(integer())),
integer()
) -> {integer(),
gleam@dict:dict(integer(), gleam@set:set(integer())),
integer()}.
pop_max_weight_node(Buckets, Max_weight) ->
case Max_weight < 0 of
true ->
erlang:error(#{gleam_error => panic,
message => <<"Bucket queue empty - no more nodes to process"/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/property/structure"/utf8>>,
function => <<"pop_max_weight_node"/utf8>>,
line => 304});
false ->
case gleam_stdlib:map_get(Buckets, Max_weight) of
{error, _} ->
pop_max_weight_node(Buckets, Max_weight - 1);
{ok, Node_set} ->
case gleam@set:size(Node_set) of
0 ->
pop_max_weight_node(Buckets, Max_weight - 1);
_ ->
Node@1 = case begin
_pipe = gleam@set:to_list(Node_set),
gleam@list:first(_pipe)
end of
{ok, Node} -> Node;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/property/structure"/utf8>>,
function => <<"pop_max_weight_node"/utf8>>,
line => 312,
value => _assert_fail,
start => 8990,
'end' => 9047,
pattern_start => 9001,
pattern_end => 9009})
end,
New_set = gleam@set:delete(Node_set, Node@1),
New_buckets = gleam@dict:insert(
Buckets,
Max_weight,
New_set
),
{Node@1, New_buckets, Max_weight}
end
end
end.
-file("src/yog/property/structure.gleam", 237).
-spec do_mcs(
yog@model:graph(any(), any()),
gleam@dict:dict(integer(), integer()),
list(integer()),
gleam@set:set(integer()),
gleam@dict:dict(integer(), gleam@set:set(integer())),
integer()
) -> list(integer()).
do_mcs(Graph, Weights, Order, Remaining, Buckets, Max_weight) ->
case gleam@set:size(Remaining) of
0 ->
lists:reverse(Order);
_ ->
{V, New_buckets, New_max_weight} = pop_max_weight_node(
Buckets,
Max_weight
),
Neighbors = yog@model:neighbor_ids(Graph, V),
{New_weights, New_buckets2, Updated_max_weight} = begin
gleam@list:fold(
Neighbors,
{Weights, New_buckets, New_max_weight},
fun(_use0, U) ->
{W_acc, B_acc, Max_w_acc} = _use0,
case gleam@set:contains(Remaining, U) of
false ->
{W_acc, B_acc, Max_w_acc};
true ->
Old_weight@1 = case gleam_stdlib:map_get(
W_acc,
U
) of
{ok, Old_weight} -> Old_weight;
_assert_fail ->
erlang:error(
#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/property/structure"/utf8>>,
function => <<"do_mcs"/utf8>>,
line => 261,
value => _assert_fail,
start => 7573,
'end' => 7619,
pattern_start => 7584,
pattern_end => 7598}
)
end,
New_weight = Old_weight@1 + 1,
W_acc2 = gleam@dict:insert(W_acc, U, New_weight),
Old_bucket = case gleam_stdlib:map_get(
B_acc,
Old_weight@1
) of
{ok, B} ->
B;
{error, _} ->
gleam@set:new()
end,
New_bucket = case gleam_stdlib:map_get(
B_acc,
New_weight
) of
{ok, B@1} ->
B@1;
{error, _} ->
gleam@set:new()
end,
B_acc2 = begin
_pipe = B_acc,
_pipe@1 = gleam@dict:insert(
_pipe,
Old_weight@1,
gleam@set:delete(Old_bucket, U)
),
gleam@dict:insert(
_pipe@1,
New_weight,
gleam@set:insert(New_bucket, U)
)
end,
Max_w_acc2 = gleam@int:max(
Max_w_acc,
New_weight
),
{W_acc2, B_acc2, Max_w_acc2}
end
end
)
end,
do_mcs(
Graph,
New_weights,
[V | Order],
gleam@set:delete(Remaining, V),
New_buckets2,
Updated_max_weight
)
end.
-file("src/yog/property/structure.gleam", 222).
-spec mcs_ordering(yog@model:graph(any(), any())) -> list(integer()).
mcs_ordering(Graph) ->
Nodes = yog@model:all_nodes(Graph),
N = erlang:length(Nodes),
case N of
0 ->
[];
_ ->
Buckets = maps:from_list([{0, gleam@set:from_list(Nodes)}]),
Weights = gleam@list:fold(
Nodes,
maps:new(),
fun(Acc, Id) -> gleam@dict:insert(Acc, Id, 0) end
),
do_mcs(Graph, Weights, [], gleam@set:from_list(Nodes), Buckets, 0)
end.
-file("src/yog/property/structure.gleam", 341).
-spec is_clique(yog@model:graph(any(), any()), list(integer())) -> boolean().
is_clique(Graph, Nodes) ->
gleam@list:all(
Nodes,
fun(U) -> gleam@list:all(Nodes, fun(V) -> case U =:= V of
true ->
true;
false ->
yog@model:has_edge(Graph, U, V)
end end) end
).
-file("src/yog/property/structure.gleam", 322).
-spec is_peo(yog@model:graph(any(), any()), list(integer())) -> boolean().
is_peo(Graph, Order) ->
Pos_map = gleam@list:index_fold(
Order,
maps:new(),
fun(Acc, Node, Index) -> gleam@dict:insert(Acc, Node, Index) end
),
gleam@list:all(
Order,
fun(V) ->
Earlier_neighbors = begin
_pipe = yog@model:neighbor_ids(Graph, V),
gleam@list:filter(
_pipe,
fun(U) ->
U_pos@1 = case gleam_stdlib:map_get(Pos_map, U) of
{ok, U_pos} -> U_pos;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/property/structure"/utf8>>,
function => <<"is_peo"/utf8>>,
line => 332,
value => _assert_fail,
start => 9576,
'end' => 9619,
pattern_start => 9587,
pattern_end => 9596})
end,
V_pos@1 = case gleam_stdlib:map_get(Pos_map, V) of
{ok, V_pos} -> V_pos;
_assert_fail@1 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/property/structure"/utf8>>,
function => <<"is_peo"/utf8>>,
line => 333,
value => _assert_fail@1,
start => 9628,
'end' => 9671,
pattern_start => 9639,
pattern_end => 9648})
end,
U_pos@1 < V_pos@1
end
)
end,
is_clique(Graph, Earlier_neighbors)
end
).
-file("src/yog/property/structure.gleam", 211).
?DOC(
" Checks if the graph is chordal using Maximum Cardinality Search.\n"
"\n"
" A chordal graph is one where every induced cycle has length 3.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_chordal(yog@model:graph(any(), any())) -> boolean().
is_chordal(Graph) ->
case erlang:element(2, Graph) of
undirected ->
is_peo(Graph, mcs_ordering(Graph));
directed ->
false
end.
-file("src/yog/property/structure.gleam", 350).
-spec has_no_self_loops(yog@model:graph(any(), any())) -> boolean().
has_no_self_loops(Graph) ->
_pipe = yog@model:all_nodes(Graph),
gleam@list:all(_pipe, fun(U) -> not yog@model:has_edge(Graph, U, U) end).
-file("src/yog/property/structure.gleam", 99).
?DOC(
" Checks if the graph is complete (every pair of distinct nodes is connected).\n"
"\n"
" **Time Complexity:** O(V)\n"
).
-spec is_complete(yog@model:graph(any(), any())) -> boolean().
is_complete(Graph) ->
N = yog@model:node_count(Graph),
case N =< 1 of
true ->
true;
false ->
E = yog@model:edge_count(Graph),
Expected = case erlang:element(2, Graph) of
undirected ->
(N * (N - 1)) div 2;
directed ->
N * (N - 1)
end,
(E =:= Expected) andalso has_no_self_loops(Graph)
end.
-file("src/yog/property/structure.gleam", 156).
?DOC(
" Checks if a directed graph is strongly connected.\n"
"\n"
" For undirected graphs, falls back to `is_connected/1`.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_strongly_connected(yog@model:graph(any(), any())) -> boolean().
is_strongly_connected(Graph) ->
case erlang:element(2, Graph) of
undirected ->
is_connected(Graph);
directed ->
case yog@connectivity:strongly_connected_components(Graph) of
[_] ->
true;
[] ->
true;
_ ->
false
end
end.
-file("src/yog/property/structure.gleam", 140).
?DOC(
" Checks if the graph is connected.\n"
"\n"
" For undirected graphs, every node is reachable from every other node.\n"
" For directed graphs, this checks for strong connectivity.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_connected(yog@model:graph(any(), any())) -> boolean().
is_connected(Graph) ->
case erlang:element(2, Graph) of
undirected ->
case yog@connectivity:connected_components(Graph) of
[_] ->
true;
[] ->
true;
_ ->
false
end;
directed ->
is_strongly_connected(Graph)
end.
-file("src/yog/property/structure.gleam", 39).
?DOC(
" Checks if the graph is a tree (connected and acyclic).\n"
" Works for undirected graphs.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_tree(yog@model:graph(any(), any())) -> boolean().
is_tree(Graph) ->
case erlang:element(2, Graph) of
undirected ->
N = yog@model:node_count(Graph),
E = yog@model:edge_count(Graph),
((N > 0) andalso (E =:= (N - 1))) andalso is_connected(Graph);
directed ->
false
end.
-file("src/yog/property/structure.gleam", 172).
?DOC(
" Checks if a directed graph is weakly connected.\n"
"\n"
" For undirected graphs, falls back to `is_connected/1`.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec is_weakly_connected(yog@model:graph(any(), any())) -> boolean().
is_weakly_connected(Graph) ->
case erlang:element(2, Graph) of
undirected ->
is_connected(Graph);
directed ->
case yog@connectivity:weakly_connected_components(Graph) of
[_] ->
true;
[] ->
true;
_ ->
false
end
end.