Gabow's path-based strong component algorithm in Python

A single-pass DFS SCC algorithm that uses two stacks instead of low-link values.

File: gabow_path_based_scc.py, 56 lines
Level: I0 not checked yet
Toolchain: Python 3.14, pytest 9
Test framework: pytest
Run the tests: python3 -m pytest

gabow_path_based_scc.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gabow-path-based-scc/. The authors are listed in prov/X5MM3D.jsonl.


def strong_components(n: int, edges: list[tuple[int, int]]) -> tuple[list[int], int]:
    """Gabow's path-based strong components of a directed graph on 0 .. n-1.

    Precondition: each edge (u, v) has 0 <= u, v < n. Loops and parallel edges are
    allowed. Returns (comp, c): comp[v] is the number of the component of v, and the
    components are numbered 0 .. c-1 in the order they close, which is a reverse
    topological order of the condensation. The search uses an explicit stack, and
    the time and the extra space are O(n + m).
    """
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    pre = [0] * n  # @line L1
    comp = [-1] * n
    counter = 0
    count = 0
    s: list[int] = []  # the stack S of vertices with no component yet
    b: list[int] = []  # the boundary stack B of preorder numbers
    for r in range(n):  # @line L2
        if pre[r]:
            continue
        calls: list[tuple[int, int]] = []  # (vertex, index of its next edge)
        counter += 1  # @line L3
        pre[r] = counter
        s.append(r)  # @line L4
        b.append(pre[r])
        calls.append((r, 0))
        while calls:
            v, k = calls[-1]
            if k < len(adj[v]):  # @line L5
                calls[-1] = (v, k + 1)
                w = adj[v][k]
                if pre[w] == 0:  # @line L6
                    counter += 1
                    pre[w] = counter
                    s.append(w)
                    b.append(pre[w])
                    calls.append((w, 0))
                elif comp[w] < 0:  # @line L7
                    while pre[w] < b[-1]:  # @line L8
                        b.pop()
                continue
            calls.pop()
            if b[-1] == pre[v]:  # @line L9
                b.pop()  # @line L10
                while True:  # @line L11
                    x = s.pop()
                    comp[x] = count
                    if x == v:
                        break
                count += 1
    return comp, count

test_gabow_path_based_scc.py 72 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gabow-path-based-scc/. The authors are listed in prov/X5MM3D.jsonl.

import random

from gabow_path_based_scc import strong_components


def reach(n: int, edges: list[tuple[int, int]]) -> list[set[int]]:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    out = []
    for s in range(n):
        seen = {s}
        stack = [s]
        while stack:
            for w in adj[stack.pop()]:
                if w not in seen:
                    seen.add(w)
                    stack.append(w)
        out.append(seen)
    return out


def check(n: int, edges: list[tuple[int, int]]) -> None:
    comp, c = strong_components(n, edges)
    r = reach(n, edges)
    assert sorted(set(comp)) == list(range(c))
    for u in range(n):
        for v in range(n):
            assert (comp[u] == comp[v]) == (v in r[u] and u in r[v])
    for u, v in edges:
        assert comp[u] >= comp[v]  # reverse topological numbering


def test_page_example() -> None:
    edges = [(0, 1), (1, 2), (2, 0), (2, 3), (1, 3), (3, 4), (4, 3),
             (4, 5), (0, 5), (5, 6), (6, 5), (6, 7), (7, 7)]
    assert strong_components(8, edges) == ([3, 3, 3, 2, 2, 1, 1, 0], 4)
    check(8, edges)


def test_edge_cases() -> None:
    assert strong_components(0, []) == ([], 0)
    assert strong_components(1, []) == ([0], 1)
    assert strong_components(1, [(0, 0), (0, 0)]) == ([0], 1)
    assert strong_components(2, [(0, 1), (0, 1)]) == ([1, 0], 2)
    assert strong_components(2, [(0, 1), (1, 0), (1, 0)]) == ([0, 0], 1)
    assert strong_components(3, []) == ([0, 1, 2], 3)
    check(4, [(0, 1), (1, 0), (2, 3), (3, 2), (1, 2)])


def test_long_path_and_cycle() -> None:
    n = 20000
    path = [(v, v + 1) for v in range(n - 1)]
    comp, c = strong_components(n, path)
    assert c == n and comp == [n - 1 - v for v in range(n)]
    comp, c = strong_components(n, path + [(n - 1, 0)])
    assert c == 1 and set(comp) == {0}
    back = [(v + 1, v) for v in range(n - 1)]
    comp, c = strong_components(n, path + back)
    assert c == 1


def test_random() -> None:
    rng = random.Random(2000)
    for _ in range(600):
        n = rng.randint(0, 9)
        m = rng.randint(0, 3 * n) if n else 0
        edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
        check(n, edges)

What the next level needs

the tests did not run in this build

Read the full page about Gabow's path-based strong component algorithm