{"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":"import-cycles","name":"Import cycles","description":"Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"main","x":500,"y":80},{"id":"cli","x":180,"y":240},{"id":"api","x":560,"y":200},{"id":"config","x":860,"y":320},{"id":"handlers","x":420,"y":340},{"id":"middleware","x":680,"y":370},{"id":"auth","x":720,"y":470},{"id":"session","x":700,"y":640},{"id":"users","x":480,"y":540},{"id":"billing","x":280,"y":470},{"id":"invoices","x":300,"y":650},{"id":"models","x":480,"y":790},{"id":"db","x":180,"y":800},{"id":"cache","x":320,"y":900},{"id":"email","x":700,"y":800},{"id":"templates","x":880,"y":860},{"id":"utils","x":900,"y":480},{"id":"logging","x":900,"y":660}],"edges":[{"from":"main","to":"cli"},{"from":"main","to":"api"},{"from":"main","to":"config"},{"from":"cli","to":"config"},{"from":"cli","to":"db"},{"from":"api","to":"handlers"},{"from":"api","to":"middleware"},{"from":"api","to":"config"},{"from":"handlers","to":"auth"},{"from":"handlers","to":"users"},{"from":"handlers","to":"billing"},{"from":"middleware","to":"auth"},{"from":"middleware","to":"logging"},{"from":"auth","to":"session"},{"from":"session","to":"users"},{"from":"users","to":"auth"},{"from":"users","to":"billing"},{"from":"users","to":"models"},{"from":"billing","to":"invoices"},{"from":"invoices","to":"users"},{"from":"invoices","to":"models"},{"from":"invoices","to":"email"},{"from":"models","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"models"},{"from":"email","to":"templates"},{"from":"templates","to":"email"},{"from":"config","to":"utils"},{"from":"utils","to":"logging"},{"from":"logging","to":"utils"}],"details":{"vertices":18,"edges":30,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.09803921568627451,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":1,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Add the imports one by one and keep a valid build order. Which imports does AddEdge turn away, because they would close a loop?","params":{},"result":{"kind":"edges","edges":[["auth","session"],["billing","invoices"],["db","cache"],["logging","utils"],["templates","email"]]},"answer":"AddEdge turns away 5 edges with ErrDAGCycle, since each would close a loop: auth to session, billing to invoices, db to cache, logging to utils and templates to email. It accepts the other 25, 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 18 vertices and no edges, from logging back to main. 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":"logging","note":"1"},{"key":"utils","note":"2"},{"key":"templates","note":"3"},{"key":"email","note":"4"},{"key":"cache","note":"5"},{"key":"db","note":"6"},{"key":"models","note":"7"},{"key":"invoices","note":"8"},{"key":"billing","note":"9"},{"key":"users","note":"10"},{"key":"session","note":"11"},{"key":"auth","note":"12"},{"key":"middleware","note":"13"},{"key":"handlers","note":"14"},{"key":"config","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"main","note":"18"}]},{"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 invoices to users. invoices is at 8 and users at 10, so the edge already points forward and nothing moves.","ops":[{"e":["invoices","users"],"state":"new"},{"panel":"numbers","set":{"Edges added":"1"}},{"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":"18"}}]},{"say":"Add the edge from invoices to email. email is at 4, before invoices at 8, but nothing points to invoices yet, so invoices moves to the front without a search.","ops":[{"e":["invoices","users"],"state":"added"},{"v":"invoices","state":"done"},{"e":["invoices","email"],"state":"new"},{"panel":"order","list":[{"key":"invoices","note":"1"},{"key":"logging","note":"2"},{"key":"utils","note":"3"},{"key":"templates","note":"4"},{"key":"email","note":"5"},{"key":"cache","note":"6"},{"key":"db","note":"7"},{"key":"models","note":"8"},{"key":"billing","note":"9"},{"key":"users","note":"10"},{"key":"session","note":"11"},{"key":"auth","note":"12"},{"key":"middleware","note":"13"},{"key":"handlers","note":"14"},{"key":"config","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"main","note":"18"}]},{"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":"36"}}]},{"say":"Add the edge from main to cli. cli is at 17, before main at 18, but nothing points to main yet, so main moves to the front without a search.","ops":[{"v":"invoices","state":"idle"},{"e":["invoices","email"],"state":"added"},{"v":"main","state":"done"},{"e":["main","cli"],"state":"new"},{"panel":"order","list":[{"key":"main","note":"1"},{"key":"invoices","note":"2"},{"key":"logging","note":"3"},{"key":"utils","note":"4"},{"key":"templates","note":"5"},{"key":"email","note":"6"},{"key":"cache","note":"7"},{"key":"db","note":"8"},{"key":"models","note":"9"},{"key":"billing","note":"10"},{"key":"users","note":"11"},{"key":"session","note":"12"},{"key":"auth","note":"13"},{"key":"middleware","note":"14"},{"key":"handlers","note":"15"},{"key":"config","note":"16"},{"key":"api","note":"17"},{"key":"cli","note":"18"}]},{"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":"54"}}]},{"say":"Add the edge from handlers to users. users is at 11, before handlers at 15, but nothing points to handlers yet, so handlers moves to the front without a search.","ops":[{"v":"main","state":"idle"},{"e":["main","cli"],"state":"added"},{"v":"handlers","state":"done"},{"e":["handlers","users"],"state":"new"},{"panel":"order","list":[{"key":"handlers","note":"1"},{"key":"main","note":"2"},{"key":"invoices","note":"3"},{"key":"logging","note":"4"},{"key":"utils","note":"5"},{"key":"templates","note":"6"},{"key":"email","note":"7"},{"key":"cache","note":"8"},{"key":"db","note":"9"},{"key":"models","note":"10"},{"key":"billing","note":"11"},{"key":"users","note":"12"},{"key":"session","note":"13"},{"key":"auth","note":"14"},{"key":"middleware","note":"15"},{"key":"config","note":"16"},{"key":"api","note":"17"},{"key":"cli","note":"18"}]},{"panel":"numbers","set":{"Edges added":"4"}},{"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":"72"}}]},{"say":"Add the edge from handlers to billing. handlers is at 1 and billing at 11, so the edge already points forward and nothing moves.","ops":[{"v":"handlers","state":"idle"},{"e":["handlers","users"],"state":"added"},{"e":["handlers","billing"],"state":"new"},{"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":"90"}}]},{"say":"Add the edge from users to billing. billing is at 11, before users at 12, but billing points to nothing yet, so billing moves to the end without a search.","ops":[{"e":["handlers","billing"],"state":"added"},{"v":"billing","state":"done"},{"e":["users","billing"],"state":"new"},{"panel":"order","list":[{"key":"handlers","note":"1"},{"key":"main","note":"2"},{"key":"invoices","note":"3"},{"key":"logging","note":"4"},{"key":"utils","note":"5"},{"key":"templates","note":"6"},{"key":"email","note":"7"},{"key":"cache","note":"8"},{"key":"db","note":"9"},{"key":"models","note":"10"},{"key":"users","note":"11"},{"key":"session","note":"12"},{"key":"auth","note":"13"},{"key":"middleware","note":"14"},{"key":"config","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"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":"108"}}]},{"say":"Add the edge from session to users. users is at 11, before session at 12, but nothing points to session yet, so session moves to the front without a search.","ops":[{"v":"billing","state":"idle"},{"e":["users","billing"],"state":"added"},{"v":"session","state":"done"},{"e":["session","users"],"state":"new"},{"panel":"order","list":[{"key":"session","note":"1"},{"key":"handlers","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"logging","note":"5"},{"key":"utils","note":"6"},{"key":"templates","note":"7"},{"key":"email","note":"8"},{"key":"cache","note":"9"},{"key":"db","note":"10"},{"key":"models","note":"11"},{"key":"users","note":"12"},{"key":"auth","note":"13"},{"key":"middleware","note":"14"},{"key":"config","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"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":"126"}}]},{"say":"Add the edge from config to utils. utils is at 6, before config at 15, but nothing points to config yet, so config moves to the front without a search.","ops":[{"v":"session","state":"idle"},{"e":["session","users"],"state":"added"},{"v":"config","state":"done"},{"e":["config","utils"],"state":"new"},{"panel":"order","list":[{"key":"config","note":"1"},{"key":"session","note":"2"},{"key":"handlers","note":"3"},{"key":"main","note":"4"},{"key":"invoices","note":"5"},{"key":"logging","note":"6"},{"key":"utils","note":"7"},{"key":"templates","note":"8"},{"key":"email","note":"9"},{"key":"cache","note":"10"},{"key":"db","note":"11"},{"key":"models","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"middleware","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"panel":"numbers","set":{"Edges added":"8"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"6"}},{"panel":"numbers","set":{"Turned away":"0"}},{"panel":"numbers","set":{"Vertices searched":"0"}},{"panel":"numbers","set":{"A full sort each time":"144"}}]},{"say":"Add the edge from billing to invoices. invoices is at 5, before billing at 18. Searching forward from invoices among the vertices placed before billing reaches billing, so the edge would close a loop. AddEdge turns it away with ErrDAGCycle and changes nothing.","ops":[{"v":"config","state":"idle"},{"e":["config","utils"],"state":"added"},{"v":"invoices","state":"waiting"},{"v":"users","state":"waiting"},{"v":"email","state":"waiting"},{"e":["billing","invoices"],"state":"rejected"},{"panel":"numbers","set":{"Edges added":"8"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"6"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"162"}}]},{"say":"Add the edge from main to api. main is at 4 and api at 16, so the edge already points forward and nothing moves.","ops":[{"v":"invoices","state":"idle"},{"v":"users","state":"idle"},{"v":"email","state":"idle"},{"e":["main","api"],"state":"new"},{"panel":"numbers","set":{"Edges added":"9"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"6"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"180"}}]},{"say":"Add the edge from models to db. db is at 11, before models at 12, but nothing points to models yet, so models moves to the front without a search.","ops":[{"e":["main","api"],"state":"added"},{"v":"models","state":"done"},{"e":["models","db"],"state":"new"},{"panel":"order","list":[{"key":"models","note":"1"},{"key":"config","note":"2"},{"key":"session","note":"3"},{"key":"handlers","note":"4"},{"key":"main","note":"5"},{"key":"invoices","note":"6"},{"key":"logging","note":"7"},{"key":"utils","note":"8"},{"key":"templates","note":"9"},{"key":"email","note":"10"},{"key":"cache","note":"11"},{"key":"db","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"middleware","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"panel":"numbers","set":{"Edges added":"10"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"7"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"198"}}]},{"say":"Add the edge from users to auth. users is at 13 and auth at 14, so the edge already points forward and nothing moves.","ops":[{"v":"models","state":"idle"},{"e":["models","db"],"state":"added"},{"e":["users","auth"],"state":"new"},{"panel":"numbers","set":{"Edges added":"11"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"7"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"216"}}]},{"say":"Add the edge from invoices to models. models is at 1, before invoices at 6, but nothing points to invoices yet, so invoices moves to the front without a search.","ops":[{"e":["users","auth"],"state":"added"},{"v":"invoices","state":"done"},{"e":["invoices","models"],"state":"new"},{"panel":"order","list":[{"key":"invoices","note":"1"},{"key":"models","note":"2"},{"key":"config","note":"3"},{"key":"session","note":"4"},{"key":"handlers","note":"5"},{"key":"main","note":"6"},{"key":"logging","note":"7"},{"key":"utils","note":"8"},{"key":"templates","note":"9"},{"key":"email","note":"10"},{"key":"cache","note":"11"},{"key":"db","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"middleware","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"panel":"numbers","set":{"Edges added":"12"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"8"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"234"}}]},{"say":"Add the edge from main to config. config is at 3, before main at 6, but nothing points to main yet, so main moves to the front without a search.","ops":[{"v":"invoices","state":"idle"},{"e":["invoices","models"],"state":"added"},{"v":"main","state":"done"},{"e":["main","config"],"state":"new"},{"panel":"order","list":[{"key":"main","note":"1"},{"key":"invoices","note":"2"},{"key":"models","note":"3"},{"key":"config","note":"4"},{"key":"session","note":"5"},{"key":"handlers","note":"6"},{"key":"logging","note":"7"},{"key":"utils","note":"8"},{"key":"templates","note":"9"},{"key":"email","note":"10"},{"key":"cache","note":"11"},{"key":"db","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"middleware","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"panel":"numbers","set":{"Edges added":"13"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"9"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"252"}}]},{"say":"Add the edge from cache to models. models is at 3, before cache at 11, but nothing points to cache yet, so cache moves to the front without a search.","ops":[{"v":"main","state":"idle"},{"e":["main","config"],"state":"added"},{"v":"cache","state":"done"},{"e":["cache","models"],"state":"new"},{"panel":"order","list":[{"key":"cache","note":"1"},{"key":"main","note":"2"},{"key":"invoices","note":"3"},{"key":"models","note":"4"},{"key":"config","note":"5"},{"key":"session","note":"6"},{"key":"handlers","note":"7"},{"key":"logging","note":"8"},{"key":"utils","note":"9"},{"key":"templates","note":"10"},{"key":"email","note":"11"},{"key":"db","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"middleware","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"panel":"numbers","set":{"Edges added":"14"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"10"}},{"panel":"numbers","set":{"Turned away":"1"}},{"panel":"numbers","set":{"Vertices searched":"3"}},{"panel":"numbers","set":{"A full sort each time":"270"}}]},{"say":"Add the edge from auth to session. session is at 6, before auth at 14. Searching forward from session among the vertices placed before auth reaches auth, so the edge would close a loop. AddEdge turns it away with ErrDAGCycle and changes nothing.","ops":[{"v":"cache","state":"idle"},{"e":["cache","models"],"state":"added"},{"v":"session","state":"waiting"},{"v":"users","state":"waiting"},{"e":["auth","session"],"state":"rejected"},{"panel":"numbers","set":{"Edges added":"14"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"10"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"5"}},{"panel":"numbers","set":{"A full sort each time":"288"}}]},{"say":"Add the edge from middleware to logging. logging is at 8, before middleware at 15, but nothing points to middleware yet, so middleware moves to the front without a search.","ops":[{"v":"session","state":"idle"},{"v":"users","state":"idle"},{"v":"middleware","state":"done"},{"e":["middleware","logging"],"state":"new"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"models","note":"5"},{"key":"config","note":"6"},{"key":"session","note":"7"},{"key":"handlers","note":"8"},{"key":"logging","note":"9"},{"key":"utils","note":"10"},{"key":"templates","note":"11"},{"key":"email","note":"12"},{"key":"db","note":"13"},{"key":"users","note":"14"},{"key":"auth","note":"15"},{"key":"api","note":"16"},{"key":"cli","note":"17"},{"key":"billing","note":"18"}]},{"panel":"numbers","set":{"Edges added":"15"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"11"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"5"}},{"panel":"numbers","set":{"A full sort each time":"306"}}]},{"say":"Add the edge from cli to db. db is at 13, before cli at 17, but db points to nothing yet, so db moves to the end without a search.","ops":[{"v":"middleware","state":"idle"},{"e":["middleware","logging"],"state":"added"},{"v":"db","state":"done"},{"e":["cli","db"],"state":"new"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"models","note":"5"},{"key":"config","note":"6"},{"key":"session","note":"7"},{"key":"handlers","note":"8"},{"key":"logging","note":"9"},{"key":"utils","note":"10"},{"key":"templates","note":"11"},{"key":"email","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"api","note":"15"},{"key":"cli","note":"16"},{"key":"billing","note":"17"},{"key":"db","note":"18"}]},{"panel":"numbers","set":{"Edges added":"16"}},{"panel":"numbers","set":{"Needed a reorder":"0"}},{"panel":"numbers","set":{"Vertices moved":"12"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"5"}},{"panel":"numbers","set":{"A full sort each time":"324"}}]},{"say":"Add the edge from cli to config. config is at 6, before cli at 16, and both ends already have edges, so it needs a search. Searching forward from config among the vertices placed before cli finds config and utils and doesn't reach cli, so there is no loop.","ops":[{"v":"db","state":"idle"},{"e":["cli","db"],"state":"added"},{"v":"config","state":"waiting"},{"v":"utils","state":"waiting"},{"e":["cli","config"],"state":"new"}]},{"say":"Two walks run side by side: one back from cli through the vertices placed after config, and one forward through everything config reaches. The walk back finishes first, after 1 edge: nothing placed after config reaches cli. cli'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. cli, config and utils get new places.","ops":[{"v":"cli","state":"behind"},{"v":"cli","state":"done"},{"v":"config","state":"done"},{"v":"utils","state":"done"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"models","note":"5"},{"key":"cli","note":"6"},{"key":"session","note":"7"},{"key":"handlers","note":"8"},{"key":"logging","note":"9"},{"key":"config","note":"10"},{"key":"templates","note":"11"},{"key":"email","note":"12"},{"key":"users","note":"13"},{"key":"auth","note":"14"},{"key":"api","note":"15"},{"key":"utils","note":"16"},{"key":"billing","note":"17"},{"key":"db","note":"18"}]},{"panel":"numbers","set":{"Edges added":"17"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"15"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"8"}},{"panel":"numbers","set":{"A full sort each time":"342"}}]},{"say":"Add the edge from utils to logging. logging is at 9, before utils at 16, but logging points to nothing yet, so logging moves to the end without a search.","ops":[{"v":"config","state":"idle"},{"v":"utils","state":"idle"},{"v":"cli","state":"idle"},{"e":["cli","config"],"state":"added"},{"v":"logging","state":"done"},{"e":["utils","logging"],"state":"new"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"models","note":"5"},{"key":"cli","note":"6"},{"key":"session","note":"7"},{"key":"handlers","note":"8"},{"key":"config","note":"9"},{"key":"templates","note":"10"},{"key":"email","note":"11"},{"key":"users","note":"12"},{"key":"auth","note":"13"},{"key":"api","note":"14"},{"key":"utils","note":"15"},{"key":"billing","note":"16"},{"key":"db","note":"17"},{"key":"logging","note":"18"}]},{"panel":"numbers","set":{"Edges added":"18"}},{"panel":"numbers","set":{"Needed a reorder":"1"}},{"panel":"numbers","set":{"Vertices moved":"16"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"8"}},{"panel":"numbers","set":{"A full sort each time":"360"}}]},{"say":"Add the edge from users to models. models is at 5, before users at 12, and both ends already have edges, so it needs a search. Searching forward from models among the vertices placed before users finds only models and doesn't reach users, so there is no loop.","ops":[{"v":"logging","state":"idle"},{"e":["utils","logging"],"state":"added"},{"v":"models","state":"waiting"},{"e":["users","models"],"state":"new"}]},{"say":"Two walks run side by side: one back from users through the vertices placed after models, and one forward through everything models reaches. The walk forward finishes first, after 3 edges, so models and everything it reaches, 2 vertices, move to the end of the order, in the order they had.","ops":[{"v":"models","state":"done"},{"v":"db","state":"done"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"cli","note":"5"},{"key":"session","note":"6"},{"key":"handlers","note":"7"},{"key":"config","note":"8"},{"key":"templates","note":"9"},{"key":"email","note":"10"},{"key":"users","note":"11"},{"key":"auth","note":"12"},{"key":"api","note":"13"},{"key":"utils","note":"14"},{"key":"billing","note":"15"},{"key":"logging","note":"16"},{"key":"models","note":"17"},{"key":"db","note":"18"}]},{"panel":"numbers","set":{"Edges added":"19"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"18"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"12"}},{"panel":"numbers","set":{"A full sort each time":"378"}}]},{"say":"Add the edge from email to templates. templates is at 9, before email at 10, but templates points to nothing yet, so templates moves to the end without a search.","ops":[{"v":"models","state":"idle"},{"v":"db","state":"idle"},{"e":["users","models"],"state":"added"},{"v":"templates","state":"done"},{"e":["email","templates"],"state":"new"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"cli","note":"5"},{"key":"session","note":"6"},{"key":"handlers","note":"7"},{"key":"config","note":"8"},{"key":"email","note":"9"},{"key":"users","note":"10"},{"key":"auth","note":"11"},{"key":"api","note":"12"},{"key":"utils","note":"13"},{"key":"billing","note":"14"},{"key":"logging","note":"15"},{"key":"models","note":"16"},{"key":"db","note":"17"},{"key":"templates","note":"18"}]},{"panel":"numbers","set":{"Edges added":"20"}},{"panel":"numbers","set":{"Needed a reorder":"2"}},{"panel":"numbers","set":{"Vertices moved":"19"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"12"}},{"panel":"numbers","set":{"A full sort each time":"396"}}]},{"say":"Add the edge from api to handlers. handlers is at 7, before api at 12, and both ends already have edges, so it needs a search. Searching forward from handlers among the vertices placed before api finds handlers, users and auth and doesn't reach api, so there is no loop.","ops":[{"v":"templates","state":"idle"},{"e":["email","templates"],"state":"added"},{"v":"handlers","state":"waiting"},{"v":"users","state":"waiting"},{"v":"auth","state":"waiting"},{"e":["api","handlers"],"state":"new"}]},{"say":"Two walks run side by side: one back from api through the vertices placed after handlers, and one forward through everything handlers reaches. The walk back finishes first, after 1 edge: nothing placed after handlers reaches api. api'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. api, handlers, users and auth get new places.","ops":[{"v":"api","state":"behind"},{"v":"api","state":"done"},{"v":"handlers","state":"done"},{"v":"users","state":"done"},{"v":"auth","state":"done"},{"panel":"order","list":[{"key":"middleware","note":"1"},{"key":"cache","note":"2"},{"key":"main","note":"3"},{"key":"invoices","note":"4"},{"key":"cli","note":"5"},{"key":"session","note":"6"},{"key":"api","note":"7"},{"key":"config","note":"8"},{"key":"email","note":"9"},{"key":"handlers","note":"10"},{"key":"users","note":"11"},{"key":"auth","note":"12"},{"key":"utils","note":"13"},{"key":"billing","note":"14"},{"key":"logging","note":"15"},{"key":"models","note":"16"},{"key":"db","note":"17"},{"key":"templates","note":"18"}]},{"panel":"numbers","set":{"Edges added":"21"}},{"panel":"numbers","set":{"Needed a reorder":"3"}},{"panel":"numbers","set":{"Vertices moved":"23"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"16"}},{"panel":"numbers","set":{"A full sort each time":"414"}}]},{"say":"Add the edge from handlers to auth. handlers is at 10 and auth at 12, so the edge already points forward and nothing moves.","ops":[{"v":"handlers","state":"idle"},{"v":"users","state":"idle"},{"v":"auth","state":"idle"},{"v":"api","state":"idle"},{"e":["api","handlers"],"state":"added"},{"e":["handlers","auth"],"state":"new"},{"panel":"numbers","set":{"Edges added":"22"}},{"panel":"numbers","set":{"Needed a reorder":"3"}},{"panel":"numbers","set":{"Vertices moved":"23"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"16"}},{"panel":"numbers","set":{"A full sort each time":"432"}}]},{"say":"Add the edge from middleware to auth. middleware is at 1 and auth at 12, so the edge already points forward and nothing moves.","ops":[{"e":["handlers","auth"],"state":"added"},{"e":["middleware","auth"],"state":"new"},{"panel":"numbers","set":{"Edges added":"23"}},{"panel":"numbers","set":{"Needed a reorder":"3"}},{"panel":"numbers","set":{"Vertices moved":"23"}},{"panel":"numbers","set":{"Turned away":"2"}},{"panel":"numbers","set":{"Vertices searched":"16"}},{"panel":"numbers","set":{"A full sort each time":"450"}}]},{"say":"Add the edge from db to cache. cache is at 2, before db at 17. Searching forward from cache among the vertices placed before db reaches db, so the edge would close a loop. AddEdge turns it away with ErrDAGCycle and changes nothing.","ops":[{"e":["middleware","auth"],"state":"added"},{"v":"cache","state":"waiting"},{"v":"models","state":"waiting"},{"e":["db","cache"],"state":"rejected"},{"panel":"numbers","set":{"Edges added":"23"}},{"panel":"numbers","set":{"Needed a reorder":"3"}},{"panel":"numbers","set":{"Vertices moved":"23"}},{"panel":"numbers","set":{"Turned away":"3"}},{"panel":"numbers","set":{"Vertices searched":"18"}},{"panel":"numbers","set":{"A full sort each time":"468"}}]},{"say":"Add the edge from api to middleware. middleware is at 1, before api at 7, and both ends already have edges, so it needs a search. Searching forward from middleware among the vertices placed before api finds only middleware and doesn't reach api, so there is no loop.","ops":[{"v":"cache","state":"idle"},{"v":"models","state":"idle"},{"v":"middleware","state":"waiting"},{"e":["api","middleware"],"state":"new"}]},{"say":"Two walks run side by side: one back from api through the vertices placed after middleware, and one forward through everything middleware reaches. The walk back finishes first, after 1 edge: main is placed after middleware and reaches api. api'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. main, api and middleware get new places.","ops":[{"v":"api","state":"behind"},{"v":"main","state":"behind"},{"v":"main","state":"done"},{"v":"api","state":"done"},{"v":"middleware","state":"done"},{"panel":"order","list":[{"key":"main","note":"1"},{"key":"cache","note":"2"},{"key":"api","note":"3"},{"key":"invoices","note":"4"},{"key":"cli","note":"5"},{"key":"session","note":"6"},{"key":"middleware","note":"7"},{"key":"config","note":"8"},{"key":"email","note":"9"},{"key":"handlers","note":"10"},{"key":"users","note":"11"},{"key":"auth","note":"12"},{"key":"utils","note":"13"},{"key":"billing","note":"14"},{"key":"logging","note":"15"},{"key":"models","note":"16"},{"key":"db","note":"17"},{"key":"templates","note":"18"}]},{"panel":"numbers","set":{"Edges added":"24"}},{"panel":"numbers","set":{"Needed a reorder":"4"}},{"panel":"numbers","set":{"Vertices moved":"26"}},{"panel":"numbers","set":{"Turned away":"3"}},{"panel":"numbers","set":{"Vertices searched":"21"}},{"panel":"numbers","set":{"A full sort each time":"486"}}]},{"say":"Add the edge from templates to email. email is at 9, before templates at 18. Searching forward from email among the vertices placed before templates reaches templates, so the edge would close a loop. AddEdge turns it away with ErrDAGCycle and changes nothing.","ops":[{"v":"middleware","state":"idle"},{"v":"api","state":"idle"},{"v":"main","state":"idle"},{"e":["api","middleware"],"state":"added"},{"v":"email","state":"waiting"},{"e":["templates","email"],"state":"rejected"},{"panel":"numbers","set":{"Edges added":"24"}},{"panel":"numbers","set":{"Needed a reorder":"4"}},{"panel":"numbers","set":{"Vertices moved":"26"}},{"panel":"numbers","set":{"Turned away":"4"}},{"panel":"numbers","set":{"Vertices searched":"22"}},{"panel":"numbers","set":{"A full sort each time":"504"}}]},{"say":"Add the edge from api to config. api is at 3 and config at 8, so the edge already points forward and nothing moves.","ops":[{"v":"email","state":"idle"},{"e":["api","config"],"state":"new"},{"panel":"numbers","set":{"Edges added":"25"}},{"panel":"numbers","set":{"Needed a reorder":"4"}},{"panel":"numbers","set":{"Vertices moved":"26"}},{"panel":"numbers","set":{"Turned away":"4"}},{"panel":"numbers","set":{"Vertices searched":"22"}},{"panel":"numbers","set":{"A full sort each time":"522"}}]},{"say":"Add the edge from logging to utils. utils is at 13, before logging at 15. Searching forward from utils among the vertices placed before logging reaches logging, so the edge would close a loop. AddEdge turns it away with ErrDAGCycle and changes nothing.","ops":[{"e":["api","config"],"state":"added"},{"v":"utils","state":"waiting"},{"e":["logging","utils"],"state":"rejected"},{"panel":"numbers","set":{"Edges added":"25"}},{"panel":"numbers","set":{"Needed a reorder":"4"}},{"panel":"numbers","set":{"Vertices moved":"26"}},{"panel":"numbers","set":{"Turned away":"5"}},{"panel":"numbers","set":{"Vertices searched":"23"}},{"panel":"numbers","set":{"A full sort each time":"540"}}]},{"say":"Done. AddEdge added 25 edges, 4 of them needed a reorder and 26 vertices moved in all. It turned away 5 edges that would close a loop. The searches visited 23 vertices in all, where sorting the whole graph after every edge would visit all 18 each time, 540 in all.","ops":[{"v":"utils","state":"idle"}]}],"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}"}
