Bridges and articulation points in Python

Why it matters

Suppose a small office network has two routers, and every computer reaches the internet through one of them. If the cable between the routers fails, half the office loses its connection. That cable is a single point of failure. A network engineer wants to find every cable like that before it fails.

The same question appears in software and in maps. A road that is the only way into a village is a critical road. A server that every request must pass through is a critical server. In graph terms, the cable is a bridge and the server is an articulation point. This lesson shows how one depth-first search finds both.

The earlier lesson on strongly connected components dealt with directed graphs, where arrows have a direction. This lesson uses undirected graphs, where an edge joins two vertices and can be used in either direction.

Definitions with a small example

An undirected graph is a set of vertices joined by edges with no arrows. An edge between 0 and 1 lets you walk from 0 to 1 and back.

A bridge is an edge whose removal makes the graph fall into more pieces. A piece here means a group of vertices that can still reach each other. A graph with one piece is connected.

An articulation point is a vertex whose removal, together with the edges touching it, makes the graph fall into more pieces. Articulation points are also called cut vertices.

Take this graph. It has six vertices, numbered 0 to 5, and seven edges: 0-1, 1-2, 2-0, 1-3, 3-4, 4-5 and 5-3. Vertices 0, 1 and 2 form a triangle. Vertices 3, 4 and 5 form another triangle. One edge, 1-3, joins the two triangles.

Remove the edge 1-3. The graph falls into two pieces: {0, 1, 2} and {3, 4, 5}. So 1-3 is a bridge.

Remove the edge 0-1 instead. The graph stays connected, because 0 can still reach 1 through 2. So 0-1 is not a bridge.

Remove vertex 1. The edges 0-1, 1-2 and 1-3 go with it. The vertices 0 and 2 are still joined to each other, but they are cut off from 3, 4 and 5. So 1 is an articulation point.

Remove vertex 3. Vertices 4 and 5 are still joined, but they are cut off from 0, 1 and 2. So 3 is also an articulation point.

Remove vertex 0. The vertices 1 and 2 are still joined through the edge 1-2, and everything else is still connected to them. The graph stays in one piece, so 0 is not an articulation point.

A slow way to find all of these is to remove each edge and each vertex in turn and count the pieces. That takes time proportional to the number of edges times the size of the graph, which is too slow for large graphs. The rest of this lesson finds the same answers with one depth-first search.

The depth-first search tree and back edges

The depth-first search lesson covers the walk itself. Here is what matters for this lesson.

When the walk moves from a vertex u to a new vertex v, the edge between them is a tree edge. Everything the walk visits while v is being explored is the subtree under v. When the walk reaches a vertex that was already visited, that edge is a back edge. In an undirected graph, a back edge always joins a vertex to one of its ancestors. An ancestor is a vertex whose call on the walk is still open when the current call runs.

Each vertex gets two numbers during the walk:

• disc[u] is the discovery time of u. It is a counter that goes up by one each time the walk first visits a vertex. The first vertex visited gets 0.
• low[u] is the low value of u. It is the smallest discovery time that u can reach by going down its subtree through tree edges and then using at most one back edge. In plain words, it is the highest point on the walk that the subtree of u can climb back to.

The low value is computed when a call finishes. Start with low[u] equal to disc[u]. For each neighbour v already visited, other than the parent along the edge you arrived by, use disc[v] if the edge is a back edge. For each neighbour v that is a new child, take low[v] after the child's call returns and use the smaller of the two values.

Computing the numbers by hand

Use the six-vertex graph from the definitions section. Start at vertex 0 and follow the walk. Here is each step.

The walk visits 0 first, so disc[0] is 0. From 0 it goes to 1, so disc[1] is 1. From 1 it goes to 2, so disc[2] is 2.

Vertex 2 has two neighbours. One is 1, the vertex it came from. That is its parent, and the walk skips it. The other is 0, which is already visited. The edge 2-0 is a back edge, and 0 has discovery time 0. So low[2] becomes 0.

Back at 1, the child 2 has a low value of 0, so low[1] becomes 0. Vertex 1 still has an unvisited neighbour, 3. The walk goes to 3, so disc[3] is 3. From 3 it goes to 4, so disc[4] is 4. From 4 it goes to 5, so disc[5] is 5.

