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 connectivity. Articulation points (cut vertices) are nodes whose removal increases the number of connected connectivity.

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

Comparison with Other Component Types

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

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

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)

Comparison with Other Component Types

Implementation Notes

This function uses model.neighbors/2 which treats edges as undirected by combining successors and predecessors for directed graphs. This is more efficient than actually converting the graph to undirected form.