Kosaraju

Finds the strongly connected components of a directed graph with two depth-first searches, the second on the graph with every edge reversed.

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

How it works

Kosaraju's algorithm finds the strongly connected components with two depth-first searches. The first runs over the whole graph and notes each vertex as it finishes, after everything it leads to. The second runs on a copy of the graph with every edge reversed, and takes its start vertices from the last one to finish to the first.

The vertex that finishes last is in a component that no other component can reach. With the edges reversed, a search from it can't leave that component, so it collects exactly that component. Each later search does the same with what is left, so a component comes out before any component it can reach.

Both searches cost O(V+E), and the reversed copy takes O(V+E) more memory than Tarjan or Gabow need. In exchange, each search is a plain depth-first search with nothing more to track.

Microservice calls

Nine services of an online shop. Each edge is a call from one service to another, and some services call each other back.

A directed graph with 9 vertices and 15 edges.

Which groups of services call each other in a loop, so that each service in a group depends on all the others?

The graph has 5 strongly connected components. The ones with more than one vertex are Orders, Payments and Shipping; Inventory and Search; Auth and Users. The other 2 components have one vertex each: Gateway and Notify.

Step by step

Kosaraju makes two passes. The first searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and pushes each vertex on a stack when it finishes, once every vertex it has an edge to has been reached. The second pass reverses every edge and searches again, taking its starts from the top of that stack. Each search in the second pass reaches exactly one strongly connected component.
Start the first pass at Gateway, the first vertex.
Follow Gateway to Auth.
Follow Auth to Users.
Follow Users to Notify.
Notify has no unreached neighbors left, so it finishes, number 1. Push it on the finish stack. Back to Users.

32 more steps lead to the last one:

Done. Kosaraju found 5 strongly connected components, 2 of them with one vertex. Each component is listed before every component it has an edge into. Every vertex now shows the component it belongs to.

Use it in Go

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

Example graphs

Microservice calls, 9 vertices and 15 edges
Import cycles, 18 vertices and 30 edges
Linked web pages, 40 vertices and 114 edges
Web crawl, 100 vertices and 274 edges