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.

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?

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

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

All algorithms