Analyzes an undirected graph to find all bridges and articulation points using Tarjan’s algorithm in a single DFS pass.

Important: This algorithm is designed for undirected graphs. For directed graphs, use strongly connected components analysis instead.

Bridges are edges whose removal increases the number of connected components. Articulation points (cut vertices) are nodes whose removal increases the number of connected components.

Bridge ordering: Bridges are returned as #(lower_id, higher_id) for consistency.

Example

import yog
import yog/connectivity

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)
  |> yog.add_node(2, Nil)
  |> yog.add_node(3, Nil)
  |> yog.add_edge(from: 1, to: 2, with: Nil)
  |> yog.add_edge(from: 2, to: 3, with: Nil)

let results = connectivity.analyze(in: graph)
// results.bridges == [#(1, 2), #(2, 3)]
// results.articulation_points == [2]

Time Complexity: O(V + E)

Finds Connected Components in an undirected graph.

A connected component is a maximal subgraph where every node is reachable from every other node via undirected edges. This uses simple DFS and runs in linear time.

Important: This algorithm is designed for undirected graphs. For directed graphs, use weakly_connected_components/1 instead.

Time Complexity: O(V + E) where V is vertices and E is edges Space Complexity: O(V) for the visited set

Example

import yog/connectivity
import yog/model.{Undirected}

let graph =
  model.new(Undirected)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_node(4, "D")
  |> model.add_edge(from: 1, to: 2, with: 1)
  |> model.add_edge(from: 3, to: 4, with: 1)

let components = connectivity.connected_components(graph)
// => [[1, 2], [3, 4]]  // Two separate components

Returns the core number of every node.

The core number of a node is the largest k such that the node belongs to a k-core. This is computed using the Batagelj–Zaversnik O(V + E) bucket elimination algorithm.

Example

// In a triangle, every node has core number 2.
let cores = connectivity.core_numbers(triangle_graph)
// cores == dict.from_list([#(1, 2), #(2, 2), #(3, 2)])

Time Complexity: O(V + E)

Returns the degeneracy of the graph.

Degeneracy is the maximum core number found in the graph. It measures how sparse or dense the graph is and provides an upper bound on many graph parameters such as chromatic number.

Time Complexity: O(V + E)

Returns the maximal subgraph where every node has at least degree k.

A k-core is obtained by repeatedly removing all nodes with degree less than k until no such nodes remain. It is useful for identifying the most resilient/connected part of a network and for pruning peripheral nodes before expensive analysis.

Example

// A square (cycle of 4) has a 2-core containing all nodes, but no 3-core.
let core_2 = connectivity.k_core(graph, 2)
let core_3 = connectivity.k_core(graph, 3)

Time Complexity: O(V + E)

Finds Strongly Connected Components (SCC) using Kosaraju’s Algorithm.

Returns a list of components, where each component is a list of NodeIds. Kosaraju’s algorithm uses two DFS passes and graph transposition:

1. First DFS: Compute finishing times (nodes added to stack when DFS completes)
2. Transpose the graph (reverse all edges) - O(1) operation!
3. Second DFS: Process nodes in reverse finishing time order on transposed graph

Time Complexity: O(V + E) where V is vertices and E is edges Space Complexity: O(V) for the visited set and finish stack

Example

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 1)
  |> model.add_edge(from: 2, to: 3, with: 1)
  |> model.add_edge(from: 3, to: 1, with: 1)

let sccs = connectivity.kosaraju(graph)
// => [[1, 2, 3]]  // All nodes form one SCC (cycle)

Comparison with Tarjan’s Algorithm

• Kosaraju: Two DFS passes, requires graph transposition, simpler to understand
• Tarjan: Single DFS pass, no transposition needed, uses low-link values

Both have the same O(V + E) time complexity, but Kosaraju may be preferred when:

• The graph is already stored in a format supporting fast transposition
• Simplicity and clarity are prioritized over single-pass execution

Groups nodes by their core number (k-shell decomposition).

A k-shell contains all nodes that have a core number of exactly k. This decomposition is useful for visualising the layered structure of a network and for identifying core-periphery patterns.

Example

// A star graph with 4 leaves has a 1-shell (the leaves) and no higher shells.
let shells = connectivity.shell_decomposition(star_graph)
// shells == dict.from_list([#(1, [2, 3, 4, 5])])

Time Complexity: O(V + E)

Finds Strongly Connected Components (SCC) using Tarjan’s Algorithm. Returns a list of components, where each component is a list of NodeIds.

Time Complexity: O(V + E)

Example

import yog/connectivity
import yog/model.{Directed}

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 1)
  |> model.add_edge(from: 2, to: 3, with: 1)
  |> model.add_edge(from: 3, to: 1, with: 1)

let sccs = connectivity.strongly_connected_components(graph)
// => [[1, 2, 3]]  // All nodes form one SCC (cycle)

Finds Weakly Connected Components in a directed graph.

A weakly connected component is a maximal subgraph where, if you ignore edge directions, all nodes are reachable from each other. This is equivalent to finding connected components on the underlying undirected graph.

For directed graphs, you have two component concepts:

• Weakly Connected Components (WCC): Treat edges as undirected
• Strongly Connected Components (SCC): Follow edge directions

Time Complexity: O(V + E) where V is vertices and E is edges Space Complexity: O(V) for the visited set

Example

import yog/connectivity
import yog/model.{Directed}

let graph =
  model.new(Directed)
  |> model.add_node(1, "A")
  |> model.add_node(2, "B")
  |> model.add_node(3, "C")
  |> model.add_edge(from: 1, to: 2, with: 1)
  |> model.add_edge(from: 3, to: 2, with: 1)  // 1->2<-3

// SCCs: [[1], [2], [3]]  (no cycles)
let sccs = connectivity.strongly_connected_components(graph)

// WCCs: [[1, 2, 3]]  (weakly connected as undirected)
let wccs = connectivity.weakly_connected_components(graph)