Gabow-Myers spanning tree enumeration algorithm in Python

Lists all spanning trees of a graph by depth-first backtracking with bridge tests, in O(n + m + nN) time for N trees of an undirected graph and O(n + m) space.

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

gabow_myers_enumeration.pyRaw GitHub

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gabow-myers-enumeration/. The authors are listed in prov/NE4VW0.jsonl.

from collections.abc import Iterator


def gabow_myers_enumeration(n: int, edges: list[tuple[int, int]]) -> Iterator[list[int]]:
    """Yield every spanning tree of an undirected graph exactly once.

    The vertices are 0 .. n - 1 and edges[i] = (u, v) is an undirected edge.
    Parallel edges are distinct edges and give distinct trees. Self-loops are
    allowed and lie in no tree. The graph is unweighted, so ties do not
    arise. If the graph is not connected it has no spanning tree and nothing
    is yielded. Each tree is a list of n - 1 edge indices, in the order in
    which the search added them.

    This is the backtracking search of Gabow and Myers: grow a tree T from
    vertex 0 depth-first, and at each level branch on an edge e leaving T
    ("trees with e", then "trees without e") until e is a bridge. The paper
    tests for a bridge in time charged to the output, which gives
    O(n + m + n N) time for N trees. This version tests for a bridge with a
    plain graph search, so each call costs O(n + m) and the total is
    O(n + m + n (n + m) N) time. Space is O(n + m) for the graph plus the
    recursion stack, whose saved copies of F take O(n m) words.
    """
    if n <= 0:
        return
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        if u != v:
            adj[u].append((v, i))
            adj[v].append((u, i))
    alive = [True] * len(edges)
    in_tree = [False] * n
    tree: list[int] = []

    def connected() -> bool:
        seen = [False] * n
        seen[0] = True
        stack = [0]
        count = 1
        while stack:
            x = stack.pop()
            for y, i in adj[x]:
                if alive[i] and not seen[y]:
                    seen[y] = True
                    count += 1
                    stack.append(y)
        return count == n

    if not connected():
        return

    def outside_end(i: int) -> int:
        u, v = edges[i]
        return v if in_tree[u] else u

    def grow(stack: list[int]) -> Iterator[list[int]]:
        if len(tree) == n - 1:                                   # @line L1
            yield list(tree)
            return
        removed: list[int] = []                                  # @line L2
        while True:                                              # @line L3
            e = stack.pop()                                      # @line L4
            w = outside_end(e)
            saved = list(stack)
            stack[:] = [f for f in stack if outside_end(f) != w]  # @line L5
            tree.append(e)
            in_tree[w] = True
            stack.extend(i for y, i in adj[w] if alive[i] and not in_tree[y])
            yield from grow(stack)                               # @line L6
            tree.pop()                                           # @line L7
            in_tree[w] = False
            stack[:] = saved
            alive[e] = False                                     # @line L8
            removed.append(e)
            bridge = not connected()                             # @line L9
            if bridge:                                           # @line L10
                break
        for e in reversed(removed):                              # @line L11
            alive[e] = True
            stack.append(e)

    in_tree[0] = True
    yield from grow([i for y, i in adj[0] if y != 0])

test_gabow_myers_enumeration.py 131 lines

# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gabow-myers-enumeration/. The authors are listed in prov/NE4VW0.jsonl.

import itertools
import random
from fractions import Fraction

from gabow_myers_enumeration import gabow_myers_enumeration

EXAMPLE = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (4, 5)]


def is_spanning_tree(n, edges, chosen):
    if len(chosen) != n - 1:
        return False
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    for i in chosen:
        a, b = find(edges[i][0]), find(edges[i][1])
        if a == b:
            return False
        parent[a] = b
    return True


def brute_force(n, edges):
    if n <= 0:
        return set()
    return {frozenset(c) for c in itertools.combinations(range(len(edges)), n - 1) if is_spanning_tree(n, edges, c)}


def kirchhoff(n, edges):
    """Number of spanning trees by the matrix-tree theorem, in exact arithmetic."""
    if n == 1:
        return 1
    lap = [[Fraction(0)] * n for _ in range(n)]
    for u, v in edges:
        if u != v:
            lap[u][u] += 1
            lap[v][v] += 1
            lap[u][v] -= 1
            lap[v][u] -= 1
    a = [row[1:] for row in lap[1:]]
    k = n - 1
    det = Fraction(1)
    for c in range(k):
        p = next((r for r in range(c, k) if a[r][c] != 0), None)
        if p is None:
            return 0
        if p != c:
            a[c], a[p] = a[p], a[c]
            det = -det
        det *= a[c][c]
        for r in range(c + 1, k):
            f = a[r][c] / a[c][c]
            for j in range(c, k):
                a[r][j] -= f * a[c][j]
    return int(det)


def run(n, edges):
    out = list(gabow_myers_enumeration(n, edges))
    sets = [frozenset(t) for t in out]
    assert len(sets) == len(set(sets)), "a tree was listed twice"
    for t in out:
        assert is_spanning_tree(n, edges, t)
    return set(sets)


def test_example_has_55_trees():
    trees = run(6, EXAMPLE)
    assert len(trees) == 55
    assert trees == brute_force(6, EXAMPLE)
    assert frozenset([1, 2, 3, 5, 8]) in trees


def test_first_trees_of_example():
    out = list(gabow_myers_enumeration(6, EXAMPLE))
    assert out[:3] == [[1, 5, 8, 7, 3], [1, 5, 8, 7, 2], [1, 5, 8, 7, 0]]
    assert len(out) == 55


def test_complete_graphs_match_cayley():
    for n in range(1, 7):
        edges = list(itertools.combinations(range(n), 2))
        assert len(run(n, edges)) == (n ** (n - 2) if n >= 2 else 1)


def test_cycle():
    n = 7
    edges = [(i, (i + 1) % n) for i in range(n)]
    trees = run(n, edges)
    assert trees == {frozenset(set(range(n)) - {i}) for i in range(n)}


def test_tree_input_gives_itself():
    edges = [(0, 1), (1, 2), (1, 3), (3, 4)]
    assert run(5, edges) == {frozenset(range(4))}


def test_single_vertex_and_empty():
    assert list(gabow_myers_enumeration(1, [])) == [[]]
    assert list(gabow_myers_enumeration(1, [(0, 0)])) == [[]]
    assert list(gabow_myers_enumeration(0, [])) == []


def test_disconnected_yields_nothing():
    assert list(gabow_myers_enumeration(4, [(0, 1), (2, 3)])) == []
    assert list(gabow_myers_enumeration(3, [(0, 1), (0, 1), (1, 1)])) == []


def test_parallel_edges_and_loops():
    edges = [(0, 1), (0, 1), (1, 2), (2, 2), (0, 2)]
    trees = run(3, edges)
    assert trees == {frozenset(s) for s in ([0, 2], [1, 2], [0, 4], [1, 4], [2, 4])}


def test_random_against_brute_force_and_kirchhoff():
    rng = random.Random(20261105)
    for _ in range(600):
        n = rng.randint(1, 6)
        m = rng.randint(0, 9)
        edges = [(rng.randrange(n), rng.randrange(n)) for _ in range(m)]
        trees = run(n, edges)
        assert trees == brute_force(n, edges)
        assert len(trees) == kirchhoff(n, edges)

What the next level needs

the tests did not run in this build

Read the full page about Gabow-Myers spanning tree enumeration algorithm