Current section
Files
Jump to
Current section
Files
src/yog@generator@random.erl
-module(yog@generator@random).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/generator/random.gleam").
-export([erdos_renyi_gnp_with_type/4, erdos_renyi_gnp/3, erdos_renyi_gnm_with_type/4, erdos_renyi_gnm/3, watts_strogatz_with_type/5, watts_strogatz/4, random_tree_with_type/3, random_tree/2, sbm_with_type/6, sbm/5, rmat_with_type/5, rmat/4, geometric_with_type/4, geometric/3, dcsbm_with_type/7, dcsbm/6, hsbm_with_type/7, hsbm/6, kronecker/4, barabasi_albert_with_type/4, barabasi_albert/3, random_regular_with_type/4, random_regular/3, configuration_model/2, randomize_degree_sequence/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(
" Stochastic graph generators for random graph models.\n"
"\n"
" Random generators use randomness to model real-world networks with properties\n"
" like scale-free distributions, small-world effects, and community structure.\n"
"\n"
" ## Available Generators\n"
"\n"
" | Generator | Model | Complexity | Key Property |\n"
" |-----------|-------|------------|--------------|\n"
" | `erdos_renyi_gnp` | G(n, p) | O(n²) | Each edge with probability p |\n"
" | `erdos_renyi_gnm` | G(n, m) | O(m) | Exactly m random edges |\n"
" | `barabasi_albert` | Preferential | O(nm) | Scale-free (power-law degrees) |\n"
" | `watts_strogatz` | Small-world | O(nk) | High clustering + short paths |\n"
" | `random_tree` | Uniform tree | O(n²) | Uniformly random spanning tree |\n"
" | `random_regular` | d-regular | O(nd) | All nodes have degree d |\n"
" | `sbm` | SBM | O(n²) | Community structure |\n"
" | `dcsbm` | DCSBM | O(n²) | Community + Degree control |\n"
" | `hsbm` | Hierarchical | O(n²) | Nested community structure |\n"
" | `configuration_model` | Fixed Degree | O(M) | Exact degree sequence |\n"
" | `rmat` | R-MAT | O(E log V) | Fast Kronecker variant |\n"
" | `kronecker` | Kronecker | O(E log V) | Recursive matrix expansion |\n"
" | `geometric` | RGG | O(n²) | Distance-based edges |\n"
"\n"
" ## Quick Start\n"
"\n"
" ```gleam\n"
" import yog/generator/random\n"
" import yog/model\n"
"\n"
" pub fn main() {\n"
" // Random network models\n"
" let sparse = random.erdos_renyi_gnp(100, 0.05, seed: None) // Sparse random (p=5%)\n"
" let exact = random.erdos_renyi_gnm(50, 100, seed: None) // Exactly 100 edges\n"
" let scale_free = random.barabasi_albert(1000, 3, seed: None) // Scale-free network\n"
" let small_world = random.watts_strogatz(100, 6, 0.1, seed: None) // Small-world (10% rewire)\n"
" let tree = random.random_tree(50, seed: None) // Random spanning tree\n"
" let regular = random.random_regular(20, 3, seed: None) // 3-regular graph\n"
" }\n"
" ```\n"
"\n"
" ## Network Models Explained\n"
"\n"
" ### Erdős-Rényi G(n, p)\n"
" - Each possible edge included independently with probability p\n"
" - Expected edges: p × n(n-1)/2 (undirected) or p × n(n-1) (directed)\n"
" - Phase transition at p = 1/n (giant component emerges)\n"
" - **Use for**: Random network modeling, percolation studies\n"
"\n"
" ### Erdős-Rényi G(n, m)\n"
" - Exactly m edges added uniformly at random\n"
" - Uniform distribution over all graphs with n nodes and m edges\n"
" - **Use for**: Fixed edge count requirements, specific density testing\n"
"\n"
" ### Barabási-Albert (Preferential Attachment)\n"
" - Starts with m₀ nodes, adds nodes connecting to m existing nodes\n"
" - New nodes prefer high-degree nodes (\"rich get richer\")\n"
" - Power-law degree distribution: P(k) ~ k^(-3)\n"
" - **Use for**: Social networks, citation networks, web graphs\n"
"\n"
" ### Watts-Strogatz (Small-World)\n"
" - Starts with ring lattice (high clustering)\n"
" - Rewires edges with probability p (creates shortcuts)\n"
" - Balances local clustering with global connectivity\n"
" - **Use for**: Social networks, neural networks, epidemic modeling\n"
"\n"
" ### Random Tree\n"
" - Builds tree by connecting new nodes to random existing nodes\n"
" - Produces uniform distribution over all labeled trees\n"
" - **Use for**: Spanning trees, hierarchical structures\n"
"\n"
" ### Stochastic Block Model (SBM)\n"
" - Nodes assigned to communities\n"
" - Edge probability depends on community membership\n"
" - **Use for**: Community detection testing, modular networks\n"
"\n"
" ## References\n"
"\n"
" - [Erdős-Rényi Model](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model)\n"
" - [Barabási-Albert Model](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model)\n"
" - [Watts-Strogatz Model](https://en.wikipedia.org/wiki/Watts%E2%80%93Strogatz_model)\n"
" - [Scale-Free Networks](https://en.wikipedia.org/wiki/Scale-free_network)\n"
" - [Small-World Network](https://en.wikipedia.org/wiki/Small-world_network)\n"
" - [Stochastic Block Model](https://en.wikipedia.org/wiki/Stochastic_block_model)\n"
" - [NetworkX Random Graphs](https://networkx.org/documentation/stable/reference/generators.html#random-graphs)\n"
).
-file("src/yog/generator/random.gleam", 466).
-spec select_preferential_targets_seeded(
list(integer()),
integer(),
gleam@set:set(integer()),
yog@internal@random:rng()
) -> {gleam@set:set(integer()), yog@internal@random:rng()}.
select_preferential_targets_seeded(Degree_list, M, Selected, Rng) ->
case (gleam@set:size(Selected) >= M) orelse gleam@list:is_empty(Degree_list) of
true ->
{Selected, Rng};
false ->
List_size = erlang:length(Degree_list),
{Index, New_rng} = yog@internal@random:next_int(Rng, List_size),
case yog@internal@util:list_at(Degree_list, Index) of
{ok, Target} ->
New_selected = gleam@set:insert(Selected, Target),
select_preferential_targets_seeded(
Degree_list,
M,
New_selected,
New_rng
);
{error, _} ->
{Selected, New_rng}
end
end.
-file("src/yog/generator/random.gleam", 586).
-spec add_random_edge_not_to_seeded(
yog@model:graph(nil, integer()),
integer(),
integer(),
yog@internal@random:rng()
) -> {yog@model:graph(nil, integer()), yog@internal@random:rng()}.
add_random_edge_not_to_seeded(Graph, From, N, Rng) ->
{To, New_rng} = yog@internal@random:next_int(Rng, N),
case To =:= From of
true ->
add_random_edge_not_to_seeded(Graph, From, N, New_rng);
false ->
Neighbors = yog@model:successors(Graph, From),
Neighbor_ids = gleam@list:map(
Neighbors,
fun(Pair) -> erlang:element(1, Pair) end
),
case gleam@list:contains(Neighbor_ids, To) of
true ->
add_random_edge_not_to_seeded(Graph, From, N, New_rng);
false ->
New_graph = yog@model:add_edge_ensure(
Graph,
From,
To,
1,
nil
),
{New_graph, New_rng}
end
end.
-file("src/yog/generator/random.gleam", 676).
-spec build_random_tree_seeded(
yog@model:graph(nil, integer()),
integer(),
gleam@set:set(integer()),
integer(),
yog@internal@random:rng()
) -> yog@model:graph(nil, integer()).
build_random_tree_seeded(Graph, N, In_tree, Next_node, Rng) ->
case Next_node >= N of
true ->
Graph;
false ->
Tree_list = gleam@set:to_list(In_tree),
Tree_size = erlang:length(Tree_list),
{Index, New_rng} = yog@internal@random:next_int(Rng, Tree_size),
case yog@internal@util:list_at(Tree_list, Index) of
{ok, Parent} ->
New_graph = yog@model:add_edge_ensure(
Graph,
Parent,
Next_node,
1,
nil
),
New_in_tree = gleam@set:insert(In_tree, Next_node),
build_random_tree_seeded(
New_graph,
N,
New_in_tree,
Next_node + 1,
New_rng
);
{error, _} ->
Graph
end
end.
-file("src/yog/generator/random.gleam", 815).
-spec create_ring_based_regular(integer(), integer(), yog@model:graph_type()) -> yog@model:graph(nil, integer()).
create_ring_based_regular(N, D, Graph_type) ->
Base = yog@model:new(Graph_type),
Graph = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
Base,
fun(G, I) -> yog@model:add_node(G, I, nil) end
)
end,
case D of
0 ->
Graph;
_ ->
Half = D div 2,
Graph_with_ring = gleam@list:fold(
yog@internal@util:range(0, N - 1),
Graph,
fun(G@1, I@1) ->
gleam@list:fold(
yog@internal@util:range(1, Half),
G@1,
fun(G2, K) ->
J = case N of
0 -> 0;
Gleam@denominator -> (I@1 + K) rem Gleam@denominator
end,
case yog@model:add_edge(G2, I@1, J, 0) of
{ok, G3} ->
G3;
{error, _} ->
G2
end
end
)
end
),
case (gleam@int:remainder(D, 2) =:= {ok, 1}) andalso (gleam@int:remainder(
N,
2
)
=:= {ok, 0}) of
true ->
gleam@list:fold(
yog@internal@util:range(0, (N div 2) - 1),
Graph_with_ring,
fun(G@2, I@2) ->
case yog@model:add_edge(
G@2,
I@2,
I@2 + (N div 2),
0
) of
{ok, G2@1} ->
G2@1;
{error, _} ->
G@2
end
end
);
false ->
Graph_with_ring
end
end.
-file("src/yog/generator/random.gleam", 906).
-spec normalize_pair(integer(), integer()) -> {integer(), integer()}.
normalize_pair(A, B) ->
case A < B of
true ->
{A, B};
false ->
{B, A}
end.
-file("src/yog/generator/random.gleam", 913).
-spec find_valid_partner(
list(integer()),
integer(),
gleam@set:set({integer(), integer()})
) -> {ok, {integer(), list(integer())}} | {error, nil}.
find_valid_partner(Stubs, Target, Used) ->
case Stubs of
[] ->
{error, nil};
[First | Rest] ->
Edge = normalize_pair(Target, First),
case (First =:= Target) orelse gleam@set:contains(Used, Edge) of
true ->
case find_valid_partner(Rest, Target, Used) of
{ok, {Partner, Remaining}} ->
{ok, {Partner, [First | Remaining]}};
{error, _} ->
{error, nil}
end;
false ->
{ok, {First, Rest}}
end
end.
-file("src/yog/generator/random.gleam", 885).
-spec greedy_match(
list(integer()),
list({integer(), integer()}),
gleam@set:set({integer(), integer()})
) -> {ok, list({integer(), integer()})} | {error, nil}.
greedy_match(Stubs, Edges, Used) ->
case Stubs of
[] ->
{ok, Edges};
[_] ->
{error, nil};
[A | Rest] ->
case find_valid_partner(Rest, A, Used) of
{ok, {B, Remaining}} ->
Edge = normalize_pair(A, B),
greedy_match(
Remaining,
[Edge | Edges],
gleam@set:insert(Used, Edge)
);
{error, _} ->
{error, nil}
end
end.
-file("src/yog/generator/random.gleam", 858).
-spec try_pairing(list(integer()), integer(), yog@model:graph_type()) -> {ok,
yog@model:graph(nil, integer())} |
{error, nil}.
try_pairing(Stubs, N, Graph_type) ->
case greedy_match(Stubs, [], gleam@set:new()) of
{ok, Edges} ->
Base = yog@model:new(Graph_type),
Graph = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
Base,
fun(G, I) -> yog@model:add_node(G, I, nil) end
)
end,
Final_graph = begin
_pipe@1 = Edges,
gleam@list:fold(
_pipe@1,
Graph,
fun(G@1, Edge) ->
{From, To} = Edge,
yog@model:add_edge_ensure(G@1, From, To, 1, nil)
end
)
end,
{ok, Final_graph};
{error, _} ->
{error, nil}
end.
-file("src/yog/generator/random.gleam", 1158).
-spec power_of_two(integer()) -> integer().
power_of_two(K) ->
case K =< 0 of
true ->
1;
false ->
2 * power_of_two(K - 1)
end.
-file("src/yog/generator/random.gleam", 1151).
-spec find_power_of_two(integer(), integer()) -> integer().
find_power_of_two(N, K) ->
case power_of_two(K) >= N of
true ->
K;
false ->
find_power_of_two(N, K + 1)
end.
-file("src/yog/generator/random.gleam", 1165).
-spec rmat_sample_edge(
integer(),
float(),
float(),
float(),
integer(),
integer(),
yog@internal@random:rng()
) -> {integer(), integer(), yog@internal@random:rng()}.
rmat_sample_edge(K, A, B, C, X, Y, Rng) ->
case K =< 0 of
true ->
{X, Y, Rng};
false ->
{R, Next_rng} = yog@internal@random:next_float(Rng),
Offset = power_of_two(K - 1),
{Nx, Ny} = case R of
_ when R < A ->
{X, Y};
_ when R < (A + B) ->
{X, Y + Offset};
_ when R < ((A + B) + C) ->
{X + Offset, Y};
_ ->
{X + Offset, Y + Offset}
end,
rmat_sample_edge(K - 1, A, B, C, Nx, Ny, Next_rng)
end.
-file("src/yog/generator/random.gleam", 1304).
-spec assign_communities(integer(), integer()) -> gleam@dict:dict(integer(), integer()).
assign_communities(N, K) ->
Base_size = case K of
0 -> 0;
Gleam@denominator -> N div Gleam@denominator
end,
Remainder = case K of
0 -> 0;
Gleam@denominator@1 -> N rem Gleam@denominator@1
end,
_pipe = yog@internal@util:range(0, N - 1),
_pipe@1 = gleam@list:fold(
_pipe,
{maps:new(), 0, 0},
fun(State, Node) ->
{Dict, Current_comm, Count} = State,
Comm_size = case Current_comm < Remainder of
true ->
Base_size + 1;
false ->
Base_size
end,
New_dict = gleam@dict:insert(Dict, Node, Current_comm),
case (Count + 1) >= Comm_size of
true ->
{New_dict, Current_comm + 1, 0};
false ->
{New_dict, Current_comm, Count + 1}
end
end
),
(fun(Result_tuple) -> erlang:element(1, Result_tuple) end)(_pipe@1).
-file("src/yog/generator/random.gleam", 1426).
-spec generate_default_thetas(integer()) -> list(float()).
generate_default_thetas(N) ->
Raw = begin
_pipe = yog@internal@util:range(1, N),
gleam@list:map(
_pipe,
fun(I) ->
F = erlang:float(I),
_pipe@1 = gleam@float:square_root(F),
_pipe@2 = gleam@result:map(_pipe@1, fun(S) -> case S of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator -> 1.0 / Gleam@denominator
end end),
gleam@result:unwrap(_pipe@2, 1.0)
end
)
end,
Sum = gleam@list:fold(Raw, +0.0, fun gleam@float:add/2),
Mean = case erlang:float(N) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator@1 -> Sum / Gleam@denominator@1
end,
gleam@list:map(Raw, fun(X) -> case Mean of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator@2 -> X / Gleam@denominator@2
end end).
-file("src/yog/generator/random.gleam", 1441).
-spec list_at_float(list(float()), integer()) -> float().
list_at_float(Lst, Index) ->
_pipe = yog@internal@util:list_at(Lst, Index),
gleam@result:unwrap(_pipe, 1.0).
-file("src/yog/generator/random.gleam", 1548).
-spec power_int(integer(), integer()) -> integer().
power_int(Base, Exp) ->
case Exp =< 0 of
true ->
1;
false ->
Base * power_int(Base, Exp - 1)
end.
-file("src/yog/generator/random.gleam", 1540).
-spec find_lca_recursive(integer(), integer(), integer(), integer()) -> integer().
find_lca_recursive(Bu, Bv, Branching, Level) ->
P = power_int(Branching, Level),
case (case P of
0 -> 0;
Gleam@denominator -> Bu div Gleam@denominator
end) =:= (case P of
0 -> 0;
Gleam@denominator@1 -> Bv div Gleam@denominator@1
end) of
true ->
Level;
false ->
find_lca_recursive(Bu, Bv, Branching, Level + 1)
end.
-file("src/yog/generator/random.gleam", 1531).
-spec hsbm_lca_level(integer(), integer(), integer(), integer()) -> integer().
hsbm_lca_level(U, V, Leaf_size, Branching) ->
Bu = case Leaf_size of
0 -> 0;
Gleam@denominator -> U div Gleam@denominator
end,
Bv = case Leaf_size of
0 -> 0;
Gleam@denominator@1 -> V div Gleam@denominator@1
end,
case Bu =:= Bv of
true ->
0;
false ->
find_lca_recursive(Bu, Bv, Branching, 1)
end.
-file("src/yog/generator/random.gleam", 1627).
-spec pair_stubs(list(integer())) -> list({integer(), integer()}).
pair_stubs(Stubs) ->
case Stubs of
[] ->
[];
[_] ->
[];
[A, B | Rest] ->
[{A, B} | pair_stubs(Rest)]
end.
-file("src/yog/generator/random.gleam", 1675).
-spec create_nodes(yog@model:graph(nil, STG), integer()) -> yog@model:graph(nil, STG).
create_nodes(Graph, N) ->
case N =< 0 of
true ->
Graph;
false ->
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
Graph,
fun(G, I) -> yog@model:add_node(G, I, nil) end
)
end.
-file("src/yog/generator/random.gleam", 137).
?DOC(" Generates an Erdős-Rényi G(n, p) graph with specified graph type.\n").
-spec erdos_renyi_gnp_with_type(
integer(),
float(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
erdos_renyi_gnp_with_type(N, P, Graph_type, Seed) ->
case ((N =< 0) orelse (P < +0.0)) orelse (P > 1.0) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
case Graph_type of
undirected ->
{Result, _} = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
{Graph, Rng},
fun(State, I) ->
{G, Rng_state} = State,
_pipe@1 = yog@internal@util:range(I + 1, N - 1),
gleam@list:fold(
_pipe@1,
{G, Rng_state},
fun(Inner_state, J) ->
{Inner_g, Inner_rng} = Inner_state,
{Rand_val, New_rng} = yog@internal@random:next_float(
Inner_rng
),
case Rand_val < P of
true ->
{yog@model:add_edge_ensure(
Inner_g,
I,
J,
1,
nil
),
New_rng};
false ->
{Inner_g, New_rng}
end
end
)
end
)
end,
Result;
directed ->
{Result@1, _} = begin
_pipe@2 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@2,
{Graph, Rng},
fun(State@1, I@1) ->
{G@1, Rng_state@1} = State@1,
_pipe@3 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@3,
{G@1, Rng_state@1},
fun(Inner_state@1, J@1) ->
{Inner_g@1, Inner_rng@1} = Inner_state@1,
case I@1 =:= J@1 of
true ->
{Inner_g@1, Inner_rng@1};
false ->
{Rand_val@1, New_rng@1} = yog@internal@random:next_float(
Inner_rng@1
),
case Rand_val@1 < P of
true ->
{yog@model:add_edge_ensure(
Inner_g@1,
I@1,
J@1,
1,
nil
),
New_rng@1};
false ->
{Inner_g@1, New_rng@1}
end
end
end
)
end
)
end,
Result@1
end
end.
-file("src/yog/generator/random.gleam", 128).
?DOC(
" Generates a random graph using the Erdős-Rényi G(n, p) model.\n"
"\n"
" Each possible edge is included independently with probability p.\n"
" For undirected graphs, each unordered pair is considered once.\n"
"\n"
" **Time Complexity:** O(n²)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Sparse random graph with seed for reproducibility\n"
" let sparse = random.erdos_renyi_gnp(100, 0.05, seed: Some(42))\n"
"\n"
" // Dense random graph\n"
" let dense = random.erdos_renyi_gnp(50, 0.8, seed: None)\n"
" ```\n"
"\n"
" ## Properties\n"
"\n"
" - Expected number of edges: p × n(n-1)/2 (undirected) or p × n(n-1) (directed)\n"
" - Phase transition at p = 1/n (giant component emerges)\n"
"\n"
" ## Use Cases\n"
"\n"
" - Random network modeling\n"
" - Percolation studies\n"
" - Average-case algorithm analysis\n"
).
-spec erdos_renyi_gnp(integer(), float(), gleam@option:option(integer())) -> yog@model:graph(nil, integer()).
erdos_renyi_gnp(N, P, Seed) ->
erdos_renyi_gnp_with_type(N, P, undirected, Seed).
-file("src/yog/generator/random.gleam", 251).
?DOC(" Generates an Erdős-Rényi G(n, m) graph with specified graph type.\n").
-spec erdos_renyi_gnm_with_type(
integer(),
integer(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
erdos_renyi_gnm_with_type(N, M, Graph_type, Seed) ->
case (N =< 0) orelse (M < 0) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
Max_edges = case Graph_type of
undirected ->
(N * (N - 1)) div 2;
directed ->
N * (N - 1)
end,
Actual_m = gleam@int:min(M, Max_edges),
All_edges = case Graph_type of
undirected ->
lists:append(
begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:map(
_pipe,
fun(I) ->
_pipe@1 = yog@internal@util:range(
I + 1,
N - 1
),
gleam@list:map(
_pipe@1,
fun(J) -> {I, J} end
)
end
)
end
);
directed ->
lists:append(
begin
_pipe@2 = yog@internal@util:range(0, N - 1),
gleam@list:map(
_pipe@2,
fun(I@1) ->
_pipe@3 = yog@internal@util:range(0, N - 1),
_pipe@4 = gleam@list:filter(
_pipe@3,
fun(J@1) -> I@1 /= J@1 end
),
gleam@list:map(
_pipe@4,
fun(J@2) -> {I@1, J@2} end
)
end
)
end
)
end,
{Shuffled, _} = yog@internal@random:shuffle(All_edges, Rng),
Selected = gleam@list:take(Shuffled, Actual_m),
_pipe@5 = Selected,
gleam@list:fold(
_pipe@5,
Graph,
fun(G, Edge) ->
{I@2, J@3} = Edge,
yog@model:add_edge_ensure(G, I@2, J@3, 1, nil)
end
)
end.
-file("src/yog/generator/random.gleam", 242).
?DOC(
" Generates a random graph using the Erdős-Rényi G(n, m) model.\n"
"\n"
" Unlike G(n, p) which includes each edge independently with probability p,\n"
" G(n, m) guarantees exactly m edges in the resulting graph.\n"
"\n"
" **Time Complexity:** O(m) expected\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Random graph with 50 nodes and exactly 100 edges\n"
" let graph = random.erdos_renyi_gnm(50, 100, seed: Some(42))\n"
" ```\n"
"\n"
" ## Properties\n"
"\n"
" - Exactly m edges (unlike G(n,p) which has expected m edges)\n"
" - Uniform distribution over all graphs with n nodes and m edges\n"
"\n"
" ## Use Cases\n"
"\n"
" - Fixed edge count requirements\n"
" - Random graph benchmarking\n"
" - Testing with specific densities\n"
).
-spec erdos_renyi_gnm(integer(), integer(), gleam@option:option(integer())) -> yog@model:graph(nil, integer()).
erdos_renyi_gnm(N, M, Seed) ->
erdos_renyi_gnm_with_type(N, M, undirected, Seed).
-file("src/yog/generator/random.gleam", 534).
?DOC(" Generates a Watts-Strogatz graph with specified graph type.\n").
-spec watts_strogatz_with_type(
integer(),
integer(),
float(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
watts_strogatz_with_type(N, K, P, Graph_type, Seed) ->
case ((((N < 3) orelse (K < 2)) orelse (K >= N)) orelse (P < +0.0)) orelse (P
> 1.0) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
Half_k = K div 2,
{Result, _} = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
{Graph, Rng},
fun(State, I) ->
{G, Rng_state} = State,
_pipe@1 = yog@internal@util:range(1, Half_k),
gleam@list:fold(
_pipe@1,
{G, Rng_state},
fun(Inner_state, Offset) ->
{Acc, Inner_rng} = Inner_state,
{Rand_val, New_rng} = yog@internal@random:next_float(
Inner_rng
),
case Rand_val < P of
false ->
J = case N of
0 -> 0;
Gleam@denominator -> (I + Offset)
rem Gleam@denominator
end,
{yog@model:add_edge_ensure(
Acc,
I,
J,
1,
nil
),
New_rng};
true ->
add_random_edge_not_to_seeded(
Acc,
I,
N,
New_rng
)
end
end
)
end
)
end,
Result
end.
-file("src/yog/generator/random.gleam", 524).
?DOC(
" Generates a small-world network using the Watts-Strogatz model.\n"
"\n"
" Generates a graph with both high clustering (like regular lattices)\n"
" and short path lengths (like random graphs). Starts with a ring\n"
" lattice and rewires edges with probability p.\n"
"\n"
" **Time Complexity:** O(nk)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Small-world network: 100 nodes, 6 neighbors each, 10% rewiring\n"
" let graph = random.watts_strogatz(100, 6, 0.1, seed: Some(42))\n"
" ```\n"
"\n"
" ## Properties\n"
"\n"
" - High clustering coefficient\n"
" - Short average path length\n"
" - p=0: regular lattice, p=1: random graph\n"
"\n"
" ## Use Cases\n"
"\n"
" - Social network modeling (six degrees of separation)\n"
" - Neural network topology\n"
" - Epidemic spread modeling\n"
).
-spec watts_strogatz(
integer(),
integer(),
float(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
watts_strogatz(N, K, P, Seed) ->
watts_strogatz_with_type(N, K, P, undirected, Seed).
-file("src/yog/generator/random.gleam", 655).
?DOC(" Generates a random tree with specified graph type.\n").
-spec random_tree_with_type(
integer(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
random_tree_with_type(N, Graph_type, Seed) ->
case N < 2 of
true ->
create_nodes(yog@model:new(Graph_type), N);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
In_tree = gleam@set:from_list([0]),
build_random_tree_seeded(Graph, N, In_tree, 1, Rng)
end.
-file("src/yog/generator/random.gleam", 650).
?DOC(
" Generates a uniformly random tree on n nodes.\n"
"\n"
" Creates a tree by starting with node 0 and repeatedly connecting\n"
" new nodes to random nodes already in the tree. This produces a\n"
" uniform distribution over all labeled trees.\n"
"\n"
" **Time Complexity:** O(n²) expected\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let tree = random.random_tree(50, seed: Some(42))\n"
" // Random tree with 50 nodes, 49 edges\n"
" ```\n"
"\n"
" ## Properties\n"
"\n"
" - Exactly n-1 edges (tree property)\n"
" - Connected\n"
" - Acyclic\n"
" - Uniform distribution over all labeled trees\n"
"\n"
" ## Use Cases\n"
"\n"
" - Random spanning tree generation\n"
" - Tree algorithm testing\n"
" - Network topology generation\n"
" - Phylogenetic tree simulation\n"
).
-spec random_tree(integer(), gleam@option:option(integer())) -> yog@model:graph(nil, integer()).
random_tree(N, Seed) ->
random_tree_with_type(N, undirected, Seed).
-file("src/yog/generator/random.gleam", 968).
?DOC(" Generates an SBM graph with specified graph type.\n").
-spec sbm_with_type(
integer(),
integer(),
float(),
float(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
sbm_with_type(N, K, P_in, P_out, Graph_type, Seed) ->
case (((((N =< 0) orelse (K < 1)) orelse (P_in < +0.0)) orelse (P_in > 1.0))
orelse (P_out < +0.0))
orelse (P_out > 1.0) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
Communities = assign_communities(N, K),
case Graph_type of
undirected ->
{Result, _} = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
{Graph, Rng},
fun(State, U) ->
{G, Rng_state} = State,
_pipe@1 = yog@internal@util:range(U + 1, N - 1),
gleam@list:fold(
_pipe@1,
{G, Rng_state},
fun(Inner_state, V) ->
{Inner_g, Inner_rng} = Inner_state,
Comm_u = case gleam_stdlib:map_get(
Communities,
U
) of
{ok, C} ->
C;
{error, _} ->
-1
end,
Comm_v = case gleam_stdlib:map_get(
Communities,
V
) of
{ok, C@1} ->
C@1;
{error, _} ->
-1
end,
P = case Comm_u =:= Comm_v of
true ->
P_in;
false ->
P_out
end,
{Rand_val, New_rng} = yog@internal@random:next_float(
Inner_rng
),
case Rand_val < P of
true ->
{yog@model:add_edge_ensure(
Inner_g,
U,
V,
1,
nil
),
New_rng};
false ->
{Inner_g, New_rng}
end
end
)
end
)
end,
Result;
directed ->
{Result@1, _} = begin
_pipe@2 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@2,
{Graph, Rng},
fun(State@1, U@1) ->
{G@1, Rng_state@1} = State@1,
_pipe@3 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@3,
{G@1, Rng_state@1},
fun(Inner_state@1, V@1) ->
{Inner_g@1, Inner_rng@1} = Inner_state@1,
case U@1 =:= V@1 of
true ->
{Inner_g@1, Inner_rng@1};
false ->
Comm_u@1 = case gleam_stdlib:map_get(
Communities,
U@1
) of
{ok, C@2} ->
C@2;
{error, _} ->
-1
end,
Comm_v@1 = case gleam_stdlib:map_get(
Communities,
V@1
) of
{ok, C@3} ->
C@3;
{error, _} ->
-1
end,
P@1 = case Comm_u@1 =:= Comm_v@1 of
true ->
P_in;
false ->
P_out
end,
{Rand_val@1, New_rng@1} = yog@internal@random:next_float(
Inner_rng@1
),
case Rand_val@1 < P@1 of
true ->
{yog@model:add_edge_ensure(
Inner_g@1,
U@1,
V@1,
1,
nil
),
New_rng@1};
false ->
{Inner_g@1, New_rng@1}
end
end
end
)
end
)
end,
Result@1
end
end.
-file("src/yog/generator/random.gleam", 957).
?DOC(
" Generates a graph using the Stochastic Block Model (SBM).\n"
"\n"
" Nodes are assigned to communities, and edges are added with probabilities\n"
" depending on community membership (higher probability within communities).\n"
"\n"
" ## Parameters\n"
" - `n` - Number of nodes\n"
" - `k` - Number of communities\n"
" - `p_in` - Probability of edge within community\n"
" - `p_out` - Probability of edge between communities\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let sbm = random.sbm(100, 4, 0.3, 0.05, seed: Some(42))\n"
" // 100 nodes, 4 communities, high intra-community connectivity\n"
" ```\n"
).
-spec sbm(
integer(),
integer(),
float(),
float(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
sbm(N, K, P_in, P_out, Seed) ->
sbm_with_type(N, K, P_in, P_out, undirected, Seed).
-file("src/yog/generator/random.gleam", 1116).
?DOC(" Generates an R-MAT graph with specified graph type.\n").
-spec rmat_with_type(
integer(),
integer(),
gleam@option:option({float(), float(), float(), float()}),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
rmat_with_type(N, M, Probs, Graph_type, Seed) ->
case (N =< 0) orelse (M < 0) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
K = find_power_of_two(N, 0),
{A, B, C, _} = gleam@option:unwrap(Probs, {0.57, 0.19, 0.19, 0.05}),
{Final_graph, _} = begin
_pipe = yog@internal@util:range(1, M),
gleam@list:fold(
_pipe,
{Graph, Rng},
fun(State, _) ->
{G, Curr_rng} = State,
{X, Y, Next_rng} = rmat_sample_edge(
K,
A,
B,
C,
0,
0,
Curr_rng
),
U = case N of
0 -> 0;
Gleam@denominator -> X rem Gleam@denominator
end,
V = case N of
0 -> 0;
Gleam@denominator@1 -> Y rem Gleam@denominator@1
end,
{yog@model:add_edge_ensure(G, U, V, 1, nil), Next_rng}
end
)
end,
Final_graph
end.
-file("src/yog/generator/random.gleam", 1106).
?DOC(
" Generates a random graph using the R-MAT (Recursive MATRIX) model.\n"
"\n"
" R-MAT is a fast generator for graphs with scale-free and small-world properties.\n"
" It recursively partitions the adjacency matrix into four quadrants with\n"
" specified probabilities.\n"
"\n"
" **Parameters:**\n"
" - `n` - Number of nodes (must be a power of 2)\n"
" - `m` - Number of edges\n"
" - `probs` - Quad probabilities #(a, b, c, d) that sum to 1.0\n"
"\n"
" **Default Probs:** #(0.57, 0.19, 0.19, 0.05) - standard scale-free parameters.\n"
"\n"
" **Time Complexity:** O(m log n)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let rmat = random.rmat(1024, 5000, None, seed: Some(42))\n"
" // 1024 nodes (2^10), 5000 edges\n"
" ```\n"
).
-spec rmat(
integer(),
integer(),
gleam@option:option({float(), float(), float(), float()}),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
rmat(N, M, Probs, Seed) ->
rmat_with_type(N, M, Probs, undirected, Seed).
-file("src/yog/generator/random.gleam", 1219).
?DOC(" Generates a Geometric graph with specified graph type.\n").
-spec geometric_with_type(
integer(),
float(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
geometric_with_type(N, Radius, Graph_type, Seed) ->
case (N =< 0) orelse (Radius < +0.0) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
{Positions, _} = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
{maps:new(), Rng},
fun(State, I) ->
{D, Curr_rng} = State,
{X, Rng1} = yog@internal@random:next_float(Curr_rng),
{Y, Rng2} = yog@internal@random:next_float(Rng1),
{gleam@dict:insert(D, I, {X, Y}), Rng2}
end
)
end,
R_sq = Radius * Radius,
case Graph_type of
undirected ->
_pipe@1 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@1,
Graph,
fun(G, I@1) ->
Pos_i = begin
_pipe@2 = gleam_stdlib:map_get(Positions, I@1),
gleam@result:unwrap(_pipe@2, {+0.0, +0.0})
end,
_pipe@3 = yog@internal@util:range(I@1 + 1, N - 1),
gleam@list:fold(
_pipe@3,
G,
fun(Acc, J) ->
Pos_j = begin
_pipe@4 = gleam_stdlib:map_get(
Positions,
J
),
gleam@result:unwrap(
_pipe@4,
{+0.0, +0.0}
)
end,
Dx = erlang:element(1, Pos_i) - erlang:element(
1,
Pos_j
),
Dy = erlang:element(2, Pos_i) - erlang:element(
2,
Pos_j
),
Dist_sq = (Dx * Dx) + (Dy * Dy),
case Dist_sq =< R_sq of
true ->
yog@model:add_edge_ensure(
Acc,
I@1,
J,
1,
nil
);
false ->
Acc
end
end
)
end
);
directed ->
_pipe@5 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@5,
Graph,
fun(G@1, I@2) ->
Pos_i@1 = begin
_pipe@6 = gleam_stdlib:map_get(Positions, I@2),
gleam@result:unwrap(_pipe@6, {+0.0, +0.0})
end,
_pipe@7 = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe@7,
G@1,
fun(Acc@1, J@1) -> case I@2 =:= J@1 of
true ->
Acc@1;
false ->
Pos_j@1 = begin
_pipe@8 = gleam_stdlib:map_get(
Positions,
J@1
),
gleam@result:unwrap(
_pipe@8,
{+0.0, +0.0}
)
end,
Dx@1 = erlang:element(1, Pos_i@1) - erlang:element(
1,
Pos_j@1
),
Dy@1 = erlang:element(2, Pos_i@1) - erlang:element(
2,
Pos_j@1
),
Dist_sq@1 = (Dx@1 * Dx@1) + (Dy@1 * Dy@1),
case Dist_sq@1 =< R_sq of
true ->
yog@model:add_edge_ensure(
Acc@1,
I@2,
J@1,
1,
nil
);
false ->
Acc@1
end
end end
)
end
)
end
end.
-file("src/yog/generator/random.gleam", 1210).
?DOC(
" Generates a Random Geometric Graph (RGG).\n"
"\n"
" Nodes are placed uniformly at random in a unit square [0, 1] x [0, 1].\n"
" Edges are created between any two nodes if their Euclidean distance\n"
" is less than or equal to `radius`.\n"
"\n"
" **Time Complexity:** O(n²)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let rgg = random.geometric(100, 0.15, seed: Some(42))\n"
" // 100 nodes, connected if distance <= 0.15\n"
" ```\n"
).
-spec geometric(integer(), float(), gleam@option:option(integer())) -> yog@model:graph(nil, integer()).
geometric(N, Radius, Seed) ->
geometric_with_type(N, Radius, undirected, Seed).
-file("src/yog/generator/random.gleam", 1353).
?DOC(" Generates a DCSBM graph with specified graph type.\n").
-spec dcsbm_with_type(
integer(),
integer(),
float(),
float(),
gleam@option:option(list(float())),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
dcsbm_with_type(N, K, P_in, P_out, Thetas, Graph_type, Seed) ->
case (N =< 0) orelse (K < 1) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
Communities = assign_communities(N, K),
Weights = case Thetas of
{some, T} ->
case erlang:length(T) =:= N of
true ->
T;
false ->
generate_default_thetas(N)
end;
_ ->
generate_default_thetas(N)
end,
{Result_graph, _} = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
{Graph, Rng},
fun(State, U) ->
{G, Curr_rng} = State,
Start_v = case Graph_type of
undirected ->
U + 1;
directed ->
0
end,
_pipe@1 = yog@internal@util:range(Start_v, N - 1),
gleam@list:fold(
_pipe@1,
{G, Curr_rng},
fun(Inner_state, V) ->
{Inner_g, Inner_rng} = Inner_state,
case U =:= V of
true ->
{Inner_g, Inner_rng};
false ->
Comm_u = begin
_pipe@2 = gleam_stdlib:map_get(
Communities,
U
),
gleam@result:unwrap(_pipe@2, -1)
end,
Comm_v = begin
_pipe@3 = gleam_stdlib:map_get(
Communities,
V
),
gleam@result:unwrap(_pipe@3, -1)
end,
P_base = case Comm_u =:= Comm_v of
true ->
P_in;
false ->
P_out
end,
Theta_u = list_at_float(Weights, U),
Theta_v = list_at_float(Weights, V),
P = gleam@float:min(
1.0,
(Theta_u * Theta_v) * P_base
),
{Rand_val, New_rng} = yog@internal@random:next_float(
Inner_rng
),
case Rand_val < P of
true ->
{yog@model:add_edge_ensure(
Inner_g,
U,
V,
1,
nil
),
New_rng};
false ->
{Inner_g, New_rng}
end
end
end
)
end
)
end,
Result_graph
end.
-file("src/yog/generator/random.gleam", 1341).
?DOC(
" Generates a Degree-Corrected Stochastic Block Model (DCSBM).\n"
"\n"
" Extends SBM with node-specific degree parameters, allowing more realistic\n"
" degree distributions while preserving community structure.\n"
"\n"
" **Parameters:**\n"
" - `n` - Number of nodes\n"
" - `k` - Number of communities\n"
" - `p_in` - Probability within community\n"
" - `p_out` - Probability between communities\n"
" - `thetas` - Custom degree parameters for each node (optional)\n"
"\n"
" **Time Complexity:** O(n²)\n"
).
-spec dcsbm(
integer(),
integer(),
float(),
float(),
gleam@option:option(list(float())),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
dcsbm(N, K, P_in, P_out, Thetas, Seed) ->
dcsbm_with_type(N, K, P_in, P_out, Thetas, undirected, Seed).
-file("src/yog/generator/random.gleam", 1464).
?DOC(" Generates an HSBM graph with specified graph type.\n").
-spec hsbm_with_type(
integer(),
integer(),
integer(),
float(),
float(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
hsbm_with_type(N, Levels, Branching, P_in, P_out, Graph_type, Seed) ->
case ((N =< 0) orelse (Levels < 1)) orelse (Branching < 2) of
true ->
yog@model:new(Graph_type);
false ->
Leaf_blocks = power_int(Branching, Levels),
Leaf_size = case Leaf_blocks of
0 -> 0;
Gleam@denominator -> N div Gleam@denominator
end,
case Leaf_size < 1 of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
Graph = create_nodes(yog@model:new(Graph_type), N),
{Result_graph, _} = begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:fold(
_pipe,
{Graph, Rng},
fun(State, U) ->
{G, Curr_rng} = State,
Start_v = case Graph_type of
undirected ->
U + 1;
directed ->
0
end,
_pipe@1 = yog@internal@util:range(
Start_v,
N - 1
),
gleam@list:fold(
_pipe@1,
{G, Curr_rng},
fun(Inner_state, V) ->
{Inner_g, Inner_rng} = Inner_state,
case U =:= V of
true ->
{Inner_g, Inner_rng};
false ->
Lca = hsbm_lca_level(
U,
V,
Leaf_size,
Branching
),
P = P_in + ((P_out - P_in) * (case erlang:float(
Levels
) of
+0.0 -> +0.0;
-0.0 -> -0.0;
Gleam@denominator@1 -> erlang:float(
Lca
)
/ Gleam@denominator@1
end)),
{Rand_val, New_rng} = yog@internal@random:next_float(
Inner_rng
),
case Rand_val < P of
true ->
{yog@model:add_edge_ensure(
Inner_g,
U,
V,
1,
nil
),
New_rng};
false ->
{Inner_g, New_rng}
end
end
end
)
end
)
end,
Result_graph
end
end.
-file("src/yog/generator/random.gleam", 1452).
?DOC(
" Generates a hierarchical SBM with nested communities.\n"
"\n"
" **Time Complexity:** O(n²)\n"
).
-spec hsbm(
integer(),
integer(),
integer(),
float(),
float(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
hsbm(N, Levels, Branching, P_in, P_out, Seed) ->
hsbm_with_type(N, Levels, Branching, P_in, P_out, undirected, Seed).
-file("src/yog/generator/random.gleam", 1660).
?DOC(
" Generates a Kronecker graph using recursive expansion (via R-MAT).\n"
"\n"
" **Parameters:**\n"
" - `k` - Number of iterations (2^k nodes)\n"
" - `initiator` - 2x2 probability matrix #(a, b, c, d)\n"
" - `m` - Desired number of edges\n"
"\n"
" **Time Complexity:** O(m log n)\n"
).
-spec kronecker(
integer(),
{float(), float(), float(), float()},
integer(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
kronecker(K, Initiator, M, Seed) ->
N = power_int(2, K),
rmat_with_type(N, M, {some, Initiator}, directed, Seed).
-file("src/yog/generator/random.gleam", 1685).
-spec build_degree_list(yog@model:graph(nil, integer()), yog@model:graph_type()) -> list(integer()).
build_degree_list(Graph, Graph_type) ->
_pipe = yog@model:all_nodes(Graph),
gleam@list:flat_map(
_pipe,
fun(Node) ->
Degree = case Graph_type of
undirected ->
erlang:length(yog@model:neighbors(Graph, Node));
directed ->
erlang:length(yog@model:successors(Graph, Node))
end,
gleam@list:repeat(Node, gleam@int:max(Degree, 1))
end
).
-file("src/yog/generator/random.gleam", 433).
-spec add_node_with_preferential_attachment_seeded(
yog@model:graph(nil, integer()),
integer(),
integer(),
yog@model:graph_type(),
yog@internal@random:rng()
) -> {yog@model:graph(nil, integer()), yog@internal@random:rng()}.
add_node_with_preferential_attachment_seeded(
Graph,
New_node,
M,
Graph_type,
Rng
) ->
With_node = yog@model:add_node(Graph, New_node, nil),
Degree_list = build_degree_list(Graph, Graph_type),
{Targets, New_rng} = select_preferential_targets_seeded(
Degree_list,
M,
gleam@set:new(),
Rng
),
Final_graph = begin
_pipe = Targets,
_pipe@1 = gleam@set:to_list(_pipe),
gleam@list:fold(
_pipe@1,
With_node,
fun(G, Target) ->
yog@model:add_edge_ensure(G, New_node, Target, 1, nil)
end
)
end,
{Final_graph, New_rng}.
-file("src/yog/generator/random.gleam", 345).
?DOC(" Generates a Barabási-Albert graph with specified graph type.\n").
-spec barabasi_albert_with_type(
integer(),
integer(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
barabasi_albert_with_type(N, M, Graph_type, Seed) ->
case (N < M) orelse (M < 1) of
true ->
yog@model:new(Graph_type);
false ->
Rng = yog@internal@random:new(Seed),
M0 = gleam@int:max(M, 2),
Initial = begin
_pipe = yog@internal@util:range(0, M0 - 1),
gleam@list:fold(
_pipe,
yog@model:new(Graph_type),
fun(G, I) -> yog@model:add_node(G, I, nil) end
)
end,
Initial_with_edges = case Graph_type of
undirected ->
{Result, _} = begin
_pipe@1 = yog@internal@util:range(0, M0 - 1),
gleam@list:fold(
_pipe@1,
{Initial, Rng},
fun(State, I@1) ->
{G@1, Rng_state} = State,
_pipe@2 = yog@internal@util:range(
I@1 + 1,
M0 - 1
),
gleam@list:fold(
_pipe@2,
{G@1, Rng_state},
fun(Inner_state, J) ->
{Inner_g, Inner_rng} = Inner_state,
{yog@model:add_edge_ensure(
Inner_g,
I@1,
J,
1,
nil
),
Inner_rng}
end
)
end
)
end,
Result;
directed ->
{Result@1, _} = begin
_pipe@3 = yog@internal@util:range(0, M0 - 1),
gleam@list:fold(
_pipe@3,
{Initial, Rng},
fun(State@1, I@2) ->
{G@2, Rng_state@1} = State@1,
_pipe@4 = yog@internal@util:range(0, M0 - 1),
gleam@list:fold(
_pipe@4,
{G@2, Rng_state@1},
fun(Inner_state@1, J@1) ->
{Inner_g@1, Inner_rng@1} = Inner_state@1,
case I@2 =:= J@1 of
true ->
{Inner_g@1, Inner_rng@1};
false ->
{yog@model:add_edge_ensure(
Inner_g@1,
I@2,
J@1,
1,
nil
),
Inner_rng@1}
end
end
)
end
)
end,
Result@1
end,
{Final_graph, _} = begin
_pipe@5 = yog@internal@util:range(M0, N - 1),
gleam@list:fold(
_pipe@5,
{Initial_with_edges, Rng},
fun(State@2, New_node) ->
{G@3, Rng_state@2} = State@2,
add_node_with_preferential_attachment_seeded(
G@3,
New_node,
M,
Graph_type,
Rng_state@2
)
end
)
end,
Final_graph
end.
-file("src/yog/generator/random.gleam", 336).
?DOC(
" Generates a scale-free network using the Barabási-Albert model.\n"
"\n"
" Creates a random graph with a power-law degree distribution (scale-free).\n"
" New nodes preferentially attach to existing high-degree nodes (\"rich get richer\").\n"
"\n"
" **Time Complexity:** O(nm)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Scale-free network with 1000 nodes, each connecting to 3 existing nodes\n"
" let graph = random.barabasi_albert(1000, 3, seed: Some(42))\n"
" ```\n"
"\n"
" ## Properties\n"
"\n"
" - Power-law degree distribution: P(k) ~ k^(-3)\n"
" - Hub nodes with very high degree\n"
" - Small-world properties\n"
"\n"
" ## Use Cases\n"
"\n"
" - Social network modeling\n"
" - Citation network analysis\n"
" - Web graph simulation\n"
).
-spec barabasi_albert(integer(), integer(), gleam@option:option(integer())) -> yog@model:graph(nil, integer()).
barabasi_albert(N, M, Seed) ->
barabasi_albert_with_type(N, M, undirected, Seed).
-file("src/yog/generator/random.gleam", 1723).
-spec do_list_take_remove(list(STY), integer(), list(STY)) -> list(STY).
do_list_take_remove(List, Index, Acc) ->
case {Index, List} of
{0, [_ | Rest]} ->
_pipe = lists:reverse(Acc),
lists:append(_pipe, Rest);
{N, [First | Rest@1]} when N > 0 ->
do_list_take_remove(Rest@1, N - 1, [First | Acc]);
{_, _} ->
lists:reverse(Acc)
end.
-file("src/yog/generator/random.gleam", 1719).
-spec list_take_remove(list(STV), integer()) -> list(STV).
list_take_remove(List, Index) ->
do_list_take_remove(List, Index, []).
-file("src/yog/generator/random.gleam", 1702).
-spec do_shuffle(list(STR), list(STR), yog@internal@random:rng()) -> list(STR).
do_shuffle(Remaining, Acc, Rng) ->
case Remaining of
[] ->
Acc;
_ ->
Len = erlang:length(Remaining),
{Index, New_rng} = yog@internal@random:next_int(Rng, Len),
Selected = yog@internal@util:list_at(Remaining, Index),
Rest = list_take_remove(Remaining, Index),
case Selected of
{ok, Val} ->
do_shuffle(Rest, [Val | Acc], New_rng);
{error, _} ->
Acc
end
end.
-file("src/yog/generator/random.gleam", 1698).
-spec shuffle(list(STO), yog@internal@random:rng()) -> list(STO).
shuffle(List, Rng) ->
do_shuffle(List, [], Rng).
-file("src/yog/generator/random.gleam", 781).
-spec generate_regular(
integer(),
integer(),
yog@model:graph_type(),
integer(),
yog@internal@random:rng()
) -> yog@model:graph(nil, integer()).
generate_regular(N, D, Graph_type, Retries, Rng) ->
case Retries =< 0 of
true ->
create_ring_based_regular(N, D, Graph_type);
false ->
Stubs = lists:append(
begin
_pipe = yog@internal@util:range(0, N - 1),
gleam@list:map(_pipe, fun(I) -> gleam@list:repeat(I, D) end)
end
),
Shuffled = shuffle(Stubs, Rng),
case try_pairing(Shuffled, N, Graph_type) of
{ok, Graph} ->
Graph;
{error, _} ->
generate_regular(N, D, Graph_type, Retries - 1, Rng)
end
end.
-file("src/yog/generator/random.gleam", 755).
?DOC(" Generates a random d-regular graph with specified graph type.\n").
-spec random_regular_with_type(
integer(),
integer(),
yog@model:graph_type(),
gleam@option:option(integer())
) -> yog@model:graph(nil, integer()).
random_regular_with_type(N, D, Graph_type, Seed) ->
case ((N =< 0) orelse (D < 0)) orelse (D >= N) of
true ->
yog@model:new(Graph_type);
false ->
case gleam@int:remainder(N * D, 2) =:= {ok, 1} of
true ->
yog@model:new(Graph_type);
false ->
case D =:= 0 of
true ->
create_nodes(yog@model:new(Graph_type), N);
false ->
Rng = yog@internal@random:new(Seed),
generate_regular(N, D, Graph_type, 100, Rng)
end
end
end.
-file("src/yog/generator/random.gleam", 750).
?DOC(
" Generates a random d-regular graph on n nodes.\n"
"\n"
" A d-regular graph has every node with exactly degree d. This implementation\n"
" uses a configuration model approach with retries to ensure simplicity\n"
" (no self-loops or parallel edges).\n"
"\n"
" **Preconditions:**\n"
" - n × d must be even (required for any d-regular graph)\n"
" - d < n (cannot have degree >= number of nodes in simple graph)\n"
" - d >= 0\n"
"\n"
" **Properties:**\n"
" - Uniform distribution over all d-regular graphs (approximate)\n"
" - Exactly n nodes, (n × d) / 2 edges\n"
" - All nodes have degree exactly d\n"
"\n"
" **Time Complexity:** O(n × d)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // Generate a 3-regular graph with 10 nodes\n"
" let regular = random.random_regular(10, 3, seed: Some(42))\n"
" ```\n"
"\n"
" ## Use Cases\n"
"\n"
" - Testing algorithms that need uniform degree distribution\n"
" - Expander graph approximations\n"
" - Network models where degree is constrained\n"
).
-spec random_regular(integer(), integer(), gleam@option:option(integer())) -> yog@model:graph(nil, integer()).
random_regular(N, D, Seed) ->
random_regular_with_type(N, D, undirected, Seed).
-file("src/yog/generator/random.gleam", 1588).
-spec try_configuration(
yog@model:graph(nil, integer()),
list(integer()),
yog@internal@random:rng(),
integer()
) -> {ok, yog@model:graph(nil, integer())} | {error, nil}.
try_configuration(Graph, Stubs, Rng, Retries) ->
case Retries < 0 of
true ->
{error, nil};
false ->
Shuffled = shuffle(Stubs, Rng),
Pairs = pair_stubs(Shuffled),
Has_self = gleam@list:any(
Pairs,
fun(P) -> erlang:element(1, P) =:= erlang:element(2, P) end
),
case Has_self of
true ->
try_configuration(
Graph,
Stubs,
erlang:element(
2,
yog@internal@random:next_int(Rng, 100)
),
Retries - 1
);
false ->
Result_graph = gleam@list:fold(
Pairs,
Graph,
fun(G, P@1) ->
yog@model:add_edge_ensure(
G,
erlang:element(1, P@1),
erlang:element(2, P@1),
1,
nil
)
end
),
{ok, Result_graph}
end
end.
-file("src/yog/generator/random.gleam", 1563).
?DOC(
" Generates a random graph with specified degree sequence using the configuration model.\n"
"\n"
" **Time Complexity:** O(M) where M is total edges.\n"
" Returns Ok(graph) or Error(Nil) if pairing fails after retries.\n"
).
-spec configuration_model(list(integer()), gleam@option:option(integer())) -> {ok,
yog@model:graph(nil, integer())} |
{error, nil}.
configuration_model(Degrees, Seed) ->
Sum = gleam@list:fold(Degrees, 0, fun gleam@int:add/2),
case ((Sum rem 2) /= 0) orelse gleam@list:any(Degrees, fun(D) -> D < 0 end) of
true ->
{error, nil};
false ->
Rng = yog@internal@random:new(Seed),
N = erlang:length(Degrees),
Graph = create_nodes(yog@model:new(undirected), N),
Stubs = begin
_pipe = Degrees,
_pipe@1 = gleam@list:index_map(
_pipe,
fun(Deg, I) -> gleam@list:repeat(I, Deg) end
),
lists:append(_pipe@1)
end,
try_configuration(Graph, Stubs, Rng, 10)
end.
-file("src/yog/generator/random.gleam", 1638).
?DOC(
" Generates a random graph matching the degree sequence of a given graph.\n"
"\n"
" **Time Complexity:** O(N + M)\n"
).
-spec randomize_degree_sequence(
yog@model:graph(nil, integer()),
gleam@option:option(integer())
) -> {ok, yog@model:graph(nil, integer())} | {error, nil}.
randomize_degree_sequence(Graph, Seed) ->
Degrees = begin
_pipe = yog@model:all_nodes(Graph),
gleam@list:map(
_pipe,
fun(U) -> erlang:length(yog@model:neighbors(Graph, U)) end
)
end,
configuration_model(Degrees, Seed).