{"algorithm":"dynamic-topological-sort","about":["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."],"template":{"id":"build-pipeline","name":"Build pipeline","description":"The jobs of a CI pipeline for a web service, and how many minutes each one takes. Each edge points from a job to a job that waits for it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"Checkout","x":100,"y":440},{"id":"Install","x":300,"y":440},{"id":"Lint","x":500,"y":280},{"id":"Compile","x":500,"y":560},{"id":"Unit tests","x":700,"y":440},{"id":"Docker image","x":700,"y":760},{"id":"Deploy","x":900,"y":440}],"edges":[{"from":"Checkout","to":"Install"},{"from":"Checkout","to":"Docker image"},{"from":"Install","to":"Lint"},{"from":"Install","to":"Compile"},{"from":"Lint","to":"Deploy"},{"from":"Compile","to":"Unit tests"},{"from":"Compile","to":"Docker image"},{"from":"Unit tests","to":"Deploy"},{"from":"Docker image","to":"Deploy"}],"durations":{"Checkout":1,"Compile":3,"Deploy":2,"Docker image":5,"Install":3,"Lint":6,"Unit tests":6},"durationUnit":"minutes","details":{"vertices":7,"edges":9,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.21428571428571427,"inDegree":{"min":0,"avg":1.2857142857142858,"max":3},"outDegree":{"min":0,"avg":1.2857142857142858,"max":2},"selfLoops":0,"components":1}},"problem":"A build tool meets the jobs from Deploy back to Checkout and reads their dependencies in no particular order. Add them one by one and keep a valid build order the whole time.","params":{},"result":{"kind":"edges","edges":[]},"answer":"AddEdge accepts all 9 edges, and the order it keeps is a valid build order after each one.","legend":{"vertex":[{"id":"idle","label":"Vertex","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Found by the forward search","color":"#E69F00","shape":"dashed-square"},{"id":"behind","label":"Reaches the source","color":"#CC79A7","shape":"ring"},{"id":"done","label":"Moved","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Not added yet","color":"#475569","shape":"line"},{"id":"new","label":"Being added","color":"#56B4E9","shape":"thick"},{"id":"added","label":"Added","color":"#009E73","shape":"line"},{"id":"rejected","label":"Turned away, would close a loop","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"order","title":"Order, first to last","kind":"list"},{"id":"numbers","title":"So far","kind":"numbers"}]},"steps":[{"say":"Start with the 7 vertices and no edges, from Deploy back to Checkout. 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.","ops":[{"panel":"order","list":[{"key":"Deploy","note":"1"},{"key":"Docker image","note":"2"},{"key":"Unit tests","note":"3"},{"key":"Compile","note":"4"},{"key":"Lint","note":"5"},{"key":"Install","note":"6"},{"key":"Checkout","note":"7"}]},{"panel":"numbers","set":{"Edges added":"0"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"0"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"0"}}]},{"say":"Add the edge from Checkout to Docker image. Docker image is at 2, before Checkout at 7, but nothing points to Checkout yet, so Checkout moves to the front without a search.","ops":[{"v":"Checkout","state":"done"},{"e":["Checkout","Docker image"],"state":"new"},{"panel":"order","list":[{"key":"Checkout","note":"1"},{"key":"Deploy","note":"2"},{"key":"Docker image","note":"3"},{"key":"Unit tests","note":"4"},{"key":"Compile","note":"5"},{"key":"Lint","note":"6"},{"key":"Install","note":"7"}]},{"panel":"numbers","set":{"Edges added":"1"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"1"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"7"}}]},{"say":"Add the edge from Unit tests to Deploy. Deploy is at 2, before Unit tests at 4, but nothing points to Unit tests yet, so Unit tests moves to the front without a search.","ops":[{"v":"Checkout","state":"idle"},{"e":["Checkout","Docker image"],"state":"added"},{"v":"Unit tests","state":"done"},{"e":["Unit tests","Deploy"],"state":"new"},{"panel":"order","list":[{"key":"Unit tests","note":"1"},{"key":"Checkout","note":"2"},{"key":"Deploy","note":"3"},{"key":"Docker image","note":"4"},{"key":"Compile","note":"5"},{"key":"Lint","note":"6"},{"key":"Install","note":"7"}]},{"panel":"numbers","set":{"Edges added":"2"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"2"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"14"}}]},{"say":"Add the edge from Install to Compile. Compile is at 5, before Install at 7, but nothing points to Install yet, so Install moves to the front without a search.","ops":[{"v":"Unit tests","state":"idle"},{"e":["Unit tests","Deploy"],"state":"added"},{"v":"Install","state":"done"},{"e":["Install","Compile"],"state":"new"},{"panel":"order","list":[{"key":"Install","note":"1"},{"key":"Unit tests","note":"2"},{"key":"Checkout","note":"3"},{"key":"Deploy","note":"4"},{"key":"Docker image","note":"5"},{"key":"Compile","note":"6"},{"key":"Lint","note":"7"}]},{"panel":"numbers","set":{"Edges added":"3"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"3"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"21"}}]},{"say":"Add the edge from Compile to Unit tests. Unit tests is at 2, before Compile at 6, and both ends already have edges, so it needs a search. Searching forward from Unit tests among the vertices placed before Compile finds Unit tests and Deploy and doesn't reach Compile, so there is no loop.","ops":[{"v":"Install","state":"idle"},{"e":["Install","Compile"],"state":"added"},{"v":"Unit tests","state":"waiting"},{"v":"Deploy","state":"waiting"},{"e":["Compile","Unit tests"],"state":"new"}]},{"say":"Two walks run side by side: one back from Compile through the vertices placed after Unit tests, and one forward through everything Unit tests reaches. The walk back finishes first, after 1 edge: nothing placed after Unit tests reaches Compile. Compile's side takes the first of the places the two sides hold, and the side found ahead takes the rest, each in the order it had. Compile, Unit tests and Deploy get new places.","ops":[{"v":"Compile","state":"behind"},{"v":"Compile","state":"done"},{"v":"Unit tests","state":"done"},{"v":"Deploy","state":"done"},{"panel":"order","list":[{"key":"Install","note":"1"},{"key":"Compile","note":"2"},{"key":"Checkout","note":"3"},{"key":"Unit tests","note":"4"},{"key":"Docker image","note":"5"},{"key":"Deploy","note":"6"},{"key":"Lint","note":"7"}]},{"panel":"numbers","set":{"Edges added":"4"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"6"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"28"}}]},{"say":"Add the edge from Lint to Deploy. Deploy is at 6, before Lint at 7, but nothing points to Lint yet, so Lint moves to the front without a search.","ops":[{"v":"Unit tests","state":"idle"},{"v":"Deploy","state":"idle"},{"v":"Compile","state":"idle"},{"e":["Compile","Unit tests"],"state":"added"},{"v":"Lint","state":"done"},{"e":["Lint","Deploy"],"state":"new"},{"panel":"order","list":[{"key":"Lint","note":"1"},{"key":"Install","note":"2"},{"key":"Compile","note":"3"},{"key":"Checkout","note":"4"},{"key":"Unit tests","note":"5"},{"key":"Docker image","note":"6"},{"key":"Deploy","note":"7"}]},{"panel":"numbers","set":{"Edges added":"5"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"7"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"35"}}]},{"say":"Add the edge from Checkout to Install. Install is at 2, before Checkout at 4, but nothing points to Checkout yet, so Checkout moves to the front without a search.","ops":[{"v":"Lint","state":"idle"},{"e":["Lint","Deploy"],"state":"added"},{"v":"Checkout","state":"done"},{"e":["Checkout","Install"],"state":"new"},{"panel":"order","list":[{"key":"Checkout","note":"1"},{"key":"Lint","note":"2"},{"key":"Install","note":"3"},{"key":"Compile","note":"4"},{"key":"Unit tests","note":"5"},{"key":"Docker image","note":"6"},{"key":"Deploy","note":"7"}]},{"panel":"numbers","set":{"Edges added":"6"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"8"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"42"}}]},{"say":"Add the edge from Compile to Docker image. Compile is at 4 and Docker image at 6, so the edge already points forward and nothing moves.","ops":[{"v":"Checkout","state":"idle"},{"e":["Checkout","Install"],"state":"added"},{"e":["Compile","Docker image"],"state":"new"},{"panel":"numbers","set":{"Edges added":"7"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"8"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"49"}}]},{"say":"Add the edge from Install to Lint. Lint is at 2, before Install at 3, and both ends already have edges, so it needs a search. Searching forward from Lint among the vertices placed before Install finds only Lint and doesn't reach Install, so there is no loop.","ops":[{"e":["Compile","Docker image"],"state":"added"},{"v":"Lint","state":"waiting"},{"e":["Install","Lint"],"state":"new"}]},{"say":"Two walks run side by side: one back from Install through the vertices placed after Lint, and one forward through everything Lint reaches. The walk back finishes first, after 1 edge: nothing placed after Lint reaches Install. Install's side takes the first of the places the two sides hold, and the side found ahead takes the rest, each in the order it had. Install and Lint get new places.","ops":[{"v":"Install","state":"behind"},{"v":"Install","state":"done"},{"v":"Lint","state":"done"},{"panel":"order","list":[{"key":"Checkout","note":"1"},{"key":"Install","note":"2"},{"key":"Lint","note":"3"},{"key":"Compile","note":"4"},{"key":"Unit tests","note":"5"},{"key":"Docker image","note":"6"},{"key":"Deploy","note":"7"}]},{"panel":"numbers","set":{"Edges added":"8"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"10"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"5"}},{"panel":"numbers","set":{"A full sort each time":"56"}}]},{"say":"Add the edge from Docker image to Deploy. Docker image is at 6 and Deploy at 7, so the edge already points forward and nothing moves.","ops":[{"v":"Lint","state":"idle"},{"v":"Install","state":"idle"},{"e":["Install","Lint"],"state":"added"},{"e":["Docker image","Deploy"],"state":"new"},{"panel":"numbers","set":{"Edges added":"9"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"10"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"5"}},{"panel":"numbers","set":{"A full sort each time":"63"}}]},{"say":"Done. AddEdge added 9 edges, 2 of them needed a reorder and 10 vertices moved in all. The searches visited 5 vertices in all, where sorting the whole graph after every edge would visit all 7 each time, 63 in all.","ops":[{"e":["Docker image","Deploy"],"state":"added"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"g := gograph.New[string](gograph.Directed(), gograph.Acyclic())\nfor _, label := range labels {\n\tg.AddVertexByLabel(label)\n}\nfor _, d := range deps {\n\t// AddEdge keeps a topological order and reorders only what it must.\n\t_, err := g.AddEdge(g.GetVertexByID(d[0]), g.GetVertexByID(d[1]))\n\tif errors.Is(err, gograph.ErrDAGCycle) {\n\t\tfmt.Println(d[0], \"->\", d[1]) // would close a loop, turned away\n\t}\n}"}
