Connectivity and Spanning Trees

Two questions sit under every network diagram. Which parts can reach each other at all? And what is the cheapest set of links that keeps everything connected? The first is answered by components and by a small structure called union-find. The second is answered by a minimum spanning tree, which is, by construction, a network with no spare link anywhere.

The two answers pull against each other. The cheapest connected network is also the most fragile one, and the price of resilience is the set of links the cheapest network leaves out. This topic computes both sides of that trade.

Components

In an undirected graph a component is a largest set of nodes that can all reach one another. Finding them takes one breadth-first or depth-first search from each node not yet visited: every node that search reaches belongs to the same component, and the next unvisited node starts a new one. The whole job costs O(nodes + edges), the same as a single traversal.

The figure's ten nodes fall into three components of four, three and three nodes, and no edge joins two of them. A message from A can reach D, and nothing it does will reach H.

In a directed graph "connected" splits in two. A strongly connected component is a set in which every node reaches every other along the arrows. A weakly connected one is connected only once the arrows are ignored. A service that calls another is weakly connected to it; the two are strongly connected only if a chain of calls also leads back.

Union-Find

Sometimes connections arrive one at a time: a link comes up, two customer accounts are merged, two records turn out to describe the same person. Re-running a traversal after every arrival repeats the whole job each time. Union-find keeps each group as a small tree whose root names the group. "Are these two in the same group?" follows parent pointers from each up to its root and compares the roots. "Join these two groups" hangs one root under the other.

Two tricks keep the trees flat. Union by size hangs the smaller tree under the root of the larger one, as in the middle panel, where the two-node tree rooted at e goes under a. Path compression re-points every node on a lookup's path straight at the root, as in the right panel, where finding d's root moves d from two steps away to one. With both, any sequence of operations costs a small constant number of pointer steps each, amortized in the sense of Chapter 1: Tarjan proved the bound grows with the inverse Ackermann function, which stays at 4 or below for any input that could exist on a real computer.

def find(parent, x):
    root = x
    while parent[root] != root:           # climb to the root
        root = parent[root]
    while parent[x] != root:              # re-point the path at it
        parent[x], x = root, parent[x]
    return root

def union(parent, size, a, b):
    ra, rb = find(parent, a), find(parent, b)
    if ra == rb:
        return False                        # already one group
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra                         # smaller under larger
    size[ra] += size[rb]
    return True

The whole structure is two small functions over two dictionaries. The first climbs from a node to its root, then walks the same path again pointing every node on it directly at the root. The second finds both roots, returns false if they are the same, and otherwise hangs the smaller group's root under the larger one's and adds the sizes. The figure was produced by this same logic.

The Minimum Spanning Tree

A spanning tree of a connected graph is a set of edges that reaches every node with no cycle, and a minimum spanning tree is the one whose weights add up to the least. For n nodes it always has exactly n − 1 edges: one fewer and some node is cut off, one more and there is a cycle. It answers the oldest network question there is: lay the least cable, fibre or pipe that still reaches every site.

Kruskal and Prim

Kruskal's algorithm sorts all edges by weight, cheapest first, then walks the list and accepts each edge unless its two ends are already connected, in which case the edge would close a cycle. "Already connected?" is a union-find query, and accepting the edge is a union. The sort dominates the cost, so Kruskal runs in about edges × log edges, using the sorting of Chapter 7.

In the figure, the four cheapest edges, weights 1, 2, 3 and 4, are all accepted. The edge of weight 5, from A to B, is rejected: A already reaches B through D. Weight 6 is rejected the same way. Weight 7, from B to C, is accepted and brings C in. At that point five edges connect all six nodes, and the last two are rejected. The tree weighs 17.

Prim's algorithm grows one tree outward from any start node instead, always adding the cheapest edge that leaves the tree, and finds that edge with a heap from Chapter 6. Both are greedy, and both are correct for the same plain-words reason. Split the nodes into any two groups; the cheapest edge crossing between them belongs to some minimum tree, because a tree without it must cross the split somewhere else, and swapping that crossing for the cheaper one never makes the tree heavier. Chapter 9 returns to this kind of swap argument as the test that separates a correct greedy algorithm from a guess.

Connected Is Not the Same as Resilient

A bridge is an edge whose loss splits a component in two. An articulation point is a node whose loss does the same. Both are single points of failure, and one depth-first search finds all of them, by noticing where a subtree has no edge reaching back above its parent. A network that survives any single link failure has no bridges.

In a spanning tree every edge is a bridge. That is what "no spare link" means: remove any one edge from the Kruskal tree in the figure and the six nodes fall into two groups.

What the Cheapest Network Costs

A minimum spanning tree is the cheapest way to connect everything and the most fragile. One cut cable partitions it. And because it minimizes total length rather than any pair's distance, two sites whose direct link the tree dropped can end up many hops apart. In a ring of four equal links, the tree drops one, and the two sites that link joined go from 1 hop apart to 3.

Real networks therefore pay for redundant links on purpose, and then have to stop them causing trouble. Switched Ethernet runs a spanning-tree protocol that blocks the redundant links, so that frames cannot circle forever, and holds them in reserve to unblock when a link fails. The protocol itself belongs to Networking Deep Dive; the structure underneath it is the one on this page.