{"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":"spreadsheet","name":"Spreadsheet formulas","description":"A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"B2","x":41,"y":195},{"id":"C2","x":41,"y":561},{"id":"D2","x":41,"y":884},{"id":"G2","x":41,"y":714},{"id":"G3","x":41,"y":408},{"id":"G4","x":194,"y":195},{"id":"G5","x":347,"y":302},{"id":"B3","x":194,"y":348},{"id":"C3","x":194,"y":654},{"id":"D3","x":194,"y":960},{"id":"B4","x":194,"y":42},{"id":"C4","x":194,"y":501},{"id":"D4","x":194,"y":807},{"id":"B5","x":347,"y":149},{"id":"C5","x":347,"y":455},{"id":"D5","x":347,"y":608},{"id":"B6","x":500,"y":218},{"id":"C6","x":500,"y":371},{"id":"D6","x":500,"y":524},{"id":"B7","x":653,"y":242},{"id":"C7","x":653,"y":395},{"id":"D7","x":653,"y":548},{"id":"E3","x":347,"y":761},{"id":"E7","x":806,"y":418},{"id":"E8","x":959,"y":487}],"edges":[{"from":"B2","to":"B3"},{"from":"G2","to":"B3"},{"from":"C2","to":"C3"},{"from":"G2","to":"C3"},{"from":"D2","to":"D3"},{"from":"G2","to":"D3"},{"from":"B2","to":"B4"},{"from":"G3","to":"B4"},{"from":"C2","to":"C4"},{"from":"G3","to":"C4"},{"from":"D2","to":"D4"},{"from":"G3","to":"D4"},{"from":"B3","to":"B5"},{"from":"B4","to":"B5"},{"from":"G4","to":"B5"},{"from":"C3","to":"C5"},{"from":"C4","to":"C5"},{"from":"G4","to":"C5"},{"from":"D3","to":"D5"},{"from":"D4","to":"D5"},{"from":"G4","to":"D5"},{"from":"B5","to":"B6"},{"from":"G5","to":"B6"},{"from":"C5","to":"C6"},{"from":"G5","to":"C6"},{"from":"D5","to":"D6"},{"from":"G5","to":"D6"},{"from":"B5","to":"B7"},{"from":"B6","to":"B7"},{"from":"C5","to":"C7"},{"from":"C6","to":"C7"},{"from":"D5","to":"D7"},{"from":"D6","to":"D7"},{"from":"B3","to":"E3"},{"from":"C3","to":"E3"},{"from":"D3","to":"E3"},{"from":"B7","to":"E7"},{"from":"C7","to":"E7"},{"from":"D7","to":"E7"},{"from":"E7","to":"E8"},{"from":"E3","to":"E8"}],"durations":{"B2":1,"B3":2,"B4":2,"B5":1,"B6":3,"B7":1,"C2":1,"C3":2,"C4":2,"C5":1,"C6":3,"C7":1,"D2":1,"D3":2,"D4":2,"D5":1,"D6":3,"D7":1,"E3":4,"E7":4,"E8":1,"G2":1,"G3":1,"G4":1,"G5":1},"durationUnit":"milliseconds","details":{"vertices":25,"edges":41,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.06833333333333333,"inDegree":{"min":0,"avg":1.64,"max":3},"outDegree":{"min":0,"avg":1.64,"max":3},"selfLoops":0,"components":1}},"problem":"Which cells can the sheet recompute at the same time, each round reading only cells an earlier round finished?","params":{},"result":{"kind":"groups","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","B4","C3","C4","D3","D4"],["B5","C5","D5","E3"],["B6","C6","D6"],["B7","C7","D7"],["E7"],["E8"]]},"answer":"The 25 vertices fall into 7 levels, so the work takes at least 7 rounds. The widest is level 1, with 7 vertices that can run at the same time: B2, C2, D2, G2, G3, G4 and G5.","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, 7 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Level 2, 6 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-3","label":"Level 3, 4 vertices","color":"#E69F00","shape":"filled"},{"id":"component-4","label":"Level 4, 3 vertices","color":"#F0E442","shape":"dashed-square"},{"id":"component-5","label":"Level 5, 3 vertices","color":"#D55E00","shape":"filled"},{"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":{"B2":"0"}},{"panel":"indegree","set":{"C2":"0"}},{"panel":"indegree","set":{"D2":"0"}},{"panel":"indegree","set":{"G2":"0"}},{"panel":"indegree","set":{"G3":"0"}},{"panel":"indegree","set":{"G4":"0"}},{"panel":"indegree","set":{"G5":"0"}},{"panel":"indegree","set":{"B3":"2"}},{"panel":"indegree","set":{"C3":"2"}},{"panel":"indegree","set":{"D3":"2"}},{"panel":"indegree","set":{"B4":"2"}},{"panel":"indegree","set":{"C4":"2"}},{"panel":"indegree","set":{"D4":"2"}},{"panel":"indegree","set":{"B5":"3"}},{"panel":"indegree","set":{"C5":"3"}},{"panel":"indegree","set":{"D5":"3"}},{"panel":"indegree","set":{"B6":"2"}},{"panel":"indegree","set":{"C6":"2"}},{"panel":"indegree","set":{"D6":"2"}},{"panel":"indegree","set":{"B7":"2"}},{"panel":"indegree","set":{"C7":"2"}},{"panel":"indegree","set":{"D7":"2"}},{"panel":"indegree","set":{"E3":"3"}},{"panel":"indegree","set":{"E7":"3"}},{"panel":"indegree","set":{"E8":"2"}}]},{"say":"Level 1: B2, C2, D2, G2, G3, G4 and G5 have no incoming edges, so they can run first, at the same time.","ops":[{"v":"B2","state":"component-1"},{"v":"C2","state":"component-1"},{"v":"D2","state":"component-1"},{"v":"G2","state":"component-1"},{"v":"G3","state":"component-1"},{"v":"G4","state":"component-1"},{"v":"G5","state":"component-1"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"]]}]},{"say":"Remove the 18 edges out of level 1. That leaves B3, C3, D3, B4, C4 and D4 with no incoming edges, so they go in level 2.","ops":[{"e":["B2","B3"],"state":"removed"},{"panel":"indegree","set":{"B3":"0"}},{"e":["B2","B4"],"state":"removed"},{"panel":"indegree","set":{"B4":"0"}},{"e":["C2","C3"],"state":"removed"},{"panel":"indegree","set":{"C3":"0"}},{"e":["C2","C4"],"state":"removed"},{"panel":"indegree","set":{"C4":"0"}},{"e":["D2","D3"],"state":"removed"},{"panel":"indegree","set":{"D3":"0"}},{"e":["D2","D4"],"state":"removed"},{"panel":"indegree","set":{"D4":"0"}},{"e":["G2","B3"],"state":"removed"},{"panel":"indegree","set":{"B3":"0"}},{"e":["G2","C3"],"state":"removed"},{"panel":"indegree","set":{"C3":"0"}},{"e":["G2","D3"],"state":"removed"},{"panel":"indegree","set":{"D3":"0"}},{"e":["G3","B4"],"state":"removed"},{"panel":"indegree","set":{"B4":"0"}},{"e":["G3","C4"],"state":"removed"},{"panel":"indegree","set":{"C4":"0"}},{"e":["G3","D4"],"state":"removed"},{"panel":"indegree","set":{"D4":"0"}},{"e":["G4","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"2"}},{"e":["G4","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"2"}},{"e":["G4","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"2"}},{"e":["G5","B6"],"state":"removed"},{"panel":"indegree","set":{"B6":"1"}},{"e":["G5","C6"],"state":"removed"},{"panel":"indegree","set":{"C6":"1"}},{"e":["G5","D6"],"state":"removed"},{"panel":"indegree","set":{"D6":"1"}},{"v":"B3","state":"waiting"},{"v":"C3","state":"waiting"},{"v":"D3","state":"waiting"},{"v":"B4","state":"waiting"},{"v":"C4","state":"waiting"},{"v":"D4","state":"waiting"}]},{"say":"Level 2: B3, C3, D3, B4, C4 and D4 have no incoming edges left, so they can run at the same time.","ops":[{"v":"B3","state":"component-2"},{"v":"C3","state":"component-2"},{"v":"D3","state":"component-2"},{"v":"B4","state":"component-2"},{"v":"C4","state":"component-2"},{"v":"D4","state":"component-2"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","C3","D3","B4","C4","D4"]]}]},{"say":"Remove the 9 edges out of level 2. That leaves E3, B5, C5 and D5 with no incoming edges, so they go in level 3.","ops":[{"e":["B3","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"0"}},{"e":["B3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"0"}},{"e":["C3","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"0"}},{"e":["C3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"0"}},{"e":["D3","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"0"}},{"e":["D3","E3"],"state":"removed"},{"panel":"indegree","set":{"E3":"0"}},{"e":["B4","B5"],"state":"removed"},{"panel":"indegree","set":{"B5":"0"}},{"e":["C4","C5"],"state":"removed"},{"panel":"indegree","set":{"C5":"0"}},{"e":["D4","D5"],"state":"removed"},{"panel":"indegree","set":{"D5":"0"}},{"v":"E3","state":"waiting"},{"v":"B5","state":"waiting"},{"v":"C5","state":"waiting"},{"v":"D5","state":"waiting"}]},{"say":"Level 3: B5, C5, D5 and E3 have no incoming edges left, so they can run at the same time.","ops":[{"v":"B5","state":"component-3"},{"v":"C5","state":"component-3"},{"v":"D5","state":"component-3"},{"v":"E3","state":"component-3"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","C3","D3","B4","C4","D4"],["B5","C5","D5","E3"]]}]},{"say":"Remove the 7 edges out of level 3. That leaves B6, C6 and D6 with no incoming edges, so they go in level 4.","ops":[{"e":["B5","B6"],"state":"removed"},{"panel":"indegree","set":{"B6":"0"}},{"e":["B5","B7"],"state":"removed"},{"panel":"indegree","set":{"B7":"1"}},{"e":["C5","C6"],"state":"removed"},{"panel":"indegree","set":{"C6":"0"}},{"e":["C5","C7"],"state":"removed"},{"panel":"indegree","set":{"C7":"1"}},{"e":["D5","D6"],"state":"removed"},{"panel":"indegree","set":{"D6":"0"}},{"e":["D5","D7"],"state":"removed"},{"panel":"indegree","set":{"D7":"1"}},{"e":["E3","E8"],"state":"removed"},{"panel":"indegree","set":{"E8":"1"}},{"v":"B6","state":"waiting"},{"v":"C6","state":"waiting"},{"v":"D6","state":"waiting"}]},{"say":"Level 4: B6, C6 and D6 have no incoming edges left, so they can run at the same time.","ops":[{"v":"B6","state":"component-4"},{"v":"C6","state":"component-4"},{"v":"D6","state":"component-4"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","C3","D3","B4","C4","D4"],["B5","C5","D5","E3"],["B6","C6","D6"]]}]},{"say":"Remove the 3 edges out of level 4. That leaves B7, C7 and D7 with no incoming edges, so they go in level 5.","ops":[{"e":["B6","B7"],"state":"removed"},{"panel":"indegree","set":{"B7":"0"}},{"e":["C6","C7"],"state":"removed"},{"panel":"indegree","set":{"C7":"0"}},{"e":["D6","D7"],"state":"removed"},{"panel":"indegree","set":{"D7":"0"}},{"v":"B7","state":"waiting"},{"v":"C7","state":"waiting"},{"v":"D7","state":"waiting"}]},{"say":"Level 5: B7, C7 and D7 have no incoming edges left, so they can run at the same time.","ops":[{"v":"B7","state":"component-5"},{"v":"C7","state":"component-5"},{"v":"D7","state":"component-5"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","C3","D3","B4","C4","D4"],["B5","C5","D5","E3"],["B6","C6","D6"],["B7","C7","D7"]]}]},{"say":"Remove the 3 edges out of level 5. That leaves E7 with no incoming edges, so it goes in level 6.","ops":[{"e":["B7","E7"],"state":"removed"},{"panel":"indegree","set":{"E7":"0"}},{"e":["C7","E7"],"state":"removed"},{"panel":"indegree","set":{"E7":"0"}},{"e":["D7","E7"],"state":"removed"},{"panel":"indegree","set":{"E7":"0"}},{"v":"E7","state":"waiting"}]},{"say":"Level 6: E7 is the only vertex with no incoming edges left. It runs on its own.","ops":[{"v":"E7","state":"single"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","C3","D3","B4","C4","D4"],["B5","C5","D5","E3"],["B6","C6","D6"],["B7","C7","D7"],["E7"]]}]},{"say":"Remove the edge from E7 to E8. That leaves E8 with no incoming edges, so it goes in level 7.","ops":[{"e":["E7","E8"],"state":"removed"},{"panel":"indegree","set":{"E8":"0"}},{"v":"E8","state":"waiting"}]},{"say":"Level 7: E8 is the only vertex with no incoming edges left. It runs on its own.","ops":[{"v":"E8","state":"single"},{"panel":"levels","groups":[["B2","C2","D2","G2","G3","G4","G5"],["B3","C3","D3","B4","C4","D4"],["B5","C5","D5","E3"],["B6","C6","D6"],["B7","C7","D7"],["E7"],["E8"]]}]},{"say":"Done. All 25 vertices have a level, 7 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}"}