Condensation

Replaces each strongly connected component with one vertex. What is left is a DAG, so it can be sorted and scheduled.

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

How it works

A strongly connected component is a group of vertices that can all reach each other. The condensation replaces each one with a single vertex, and all the edges from one component to another with a single edge. A cycle never leaves its component, so the condensed graph has none.

connectivity.Condense runs Tarjan once and numbers the components so that every edge between two of them goes from a lower number to a higher one, which is a topological order. The members of each component keep the graph's vertex order, and Members and ComponentOf map between the two graphs. It costs O(V+E).

WithComponentWeight gives each component a weight from its members, such as the sum of their weights, and WithCrossingWeight gives each condensed edge a weight from the edges it stands for. A build tool does this with packages that import each other: each loop is built as one unit, and the units are sorted like any other dependency graph.

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 a crawler move around freely, and which groups lead on to which once each group counts as one page?

The 100 vertices condense into 6 components joined by 8 edges, with no cycle left. The largest component has 66 vertices: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 56 more. The components are listed in topological order: every edge between two of them goes from an earlier one to a later one, so in reverse, each component comes after every component it has an edge into.

Step by step

Condense runs Tarjan once to find the strongly connected components, the groups of vertices that can all reach each other. It numbers them so that every edge between two components goes from a lower number to a higher one. Then each component becomes one vertex, and the edges from one component to another become one edge.
Component 1: P90 reaches no vertex that reaches it back, so it is a component on its own.
Component 2: P47, P48, P49, P50, P51 and P52 can all reach each other, so they become one vertex. The 10 edges among them drop out.
Component 3: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 56 more can all reach each other, so they become one vertex. The 177 edges among them drop out.
Component 4: P53, P54, P55, P56, P57, P58, P59, P60, P61 and P62 can all reach each other, so they become one vertex. The 24 edges among them drop out.
Component 5: P31, P32, P33, P34, P35, P36 and P37 can all reach each other, so they become one vertex. The 16 edges among them drop out.

4 more steps lead to the last one:

Done. The 100 vertices condense into 6 components and 8 edges between them. The condensed graph has no cycle, and its vertices are listed in topological order.

Use it in Go

sum := func(members []*gograph.Vertex[string]) float64 {
	var total float64
	for _, v := range members {
		total += v.Weight()
	}
	return total
}
c, err := connectivity.Condense(g, connectivity.WithComponentWeight(sum))
if err != nil {
	return err
}
for i, members := range c.Members {
	var names []string
	for _, v := range members {
		names = append(names, v.Label())
	}
	fmt.Println(i, strings.Join(names, ", "), c.Graph.GetVertexByID(i).Weight())
}
for _, e := range c.Graph.AllEdges() {
	fmt.Println(e.Source().Label(), "->", e.Destination().Label())
}

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