{"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":"course-prereqs","name":"Course prerequisites","description":"Fourteen courses of a computer science degree, each one semester long. Each edge points from a course to a course that requires it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"Programming 1","x":100,"y":200},{"id":"Discrete math","x":100,"y":500},{"id":"Calculus 1","x":100,"y":800},{"id":"Programming 2","x":300,"y":200},{"id":"Calculus 2","x":300,"y":720},{"id":"Linear algebra","x":300,"y":880},{"id":"Computer systems","x":500,"y":120},{"id":"Data structures","x":500,"y":360},{"id":"Probability","x":500,"y":700},{"id":"Operating systems","x":700,"y":260},{"id":"Databases","x":700,"y":420},{"id":"Algorithms","x":700,"y":580},{"id":"Compilers","x":900,"y":240},{"id":"Machine learning","x":900,"y":600}],"edges":[{"from":"Programming 1","to":"Programming 2"},{"from":"Discrete math","to":"Data structures"},{"from":"Discrete math","to":"Probability"},{"from":"Discrete math","to":"Algorithms"},{"from":"Calculus 1","to":"Calculus 2"},{"from":"Calculus 1","to":"Linear algebra"},{"from":"Programming 2","to":"Computer systems"},{"from":"Programming 2","to":"Data structures"},{"from":"Calculus 2","to":"Probability"},{"from":"Linear algebra","to":"Machine learning"},{"from":"Computer systems","to":"Operating systems"},{"from":"Computer systems","to":"Compilers"},{"from":"Data structures","to":"Operating systems"},{"from":"Data structures","to":"Databases"},{"from":"Data structures","to":"Algorithms"},{"from":"Probability","to":"Machine learning"},{"from":"Algorithms","to":"Compilers"},{"from":"Algorithms","to":"Machine learning"}],"durations":{"Algorithms":1,"Calculus 1":1,"Calculus 2":1,"Compilers":1,"Computer systems":1,"Data structures":1,"Databases":1,"Discrete math":1,"Linear algebra":1,"Machine learning":1,"Operating systems":1,"Probability":1,"Programming 1":1,"Programming 2":1},"durationUnit":"semesters","details":{"vertices":14,"edges":18,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.0989010989010989,"inDegree":{"min":0,"avg":1.2857142857142858,"max":3},"outDegree":{"min":0,"avg":1.2857142857142858,"max":3},"selfLoops":0,"components":1}},"problem":"Add the prerequisites one by one, from a list in no particular order, and keep a valid order to take the courses after each one.","params":{},"result":{"kind":"edges","edges":[]},"answer":"AddEdge accepts all 18 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 14 vertices and no edges, from Machine learning back to Programming 1. 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":"Machine learning","note":"1"},{"key":"Compilers","note":"2"},{"key":"Algorithms","note":"3"},{"key":"Databases","note":"4"},{"key":"Operating systems","note":"5"},{"key":"Probability","note":"6"},{"key":"Data structures","note":"7"},{"key":"Computer systems","note":"8"},{"key":"Linear algebra","note":"9"},{"key":"Calculus 2","note":"10"},{"key":"Programming 2","note":"11"},{"key":"Calculus 1","note":"12"},{"key":"Discrete math","note":"13"},{"key":"Programming 1","note":"14"}]},{"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 Discrete math to Data structures. Data structures is at 7, before Discrete math at 13, but nothing points to Discrete math yet, so Discrete math moves to the front without a search.","ops":[{"v":"Discrete math","state":"done"},{"e":["Discrete math","Data structures"],"state":"new"},{"panel":"order","list":[{"key":"Discrete math","note":"1"},{"key":"Machine learning","note":"2"},{"key":"Compilers","note":"3"},{"key":"Algorithms","note":"4"},{"key":"Databases","note":"5"},{"key":"Operating systems","note":"6"},{"key":"Probability","note":"7"},{"key":"Data structures","note":"8"},{"key":"Computer systems","note":"9"},{"key":"Linear algebra","note":"10"},{"key":"Calculus 2","note":"11"},{"key":"Programming 2","note":"12"},{"key":"Calculus 1","note":"13"},{"key":"Programming 1","note":"14"}]},{"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":"14"}}]},{"say":"Add the edge from Discrete math to Algorithms. Discrete math is at 1 and Algorithms at 4, so the edge already points forward and nothing moves.","ops":[{"v":"Discrete math","state":"idle"},{"e":["Discrete math","Data structures"],"state":"added"},{"e":["Discrete math","Algorithms"],"state":"new"},{"panel":"numbers","set":{"Edges added":"2"}},{"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":"28"}}]},{"say":"Add the edge from Programming 1 to Programming 2. Programming 2 is at 12, before Programming 1 at 14, but nothing points to Programming 1 yet, so Programming 1 moves to the front without a search.","ops":[{"e":["Discrete math","Algorithms"],"state":"added"},{"v":"Programming 1","state":"done"},{"e":["Programming 1","Programming 2"],"state":"new"},{"panel":"order","list":[{"key":"Programming 1","note":"1"},{"key":"Discrete math","note":"2"},{"key":"Machine learning","note":"3"},{"key":"Compilers","note":"4"},{"key":"Algorithms","note":"5"},{"key":"Databases","note":"6"},{"key":"Operating systems","note":"7"},{"key":"Probability","note":"8"},{"key":"Data structures","note":"9"},{"key":"Computer systems","note":"10"},{"key":"Linear algebra","note":"11"},{"key":"Calculus 2","note":"12"},{"key":"Programming 2","note":"13"},{"key":"Calculus 1","note":"14"}]},{"panel":"numbers","set":{"Edges added":"3"}},{"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":"42"}}]},{"say":"Add the edge from Discrete math to Probability. Discrete math is at 2 and Probability at 8, so the edge already points forward and nothing moves.","ops":[{"v":"Programming 1","state":"idle"},{"e":["Programming 1","Programming 2"],"state":"added"},{"e":["Discrete math","Probability"],"state":"new"},{"panel":"numbers","set":{"Edges added":"4"}},{"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":"56"}}]},{"say":"Add the edge from Calculus 1 to Linear algebra. Linear algebra is at 11, before Calculus 1 at 14, but nothing points to Calculus 1 yet, so Calculus 1 moves to the front without a search.","ops":[{"e":["Discrete math","Probability"],"state":"added"},{"v":"Calculus 1","state":"done"},{"e":["Calculus 1","Linear algebra"],"state":"new"},{"panel":"order","list":[{"key":"Calculus 1","note":"1"},{"key":"Programming 1","note":"2"},{"key":"Discrete math","note":"3"},{"key":"Machine learning","note":"4"},{"key":"Compilers","note":"5"},{"key":"Algorithms","note":"6"},{"key":"Databases","note":"7"},{"key":"Operating systems","note":"8"},{"key":"Probability","note":"9"},{"key":"Data structures","note":"10"},{"key":"Computer systems","note":"11"},{"key":"Linear algebra","note":"12"},{"key":"Calculus 2","note":"13"},{"key":"Programming 2","note":"14"}]},{"panel":"numbers","set":{"Edges added":"5"}},{"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":"70"}}]},{"say":"Add the edge from Computer systems to Compilers. Compilers is at 5, before Computer systems at 11, but nothing points to Computer systems yet, so Computer systems moves to the front without a search.","ops":[{"v":"Calculus 1","state":"idle"},{"e":["Calculus 1","Linear algebra"],"state":"added"},{"v":"Computer systems","state":"done"},{"e":["Computer systems","Compilers"],"state":"new"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Compilers","note":"6"},{"key":"Algorithms","note":"7"},{"key":"Databases","note":"8"},{"key":"Operating systems","note":"9"},{"key":"Probability","note":"10"},{"key":"Data structures","note":"11"},{"key":"Linear algebra","note":"12"},{"key":"Calculus 2","note":"13"},{"key":"Programming 2","note":"14"}]},{"panel":"numbers","set":{"Edges added":"6"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"4"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"84"}}]},{"say":"Add the edge from Data structures to Databases. Databases is at 8, before Data structures at 11, but Databases points to nothing yet, so Databases moves to the end without a search.","ops":[{"v":"Computer systems","state":"idle"},{"e":["Computer systems","Compilers"],"state":"added"},{"v":"Databases","state":"done"},{"e":["Data structures","Databases"],"state":"new"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Compilers","note":"6"},{"key":"Algorithms","note":"7"},{"key":"Operating systems","note":"8"},{"key":"Probability","note":"9"},{"key":"Data structures","note":"10"},{"key":"Linear algebra","note":"11"},{"key":"Calculus 2","note":"12"},{"key":"Programming 2","note":"13"},{"key":"Databases","note":"14"}]},{"panel":"numbers","set":{"Edges added":"7"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"5"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"98"}}]},{"say":"Add the edge from Programming 2 to Data structures. Data structures is at 10, before Programming 2 at 13, and both ends already have edges, so it needs a search. Searching forward from Data structures among the vertices placed before Programming 2 finds only Data structures and doesn't reach Programming 2, so there is no loop.","ops":[{"v":"Databases","state":"idle"},{"e":["Data structures","Databases"],"state":"added"},{"v":"Data structures","state":"waiting"},{"e":["Programming 2","Data structures"],"state":"new"}]},{"say":"Two walks run side by side: one back from Programming 2 through the vertices placed after Data structures, and one forward through everything Data structures reaches. The walk back finishes first, after 1 edge: nothing placed after Data structures reaches Programming 2. Programming 2'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. Programming 2 and Data structures get new places.","ops":[{"v":"Programming 2","state":"behind"},{"v":"Programming 2","state":"done"},{"v":"Data structures","state":"done"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Compilers","note":"6"},{"key":"Algorithms","note":"7"},{"key":"Operating systems","note":"8"},{"key":"Probability","note":"9"},{"key":"Programming 2","note":"10"},{"key":"Linear algebra","note":"11"},{"key":"Calculus 2","note":"12"},{"key":"Data structures","note":"13"},{"key":"Databases","note":"14"}]},{"panel":"numbers","set":{"Edges added":"8"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"7"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"2"}},{"panel":"numbers","set":{"A full sort each time":"112"}}]},{"say":"Add the edge from Computer systems to Operating systems. Computer systems is at 1 and Operating systems at 8, so the edge already points forward and nothing moves.","ops":[{"v":"Data structures","state":"idle"},{"v":"Programming 2","state":"idle"},{"e":["Programming 2","Data structures"],"state":"added"},{"e":["Computer systems","Operating systems"],"state":"new"},{"panel":"numbers","set":{"Edges added":"9"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"7"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"2"}},{"panel":"numbers","set":{"A full sort each time":"126"}}]},{"say":"Add the edge from Calculus 1 to Calculus 2. Calculus 1 is at 2 and Calculus 2 at 12, so the edge already points forward and nothing moves.","ops":[{"e":["Computer systems","Operating systems"],"state":"added"},{"e":["Calculus 1","Calculus 2"],"state":"new"},{"panel":"numbers","set":{"Edges added":"10"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"7"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"2"}},{"panel":"numbers","set":{"A full sort each time":"140"}}]},{"say":"Add the edge from Algorithms to Compilers. Compilers is at 6, before Algorithms at 7, but Compilers points to nothing yet, so Compilers moves to the end without a search.","ops":[{"e":["Calculus 1","Calculus 2"],"state":"added"},{"v":"Compilers","state":"done"},{"e":["Algorithms","Compilers"],"state":"new"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Algorithms","note":"6"},{"key":"Operating systems","note":"7"},{"key":"Probability","note":"8"},{"key":"Programming 2","note":"9"},{"key":"Linear algebra","note":"10"},{"key":"Calculus 2","note":"11"},{"key":"Data structures","note":"12"},{"key":"Databases","note":"13"},{"key":"Compilers","note":"14"}]},{"panel":"numbers","set":{"Edges added":"11"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"8"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"2"}},{"panel":"numbers","set":{"A full sort each time":"154"}}]},{"say":"Add the edge from Data structures to Algorithms. Algorithms is at 6, before Data structures at 12, and both ends already have edges, so it needs a search. Searching forward from Algorithms among the vertices placed before Data structures finds only Algorithms and doesn't reach Data structures, so there is no loop.","ops":[{"v":"Compilers","state":"idle"},{"e":["Algorithms","Compilers"],"state":"added"},{"v":"Algorithms","state":"waiting"},{"e":["Data structures","Algorithms"],"state":"new"}]},{"say":"Two walks run side by side: one back from Data structures through the vertices placed after Algorithms, and one forward through everything Algorithms reaches. The walk forward finishes first, after 3 edges, so Algorithms and everything it reaches, 2 vertices, move to the end of the order, in the order they had.","ops":[{"v":"Algorithms","state":"done"},{"v":"Compilers","state":"done"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Operating systems","note":"6"},{"key":"Probability","note":"7"},{"key":"Programming 2","note":"8"},{"key":"Linear algebra","note":"9"},{"key":"Calculus 2","note":"10"},{"key":"Data structures","note":"11"},{"key":"Databases","note":"12"},{"key":"Algorithms","note":"13"},{"key":"Compilers","note":"14"}]},{"panel":"numbers","set":{"Edges added":"12"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"10"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"6"}},{"panel":"numbers","set":{"A full sort each time":"168"}}]},{"say":"Add the edge from Calculus 2 to Probability. Probability is at 7, before Calculus 2 at 10, but Probability points to nothing yet, so Probability moves to the end without a search.","ops":[{"v":"Algorithms","state":"idle"},{"v":"Compilers","state":"idle"},{"e":["Data structures","Algorithms"],"state":"added"},{"v":"Probability","state":"done"},{"e":["Calculus 2","Probability"],"state":"new"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Operating systems","note":"6"},{"key":"Programming 2","note":"7"},{"key":"Linear algebra","note":"8"},{"key":"Calculus 2","note":"9"},{"key":"Data structures","note":"10"},{"key":"Databases","note":"11"},{"key":"Algorithms","note":"12"},{"key":"Compilers","note":"13"},{"key":"Probability","note":"14"}]},{"panel":"numbers","set":{"Edges added":"13"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"11"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"6"}},{"panel":"numbers","set":{"A full sort each time":"182"}}]},{"say":"Add the edge from Data structures to Operating systems. Operating systems is at 6, before Data structures at 10, but Operating systems points to nothing yet, so Operating systems moves to the end without a search.","ops":[{"v":"Probability","state":"idle"},{"e":["Calculus 2","Probability"],"state":"added"},{"v":"Operating systems","state":"done"},{"e":["Data structures","Operating systems"],"state":"new"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Machine learning","note":"5"},{"key":"Programming 2","note":"6"},{"key":"Linear algebra","note":"7"},{"key":"Calculus 2","note":"8"},{"key":"Data structures","note":"9"},{"key":"Databases","note":"10"},{"key":"Algorithms","note":"11"},{"key":"Compilers","note":"12"},{"key":"Probability","note":"13"},{"key":"Operating systems","note":"14"}]},{"panel":"numbers","set":{"Edges added":"14"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"12"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"6"}},{"panel":"numbers","set":{"A full sort each time":"196"}}]},{"say":"Add the edge from Linear algebra to Machine learning. Machine learning is at 5, before Linear algebra at 7, but Machine learning points to nothing yet, so Machine learning moves to the end without a search.","ops":[{"v":"Operating systems","state":"idle"},{"e":["Data structures","Operating systems"],"state":"added"},{"v":"Machine learning","state":"done"},{"e":["Linear algebra","Machine learning"],"state":"new"},{"panel":"order","list":[{"key":"Computer systems","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 1","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Programming 2","note":"5"},{"key":"Linear algebra","note":"6"},{"key":"Calculus 2","note":"7"},{"key":"Data structures","note":"8"},{"key":"Databases","note":"9"},{"key":"Algorithms","note":"10"},{"key":"Compilers","note":"11"},{"key":"Probability","note":"12"},{"key":"Operating systems","note":"13"},{"key":"Machine learning","note":"14"}]},{"panel":"numbers","set":{"Edges added":"15"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"13"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"6"}},{"panel":"numbers","set":{"A full sort each time":"210"}}]},{"say":"Add the edge from Probability to Machine learning. Probability is at 12 and Machine learning at 14, so the edge already points forward and nothing moves.","ops":[{"v":"Machine learning","state":"idle"},{"e":["Linear algebra","Machine learning"],"state":"added"},{"e":["Probability","Machine learning"],"state":"new"},{"panel":"numbers","set":{"Edges added":"16"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"13"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"6"}},{"panel":"numbers","set":{"A full sort each time":"224"}}]},{"say":"Add the edge from Programming 2 to Computer systems. Computer systems is at 1, before Programming 2 at 5, and both ends already have edges, so it needs a search. Searching forward from Computer systems among the vertices placed before Programming 2 finds only Computer systems and doesn't reach Programming 2, so there is no loop.","ops":[{"e":["Probability","Machine learning"],"state":"added"},{"v":"Computer systems","state":"waiting"},{"e":["Programming 2","Computer systems"],"state":"new"}]},{"say":"Two walks run side by side: one back from Programming 2 through the vertices placed after Computer systems, and one forward through everything Computer systems reaches. The walk back finishes first, after 1 edge: Programming 1 is placed after Computer systems and reaches Programming 2. Programming 2'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. Programming 1, Programming 2 and Computer systems get new places.","ops":[{"v":"Programming 2","state":"behind"},{"v":"Programming 1","state":"behind"},{"v":"Programming 1","state":"done"},{"v":"Programming 2","state":"done"},{"v":"Computer systems","state":"done"},{"panel":"order","list":[{"key":"Programming 1","note":"1"},{"key":"Calculus 1","note":"2"},{"key":"Programming 2","note":"3"},{"key":"Discrete math","note":"4"},{"key":"Computer systems","note":"5"},{"key":"Linear algebra","note":"6"},{"key":"Calculus 2","note":"7"},{"key":"Data structures","note":"8"},{"key":"Databases","note":"9"},{"key":"Algorithms","note":"10"},{"key":"Compilers","note":"11"},{"key":"Probability","note":"12"},{"key":"Operating systems","note":"13"},{"key":"Machine learning","note":"14"}]},{"panel":"numbers","set":{"Edges added":"17"}},{"panel":"numbers","set":{"Needed a reorder":"3"}},{"panel":"numbers","set":{"Vertices moved":"16"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"9"}},{"panel":"numbers","set":{"A full sort each time":"238"}}]},{"say":"Add the edge from Algorithms to Machine learning. Algorithms is at 10 and Machine learning at 14, so the edge already points forward and nothing moves.","ops":[{"v":"Computer systems","state":"idle"},{"v":"Programming 2","state":"idle"},{"v":"Programming 1","state":"idle"},{"e":["Programming 2","Computer systems"],"state":"added"},{"e":["Algorithms","Machine learning"],"state":"new"},{"panel":"numbers","set":{"Edges added":"18"}},{"panel":"numbers","set":{"Needed a reorder":"3"}},{"panel":"numbers","set":{"Vertices moved":"16"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"9"}},{"panel":"numbers","set":{"A full sort each time":"252"}}]},{"say":"Done. AddEdge added 18 edges, 3 of them needed a reorder and 16 vertices moved in all. The searches visited 9 vertices in all, where sorting the whole graph after every edge would visit all 14 each time, 252 in all.","ops":[{"e":["Algorithms","Machine learning"],"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}"}