Vertex 5 has two neighbours. One is 4, its parent. The other is 3, which is already visited with discovery time 3. So low[5] becomes 3. Back at 4, the child 5 has a low value of 3, so low[4] becomes 3. Back at 3, the child 4 has low value 3, so low[3] becomes 3. Vertex 3 also has the neighbour 1, which is its parent, and the walk skips it.

Back at 1, the child 3 has low value 3, which does not lower low[1], because it stays 0. Back at 0, nothing changes.

The final values are:

Vertex 3 has low equal to 3, which is its own discovery time. That means nothing in its subtree can climb higher than 3. Vertex 1 has low 0, which means its subtree can climb all the way back to vertex 0.

The rules for bridges and articulation points

The numbers give the answers directly.

Bridge rule. Take a tree edge from u to its child v. It is a bridge if low[v] > disc[u]. Here is why. If low[v] is larger than disc[u], then nothing in the subtree of v can reach u or anything above u without using the edge u-v itself. Removing that edge cuts the subtree off.

Check it on the example. The tree edge from 1 to 3 has low[3] equal to 3 and disc[1] equal to 1. Since 3 is greater than 1, the edge 1-3 is a bridge. The tree edge from 0 to 1 has low[1] equal to 0 and disc[0] equal to 0. Since 0 is not greater than 0, it is not a bridge.

Articulation rule for non-root vertices. Take a vertex u that is not the start of the walk, which is called the root. Then u is an articulation point if any child v of u has low[v] >= disc[u]. The child's subtree cannot climb above u, so removing u cuts it off.

Check it on the example. Vertex 1 has the child 3, with low[3] equal to 3, which is at least disc[1], which is 1. So 1 is an articulation point. Vertex 3 has the child 4, with low[4] equal to 3, which is at least disc[3], which is 3. So 3 is an articulation point. Vertex 2 has no children in the walk, so it is not one.

Notice that the articulation rule uses >=, while the bridge rule uses >. Vertex 3 shows why. Its child 4 has low[4] equal to 3, the same as disc[3]. The subtree of 4 reaches back to 3 exactly, and not above it. Removing the edge 3-4 would not cut the subtree off, because 4 is still joined to 3 through 5. But removing vertex 3 would cut it off. So the vertex test has to include equality, and the edge test does not.

Root rule. The root is the vertex where the walk starts. The root is an articulation point if it has two or more children in the walk. Each child's subtree is joined to the rest of the graph only through the root, so removing the root separates them. A root with one child is not an articulation point, because removing it leaves just that one subtree.

The root needs its own rule because the non-root rule would give the wrong answer. The root's discovery time is 0, so every child has low at least 0, and the non-root rule would mark the root for every child, even when there is only one.

Program 1: bridges and articulation points

Here is the complete program. It stores each edge with an id, which is its position in the input list. Each adjacency list entry holds the neighbour and the id of the edge that leads there.

Arc is a small class made with NamedTuple from the typing module. It groups two values under names, so arc.to reads the neighbour and arc.id reads the edge id.

The function dfs is defined inside find_bridges. It can read the lists disc, low and adj from the outer function. The line nonlocal timer tells Python that timer belongs to the outer function. Without it, timer += 1 would try to create a new local variable, and Python would stop with an error. The Common mistakes section shows that error.

Type hints such as list[list[Arc]] describe the shape of the data for a reader and for editor tools. Python does not check them while the program runs.

Save the file as bridges.py and run it with python3 bridges.py. The output is:

disc: [0, 1, 2, 3, 4, 5]
low:  [0, 0, 0, 3, 3, 3]
bridges: 1-3
articulation points: 1 3

The values match the table in the hand calculation. The first call to dfs for each piece passes -1 as the parent edge. No edge has id -1, so the root never skips anything.

The walk starts at vertex 0 because the loop at the end of find_bridges goes from 0 upward. If the graph were split into several pieces, the loop would start a new walk in each piece. That is why the check disc[u] == -1 is there. A value of -1 means the vertex has not been visited yet.

The last two lines of the file run only when the file is started directly. Python sets the name __name__ to "__main__" in that case. Other programs can import find_bridges from this file without the printed output appearing.

Worked example 2: parallel edges

Two edges that join the same pair of vertices are called parallel edges. They matter for bridges. If two edges join 0 and 1, removing one of them leaves the other, so the pair stays connected. Neither edge is a bridge.

Take three vertices and the edges 0-1, 0-1 and 1-2. The second copy of 0-1 is the one that makes the difference. Here is the hand walk.

