Dynamic topological sort
Keeps a topological order while edges are added one at a time, and moves only the vertices between the two ends of an edge that points backward.
Time complexity O(V+E) per edge, gograph function Graph.AddEdge.
gograph does this inside AddEdge on a graph created with gograph.Acyclic. It doesn't expose the order it keeps, so the order on this page comes from the step-by-step copy.
How it works
A build tool that adds dependencies one at a time has to know right away when a new one closes a loop. Sorting the whole graph again after every edge costs O(V+E) each time, which adds up as the graph grows. Pearce and Kelly's dynamic topological sort keeps an order instead, and when a new edge points backward in it, reorders only the vertices between the edge's two ends.
An edge that already points forward needs nothing. Neither does an edge from a vertex with no incoming edges, which can move to the front, or to a vertex with no outgoing edges, which can move to the end. Any other backward edge first searches forward from its destination among the vertices placed before its source. Reaching the source means the edge would close a loop, and AddEdge returns ErrDAGCycle without adding it.
Otherwise gograph runs two walks side by side, each allowed a number of edges that doubles every round, and uses the first to finish. The walk back from the source finds the vertices placed after the destination that reach the source. They swap places with the ones the forward search found, so each set keeps its order and every edge still points forward. The walk forward finds everything the destination reaches, and if it finishes first, all of it moves to the end of the order. Either way an edge costs little more than one search over the vertices the destination reaches.
All of this happens inside g.AddEdge on a graph created with gograph.Acyclic, and gograph.TopologySort still gives an order on demand. The order AddEdge keeps isn't exposed, so the steps here come from a copy of it, checked against the edges gograph turns away, and in the site's tests against gographtest.IsTopologicalOrder.
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.
Add the requirements of the module graph one by one and keep an order where every module comes before what it requires.
AddEdge accepts all 116 edges, and the order it keeps is a valid build order after each one.
Step by step
- Start with the 62 vertices and no edges, from github.com/stretchr/testify@v1.7.1 back to github.com/gin-gonic/gin. Each new vertex goes after the others, so the order starts as the order they were added in, and every edge below is added in a fixed mixed order.
- Add the edge from github.com/go-playground/validator/v10@v10.14.0 to golang.org/x/sys@v0.6.0. golang.org/x/sys@v0.6.0 is at 24, before github.com/go-playground/validator/v10@v10.14.0 at 54, but nothing points to github.com/go-playground/validator/v10@v10.14.0 yet, so github.com/go-playground/validator/v10@v10.14.0 moves to the front without a search.
- Add the edge from golang.org/x/arch@v0.3.0 to rsc.io/pdf@v0.1.1. rsc.io/pdf@v0.1.1 is at 19, before golang.org/x/arch@v0.3.0 at 42, but nothing points to golang.org/x/arch@v0.3.0 yet, so golang.org/x/arch@v0.3.0 moves to the front without a search.
- Add the edge from github.com/bytedance/sonic@v1.9.1 to golang.org/x/arch@v0.0.0-20210923205945-b76863e36670. golang.org/x/arch@v0.0.0-20210923205945-b76863e36670 is at 34, before github.com/bytedance/sonic@v1.9.1 at 61, but nothing points to github.com/bytedance/sonic@v1.9.1 yet, so github.com/bytedance/sonic@v1.9.1 moves to the front without a search.
- Add the edge from github.com/stretchr/testify@v1.3.0 to github.com/pmezard/go-difflib@v1.0.0. github.com/stretchr/testify@v1.3.0 is at 32 and github.com/pmezard/go-difflib@v1.0.0 at 47, so the edge already points forward and nothing moves.
- Add the edge from github.com/gin-gonic/gin to github.com/gabriel-vasile/mimetype@v1.4.2. github.com/gabriel-vasile/mimetype@v1.4.2 is at 59, before github.com/gin-gonic/gin at 62, but nothing points to github.com/gin-gonic/gin yet, so github.com/gin-gonic/gin moves to the front without a search.
121 more steps lead to the last one:
- Done. AddEdge added 116 edges, 10 of them needed a reorder and 76 vertices moved in all. The searches visited 47 vertices in all, where sorting the whole graph after every edge would visit all 62 each time, 7192 in all.
Use it in Go
g := gograph.New[string](gograph.Directed(), gograph.Acyclic())
for _, label := range labels {
g.AddVertexByLabel(label)
}
for _, d := range deps {
// AddEdge keeps a topological order and reorders only what it must.
_, err := g.AddEdge(g.GetVertexByID(d[0]), g.GetVertexByID(d[1]))
if errors.Is(err, gograph.ErrDAGCycle) {
fmt.Println(d[0], "->", d[1]) // would close a loop, turned away
}
}
Example graphs
- Build pipeline, 7 vertices and 9 edges
- Course prerequisites, 14 vertices and 18 edges
- Import cycles, 18 vertices and 30 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.
- 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.
- Topological levels: Splits a graph without cycles into levels, so that every edge goes to a later level and each level can run at the same time.
- Ready-set tracker: Hands out the tasks of a graph without cycles as soon as every task they depend on is done, so a slow task holds up only the tasks that wait for it.