Stable topological sort

Puts the vertices of a graph without cycles in an order where every edge points forward, taking the ready vertex that comes first alphabetically.

Time complexity O((V+E) log V), gograph function gograph.StableTopologySort.

Spreadsheet formulas

A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each edge points from a cell to a formula that reads it.

A directed graph with 25 vertices and 41 edges.

In what order should the sheet recompute its cells, so that every formula reads cells that are already up to date?

Use it in Go

order, err := gograph.StableTopologySort(g, cmp.Compare)
if err != nil {
	return err // gograph.ErrDAGHasCycle
}
for _, v := range order {
	fmt.Println(v.Label())
}

Example graphs

• Build pipeline, 7 vertices and 9 edges
• Course prerequisites, 14 vertices and 18 edges
• Spreadsheet formulas, 25 vertices and 41 edges
• Go module graph, 62 vertices and 116 edges
• Monorepo build, 100 vertices and 266 edges

More in Ordering

• Topological sort: Puts the vertices of a graph without cycles in an order where every edge points forward, taking vertices in the order they become ready.

All algorithms