{"algorithm":"topological-sort","about":["A topological sort puts the vertices of a directed graph without cycles in an order where every edge points forward: for an edge from A to B, A comes before B. gograph uses Kahn's algorithm. It counts the incoming edges of each vertex and queues the vertices that have none. Each time it takes a vertex from the queue, it removes that vertex's outgoing edges, and a vertex left with no incoming edges joins the back of the queue.","If the queue empties before every vertex is placed, the rest are on a cycle or after one, and gograph.TopologySort returns ErrDAGHasCycle instead of an order. It costs O(V+E). The order depends only on the order the vertices and edges were added, so a graph built the same way gives the same order every time.","Use it to schedule work with dependencies, such as build steps, course plans or database migrations. To break ties between ready vertices by a fixed rule instead of by the order the graph was built, use the stable topological sort."],"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":"In what order can the jobs run, so that each job starts only after the jobs it waits for?","params":{},"result":{"kind":"order","vertices":["Checkout","Install","Lint","Compile","Unit tests","Docker image","Deploy"]},"answer":"In this order, every edge points forward: Checkout, Install, Lint, Compile, Unit tests, Docker image and Deploy.","legend":{"vertex":[{"id":"idle","label":"Has incoming edges left","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In the queue","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Being placed","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Placed","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"removed","label":"Removed, its start is placed","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"ready","title":"Queue, front first","kind":"list"},{"id":"indegree","title":"In-degree left","kind":"table"},{"id":"order","title":"Topological order","kind":"list"}]},"steps":[{"say":"Count the incoming edges of each vertex, its in-degree. Only Checkout has none, so it starts the queue.","ops":[{"panel":"indegree","set":{"Checkout":"0"}},{"panel":"indegree","set":{"Install":"1"}},{"panel":"indegree","set":{"Lint":"1"}},{"panel":"indegree","set":{"Compile":"1"}},{"panel":"indegree","set":{"Unit tests":"1"}},{"panel":"indegree","set":{"Docker image":"2"}},{"panel":"indegree","set":{"Deploy":"3"}},{"v":"Checkout","state":"waiting"},{"panel":"ready","list":[{"key":"Checkout"}]}]},{"say":"Take Checkout, the only vertex in the queue, and add it to the order.","ops":[{"v":"Checkout","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"}]}]},{"say":"Remove the 2 edges out of Checkout. Install has no incoming edges left, so it joins the back of the queue. Docker image still has 1 incoming edge.","ops":[{"e":["Checkout","Install"],"state":"removed"},{"panel":"indegree","set":{"Install":"0"}},{"e":["Checkout","Docker image"],"state":"removed"},{"panel":"indegree","set":{"Docker image":"1"}},{"v":"Install","state":"waiting"},{"panel":"ready","list":[{"key":"Install"}]}]},{"say":"Take Install, the only vertex in the queue, and add it to the order.","ops":[{"v":"Install","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"}]},{"v":"Checkout","state":"done"}]},{"say":"Remove the 2 edges out of Install. Lint and Compile have no incoming edges left, so they join the back of the queue in that order.","ops":[{"e":["Install","Lint"],"state":"removed"},{"panel":"indegree","set":{"Lint":"0"}},{"e":["Install","Compile"],"state":"removed"},{"panel":"indegree","set":{"Compile":"0"}},{"v":"Lint","state":"waiting"},{"v":"Compile","state":"waiting"},{"panel":"ready","list":[{"key":"Lint"},{"key":"Compile"}]}]},{"say":"Take Lint from the front of the queue and add it to the order.","ops":[{"v":"Lint","state":"current"},{"panel":"ready","list":[{"key":"Compile"}]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"}]},{"v":"Install","state":"done"}]},{"say":"Remove the edge from Lint to Deploy. Deploy still has 2 incoming edges.","ops":[{"e":["Lint","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"2"}},{"panel":"ready","list":[{"key":"Compile"}]}]},{"say":"Take Compile, the only vertex in the queue, and add it to the order.","ops":[{"v":"Compile","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"},{"key":"Compile"}]},{"v":"Lint","state":"done"}]},{"say":"Remove the 2 edges out of Compile. Unit tests and Docker image have no incoming edges left, so they join the back of the queue in that order.","ops":[{"e":["Compile","Unit tests"],"state":"removed"},{"panel":"indegree","set":{"Unit tests":"0"}},{"e":["Compile","Docker image"],"state":"removed"},{"panel":"indegree","set":{"Docker image":"0"}},{"v":"Unit tests","state":"waiting"},{"v":"Docker image","state":"waiting"},{"panel":"ready","list":[{"key":"Unit tests"},{"key":"Docker image"}]}]},{"say":"Take Unit tests from the front of the queue and add it to the order.","ops":[{"v":"Unit tests","state":"current"},{"panel":"ready","list":[{"key":"Docker image"}]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"},{"key":"Compile"},{"key":"Unit tests"}]},{"v":"Compile","state":"done"}]},{"say":"Remove the edge from Unit tests to Deploy. Deploy still has 1 incoming edge.","ops":[{"e":["Unit tests","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"1"}},{"panel":"ready","list":[{"key":"Docker image"}]}]},{"say":"Take Docker image, the only vertex in the queue, and add it to the order.","ops":[{"v":"Docker image","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"},{"key":"Compile"},{"key":"Unit tests"},{"key":"Docker image"}]},{"v":"Unit tests","state":"done"}]},{"say":"Remove the edge from Docker image to Deploy. Deploy has no incoming edges left, so it joins the back of the queue.","ops":[{"e":["Docker image","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"0"}},{"v":"Deploy","state":"waiting"},{"panel":"ready","list":[{"key":"Deploy"}]}]},{"say":"Take Deploy, the only vertex in the queue, and add it to the order. It has no outgoing edges.","ops":[{"v":"Deploy","state":"current"},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Checkout"},{"key":"Install"},{"key":"Lint"},{"key":"Compile"},{"key":"Unit tests"},{"key":"Docker image"},{"key":"Deploy"}]},{"v":"Docker image","state":"done"}]},{"say":"Done. All 7 vertices are in the order, and every edge points from an earlier vertex to a later one.","ops":[{"v":"Deploy","state":"done"}]}],"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":"order, err := traverse.Topological(g)\nif err != nil {\n\treturn err // gograph.ErrDAGHasCycle\n}\nfor v := range order {\n\tfmt.Println(v.Label())\n}"}
