Unit 22: Weak Points

Two kinds of edge, and only two

Number each node as the search first reaches it. The edges it walks down make a tree; every other edge turns out to join a node to an ancestor of itself.

There is never an edge across to a different branch. If there were, the search would have taken it and that node would be in this branch.

Python

n = 6
adj = [[1, 2], [0, 2, 3], [0, 1], [1, 4, 5], [3, 5], [3, 4]]
disc = [-1] * n
timer = [0]
tree_edges = []
back_edges = []

def dfs(node, parent):
    disc[node] = timer[0]
    timer[0] += 1
    for nxt in adj[node]:
        if nxt == parent:
            continue
        if disc[nxt] == -1:
            tree_edges.append((node, nxt))
            dfs(nxt, node)
        elif disc[nxt] < disc[node]:
            back_edges.append((node, nxt))

dfs(0, -1)
print(disc)
print(tree_edges)
print(back_edges)

It prints

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

What the graph looks like

Two triangles — 0, 1, 2 and 3, 4, 5 — joined by the single edge from 1 to 3.

The search walked a long chain down and found two edges pointing back up: 2 to 0, and 5 to 3. Those are the two triangles closing themselves.

A back edge means a cycle

An edge from a node back to an ancestor closes a loop with the tree path between them. So every cycle in the graph shows up as a back edge, and a graph with no back edges is a tree.

That is unit 11's undirected cycle test, seen properly.

The one road whose loss cuts the map

A bridge is an edge that is in no cycle: remove it and the graph falls into two pieces.

Testing each edge by removing it costs m searches. One search is enough, using one extra number per node.

How high can this branch reach?

low[node] is the smallest discovery number reachable from that node's subtree, using tree edges downwards and at most one back edge up.

The edge from a node to a child is a bridge exactly when low[child] > disc[node] — the whole branch below cannot get back up past the parent any other way.

Python

n = 6
adj = [[1, 2], [0, 2, 3], [0, 1], [1, 4, 5], [3, 5], [3, 4]]
disc = [-1] * n
low = [0] * n
timer = [0]
bridges = []

def dfs(node, parent):
    disc[node] = timer[0]
    low[node] = timer[0]
    timer[0] += 1
    for nxt in adj[node]:
        if nxt == parent:
            continue
        if disc[nxt] == -1:
            dfs(nxt, node)
            low[node] = min(low[node], low[nxt])
            if low[nxt] > disc[node]:
                bridges.append((node, nxt))
        else:
            low[node] = min(low[node], disc[nxt])

dfs(0, -1)
print(disc)
print(low)
print(bridges)

It prints

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

Reading the numbers

Nodes 0, 1 and 2 all have low 0 — the first triangle can always reach the start. Nodes 3, 4 and 5 all have low 3, because the only way out of the second triangle is the edge back to 1.

So low[3] = 3 is bigger than disc[1] = 1: the edge from 1 to 3 is a bridge, and it is the only one.

One warning about the parent

Skipping the parent is what stops the edge you came down counting as a way back up. If the graph can have the same edge twice between two nodes, skipping by node number is wrong — those two roads really are a way back, and neither is a bridge.

Skip by edge number instead when that is possible.

The town whose loss cuts the map

An articulation point is a node whose removal breaks the graph into more pieces. Almost the same numbers answer it, with one sign changed.

A node is one when some child's subtree cannot reach above it: low[child] >= disc[node]. Not strictly greater — reaching the node itself is not good enough, because the node is the thing being removed.

Python

n = 6
adj = [[1, 2], [0, 2, 3], [0, 1], [1, 4, 5], [3, 5], [3, 4]]
disc = [-1] * n
low = [0] * n
timer = [0]
points = set()

def dfs(node, parent):
    disc[node] = timer[0]
    low[node] = timer[0]
    timer[0] += 1
    children = 0
    for nxt in adj[node]:
        if nxt == parent:
            continue
        if disc[nxt] == -1:
            children += 1
            dfs(nxt, node)
            low[node] = min(low[node], low[nxt])
            if parent != -1 and low[nxt] >= disc[node]:
                points.add(node)
        else:
            low[node] = min(low[node], disc[nxt])
    if parent == -1 and children > 1:
        points.add(node)

dfs(0, -1)
print(sorted(points))

It prints

[1, 3]

Why 1 and 3

Take node 1 away and the second triangle is cut off. Take node 3 away and the first one is.

Nodes 0, 2, 4 and 5 are all in a triangle with another way round, so losing any of them changes nothing.

The root is different, and here is why

The root has no parent, so the test above never applies to it. Instead: the root is an articulation point exactly when it has two or more tree children — those branches had no other way of reaching each other, or the search would have joined them.

One child means everything hangs below in a single piece, and removing the root leaves that piece whole.

A network with no weak points at all

A graph where no single node breaks it is called two-connected. A graph where no single edge breaks it is bridgeless.

Problems ask for exactly this: which cables must never fail, which routers are single points of failure, and how many extra links would fix it.

Checking a claimed bridge by hand

The honest test of a bridge finder: take the edge out, count the pieces, and see whether it went up. Slow — m searches — and exactly right.

On the two triangles it agrees: only the edge from 1 to 3 splits the graph.

Python

n = 6
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (3, 5), (4, 5)]

def pieces(skip):
    adj = [[] for i in range(n)]
    for index, pair in enumerate(edges):
        if index == skip:
            continue
        a, b = pair
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * n
    total = 0
    for start in range(n):
        if seen[start]:
            continue
        total += 1
        stack = [start]
        while stack:
            node = stack.pop()
            if seen[node]:
                continue
            seen[node] = True
            for nxt in adj[node]:
                if not seen[nxt]:
                    stack.append(nxt)
    return total

whole = pieces(-1)
print(whole)
print([edges[i] for i in range(len(edges)) if pieces(i) > whole])

It prints

1
[(1, 3)]

The same check for nodes

Remove a node and everything touching it, then count the pieces of what is left — ignoring the removed node itself.

Again it agrees with the one-pass version: 1 and 3.

Python

n = 6
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4), (3, 5), (4, 5)]

def pieces_without(skip):
    adj = [[] for i in range(n)]
    for a, b in edges:
        if a == skip or b == skip:
            continue
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * n
    total = 0
    for start in range(n):
        if start == skip or seen[start]:
            continue
        total += 1
        stack = [start]
        while stack:
            node = stack.pop()
            if seen[node]:
                continue
            seen[node] = True
            for nxt in adj[node]:
                if not seen[nxt]:
                    stack.append(nxt)
    return total

print([i for i in range(n) if pieces_without(i) > 1])

It prints

[1, 3]

Why bother with low-link at all, then

Because the slow check is n or m searches. At 100000 edges that is ten thousand million steps; the one-pass version is 200000.

But the slow one is how you test the fast one, on a graph small enough to draw. That is this whole track's method in one sentence.