Current section
Files
Jump to
Current section
Files
src/yog@connectivity.erl
-module(yog@connectivity).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/yog/connectivity.gleam").
-export([analyze/1, strongly_connected_components/1, kosaraju/1, connected_components/1, weakly_connected_components/1, k_core/2, core_numbers/1, degeneracy/1, shell_decomposition/1]).
-export_type([connectivity_results/0, internal_state/0, tarjan_state/0]).
-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 connectivity analysis - finding connected components, bridges, articulation points,\n"
" and strongly connected components.\n"
"\n"
" This module provides algorithms for analyzing the connectivity structure of graphs,\n"
" identifying components, and finding critical elements whose removal would disconnect the graph.\n"
"\n"
" ## Component Types\n"
"\n"
" | Component Type | Function | Graph Type | Description |\n"
" |----------------|----------|------------|-------------|\n"
" | **Connected Components** | `connected_components/1` | Undirected | Maximal connected subgraphs |\n"
" | **Weakly Connected Components** | `weakly_connected_components/1` | Directed | Connected when ignoring direction |\n"
" | **Strongly Connected Components** | `strongly_connected_components/1` | Directed | Connected following edge directions |\n"
"\n"
" ## Bridges vs Articulation Points\n"
"\n"
" - **Bridge** (cut edge): An edge whose removal increases the number of connected components.\n"
" In a network, this represents a single point of failure.\n"
" - **Articulation Point** (cut vertex): A node whose removal increases the number of connected\n"
" components. These are critical nodes in the network.\n"
"\n"
" ## Algorithms\n"
"\n"
" | Algorithm | Function | Use Case | Complexity |\n"
" |-----------|----------|----------|------------|\n"
" | DFS-based CC | `connected_components/1` | Undirected graph components | O(V + E) |\n"
" | DFS-based WCC | `weakly_connected_components/1` | Directed graph, ignore direction | O(V + E) |\n"
" | [Tarjan's SCC](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) | `strongly_connected_components/1` | Find SCCs in one pass | O(V + E) |\n"
" | [Kosaraju's Algorithm](https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm) | `kosaraju/1` | Find SCCs using two DFS passes | O(V + E) |\n"
" | [Tarjan's Bridge-Finding](https://en.wikipedia.org/wiki/Bridge_(graph_theory)) | `analyze/1` | Find bridges and articulation points | O(V + E) |\n"
"\n"
" All algorithms run in **O(V + E)** linear time.\n"
"\n"
" ## References\n"
"\n"
" - [Wikipedia: Connected Component](https://en.wikipedia.org/wiki/Component_(graph_theory))\n"
" - [Wikipedia: Strongly Connected Components](https://en.wikipedia.org/wiki/Strongly_connected_component)\n"
" - [Wikipedia: Biconnected Component](https://en.wikipedia.org/wiki/Biconnected_component)\n"
" - [CP-Algorithms: Finding Bridges](https://cp-algorithms.com/graph/bridge-searching.html)\n"
).
-type connectivity_results() :: {connectivity_results,
list({integer(), integer()}),
list(integer())}.
-type internal_state() :: {internal_state,
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer()),
integer(),
list({integer(), integer()}),
gleam@set:set(integer()),
gleam@set:set(integer())}.
-type tarjan_state() :: {tarjan_state,
integer(),
list(integer()),
gleam@dict:dict(integer(), boolean()),
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer()),
list(list(integer()))}.
-file("src/yog/connectivity.gleam", 137).
-spec do_analyze(
yog@model:graph(any(), any()),
integer(),
gleam@option:option(integer()),
internal_state()
) -> internal_state().
do_analyze(Graph, V, Parent, State) ->
Tin = gleam@dict:insert(
erlang:element(2, State),
V,
erlang:element(4, State)
),
Low = gleam@dict:insert(
erlang:element(3, State),
V,
erlang:element(4, State)
),
Visited = gleam@set:insert(erlang:element(7, State), V),
Timer = erlang:element(4, State) + 1,
State@1 = {internal_state,
Tin,
Low,
Timer,
erlang:element(5, State),
erlang:element(6, State),
Visited},
Neighbors = yog@model:successor_ids(Graph, V),
{Final_state, Children} = begin
gleam@list:fold(
Neighbors,
{State@1, 0},
fun(_use0, To) ->
{Acc_state, Children_count} = _use0,
case {Parent,
gleam@set:contains(erlang:element(7, Acc_state), To)} of
{{some, Parent_id}, _} when To =:= Parent_id ->
{Acc_state, Children_count};
{_, true} ->
V_low@1 = case gleam_stdlib:map_get(
erlang:element(3, Acc_state),
V
) of
{ok, V_low} -> V_low;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_analyze"/utf8>>,
line => 156,
value => _assert_fail,
start => 5980,
'end' => 6029,
pattern_start => 5991,
pattern_end => 6000})
end,
To_tin@1 = case gleam_stdlib:map_get(
erlang:element(2, Acc_state),
To
) of
{ok, To_tin} -> To_tin;
_assert_fail@1 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_analyze"/utf8>>,
line => 157,
value => _assert_fail@1,
start => 6038,
'end' => 6089,
pattern_start => 6049,
pattern_end => 6059})
end,
New_low = gleam@int:min(V_low@1, To_tin@1),
{{internal_state,
erlang:element(2, Acc_state),
gleam@dict:insert(
erlang:element(3, Acc_state),
V,
New_low
),
erlang:element(4, Acc_state),
erlang:element(5, Acc_state),
erlang:element(6, Acc_state),
erlang:element(7, Acc_state)},
Children_count};
{_, false} ->
Post_dfs_state = do_analyze(
Graph,
To,
{some, V},
Acc_state
),
V_low@3 = case gleam_stdlib:map_get(
erlang:element(3, Post_dfs_state),
V
) of
{ok, V_low@2} -> V_low@2;
_assert_fail@2 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_analyze"/utf8>>,
line => 169,
value => _assert_fail@2,
start => 6409,
'end' => 6463,
pattern_start => 6420,
pattern_end => 6429})
end,
To_low@1 = case gleam_stdlib:map_get(
erlang:element(3, Post_dfs_state),
To
) of
{ok, To_low} -> To_low;
_assert_fail@3 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_analyze"/utf8>>,
line => 170,
value => _assert_fail@3,
start => 6472,
'end' => 6528,
pattern_start => 6483,
pattern_end => 6493})
end,
New_v_low = gleam@int:min(V_low@3, To_low@1),
V_tin@1 = case gleam_stdlib:map_get(
erlang:element(2, Post_dfs_state),
V
) of
{ok, V_tin} -> V_tin;
_assert_fail@4 ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_analyze"/utf8>>,
line => 172,
value => _assert_fail@4,
start => 6584,
'end' => 6638,
pattern_start => 6595,
pattern_end => 6604})
end,
New_bridges = case To_low@1 > V_tin@1 of
true ->
Bridge = case V < To of
true ->
{V, To};
false ->
{To, V}
end,
[Bridge | erlang:element(5, Post_dfs_state)];
false ->
erlang:element(5, Post_dfs_state)
end,
New_points = case {Parent, To_low@1 >= V_tin@1} of
{{some, _}, true} ->
gleam@set:insert(
erlang:element(6, Post_dfs_state),
V
);
{_, _} ->
erlang:element(6, Post_dfs_state)
end,
{{internal_state,
erlang:element(2, Post_dfs_state),
gleam@dict:insert(
erlang:element(3, Post_dfs_state),
V,
New_v_low
),
erlang:element(4, Post_dfs_state),
New_bridges,
New_points,
erlang:element(7, Post_dfs_state)},
Children_count + 1}
end
end
)
end,
case {Parent, Children > 1} of
{none, true} ->
{internal_state,
erlang:element(2, Final_state),
erlang:element(3, Final_state),
erlang:element(4, Final_state),
erlang:element(5, Final_state),
gleam@set:insert(erlang:element(6, Final_state), V),
erlang:element(7, Final_state)};
{_, _} ->
Final_state
end.
-file("src/yog/connectivity.gleam", 100).
?DOC(
" Analyzes an **undirected graph** to find all bridges and articulation points\n"
" using Tarjan's algorithm in a single DFS pass.\n"
"\n"
" **Important:** This algorithm is designed for undirected graphs. For directed\n"
" graphs, use strongly connected components analysis instead.\n"
"\n"
" **Bridges** are edges whose removal increases the number of connected components.\n"
" **Articulation points** (cut vertices) are nodes whose removal increases the number\n"
" of connected components.\n"
"\n"
" **Bridge ordering:** Bridges are returned as `#(lower_id, higher_id)` for consistency.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import yog\n"
" import yog/connectivity\n"
"\n"
" let graph =\n"
" yog.undirected()\n"
" |> yog.add_node(1, Nil)\n"
" |> yog.add_node(2, Nil)\n"
" |> yog.add_node(3, Nil)\n"
" |> yog.add_edge(from: 1, to: 2, with: Nil)\n"
" |> yog.add_edge(from: 2, to: 3, with: Nil)\n"
"\n"
" let results = connectivity.analyze(in: graph)\n"
" // results.bridges == [#(1, 2), #(2, 3)]\n"
" // results.articulation_points == [2]\n"
" ```\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec analyze(yog@model:graph(any(), any())) -> connectivity_results().
analyze(Graph) ->
Nodes = maps:keys(erlang:element(3, Graph)),
Initial_state = {internal_state,
maps:new(),
maps:new(),
0,
[],
gleam@set:new(),
gleam@set:new()},
Final_state = gleam@list:fold(
Nodes,
Initial_state,
fun(State, Node) ->
case gleam@set:contains(erlang:element(7, State), Node) of
true ->
State;
false ->
do_analyze(Graph, Node, none, State)
end
end
),
{connectivity_results,
erlang:element(5, Final_state),
gleam@set:to_list(erlang:element(6, Final_state))}.
-file("src/yog/connectivity.gleam", 326).
-spec pop_stack_until(integer(), tarjan_state(), list(integer())) -> tarjan_state().
pop_stack_until(U, State, Component) ->
case erlang:element(3, State) of
[] ->
State;
[Head | Tail] ->
New_component = [Head | Component],
New_on_stack = gleam@dict:insert(
erlang:element(4, State),
Head,
false
),
Next_state = {tarjan_state,
erlang:element(2, State),
Tail,
New_on_stack,
erlang:element(5, State),
erlang:element(6, State),
erlang:element(7, State)},
case Head =:= U of
true ->
{tarjan_state,
erlang:element(2, Next_state),
erlang:element(3, Next_state),
erlang:element(4, Next_state),
erlang:element(5, Next_state),
erlang:element(6, Next_state),
[New_component | erlang:element(7, State)]};
false ->
pop_stack_until(U, Next_state, New_component)
end
end.
-file("src/yog/connectivity.gleam", 273).
-spec strong_connect(yog@model:graph(any(), any()), integer(), tarjan_state()) -> tarjan_state().
strong_connect(Graph, U, State) ->
State@1 = {tarjan_state,
erlang:element(2, State) + 1,
[U | erlang:element(3, State)],
gleam@dict:insert(erlang:element(4, State), U, true),
gleam@dict:insert(erlang:element(5, State), U, erlang:element(2, State)),
gleam@dict:insert(erlang:element(6, State), U, erlang:element(2, State)),
erlang:element(7, State)},
Successors = yog@model:successor_ids(Graph, U),
State@2 = begin
gleam@list:fold(
Successors,
State@1,
fun(St, V) ->
case {gleam@dict:has_key(erlang:element(5, St), V),
begin
_pipe = gleam_stdlib:map_get(erlang:element(4, St), V),
gleam@result:unwrap(_pipe, false)
end} of
{false, _} ->
St@1 = strong_connect(Graph, V, St),
U_low = begin
_pipe@1 = gleam_stdlib:map_get(
erlang:element(6, St@1),
U
),
gleam@result:unwrap(_pipe@1, 0)
end,
V_low = begin
_pipe@2 = gleam_stdlib:map_get(
erlang:element(6, St@1),
V
),
gleam@result:unwrap(_pipe@2, 0)
end,
{tarjan_state,
erlang:element(2, St@1),
erlang:element(3, St@1),
erlang:element(4, St@1),
erlang:element(5, St@1),
gleam@dict:insert(
erlang:element(6, St@1),
U,
gleam@int:min(U_low, V_low)
),
erlang:element(7, St@1)};
{true, true} ->
U_low@1 = begin
_pipe@3 = gleam_stdlib:map_get(
erlang:element(6, St),
U
),
gleam@result:unwrap(_pipe@3, 0)
end,
V_index = begin
_pipe@4 = gleam_stdlib:map_get(
erlang:element(5, St),
V
),
gleam@result:unwrap(_pipe@4, 0)
end,
{tarjan_state,
erlang:element(2, St),
erlang:element(3, St),
erlang:element(4, St),
erlang:element(5, St),
gleam@dict:insert(
erlang:element(6, St),
U,
gleam@int:min(U_low@1, V_index)
),
erlang:element(7, St)};
{true, false} ->
St
end
end
)
end,
U_index = begin
_pipe@5 = gleam_stdlib:map_get(erlang:element(5, State@2), U),
gleam@result:unwrap(_pipe@5, 0)
end,
U_low@2 = begin
_pipe@6 = gleam_stdlib:map_get(erlang:element(6, State@2), U),
gleam@result:unwrap(_pipe@6, 0)
end,
case U_low@2 =:= U_index of
true ->
pop_stack_until(U, State@2, []);
false ->
State@2
end.
-file("src/yog/connectivity.gleam", 249).
?DOC(
" Finds Strongly Connected Components (SCC) using Tarjan's Algorithm.\n"
" Returns a list of components, where each component is a list of NodeIds.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import yog/connectivity\n"
" import yog/model.{Directed}\n"
"\n"
" let graph =\n"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_edge(from: 1, to: 2, with: 1)\n"
" |> model.add_edge(from: 2, to: 3, with: 1)\n"
" |> model.add_edge(from: 3, to: 1, with: 1)\n"
"\n"
" let sccs = connectivity.strongly_connected_components(graph)\n"
" // => [[1, 2, 3]] // All nodes form one SCC (cycle)\n"
" ```\n"
).
-spec strongly_connected_components(yog@model:graph(any(), any())) -> list(list(integer())).
strongly_connected_components(Graph) ->
Nodes = yog@model:all_nodes(Graph),
Initial_state = {tarjan_state,
0,
[],
maps:new(),
maps:new(),
maps:new(),
[]},
Final_state = gleam@list:fold(
Nodes,
Initial_state,
fun(State, Node) ->
case gleam@dict:has_key(erlang:element(5, State), Node) of
true ->
State;
false ->
strong_connect(Graph, Node, State)
end
end
),
erlang:element(7, Final_state).
-file("src/yog/connectivity.gleam", 415).
-spec first_dfs(
yog@model:graph(any(), any()),
integer(),
gleam@set:set(integer()),
list(integer())
) -> {list(integer()), gleam@set:set(integer())}.
first_dfs(Graph, Node, Visited, Stack) ->
case gleam@set:contains(Visited, Node) of
true ->
{Stack, Visited};
false ->
New_visited = gleam@set:insert(Visited, Node),
Successors = yog@model:successor_ids(Graph, Node),
{New_stack, Final_visited} = begin
gleam@list:fold(
Successors,
{Stack, New_visited},
fun(_use0, Succ) ->
{S, V} = _use0,
first_dfs(Graph, Succ, V, S)
end
)
end,
{[Node | New_stack], Final_visited}
end.
-file("src/yog/connectivity.gleam", 437).
-spec second_dfs(
yog@model:graph(any(), any()),
integer(),
gleam@set:set(integer()),
list(integer())
) -> {list(integer()), gleam@set:set(integer())}.
second_dfs(Transposed, Node, Visited, Component) ->
case gleam@set:contains(Visited, Node) of
true ->
{Component, Visited};
false ->
New_visited = gleam@set:insert(Visited, Node),
New_component = [Node | Component],
Successors = yog@model:successor_ids(Transposed, Node),
gleam@list:fold(
Successors,
{New_component, New_visited},
fun(_use0, Succ) ->
{Comp, Vis} = _use0,
second_dfs(Transposed, Succ, Vis, Comp)
end
)
end.
-file("src/yog/connectivity.gleam", 390).
?DOC(
" Finds Strongly Connected Components (SCC) using Kosaraju's Algorithm.\n"
"\n"
" Returns a list of components, where each component is a list of NodeIds.\n"
" Kosaraju's algorithm uses two DFS passes and graph transposition:\n"
"\n"
" 1. First DFS: Compute finishing times (nodes added to stack when DFS completes)\n"
" 2. Transpose the graph (reverse all edges) - O(1) operation!\n"
" 3. Second DFS: Process nodes in reverse finishing time order on transposed graph\n"
"\n"
" **Time Complexity:** O(V + E) where V is vertices and E is edges\n"
" **Space Complexity:** O(V) for the visited set and finish stack\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" let graph =\n"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_edge(from: 1, to: 2, with: 1)\n"
" |> model.add_edge(from: 2, to: 3, with: 1)\n"
" |> model.add_edge(from: 3, to: 1, with: 1)\n"
"\n"
" let sccs = connectivity.kosaraju(graph)\n"
" // => [[1, 2, 3]] // All nodes form one SCC (cycle)\n"
" ```\n"
"\n"
" ## Comparison with Tarjan's Algorithm\n"
"\n"
" - **Kosaraju:** Two DFS passes, requires graph transposition, simpler to understand\n"
" - **Tarjan:** Single DFS pass, no transposition needed, uses low-link values\n"
"\n"
" Both have the same O(V + E) time complexity, but Kosaraju may be preferred when:\n"
" - The graph is already stored in a format supporting fast transposition\n"
" - Simplicity and clarity are prioritized over single-pass execution\n"
).
-spec kosaraju(yog@model:graph(any(), any())) -> list(list(integer())).
kosaraju(Graph) ->
Nodes = yog@model:all_nodes(Graph),
{Finish_stack, _} = begin
gleam@list:fold(
Nodes,
{[], gleam@set:new()},
fun(_use0, Node) ->
{Stack, Visited} = _use0,
first_dfs(Graph, Node, Visited, Stack)
end
)
end,
Transposed = yog@transform:transpose(Graph),
{Components@1, _} = begin
gleam@list:fold(
Finish_stack,
{[], gleam@set:new()},
fun(_use0@1, Node@1) ->
{Components, Visited@1} = _use0@1,
case gleam@set:contains(Visited@1, Node@1) of
true ->
{Components, Visited@1};
false ->
{Component, New_visited} = second_dfs(
Transposed,
Node@1,
Visited@1,
[]
),
{[Component | Components], New_visited}
end
end
)
end,
Components@1.
-file("src/yog/connectivity.gleam", 520).
-spec dfs_collect(
yog@model:graph(any(), any()),
integer(),
gleam@set:set(integer()),
list(integer())
) -> {list(integer()), gleam@set:set(integer())}.
dfs_collect(Graph, Node, Visited, Component) ->
case gleam@set:contains(Visited, Node) of
true ->
{Component, Visited};
false ->
New_visited = gleam@set:insert(Visited, Node),
Neighbors = yog@model:successor_ids(Graph, Node),
gleam@list:fold(
Neighbors,
{[Node | Component], New_visited},
fun(_use0, Neighbor) ->
{Comp, Vis} = _use0,
dfs_collect(Graph, Neighbor, Vis, Comp)
end
)
end.
-file("src/yog/connectivity.gleam", 498).
-spec do_connected_components(
yog@model:graph(any(), any()),
list(integer()),
gleam@set:set(integer()),
list(list(integer()))
) -> list(list(integer())).
do_connected_components(Graph, Nodes, Visited, Components) ->
case Nodes of
[] ->
Components;
[Node | Rest] ->
case gleam@set:contains(Visited, Node) of
true ->
do_connected_components(Graph, Rest, Visited, Components);
false ->
{Component, New_visited} = dfs_collect(
Graph,
Node,
Visited,
[]
),
do_connected_components(
Graph,
Rest,
New_visited,
[Component | Components]
)
end
end.
-file("src/yog/connectivity.gleam", 493).
?DOC(
" Finds Connected Components in an **undirected graph**.\n"
"\n"
" A connected component is a maximal subgraph where every node is reachable\n"
" from every other node via undirected edges. This uses simple DFS and runs\n"
" in linear time.\n"
"\n"
" **Important:** This algorithm is designed for undirected graphs. For directed\n"
" graphs, use `weakly_connected_components/1` instead.\n"
"\n"
" **Time Complexity:** O(V + E) where V is vertices and E is edges\n"
" **Space Complexity:** O(V) for the visited set\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import yog/connectivity\n"
" import yog/model.{Undirected}\n"
"\n"
" let graph =\n"
" model.new(Undirected)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_node(4, \"D\")\n"
" |> model.add_edge(from: 1, to: 2, with: 1)\n"
" |> model.add_edge(from: 3, to: 4, with: 1)\n"
"\n"
" let components = connectivity.connected_components(graph)\n"
" // => [[1, 2], [3, 4]] // Two separate components\n"
" ```\n"
).
-spec connected_components(yog@model:graph(any(), any())) -> list(list(integer())).
connected_components(Graph) ->
Nodes = yog@model:all_nodes(Graph),
do_connected_components(Graph, Nodes, gleam@set:new(), []).
-file("src/yog/connectivity.gleam", 606).
-spec wcc_dfs_collect(
yog@model:graph(any(), any()),
integer(),
gleam@set:set(integer()),
list(integer())
) -> {list(integer()), gleam@set:set(integer())}.
wcc_dfs_collect(Graph, Node, Visited, Component) ->
case gleam@set:contains(Visited, Node) of
true ->
{Component, Visited};
false ->
New_visited = gleam@set:insert(Visited, Node),
Neighbors = yog@model:neighbor_ids(Graph, Node),
gleam@list:fold(
Neighbors,
{[Node | Component], New_visited},
fun(_use0, Neighbor) ->
{Comp, Vis} = _use0,
wcc_dfs_collect(Graph, Neighbor, Vis, Comp)
end
)
end.
-file("src/yog/connectivity.gleam", 583).
-spec do_weakly_connected_components(
yog@model:graph(any(), any()),
list(integer()),
gleam@set:set(integer()),
list(list(integer()))
) -> list(list(integer())).
do_weakly_connected_components(Graph, Nodes, Visited, Components) ->
case Nodes of
[] ->
Components;
[Node | Rest] ->
case gleam@set:contains(Visited, Node) of
true ->
do_weakly_connected_components(
Graph,
Rest,
Visited,
Components
);
false ->
{Component, New_visited} = wcc_dfs_collect(
Graph,
Node,
Visited,
[]
),
do_weakly_connected_components(
Graph,
Rest,
New_visited,
[Component | Components]
)
end
end.
-file("src/yog/connectivity.gleam", 578).
?DOC(
" Finds Weakly Connected Components in a **directed graph**.\n"
"\n"
" A weakly connected component is a maximal subgraph where, if you ignore\n"
" edge directions, all nodes are reachable from each other. This is equivalent\n"
" to finding connected components on the underlying undirected graph.\n"
"\n"
" For directed graphs, you have two component concepts:\n"
" - **Weakly Connected Components** (WCC): Treat edges as undirected\n"
" - **Strongly Connected Components** (SCC): Follow edge directions\n"
"\n"
" **Time Complexity:** O(V + E) where V is vertices and E is edges\n"
" **Space Complexity:** O(V) for the visited set\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" import yog/connectivity\n"
" import yog/model.{Directed}\n"
"\n"
" let graph =\n"
" model.new(Directed)\n"
" |> model.add_node(1, \"A\")\n"
" |> model.add_node(2, \"B\")\n"
" |> model.add_node(3, \"C\")\n"
" |> model.add_edge(from: 1, to: 2, with: 1)\n"
" |> model.add_edge(from: 3, to: 2, with: 1) // 1->2<-3\n"
"\n"
" // SCCs: [[1], [2], [3]] (no cycles)\n"
" let sccs = connectivity.strongly_connected_components(graph)\n"
"\n"
" // WCCs: [[1, 2, 3]] (weakly connected as undirected)\n"
" let wccs = connectivity.weakly_connected_components(graph)\n"
" ```\n"
).
-spec weakly_connected_components(yog@model:graph(any(), any())) -> list(list(integer())).
weakly_connected_components(Graph) ->
Nodes = yog@model:all_nodes(Graph),
do_weakly_connected_components(Graph, Nodes, gleam@set:new(), []).
-file("src/yog/connectivity.gleam", 664).
-spec initial_degrees(yog@model:graph(any(), any()), list(integer())) -> gleam@dict:dict(integer(), integer()).
initial_degrees(Graph, Nodes) ->
gleam@list:fold(
Nodes,
maps:new(),
fun(Acc, U) ->
Deg = case gleam_stdlib:map_get(erlang:element(4, Graph), U) of
{ok, Neighbors} ->
maps:size(Neighbors);
{error, _} ->
0
end,
gleam@dict:insert(Acc, U, Deg)
end
).
-file("src/yog/connectivity.gleam", 673).
-spec do_prune_k_core(
gleam@dict:dict(integer(), gleam@dict:dict(integer(), any())),
list(integer()),
gleam@set:set(integer()),
gleam@dict:dict(integer(), integer()),
integer(),
gleam@set:set(integer())
) -> gleam@set:set(integer()).
do_prune_k_core(Out_edges, Queue, Queue_set, Degrees, K, Pruned) ->
case Queue of
[] ->
Pruned;
[U | Rest] ->
Queue_set@1 = gleam@set:delete(Queue_set, U),
case gleam@set:contains(Pruned, U) of
true ->
do_prune_k_core(
Out_edges,
Rest,
Queue_set@1,
Degrees,
K,
Pruned
);
false ->
New_pruned = gleam@set:insert(Pruned, U),
Neighbors = case gleam_stdlib:map_get(Out_edges, U) of
{ok, Nbrs} ->
maps:keys(Nbrs);
{error, _} ->
[]
end,
{New_rest, New_queue_set, New_degrees} = gleam@list:fold(
Neighbors,
{Rest, Queue_set@1, Degrees},
fun(Acc, V) ->
{Acc_rest, Acc_qs, Acc_deg} = Acc,
case gleam@set:contains(New_pruned, V) of
true ->
Acc;
false ->
Old_deg@1 = case gleam_stdlib:map_get(
Acc_deg,
V
) of
{ok, Old_deg} -> Old_deg;
_assert_fail ->
erlang:error(
#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_prune_k_core"/utf8>>,
line => 699,
value => _assert_fail,
start => 22573,
'end' => 22618,
pattern_start => 22584,
pattern_end => 22595}
)
end,
New_deg = Old_deg@1 - 1,
Acc_deg@1 = gleam@dict:insert(
Acc_deg,
V,
New_deg
),
case (New_deg < K) andalso not gleam@set:contains(
Acc_qs,
V
) of
true ->
{[V | Acc_rest],
gleam@set:insert(Acc_qs, V),
Acc_deg@1};
false ->
{Acc_rest, Acc_qs, Acc_deg@1}
end
end
end
),
do_prune_k_core(
Out_edges,
New_rest,
New_queue_set,
New_degrees,
K,
New_pruned
)
end
end.
-file("src/yog/connectivity.gleam", 647).
?DOC(
" Returns the maximal subgraph where every node has at least degree `k`.\n"
"\n"
" A [k-core](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)) is obtained\n"
" by repeatedly removing all nodes with degree less than `k` until no such nodes\n"
" remain. It is useful for identifying the most resilient/connected part of a\n"
" network and for pruning peripheral nodes before expensive analysis.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // A square (cycle of 4) has a 2-core containing all nodes, but no 3-core.\n"
" let core_2 = connectivity.k_core(graph, 2)\n"
" let core_3 = connectivity.k_core(graph, 3)\n"
" ```\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec k_core(yog@model:graph(NVJ, NVK), integer()) -> yog@model:graph(NVJ, NVK).
k_core(Graph, K) ->
Nodes = yog@model:all_nodes(Graph),
Degrees = initial_degrees(Graph, Nodes),
To_prune = gleam@list:filter(
Nodes,
fun(U) -> case gleam_stdlib:map_get(Degrees, U) of
{ok, Deg} ->
Deg < K;
{error, _} ->
false
end end
),
Queue_set = gleam@set:from_list(To_prune),
Pruned = do_prune_k_core(
erlang:element(4, Graph),
To_prune,
Queue_set,
Degrees,
K,
gleam@set:new()
),
Remaining = begin
_pipe = gleam@set:difference(gleam@set:from_list(Nodes), Pruned),
gleam@set:to_list(_pipe)
end,
yog@transform:subgraph(Graph, Remaining).
-file("src/yog/connectivity.gleam", 774).
-spec process_bucket(
gleam@dict:dict(integer(), gleam@dict:dict(integer(), any())),
integer(),
{gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), list(integer())),
gleam@set:set(integer())}
) -> {gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), list(integer())),
gleam@set:set(integer())}.
process_bucket(Out_edges, I, State) ->
{Degs, Cores, Buckets, Processed} = State,
case gleam_stdlib:map_get(Buckets, I) of
{error, _} ->
State;
{ok, []} ->
State;
{ok, [U | Rest]} ->
case gleam@set:contains(Processed, U) of
true ->
process_bucket(
Out_edges,
I,
{Degs,
Cores,
gleam@dict:insert(Buckets, I, Rest),
Processed}
);
false ->
Cores@1 = gleam@dict:insert(Cores, U, I),
Processed@1 = gleam@set:insert(Processed, U),
Neighbors = case gleam_stdlib:map_get(Out_edges, U) of
{ok, Nbrs} ->
maps:keys(Nbrs);
{error, _} ->
[]
end,
{New_degs, New_buckets} = gleam@list:fold(
Neighbors,
{Degs, gleam@dict:insert(Buckets, I, Rest)},
fun(Acc, V) ->
{D_acc, B_acc} = Acc,
case gleam@set:contains(Processed@1, V) of
true ->
Acc;
false ->
Old_v_deg@1 = case gleam_stdlib:map_get(
D_acc,
V
) of
{ok, Old_v_deg} -> Old_v_deg;
_assert_fail ->
erlang:error(
#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"process_bucket"/utf8>>,
line => 818,
value => _assert_fail,
start => 25900,
'end' => 25945,
pattern_start => 25911,
pattern_end => 25924}
)
end,
New_v_deg = Old_v_deg@1 - 1,
D_acc@1 = gleam@dict:insert(
D_acc,
V,
New_v_deg
),
Target_bucket = gleam@int:max(New_v_deg, I),
Existing = case gleam_stdlib:map_get(
B_acc,
Target_bucket
) of
{ok, B} ->
B;
{error, _} ->
[]
end,
B_acc@1 = gleam@dict:insert(
B_acc,
Target_bucket,
[V | Existing]
),
{D_acc@1, B_acc@1}
end
end
),
process_bucket(
Out_edges,
I,
{New_degs, Cores@1, New_buckets, Processed@1}
)
end
end.
-file("src/yog/connectivity.gleam", 748).
-spec do_calculate_core_numbers(
gleam@dict:dict(integer(), gleam@dict:dict(integer(), any())),
list(integer()),
gleam@dict:dict(integer(), integer()),
integer()
) -> gleam@dict:dict(integer(), integer()).
do_calculate_core_numbers(Out_edges, Nodes, Degrees, Max_deg) ->
Buckets = gleam@list:fold(
Nodes,
maps:new(),
fun(Acc, U) ->
Deg@1 = case gleam_stdlib:map_get(Degrees, U) of
{ok, Deg} -> Deg;
_assert_fail ->
erlang:error(#{gleam_error => let_assert,
message => <<"Pattern match failed, no pattern matched the value."/utf8>>,
file => <<?FILEPATH/utf8>>,
module => <<"yog/connectivity"/utf8>>,
function => <<"do_calculate_core_numbers"/utf8>>,
line => 756,
value => _assert_fail,
start => 24243,
'end' => 24284,
pattern_start => 24254,
pattern_end => 24261})
end,
Existing = case gleam_stdlib:map_get(Acc, Deg@1) of
{ok, B} ->
B;
{error, _} ->
[]
end,
gleam@dict:insert(Acc, Deg@1, [U | Existing])
end
),
Initial_state = {Degrees, maps:new(), Buckets, gleam@set:new()},
{_, Cores, _, _} = gleam@int:range(
0,
Max_deg + 1,
Initial_state,
fun(State, I) -> process_bucket(Out_edges, I, State) end
),
Cores.
-file("src/yog/connectivity.gleam", 738).
?DOC(
" Returns the core number of every node.\n"
"\n"
" The core number of a node is the largest `k` such that the node belongs to a\n"
" k-core. This is computed using the Batagelj–Zaversnik O(V + E) bucket\n"
" elimination algorithm.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // In a triangle, every node has core number 2.\n"
" let cores = connectivity.core_numbers(triangle_graph)\n"
" // cores == dict.from_list([#(1, 2), #(2, 2), #(3, 2)])\n"
" ```\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec core_numbers(yog@model:graph(any(), any())) -> gleam@dict:dict(integer(), integer()).
core_numbers(Graph) ->
Nodes = yog@model:all_nodes(Graph),
Degrees = initial_degrees(Graph, Nodes),
Max_deg = case maps:values(Degrees) of
[] ->
0;
Vals ->
gleam@list:fold(Vals, 0, fun gleam@int:max/2)
end,
do_calculate_core_numbers(erlang:element(4, Graph), Nodes, Degrees, Max_deg).
-file("src/yog/connectivity.gleam", 853).
?DOC(
" Returns the [degeneracy](https://en.wikipedia.org/wiki/Degeneracy_(graph_theory))\n"
" of the graph.\n"
"\n"
" Degeneracy is the maximum core number found in the graph. It measures how\n"
" sparse or dense the graph is and provides an upper bound on many graph\n"
" parameters such as chromatic number.\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec degeneracy(yog@model:graph(any(), any())) -> integer().
degeneracy(Graph) ->
Cores = core_numbers(Graph),
case maps:values(Cores) of
[] ->
0;
Vals ->
gleam@list:fold(Vals, 0, fun gleam@int:max/2)
end.
-file("src/yog/connectivity.gleam", 876).
?DOC(
" Groups nodes by their core number (k-shell decomposition).\n"
"\n"
" A k-shell contains all nodes that have a core number of exactly `k`. This\n"
" decomposition is useful for visualising the layered structure of a network\n"
" and for identifying core-periphery patterns.\n"
"\n"
" ## Example\n"
"\n"
" ```gleam\n"
" // A star graph with 4 leaves has a 1-shell (the leaves) and no higher shells.\n"
" let shells = connectivity.shell_decomposition(star_graph)\n"
" // shells == dict.from_list([#(1, [2, 3, 4, 5])])\n"
" ```\n"
"\n"
" **Time Complexity:** O(V + E)\n"
).
-spec shell_decomposition(yog@model:graph(any(), any())) -> gleam@dict:dict(integer(), list(integer())).
shell_decomposition(Graph) ->
gleam@dict:fold(
core_numbers(Graph),
maps:new(),
fun(Acc, Node, Core) ->
Existing = case gleam_stdlib:map_get(Acc, Core) of
{ok, Nodes} ->
Nodes;
{error, _} ->
[]
end,
gleam@dict:insert(Acc, Core, [Node | Existing])
end
).