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.

Build pipeline

The jobs of a CI pipeline for a web service. Each edge points from a job to a job that waits for it.

A directed graph with 7 vertices and 9 edges.

In what order can the jobs run, so that each job starts only after the jobs it waits for?

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