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.
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.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.