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.

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

Import cycles

Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.

A directed graph with 18 vertices and 30 edges.

Which groups of packages import each other in a loop, so that none of them can load without the others?

Use it in Go

for _, component := range connectivity.Tarjan(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

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

All algorithms