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.

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?

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