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/3, erdos_renyi_gnp/2, erdos_renyi_gnm_with_type/3, erdos_renyi_gnm/2, watts_strogatz_with_type/4, watts_strogatz/3, barabasi_albert_with_type/3, barabasi_albert/2, random_tree_with_type/2, random_tree/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(
" 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"
"\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) // Sparse random (p=5%)\n"
" let exact = random.erdos_renyi_gnm(50, 100) // Exactly 100 edges\n"
" let scale_free = random.barabasi_albert(1000, 3) // Scale-free network\n"
" let small_world = random.watts_strogatz(100, 6, 0.1) // Small-world (10% rewire)\n"
" let tree = random.random_tree(50) // Random spanning tree\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"
" ## 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"
" - [NetworkX Random Graphs](https://networkx.org/documentation/stable/reference/generators.html#random-graphs)\n"
).
-file("src/yog/generator/random.gleam", 207).
-spec add_random_edges(
yog@model:graph(nil, integer()),
integer(),
integer(),
gleam@set:set({integer(), integer()}),
yog@model:graph_type()
) -> yog@model:graph(nil, integer()).
add_random_edges(Graph, N, M, Existing, Graph_type) ->
case M =< 0 of
true ->
Graph;
false ->
I = gleam@int:random(N),
J = gleam@int:random(N),
case I =:= J of
true ->
add_random_edges(Graph, N, M, Existing, Graph_type);
false ->
Edge = case Graph_type of
undirected ->
case I < J of
true ->
{I, J};
false ->
{J, I}
end;
directed ->
{I, J}
end,
case gleam@set:contains(Existing, Edge) of
true ->
add_random_edges(Graph, N, M, Existing, Graph_type);
false ->
New_graph = yog@model:add_edge_ensure(
Graph,
erlang:element(1, Edge),
erlang:element(2, Edge),
1,
nil
),
New_existing = gleam@set:insert(Existing, Edge),
add_random_edges(
New_graph,
N,
M - 1,
New_existing,
Graph_type
)
end
end
end.
-file("src/yog/generator/random.gleam", 364).
-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", 466).
-spec add_random_edge_not_to(
yog@model:graph(nil, integer()),
integer(),
integer()
) -> yog@model:graph(nil, integer()).
add_random_edge_not_to(Graph, From, N) ->
To = gleam@int:random(N),
case To =:= From of
true ->
add_random_edge_not_to(Graph, From, N);
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(Graph, From, N);
false ->
yog@model:add_edge_ensure(Graph, From, To, 1, nil)
end
end.
-file("src/yog/generator/random.gleam", 577).
-spec create_nodes(yog@model:graph(nil, POC), integer()) -> yog@model:graph(nil, POC).
create_nodes(Graph, N) ->
_pipe = yog@internal@utils:range(0, N - 1),
gleam@list:fold(
_pipe,
Graph,
fun(G, I) -> yog@model:add_node(G, I, nil) end
).
-file("src/yog/generator/random.gleam", 110).
?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()) -> yog@model:graph(nil, integer()).
erdos_renyi_gnp_with_type(N, P, Graph_type) ->
Graph = create_nodes(yog@model:new(Graph_type), N),
case Graph_type of
undirected ->
_pipe = yog@internal@utils:range(0, N - 1),
gleam@list:fold(
_pipe,
Graph,
fun(G, I) -> _pipe@1 = yog@internal@utils:range(I + 1, N - 1),
gleam@list:fold(
_pipe@1,
G,
fun(Acc, J) -> case rand:uniform() < P of
true ->
yog@model:add_edge_ensure(Acc, I, J, 1, nil);
false ->
Acc
end end
) end
);
directed ->
_pipe@2 = yog@internal@utils:range(0, N - 1),
gleam@list:fold(
_pipe@2,
Graph,
fun(G@1, I@1) -> _pipe@3 = yog@internal@utils:range(0, N - 1),
gleam@list:fold(
_pipe@3,
G@1,
fun(Acc@1, J@1) -> case I@1 =:= J@1 of
true ->
Acc@1;
false ->
case rand:uniform() < P of
true ->
yog@model:add_edge_ensure(
Acc@1,
I@1,
J@1,
1,
nil
);
false ->
Acc@1
end
end end
) end
)
end.
-file("src/yog/generator/random.gleam", 105).
?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\n"
" let sparse = random.erdos_renyi_gnp(100, 0.05)\n"
"\n"
" // Dense random graph\n"
" let dense = random.erdos_renyi_gnp(50, 0.8)\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()) -> yog@model:graph(nil, integer()).
erdos_renyi_gnp(N, P) ->
erdos_renyi_gnp_with_type(N, P, undirected).
-file("src/yog/generator/random.gleam", 188).
?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()) -> yog@model:graph(nil, integer()).
erdos_renyi_gnm_with_type(N, M, Graph_type) ->
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),
add_random_edges(Graph, N, Actual_m, gleam@set:new(), Graph_type).
-file("src/yog/generator/random.gleam", 183).
?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)\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()) -> yog@model:graph(nil, integer()).
erdos_renyi_gnm(N, M) ->
erdos_renyi_gnm_with_type(N, M, undirected).
-file("src/yog/generator/random.gleam", 430).
?DOC(" Generates a Watts-Strogatz graph with specified graph type.\n").
-spec watts_strogatz_with_type(
integer(),
integer(),
float(),
yog@model:graph_type()
) -> yog@model:graph(nil, integer()).
watts_strogatz_with_type(N, K, P, Graph_type) ->
case ((N < 3) orelse (K < 2)) orelse (K >= N) of
true ->
yog@model:new(Graph_type);
false ->
Graph = create_nodes(yog@model:new(Graph_type), N),
Half_k = K div 2,
_pipe = yog@internal@utils:range(0, N - 1),
gleam@list:fold(
_pipe,
Graph,
fun(G, I) -> _pipe@1 = yog@internal@utils:range(1, Half_k),
gleam@list:fold(
_pipe@1,
G,
fun(Acc, Offset) -> case rand:uniform() < 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);
true ->
add_random_edge_not_to(Acc, I, N)
end end
) end
)
end.
-file("src/yog/generator/random.gleam", 425).
?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)\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()) -> yog@model:graph(nil, integer()).
watts_strogatz(N, K, P) ->
watts_strogatz_with_type(N, K, P, undirected).
-file("src/yog/generator/random.gleam", 583).
-spec list_at(list(POH), integer()) -> {ok, POH} | {error, nil}.
list_at(Lst, Index) ->
case {Index, Lst} of
{0, [First | _]} ->
{ok, First};
{N, [_ | Rest]} when N > 0 ->
list_at(Rest, N - 1);
{_, _} ->
{error, nil}
end.
-file("src/yog/generator/random.gleam", 377).
-spec select_preferential_targets(
list(integer()),
integer(),
gleam@set:set(integer())
) -> gleam@set:set(integer()).
select_preferential_targets(Degree_list, M, Selected) ->
case (gleam@set:size(Selected) >= M) orelse gleam@list:is_empty(Degree_list) of
true ->
Selected;
false ->
List_size = erlang:length(Degree_list),
Index = gleam@int:random(List_size),
case list_at(Degree_list, Index) of
{ok, Target} ->
New_selected = gleam@set:insert(Selected, Target),
select_preferential_targets(Degree_list, M, New_selected);
{error, _} ->
Selected
end
end.
-file("src/yog/generator/random.gleam", 341).
-spec add_node_with_preferential_attachment(
yog@model:graph(nil, integer()),
integer(),
integer(),
yog@model:graph_type()
) -> yog@model:graph(nil, integer()).
add_node_with_preferential_attachment(Graph, New_node, M, Graph_type) ->
With_node = yog@model:add_node(Graph, New_node, nil),
Degree_list = build_degree_list(Graph, Graph_type),
Targets = select_preferential_targets(Degree_list, M, gleam@set:new()),
_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
).
-file("src/yog/generator/random.gleam", 285).
?DOC(" Generates a Barabási-Albert graph with specified graph type.\n").
-spec barabasi_albert_with_type(integer(), integer(), yog@model:graph_type()) -> yog@model:graph(nil, integer()).
barabasi_albert_with_type(N, M, Graph_type) ->
case (N < M) orelse (M < 1) of
true ->
yog@model:new(Graph_type);
false ->
M0 = gleam@int:max(M, 2),
Initial = begin
_pipe = yog@internal@utils: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 ->
_pipe@1 = yog@internal@utils:range(0, M0 - 1),
gleam@list:fold(
_pipe@1,
Initial,
fun(G@1, I@1) ->
_pipe@2 = yog@internal@utils:range(I@1 + 1, M0 - 1),
gleam@list:fold(
_pipe@2,
G@1,
fun(Acc, J) ->
yog@model:add_edge_ensure(
Acc,
I@1,
J,
1,
nil
)
end
)
end
);
directed ->
_pipe@3 = yog@internal@utils:range(0, M0 - 1),
gleam@list:fold(
_pipe@3,
Initial,
fun(G@2, I@2) ->
_pipe@4 = yog@internal@utils:range(0, M0 - 1),
gleam@list:fold(
_pipe@4,
G@2,
fun(Acc@1, J@1) -> case I@2 =:= J@1 of
true ->
Acc@1;
false ->
yog@model:add_edge_ensure(
Acc@1,
I@2,
J@1,
1,
nil
)
end end
)
end
)
end,
_pipe@5 = yog@internal@utils:range(M0, N - 1),
gleam@list:fold(
_pipe@5,
Initial_with_edges,
fun(G@3, New_node) ->
add_node_with_preferential_attachment(
G@3,
New_node,
M,
Graph_type
)
end
)
end.
-file("src/yog/generator/random.gleam", 280).
?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)\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()) -> yog@model:graph(nil, integer()).
barabasi_albert(N, M) ->
barabasi_albert_with_type(N, M, undirected).
-file("src/yog/generator/random.gleam", 543).
-spec build_random_tree(
yog@model:graph(nil, integer()),
integer(),
gleam@set:set(integer()),
integer()
) -> yog@model:graph(nil, integer()).
build_random_tree(Graph, N, In_tree, Next_node) ->
case Next_node >= N of
true ->
Graph;
false ->
Tree_list = gleam@set:to_list(In_tree),
Tree_size = erlang:length(Tree_list),
Index = gleam@int:random(Tree_size),
case 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(New_graph, N, New_in_tree, Next_node + 1);
{error, _} ->
Graph
end
end.
-file("src/yog/generator/random.gleam", 527).
?DOC(" Generates a random tree with specified graph type.\n").
-spec random_tree_with_type(integer(), yog@model:graph_type()) -> yog@model:graph(nil, integer()).
random_tree_with_type(N, Graph_type) ->
case N < 2 of
true ->
create_nodes(yog@model:new(Graph_type), N);
false ->
Graph = create_nodes(yog@model:new(Graph_type), N),
In_tree = gleam@set:from_list([0]),
build_random_tree(Graph, N, In_tree, 1)
end.
-file("src/yog/generator/random.gleam", 522).
?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)\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()) -> yog@model:graph(nil, integer()).
random_tree(N) ->
random_tree_with_type(N, undirected).