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.
Time complexity O(V+E), gograph function gograph.TopologySort.
traverse.NewTopologicalIterator returns the same order one vertex at a time, because it calls gograph.TopologySort.
Monorepo build
One hundred build targets, T1 to T100, in the repository of an online shop. T1 to T32 are shared libraries, T33 to T41 the code generator and API definitions, T42 to T58 services, T59 to T63 batch jobs, T64 to T71 the API client and UI packages, T72 to T76 apps, T77 to T95 container images, and T96 to T100 the deploys and the contract and end-to-end tests. Each edge points from a target to a target that builds on it.
A directed graph with 100 vertices and 266 edges.
In what order can the targets build, so that each one builds after every target it builds on?
Use it in Go
order, err := gograph.TopologySort(g)
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
- 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.