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.

Go module graph

The module graph of github.com/gin-gonic/gin v1.9.1, as go mod graph prints it. Each edge points from a module to a module version it requires.

A directed graph with 62 vertices and 116 edges.

In what order can the modules be listed, so that each one comes before every module version it requires?

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