{"algorithm":"levels","about":["The levels of a directed graph without cycles are waves of work. The first level holds the vertices with no incoming edges. Each later level holds the vertices whose incoming edges all come from earlier levels, so the vertices of one level have no edges between them and can all run at once.","dag.Levels works like Kahn's topological sort. It counts the incoming edges of each vertex, and each time it removes the edges out of a vertex, a vertex left with none gets the level after the deepest vertex that pointed to it. The level of a vertex is the length of the longest path to it, levels[0] holds the vertices with no incoming edges, and the vertices of each level keep the graph's vertex order. It costs O(V+E).","The number of levels is the fewest rounds the work can take, and the widest level is the most workers a round can use. A round waits for its slowest task, though. To start each task as soon as its own dependencies finish, use the ready-set tracker. Levels returns ErrDAGHasCycle for a graph with a cycle and ErrNotDirected for an undirected one."],"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":"Which jobs of the pipeline can run at the same time, and how many rounds of jobs does it take?","params":{},"result":{"kind":"groups","groups":[["Checkout"],["Install"],["Compile","Lint"],["Docker image","Unit tests"],["Deploy"]]},"answer":"The 7 vertices fall into 5 levels, so the work takes at least 5 rounds. The widest is level 3, with 2 vertices that can run at the same time: Compile and Lint.","legend":{"vertex":[{"id":"idle","label":"Has incoming edges left","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"No incoming edges left, next level","color":"#E69F00","shape":"dashed-square"},{"id":"component-3","label":"Level 3, 2 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-4","label":"Level 4, 2 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"single","label":"A level of one vertex","color":"#CBD5E1","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"removed","label":"Removed, its start has a level","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"indegree","title":"In-degree left","kind":"table"},{"id":"levels","title":"Levels","kind":"groups"}]},"steps":[{"say":"Count the incoming edges of each vertex. A vertex with none waits for nothing, so it can go in the first level.","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"}}]},{"say":"Level 1: only Checkout has no incoming edges, so it runs first, on its own.","ops":[{"v":"Checkout","state":"single"},{"panel":"levels","groups":[["Checkout"]]}]},{"say":"Remove the 2 edges out of level 1. That leaves Install with no incoming edges, so it goes in level 2.","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"}]},{"say":"Level 2: Install is the only vertex with no incoming edges left. It runs on its own.","ops":[{"v":"Install","state":"single"},{"panel":"levels","groups":[["Checkout"],["Install"]]}]},{"say":"Remove the 2 edges out of level 2. That leaves Lint and Compile with no incoming edges, so they go in level 3.","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"}]},{"say":"Level 3: Lint and Compile have no incoming edges left, so they can run at the same time.","ops":[{"v":"Lint","state":"component-3"},{"v":"Compile","state":"component-3"},{"panel":"levels","groups":[["Checkout"],["Install"],["Lint","Compile"]]}]},{"say":"Remove the 3 edges out of level 3. That leaves Unit tests and Docker image with no incoming edges, so they go in level 4.","ops":[{"e":["Lint","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"2"}},{"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"}]},{"say":"Level 4: Unit tests and Docker image have no incoming edges left, so they can run at the same time.","ops":[{"v":"Unit tests","state":"component-4"},{"v":"Docker image","state":"component-4"},{"panel":"levels","groups":[["Checkout"],["Install"],["Lint","Compile"],["Unit tests","Docker image"]]}]},{"say":"Remove the 2 edges out of level 4. That leaves Deploy with no incoming edges, so it goes in level 5.","ops":[{"e":["Unit tests","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"0"}},{"e":["Docker image","Deploy"],"state":"removed"},{"panel":"indegree","set":{"Deploy":"0"}},{"v":"Deploy","state":"waiting"}]},{"say":"Level 5: Deploy is the only vertex with no incoming edges left. It runs on its own.","ops":[{"v":"Deploy","state":"single"},{"panel":"levels","groups":[["Checkout"],["Install"],["Lint","Compile"],["Unit tests","Docker image"],["Deploy"]]}]},{"say":"Done. All 7 vertices have a level, 5 levels in all, and every edge goes from a level to a later one."}],"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":"levels, err := dag.Levels(g)\nif err != nil {\n\treturn err\n}\nfor i, level := range levels {\n\tvar names []string\n\tfor _, v := range level {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(i, strings.Join(names, \", \"))\n}"}