{"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":"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":"Which courses can a student take in the same semester, and how many semesters does the degree take at least?","params":{},"result":{"kind":"groups","groups":[["Calculus 1","Discrete math","Programming 1"],["Calculus 2","Linear algebra","Programming 2"],["Computer systems","Data structures","Probability"],["Algorithms","Databases","Operating systems"],["Compilers","Machine learning"]]},"answer":"The 14 vertices fall into 5 levels, so the work takes at least 5 rounds. The widest is level 1, with 3 vertices that can run at the same time: Calculus 1, Discrete math and Programming 1.","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-1","label":"Level 1, 3 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Level 2, 3 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-3","label":"Level 3, 3 vertices","color":"#E69F00","shape":"filled"},{"id":"component-4","label":"Level 4, 3 vertices","color":"#F0E442","shape":"dashed-square"},{"id":"component-5","label":"Level 5, 2 vertices","color":"#D55E00","shape":"filled"}],"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":{"Programming 1":"0"}},{"panel":"indegree","set":{"Discrete math":"0"}},{"panel":"indegree","set":{"Calculus 1":"0"}},{"panel":"indegree","set":{"Programming 2":"1"}},{"panel":"indegree","set":{"Calculus 2":"1"}},{"panel":"indegree","set":{"Linear algebra":"1"}},{"panel":"indegree","set":{"Computer systems":"1"}},{"panel":"indegree","set":{"Data structures":"2"}},{"panel":"indegree","set":{"Probability":"2"}},{"panel":"indegree","set":{"Operating systems":"2"}},{"panel":"indegree","set":{"Databases":"1"}},{"panel":"indegree","set":{"Algorithms":"2"}},{"panel":"indegree","set":{"Compilers":"2"}},{"panel":"indegree","set":{"Machine learning":"3"}}]},{"say":"Level 1: Programming 1, Discrete math and Calculus 1 have no incoming edges, so they can run first, at the same time.","ops":[{"v":"Programming 1","state":"component-1"},{"v":"Discrete math","state":"component-1"},{"v":"Calculus 1","state":"component-1"},{"panel":"levels","groups":[["Programming 1","Discrete math","Calculus 1"]]}]},{"say":"Remove the 6 edges out of level 1. That leaves Programming 2, Calculus 2 and Linear algebra with no incoming edges, so they go in level 2.","ops":[{"e":["Programming 1","Programming 2"],"state":"removed"},{"panel":"indegree","set":{"Programming 2":"0"}},{"e":["Discrete math","Data structures"],"state":"removed"},{"panel":"indegree","set":{"Data structures":"1"}},{"e":["Discrete math","Probability"],"state":"removed"},{"panel":"indegree","set":{"Probability":"1"}},{"e":["Discrete math","Algorithms"],"state":"removed"},{"panel":"indegree","set":{"Algorithms":"1"}},{"e":["Calculus 1","Calculus 2"],"state":"removed"},{"panel":"indegree","set":{"Calculus 2":"0"}},{"e":["Calculus 1","Linear algebra"],"state":"removed"},{"panel":"indegree","set":{"Linear algebra":"0"}},{"v":"Programming 2","state":"waiting"},{"v":"Calculus 2","state":"waiting"},{"v":"Linear algebra","state":"waiting"}]},{"say":"Level 2: Programming 2, Calculus 2 and Linear algebra have no incoming edges left, so they can run at the same time.","ops":[{"v":"Programming 2","state":"component-2"},{"v":"Calculus 2","state":"component-2"},{"v":"Linear algebra","state":"component-2"},{"panel":"levels","groups":[["Programming 1","Discrete math","Calculus 1"],["Programming 2","Calculus 2","Linear algebra"]]}]},{"say":"Remove the 4 edges out of level 2. That leaves Computer systems, Data structures and Probability with no incoming edges, so they go in level 3.","ops":[{"e":["Programming 2","Computer systems"],"state":"removed"},{"panel":"indegree","set":{"Computer systems":"0"}},{"e":["Programming 2","Data structures"],"state":"removed"},{"panel":"indegree","set":{"Data structures":"0"}},{"e":["Calculus 2","Probability"],"state":"removed"},{"panel":"indegree","set":{"Probability":"0"}},{"e":["Linear algebra","Machine learning"],"state":"removed"},{"panel":"indegree","set":{"Machine learning":"2"}},{"v":"Computer systems","state":"waiting"},{"v":"Data structures","state":"waiting"},{"v":"Probability","state":"waiting"}]},{"say":"Level 3: Computer systems, Data structures and Probability have no incoming edges left, so they can run at the same time.","ops":[{"v":"Computer systems","state":"component-3"},{"v":"Data structures","state":"component-3"},{"v":"Probability","state":"component-3"},{"panel":"levels","groups":[["Programming 1","Discrete math","Calculus 1"],["Programming 2","Calculus 2","Linear algebra"],["Computer systems","Data structures","Probability"]]}]},{"say":"Remove the 6 edges out of level 3. That leaves Operating systems, Databases and Algorithms with no incoming edges, so they go in level 4.","ops":[{"e":["Computer systems","Operating systems"],"state":"removed"},{"panel":"indegree","set":{"Operating systems":"0"}},{"e":["Computer systems","Compilers"],"state":"removed"},{"panel":"indegree","set":{"Compilers":"1"}},{"e":["Data structures","Operating systems"],"state":"removed"},{"panel":"indegree","set":{"Operating systems":"0"}},{"e":["Data structures","Databases"],"state":"removed"},{"panel":"indegree","set":{"Databases":"0"}},{"e":["Data structures","Algorithms"],"state":"removed"},{"panel":"indegree","set":{"Algorithms":"0"}},{"e":["Probability","Machine learning"],"state":"removed"},{"panel":"indegree","set":{"Machine learning":"1"}},{"v":"Operating systems","state":"waiting"},{"v":"Databases","state":"waiting"},{"v":"Algorithms","state":"waiting"}]},{"say":"Level 4: Operating systems, Databases and Algorithms have no incoming edges left, so they can run at the same time.","ops":[{"v":"Operating systems","state":"component-4"},{"v":"Databases","state":"component-4"},{"v":"Algorithms","state":"component-4"},{"panel":"levels","groups":[["Programming 1","Discrete math","Calculus 1"],["Programming 2","Calculus 2","Linear algebra"],["Computer systems","Data structures","Probability"],["Operating systems","Databases","Algorithms"]]}]},{"say":"Remove the 2 edges out of level 4. That leaves Compilers and Machine learning with no incoming edges, so they go in level 5.","ops":[{"e":["Algorithms","Compilers"],"state":"removed"},{"panel":"indegree","set":{"Compilers":"0"}},{"e":["Algorithms","Machine learning"],"state":"removed"},{"panel":"indegree","set":{"Machine learning":"0"}},{"v":"Compilers","state":"waiting"},{"v":"Machine learning","state":"waiting"}]},{"say":"Level 5: Compilers and Machine learning have no incoming edges left, so they can run at the same time.","ops":[{"v":"Compilers","state":"component-5"},{"v":"Machine learning","state":"component-5"},{"panel":"levels","groups":[["Programming 1","Discrete math","Calculus 1"],["Programming 2","Calculus 2","Linear algebra"],["Computer systems","Data structures","Probability"],["Operating systems","Databases","Algorithms"],["Compilers","Machine learning"]]}]},{"say":"Done. All 14 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}"}