yog/connectivity

Graph connectivity analysis - finding bridges, articulation points, and strongly connected components.

This module provides algorithms for analyzing the connectivity structure of graphs, identifying critical components whose removal would disconnect the graph.

Algorithms

Algorithm	Function	Use Case
Tarjan’s Bridge-Finding	`analyze/1`	Find bridges and articulation points
Tarjan’s SCC	`strongly_connected_components/1`	Find SCCs in one pass
Kosaraju’s Algorithm	`kosaraju/1`	Find SCCs using two DFS passes

Bridges vs Articulation Points

Bridge (cut edge): An edge whose removal increases the number of connected components. In a network, this represents a single point of failure.
Articulation Point (cut vertex): A node whose removal increases the number of connected components. These are critical nodes in the network.

Strongly Connected Components

A strongly connected component (SCC) is a maximal subgraph where every node is reachable from every other node. SCCs form a DAG when collapsed, useful for:

Identifying cycles in dependency graphs
Finding groups of mutually reachable web pages
Analyzing feedback loops in systems

All algorithms run in O(V + E) linear time.

Types

Bridge

</>

Represents a bridge (critical edge) in an undirected graph. Bridges are stored as ordered pairs where the first node ID is smaller.

pub type Bridge =
  #(Int, Int)

ConnectivityResults

</>

Results from connectivity analysis containing bridges and articulation points.

pub type ConnectivityResults {
  ConnectivityResults(
    bridges: List(#(Int, Int)),
    articulation_points: List(Int),
  )
}

Constructors

ConnectivityResults(
  bridges: List(#(Int, Int)),
  articulation_points: List(Int),
)

TarjanState

</>

pub type TarjanState {
  TarjanState(
    index: Int,
    stack: List(Int),
    on_stack: dict.Dict(Int, Bool),
    indices: dict.Dict(Int, Int),
    low_links: dict.Dict(Int, Int),
    components: List(List(Int)),
  )
}

Constructors

TarjanState(
  index: Int,
  stack: List(Int),
  on_stack: dict.Dict(Int, Bool),
  indices: dict.Dict(Int, Int),
  low_links: dict.Dict(Int, Int),
  components: List(List(Int)),
)

Values

analyze

</>

pub fn analyze(
  in graph: model.Graph(n, e),
) -> ConnectivityResults

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)

kosaraju

</>

pub fn kosaraju(graph: model.Graph(n, e)) -> List(List(Int))

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:

First DFS: Compute finishing times (nodes added to stack when DFS completes)
Transpose the graph (reverse all edges) - O(1) operation!
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

strongly_connected_components

</>

pub fn strongly_connected_components(
  graph: model.Graph(n, e),
) -> List(List(Int))

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