Start at 0, so disc[0] is 0. The first edge leads to 1, so disc[1] is 1. Vertex 1 has the edge back to 0 through the first copy, which is the parent edge, so the walk skips it. It has the edge back to 0 through the second copy. That is a back edge to a visited vertex with discovery time 0, so low[1] becomes 0.

Vertex 1 also has the edge to 2. That is a new child, with disc[2] equal to 2. Vertex 2 has only its parent edge, which it skips, so low[2] stays 2.

Now check the bridge rule on the edge 1-2. low[2] is 2 and disc[1] is 1. Since 2 is greater than 1, the edge 1-2 is a bridge. Check the first copy of 0-1 in the same way. It is the tree edge from 0 to 1, and low[1] is 0, which is not greater than disc[0], which is 0. It is not a bridge, because the second copy keeps 0 and 1 connected.

Calling find_bridges(3, [(0, 1), (0, 1), (1, 2)]) gives this result:

disc: [0, 1, 2]
low:  [0, 0, 2]
bridges: 1-2
articulation points: 1

Vertex 1 is the only articulation point. Removing it separates 2 from 0.

Worked example 3: a star

A star is a root with several leaves, each joined only to the root. Take vertex 0 joined to vertices 1, 2 and 3. Every edge is a bridge, and the root is an articulation point.

The walk starts at 0 and visits 1, 2 and 3 as its three children. None of the leaves has a back edge, so each leaf's low value is its own discovery time. Each child is cut off when its edge to 0 is removed, so every edge is a bridge. The root has three children, so the root rule makes it an articulation point.

Calling find_bridges(4, [(0, 1), (0, 2), (0, 3)]) gives:

disc: [0, 1, 2, 3]
low:  [0, 1, 2, 3]
bridges: 0-1 0-2 0-3
articulation points: 0

Common mistakes

Skipping the parent by vertex instead of by edge

The most common mistake is to skip the parent vertex, not the parent edge. A vertex is the point, and an edge is the line between two points. When the graph has parallel edges, skipping the vertex also skips the second copy of the edge, and the program then reports a bridge that is not one.

Here is what happens when the program skips by vertex, run on the parallel-edge graph from worked example 2:

disc: [0, 1, 2]
low:  [0, 1, 2]
bridges: 1-2 0-1
articulation points: 1

The edge 0-1 is reported as a bridge. Look at low[1]. It is 1, not 0, because the second copy of 0-1 was skipped, so vertex 1 never saw a back edge to 0. The fix is to skip by edge id, as the program does with if arc.id == parent_edge.

Not skipping the parent at all

The opposite mistake is to skip nothing. Then the edge the walk arrived by counts as a back edge. Every child sees its parent as a visited vertex with the parent's discovery time, so its low value becomes the parent's discovery time. The bridge test low[v] > disc[u] then fails for every edge, and no bridge is reported.

Here is the output of that version run on the star:

disc: [0, 1, 2, 3]
low:  [0, 0, 0, 0]
bridges:
articulation points: 0

No bridges are reported, although all three edges are bridges. The low values are all 0, which means every leaf has climbed back to the root through its parent edge. That is the signal that the parent edge was not skipped.

Using the wrong comparison

If the articulation test uses > instead of >=, a vertex whose child climbs back to exactly its own discovery time is missed. The program then reports too few articulation points. Here is the output of that version on the six-vertex graph:

disc: [0, 1, 2, 3, 4, 5]
low:  [0, 0, 0, 3, 3, 3]
bridges: 1-3
articulation points: 1

Vertex 3 is missing. Its child 4 has low[4] equal to 3, the same as disc[3]. Removing 3 cuts off 4 and 5, so 3 is an articulation point, and the test must use >=.

Forgetting the root rule

If the root's children are not counted, the root is never marked as an articulation point, because the non-root test does not apply to it. The version with the root rule removed gives the following output on the star:

disc: [0, 1, 2, 3]
low:  [0, 1, 2, 3]
bridges: 0-1 0-2 0-3
articulation points:

The root with three children is missing from the list. Keep the separate rule that counts children for the root.

Starting the walk from one vertex only

If the program starts the walk from vertex 0 only, it looks at the piece that contains 0 and nothing else. Calling the function on the graph with edges 0-1, 1-2 and 3-4 and six vertices, starting only at 0, gives:

