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.

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

How it works

Gabow's algorithm finds the strongly connected components in one depth-first search, as Tarjan's does, but without lowlink values. It keeps two stacks. The first holds the vertices the search has reached that aren't in a component yet. The second holds the vertices on the current path that could still be the first vertex of a component.

When an edge leads to a vertex still on the first stack, every vertex on the path after it is in the same component, so the second stack is popped back to it. When the search finishes a vertex that is still on top of the second stack, that vertex starts a component. The first stack is popped down to it, and those vertices form the component.

It costs O(V+E). On the same graph, Tarjan's and Gabow's algorithms find the same components in the same order. They differ only in how they tell that the search has finished one.

Web crawl

A hundred pages on ten sites that a crawler reached by following links, P1 to P100, where P stands for page. Pages are numbered site by site: an encyclopedia (P1 to P16), news (P17 to P30), a city (P31 to P37), a university (P38 to P46), a link directory (P47 to P52), docs (P53 to P62), a forum (P63 to P74), videos (P75 to P82), a blog (P83 to P90) and a shop (P91 to P100). Each edge counts the links from one page to another. The docs, shop and city sites never link back, and no page links to the directory.

A directed, weighted graph with 100 vertices and 274 edges.

Which groups of pages can all reach each other by following links, so a crawler that enters a group can get back to where it started?

The graph has 6 strongly connected components. The ones with more than one vertex are P91, P92, P93, P94, P95, P96, P97, P98, P99 and P100; P31, P32, P33, P34, P35, P36 and P37; P53, P54, P55, P56, P57, P58, P59, P60, P61 and P62; P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 56 more; P47, P48, P49, P50, P51 and P52. The other component has one vertex, P90.

Step by step

  1. Gabow's path-based algorithm searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and numbers the vertices in the order it reaches them. Stack S holds every vertex reached but not yet placed in a component. Stack P holds the vertices on the search path that can still be the root of a component. An edge to a vertex still on S closes a cycle, so P loses every vertex numbered above that vertex. When a vertex finishes on top of P, it is the root of a component: it and the vertices above it on S form one strongly connected component.
  2. Start at P1, the first vertex. P1 gets number 0 and goes on S and P.
  3. Follow P1 to P3. P3 gets number 1 and goes on S and P.
  4. P3 has an edge to P1, which is still on S with number 0. That closes a cycle through P1, so every vertex on P numbered above 0 is in the same component as P1 and can't be its root. Pop P3 off P.
  5. Follow P3 to P4. P4 gets number 2 and goes on S and P.
  6. P4 has an edge to P3, which is still on S with number 1. That closes a cycle through P3, so every vertex on P numbered above 1 is in the same component as P3 and can't be its root. Pop P4 off P.

354 more steps lead to the last one:

  1. Done. Gabow found 6 strongly connected components, 1 of them with one vertex. Each component is listed after every component it has an edge into. Every vertex now shows the component it belongs to.

Use it in Go

for _, component := range connectivity.Gabow(g) {
	var names []string
	for _, v := range component {
		names = append(names, v.Label())
	}
	fmt.Println(strings.Join(names, ", "))
}

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.
  • 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.
  • 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.

All algorithms