Bridges and articulation points

Finds the edges and the vertices whose loss splits an undirected graph into more pieces, its single points of failure, from one depth-first search.

Time complexity O(V+E), gograph function gograph.UndirectedCuts.

connectivity.Bridges returns the bridges alone, and connectivity.ArticulationPoints the articulation points.

How it works

A bridge is an edge whose loss splits a network in two, and an articulation point is a vertex whose loss does. Network and power engineers look for them to find single points of failure: a cable or a switch with no way around it.

One depth-first search finds both. Each vertex gets a discovery time when the search reaches it, and a low value: the earliest discovery time it can reach by going down the search tree and then along one back edge. A back edge is an edge to a vertex already on the search path, so it is a way around the tree edges below that vertex. When a vertex is finished, its low value passes to the vertex it was reached from.

The rule compares the two numbers. When a child's low value is above its parent's discovery time, nothing below the child reaches the parent or above except through the edge between them, so that edge is a bridge. When it isn't below the parent's discovery time, nothing below the child gets past the parent, so the parent is an articulation point. The first vertex of the search has nothing above it, so it is an articulation point when it has more than one child in the search tree.

gograph.UndirectedCuts returns the bridges, each from parent to child in the order the search finishes them, and the articulation points in the graph's vertex order, in O(V+E). connectivity.Bridges and connectivity.ArticulationPoints return one of the two. A directed graph returns gograph.ErrNotUndirected, since a one-way edge has no other end to fall back on. Tarjan's strongly connected components use the same low value on directed graphs.

Campus network

A hundred switches, servers and computers in ten buildings of a university campus, A to J. Each id is a building letter and a number, so D7 is number 7 in building D. A is the data center, where the core switches A1 and A2 link to the main switch of every other building, always number 1. The larger buildings have more switches between the main switch and the computers, and two pairs of neighboring buildings also have a direct link.

An undirected graph with 100 vertices and 114 edges.

Which single link or device would cut part of the campus off from the rest if it failed?

There are 83 bridges: A3 and A5; A3 and A6; A3 and A7; A3 and A8; A3 and A9; A3 and A10; A4 and A11; A4 and A12; A4 and A13; A4 and A14; and 73 more. Losing any one of the 18 articulation points splits the graph: A3, A4, B1, B2, B3, C1, D1, D2, D3, E1 and 8 more.

Step by step

  1. Start the search at A1, the first vertex. Its discovery time is 1, and its low value starts at 1: so far, the earliest discovery time it can reach is its own.
  2. A1 to A2 is a tree edge. Discover A2 at 2, with a low value of 2.
  3. A2 to A1 is the tree edge A2 was reached by, seen from this end. The search skips it, since it isn't a way around itself.
  4. A2 to A3 is a tree edge. Discover A3 at 3, with a low value of 3.
  5. A3 to A1 is a back edge to A1, discovered at 1. That's earlier than A3's low value, 3, so its low value becomes 1.
  6. A3 to A5 is a tree edge. Discover A5 at 4, with a low value of 4.

211 more steps lead to the last one:

  1. Done. The search found 83 bridges and 18 articulation points.

Use it in Go

bridges, points, err := gograph.UndirectedCuts(g)
if err != nil {
	return err // gograph.ErrNotUndirected
}
for _, e := range bridges {
	fmt.Println(e.Source().Label(), e.Destination().Label())
}
for _, v := range points {
	fmt.Println(v.Label())
}

Example graphs

More in Connectivity

  • Tarjan: Finds the strongly connected components of a directed graph, the groups of vertices that can all reach each other, with one depth-first search.
  • Kosaraju: Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.
  • Gabow: Finds the strongly connected components of a directed graph with one depth-first search and two stacks, without the lowlink values of Tarjan's algorithm.
  • Condensation: Replaces each strongly connected component with one vertex. What is left is a DAG, so it can be sorted and scheduled.
  • Connected components: Splits a graph into its connected pieces, the groups of vertices joined to each other by some path, with one search per piece.
  • Cycle detection: Says whether a graph has a cycle, a way to follow its edges from a vertex back to the same vertex, and stops at the first one it finds.
  • Find a cycle: Returns the vertices of one cycle in order: the first one a depth-first search closes with an edge back to its search path.

All algorithms