disc: [0, 1, 2, -1, -1, -1]
low:  [0, 1, 2, 0, 0, 0]
bridges: 1-2 0-1
articulation points: 1

The vertices 3, 4 and 5 still have discovery time -1, which means they were never visited. Their bridges and articulation points are missed. The loop in find_bridges that starts a new walk from each unvisited vertex is needed.

Forgetting nonlocal

Python needs nonlocal when a nested function changes a variable from the outer function. Without it, the program fails as soon as the change happens. This short example has the same shape as dfs:

def make_counter():
    timer = 0
 
    def step():
        timer += 1
        return timer
 
    return step
 
make_counter()()

The last line of the error reads:

UnboundLocalError: cannot access local variable 'timer' where it is not associated with a value

Adding nonlocal timer as the first line of step fixes it. The name timer then refers to the variable in make_counter.

Deep recursion

The walk is recursive, so a long path of vertices makes the chain of calls deep. Python stops a chain of calls once it reaches a fixed limit, which is 1000 by default. A path with 5001 vertices is past that limit. Calling find_bridges on it raises an error whose last line is:

RecursionError: maximum recursion depth exceeded

sys.setrecursionlimit(100000) raises the limit, and the same 5001-vertex path then works. A very large limit is still a limit on memory, so for graphs with hundreds of thousands of vertices in one path, write the walk with a list used as an explicit stack instead of recursive calls.

Practice

Exercise 1 (easy). Take the path 0-1-2-3, with the edges 0-1, 1-2 and 2-3 and no other edges. Which edges are bridges, and which vertices are articulation points?

Show the answer

All three edges are bridges. Removing any one of them splits the path. Vertices 1 and 2 are articulation points. Removing 1 cuts 0 off from 2 and 3, and removing 2 cuts 3 off from 0 and 1. Vertices 0 and 3 are not articulation points, because they are the ends of the path and removing one of them leaves a connected path.

Exercise 2 (easy). Take a four-vertex cycle with the edges 0-1, 1-2, 2-3 and 3-0. Does it have any bridges or articulation points? Hint: what happens when you remove one edge, or one vertex?

Show the answer

It has neither. Removing any single edge leaves a path that still connects all four vertices. Removing any single vertex leaves a path of three vertices, which is still connected. Every edge and vertex lies on a loop, so none of them is a single point of failure.

Exercise 3 (easy). In the six-vertex graph of this lesson, why is the edge 0-1 not a bridge? Use the low values in your answer.

Show the answer

The tree edge from 0 to 1 is a bridge only if low[1] is greater than disc[0]. The value low[1] is 0, and disc[0] is also 0, so the test fails. The subtree of 1 reaches vertex 0 through vertex 2, using the back edge 2-0. So removing 0-1 does not cut the subtree off.

Exercise 4 (medium). Explain why every edge of a tree is a bridge. A tree is a connected graph with no cycles. Hint: a tree has no back edges.

Show the answer

With no cycles, the depth-first walk never finds a back edge, so every edge is a tree edge. For each child v of u, the low value low[v] can only be disc[v] itself, since no back edge lowers it. The discovery time of v is larger than disc[u], so low[v] > disc[u] is true, and the edge is a bridge. Removing any edge of a tree splits it, which matches the rule.

Exercise 5 (medium). Change find_bridges so that it also returns the number of connected pieces. Hint: each time the loop in find_bridges starts a new walk, that is a new piece.

Show the answer

Add a counter before the loop that starts the walks, increase it each time dfs is called from there, and return it as a fifth value:

    pieces = 0
    for u in range(n):
        if disc[u] == -1:
            pieces += 1
            dfs(u, -1)
    ...
    return disc, low, bridges, articulation, pieces

On six vertices with the edges 0-1, 1-2 and 3-4, the count is 3. The three pieces are {0, 1, 2}, {3, 4} and {5}.

Summary

• A bridge is an edge whose removal splits the graph into more pieces. An articulation point is a vertex whose removal does the same.
• One depth-first search gives each vertex a discovery time and a low value, which is the highest point on the walk that its subtree can climb back to.
• A tree edge from u to v is a bridge when low[v] is greater than disc[u]. A non-root vertex is an articulation point when a child has low at least its own discovery time.
• The root is an articulation point when it has two or more children in the walk.
• Skip the parent by edge id, not by vertex, so that parallel edges are counted correctly.