Even-Tarjan vertex connectivity algorithm in Python
Tests and computes vertex connectivity by running a bounded number of max-flow computations.
- File
even_tarjan_vertex_connectivity.py, 105 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/even-tarjan-vertex-connectivity/. The authors are listed in prov/NX705H.jsonl.
from collections import deque
def _neighbours(n: int, edges: list[tuple[int, int]]) -> list[set[int]]:
nb: list[set[int]] = [set() for _ in range(n)]
for u, v in edges:
if u != v: # loops play no part; parallel edges collapse in the sets
nb[u].add(v)
nb[v].add(u)
return nb
class SplitGraph:
"""The split digraph of an undirected graph, with unit capacities.
The vertex w becomes w_in = 2w and w_out = 2w + 1 with the arc w_in -> w_out, and
the edge {a, b} becomes the arcs a_out -> b_in and b_out -> a_in. Every arc has
capacity 1, so a flow of value f from s_out to t_in is a set of f paths from s to t
with pairwise disjoint inner vertices. Building it costs O(n + m).
"""
def __init__(self, nb: list[set[int]]) -> None:
self.n = len(nb)
self.head: list[list[int]] = [[] for _ in range(2 * self.n)]
self.to: list[int] = []
self.res: list[int] = []
for w in range(self.n): # @line L9
self._arc(2 * w, 2 * w + 1)
for x in sorted(nb[w]):
self._arc(2 * w + 1, 2 * x)
def _arc(self, a: int, b: int) -> None:
self.head[a].append(len(self.to))
self.to.append(b)
self.res.append(1)
self.head[b].append(len(self.to))
self.to.append(a)
self.res.append(0)
def flow(self, s: int, t: int, cap: int) -> int:
"""min(cap, the most s-t paths with pairwise disjoint inner vertices).
Precondition: s != t are not adjacent. Each augmenting path is found by
breadth-first search, so the time is O(min(cap, n) (n + m)). The residual
capacities are restored before the return.
"""
head, to, res = self.head, self.to, self.res
source, sink = 2 * s + 1, 2 * t
used: list[int] = []
f = 0 # @line L10
while f < cap: # @line L11
prev = {source: -2}
queue = deque([source])
while queue and sink not in prev:
a = queue.popleft()
for e in head[a]:
b = to[e]
if res[e] and b not in prev:
prev[b] = e
queue.append(b)
if sink not in prev:
break
b = sink # @line L12
while b != source:
e = prev[b]
res[e] -= 1
res[e ^ 1] += 1
used.append(e)
b = to[e ^ 1]
f += 1
for e in used:
res[e] += 1
res[e ^ 1] -= 1
return f # @line L13
def local_connectivity(nb: list[set[int]], s: int, t: int, cap: int) -> int:
"""min(cap, kappa(s, t)) for non-adjacent s != t; builds the split graph first."""
return SplitGraph(nb).flow(s, t, cap)
def vertex_connectivity(n: int, edges: list[tuple[int, int]]) -> int:
"""The vertex connectivity kappa(G) of an undirected graph on 0 .. n-1.
Precondition: n >= 1. Parallel edges and loops are allowed and ignored. kappa is
the least size of a vertex cut, or n - 1 if G is complete. The vertices are taken
in the order 0 .. n-1. At most (kappa + 1) n local flows run, each stopped at the
current bound k <= n - 1, so the time is O((kappa + 1) n^2 (n + m)) in the worst
case; Dinic's algorithm in place of plain augmenting paths gives
O((kappa + 1) n^(3/2) m).
"""
nb = _neighbours(n, edges)
split = SplitGraph(nb)
k = n - 1 # @line L1
i = 0 # @line L2
# The page counts vertices from 1, so its test i <= k becomes i + 1 <= k here.
while i + 1 <= k: # @line L3
for j in range(i + 1, n): # @line L4
if j not in nb[i]: # @line L5
k = min(k, split.flow(i, j, k)) # @line L6
i += 1 # @line L7
return k # @line L8
test_even_tarjan_vertex_connectivity.py 115 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/even-tarjan-vertex-connectivity/. The authors are listed in prov/NX705H.jsonl.
import itertools
import random
from even_tarjan_vertex_connectivity import local_connectivity, vertex_connectivity
def connected(n: int, edges: list[tuple[int, int]], removed: set[int]) -> bool:
left = [v for v in range(n) if v not in removed]
if len(left) <= 1:
return True
seen = {left[0]}
stack = [left[0]]
while stack:
a = stack.pop()
for u, v in edges:
for x, y in ((u, v), (v, u)):
if x == a and y not in removed and y not in seen:
seen.add(y)
stack.append(y)
return len(seen) == len(left)
def brute(n: int, edges: list[tuple[int, int]]) -> int:
"""The least |X| with G - X disconnected (and at least 2 vertices left), else n - 1."""
for size in range(n - 1):
for x in itertools.combinations(range(n), size):
if not connected(n, edges, set(x)):
return size
return n - 1
def two_k4() -> list[tuple[int, int]]:
edges = [(a, b) for a in range(4) for b in range(a + 1, 4)]
edges += [(a + 4, b + 4) for a, b in edges]
return edges + [(3, 4), (3, 5)]
def test_example() -> None:
assert vertex_connectivity(8, two_k4()) == 1
nb = [set() for _ in range(8)]
for u, v in two_k4():
nb[u].add(v)
nb[v].add(u)
assert local_connectivity(nb, 0, 4, 7) == 1
assert local_connectivity(nb, 4, 6, 7) == 3
def test_page_example() -> None:
# The page names the vertices 1 .. 8; here they are 0 .. 7.
edges = [(0, 1), (0, 1), (7, 7)]
edges += [(h, x) for h in (0, 1) for x in range(2, 8)]
edges += [(2, 3), (3, 4), (4, 2), (5, 6), (6, 7), (7, 5)]
assert len(edges) == 21
assert vertex_connectivity(8, edges) == 2
nb = [set() for _ in range(8)]
for u, v in edges:
if u != v:
nb[u].add(v)
nb[v].add(u)
assert [local_connectivity(nb, 2, j, 7) for j in (5, 6, 7)] == [2, 2, 2]
def test_known_graphs() -> None:
cycle = [(i, (i + 1) % 6) for i in range(6)]
assert vertex_connectivity(6, cycle) == 2
k5 = [(a, b) for a in range(5) for b in range(a + 1, 5)]
assert vertex_connectivity(5, k5) == 4
k23 = [(a, b) for a in range(2) for b in range(2, 5)]
assert vertex_connectivity(5, k23) == 2
outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
inner = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
assert vertex_connectivity(10, outer + spokes + inner) == 3 # Petersen
cube = [(a, a ^ (1 << b)) for a in range(8) for b in range(3) if a < a ^ (1 << b)]
assert vertex_connectivity(8, cube) == 3
def test_edges() -> None:
assert vertex_connectivity(1, []) == 0
assert vertex_connectivity(1, [(0, 0)]) == 0
assert vertex_connectivity(2, []) == 0
assert vertex_connectivity(2, [(0, 1), (0, 1), (1, 0)]) == 1 # K2, parallel edges
assert vertex_connectivity(3, [(0, 1), (0, 1), (1, 2), (2, 2)]) == 1
assert vertex_connectivity(4, [(0, 1), (2, 3)]) == 0
assert vertex_connectivity(4, [(0, 1), (1, 2), (2, 0)]) == 0 # isolated vertex 3
def test_long_path() -> None:
n = 20000
nb = [set() for _ in range(n)]
for v in range(n - 1):
nb[v].add(v + 1)
nb[v + 1].add(v)
assert local_connectivity(nb, 0, n - 1, n) == 1
ring = [(v, (v + 1) % n) for v in range(n)]
nb2 = [set() for _ in range(n)]
for u, v in ring:
nb2[u].add(v)
nb2[v].add(u)
assert local_connectivity(nb2, 0, n // 2, n) == 2
m = 400 # the first pass runs m - 2 flows from vertex 0, so the time is quadratic
assert vertex_connectivity(m, [(v, v + 1) for v in range(m - 1)]) == 1
def test_random() -> None:
rng = random.Random(1975)
for _ in range(700):
n = rng.randint(1, 7)
p = rng.random()
edges = [(a, b) for a in range(n) for b in range(a + 1, n) if rng.random() < p]
edges += [(rng.randrange(n), rng.randrange(n)) for _ in range(rng.randint(0, 3))]
assert vertex_connectivity(n, edges) == brute(n, edges)
What the next level needs
- the tests did not run in this build
Read the full page about Even-Tarjan vertex connectivity algorithm