Advanced graphs

Which one cable takes the network down?

An internal network has 60,000 machines and 100,000 links. Before a big sale, one question has to be answered: which single link, if it failed, would split the network in two?

The direct script is easy to write. For each link, remove it, run a BFS, and see whether every machine is still reachable. Work out the cost before reading on. One BFS touches 160,000 machines and links. Doing it 100,000 times is 1.6 × 10¹⁰ steps. In Python, at about a million steps a second, that is four and a half hours, and the map changes every week.

Draw a small piece of the network instead: two triangles joined by one line, and a machine hanging off the second triangle. Cutting a triangle's side changes nothing, because the other two sides go round. Cutting the joining line splits the picture, and so does cutting the hanging machine's only link.

So the question to ask about each link is whether some other route goes round it. A single DFS can see every such route, because in an undirected graph every edge that is not part of the DFS tree points back up to an ancestor.

Pause and predict In one DFS, with u the parent of v, when is the tree edge u-v a bridge?

What a subtree can reach

Plain BFS and DFS answer some graph questions too slowly or not at all. This unit covers four tools for those questions, and the deepest is the first: which edges, removed one at a time, would disconnect the graph? Such an edge is a bridge.

Removing each edge and testing connectivity costs O(E · (V + E)). With 100,000 edges that is about 10¹⁰ steps. One DFS is enough.

Start by asking which edges could be bridges. A DFS splits the edges into tree edges, the ones it walked to reach a new node, and the rest. In an undirected graph every other edge joins a node to one of its ancestors: a back edge. (An edge to a node in a different branch is impossible, because the DFS would have walked that edge while the first branch was still open.) A back edge closes a cycle with the tree path, so it is never a bridge. Only tree edges can be.

Take a tree edge u-v, with u the parent. Removing it cuts v's subtree off from the rest of the graph, unless some edge from inside the subtree climbs back to u or above. Two numbers measure that:

• disc[x] is the time at which the DFS first reaches x, counting 0, 1, 2 and so on. An ancestor always gets a smaller number than its descendants.
• low[x] is the smallest disc that any node in x's subtree reaches with one edge, not counting the tree edge into x. This is called its low-link value.

Pause and predict low[v] equals disc[u] exactly. Is u-v a bridge?

Depth

Critical Connections allows 100,000 servers. If they form one long path, a recursive DFS is 100,000 calls deep. Python's limit is about 1,000 nested calls, and the Java runtime in this browser allows about 4,000. So the solutions use an explicit stack. Each stack frame remembers three things: the node, the edge it came in by, and how far through its neighbours it has got, so that the scan resumes where it left off after a child returns. The template shows the change.

Three more tools

Each of the other three tools answers one specific question, and each has one invariant to keep.

Pause and predict You hold three tickets: JFK to ATL, JFK to SFO, and SFO to JFK. Starting at JFK, you always fly to the alphabetically smallest airport you have an unused ticket for. Does this use every ticket?

How to recognise it

Read the question for what it asks: which links the network cannot survive losing, a route that uses up every edge, or a distance for every pair of nodes.

Pause and predict Which question needs low-link values?

Four that only look like it

• When the question is "are these two connected?" and edges are only ever added, use union-find. Bridges ask what happens when an edge is taken away, and union-find cannot undo a union.
• When you need distances from one source, use Dijkstra or BFS, from shortest paths. Floyd-Warshall only pays off when every pair is needed and n is small.
• When you must visit every node once in some order, that is a topological order if there are dependencies, or otherwise a Hamiltonian path, for which no fast algorithm is known. An Euler path uses every edge once, which is a different problem.
• To find a cycle in a directed graph, use the three colours of topological sort. Low-link values answer a different question: which edges no cycle passes through.

Where it bites

Pause and predict Java Floyd-Warshall with INF = Integer.MAX_VALUE. What is INF + INF?

• Using ≥ in the bridge test. That is the articulation-point test, and on a triangle it calls the first tree edge a bridge.
• Using disc[v] after the call instead of low[v]. The parent then loses what the child's subtree can reach.
• Not skipping the edge you came in by, or skipping every edge to the parent node when the graph may have two parallel edges between the same nodes.
• Recursion on 100,000 nodes. Use an explicit stack whose frames store a "next neighbour" index.
• In Hierholzer's algorithm, recording an airport when you arrive instead of when you are stuck, or forgetting to reverse the list.
• Floyd-Warshall with k as the inner loop. The loop over the stop k must always be the outer one.