{"algorithm":"critical-path","about":["When tasks run in parallel, the total time is set by the longest chain of tasks that wait on each other. That chain is the critical path. Making a task on it faster shortens the whole run, and making any other task faster doesn't, since that task already has time to spare.","dag.CriticalPath takes the vertices in topological order, as Kahn's algorithm does. Each vertex finishes at the latest finish among the vertices it depends on, plus its own weight and the weight of the edge from that dependency. The path ends at the vertex with the latest finish among those nothing depends on, and following each vertex back to the dependency that set its start gives the path. It costs O(V+E).","Weights are read with Vertex.Weight and Edge.Weight, so the graph needs no Weighted option, and an unset weight counts as 0. On a tie, the path found first in topological order wins. CriticalPathFunc takes the costs from functions instead, such as durations measured on the last run. For a graph with cycles, condense it first: each loop of tasks becomes one vertex, which WithComponentWeight can give the sum of its tasks."],"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":"Even with a thread for every cell, how long does a recompute take, and which chain of formulas sets that?","params":{},"result":{"kind":"order","vertices":["B2","B3","B5","B6","B7","E7","E8"]},"answer":"The critical path is B2, B3, B5, B6, B7, E7 and E8, 7 tasks taking 13 in all. Every task one after another takes 43, so running in parallel saves 30. Only a faster task on the path makes the whole run shorter.","legend":{"vertex":[{"id":"idle","label":"Not checked yet","color":"#64748B","shape":"hollow"},{"id":"current","label":"Being checked","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Earliest finish known","color":"#009E73","shape":"filled"},{"id":"critical","label":"On the critical path","color":"#D55E00","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"latest","label":"From the dependency that finishes last so far","color":"#56B4E9","shape":"thick"},{"id":"examined","label":"From a dependency that finishes earlier","color":"#CC79A7","shape":"dashed"},{"id":"critical","label":"On the critical path","color":"#D55E00","shape":"thick"}],"panels":[{"id":"finish","title":"Earliest finish","kind":"table"},{"id":"order","title":"Critical path","kind":"list"}]},"steps":[{"say":"Take the tasks in topological order, so every task comes after the tasks it depends on. A task finishes at the latest finish among its dependencies, plus its own weight. The tasks with no dependencies, B2, C2, D2, G2, G3, G4 and G5, start at 0."},{"say":"B2 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. B3 and B4 can't start before 1.","ops":[{"v":"B2","state":"current"},{"panel":"finish","set":{"B2":"1"}},{"e":["B2","B3"],"state":"latest"},{"e":["B2","B4"],"state":"latest"}]},{"say":"C2 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. C3 and C4 can't start before 1.","ops":[{"v":"C2","state":"current"},{"panel":"finish","set":{"C2":"1"}},{"e":["C2","C3"],"state":"latest"},{"e":["C2","C4"],"state":"latest"},{"v":"B2","state":"done"}]},{"say":"D2 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. D3 and D4 can't start before 1.","ops":[{"v":"D2","state":"current"},{"panel":"finish","set":{"D2":"1"}},{"e":["D2","D3"],"state":"latest"},{"e":["D2","D4"],"state":"latest"},{"v":"C2","state":"done"}]},{"say":"G2 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. B3, C3 and D3 already wait at least that long for other tasks.","ops":[{"v":"G2","state":"current"},{"panel":"finish","set":{"G2":"1"}},{"e":["G2","B3"],"state":"examined"},{"e":["G2","C3"],"state":"examined"},{"e":["G2","D3"],"state":"examined"},{"v":"D2","state":"done"}]},{"say":"G3 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. B4, C4 and D4 already wait at least that long for other tasks.","ops":[{"v":"G3","state":"current"},{"panel":"finish","set":{"G3":"1"}},{"e":["G3","B4"],"state":"examined"},{"e":["G3","C4"],"state":"examined"},{"e":["G3","D4"],"state":"examined"},{"v":"G2","state":"done"}]},{"say":"G4 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. B5, C5 and D5 can't start before 1.","ops":[{"v":"G4","state":"current"},{"panel":"finish","set":{"G4":"1"}},{"e":["G4","B5"],"state":"latest"},{"e":["G4","C5"],"state":"latest"},{"e":["G4","D5"],"state":"latest"},{"v":"G3","state":"done"}]},{"say":"G5 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. B6, C6 and D6 can't start before 1.","ops":[{"v":"G5","state":"current"},{"panel":"finish","set":{"G5":"1"}},{"e":["G5","B6"],"state":"latest"},{"e":["G5","C6"],"state":"latest"},{"e":["G5","D6"],"state":"latest"},{"v":"G4","state":"done"},{"e":["G4","B5"],"state":"examined"}]},{"say":"B3 starts at 1, when B2 finishes, and takes 2, so it finishes at 3. B5 and E3 can't start before 3.","ops":[{"v":"B3","state":"current"},{"panel":"finish","set":{"B3":"3"}},{"e":["B3","B5"],"state":"latest"},{"e":["B3","E3"],"state":"latest"},{"v":"G5","state":"done"},{"e":["G4","C5"],"state":"examined"}]},{"say":"C3 starts at 1, when C2 finishes, and takes 2, so it finishes at 3. C5 can't start before 3. E3 already waits at least that long for another task.","ops":[{"v":"C3","state":"current"},{"panel":"finish","set":{"C3":"3"}},{"e":["C3","C5"],"state":"latest"},{"e":["C3","E3"],"state":"examined"},{"v":"B3","state":"done"},{"e":["G4","D5"],"state":"examined"}]},{"say":"D3 starts at 1, when D2 finishes, and takes 2, so it finishes at 3. D5 can't start before 3. E3 already waits at least that long for another task.","ops":[{"v":"D3","state":"current"},{"panel":"finish","set":{"D3":"3"}},{"e":["D3","D5"],"state":"latest"},{"e":["D3","E3"],"state":"examined"},{"v":"C3","state":"done"}]},{"say":"B4 starts at 1, when B2 finishes, and takes 2, so it finishes at 3. B5 already waits at least that long for another task.","ops":[{"v":"B4","state":"current"},{"panel":"finish","set":{"B4":"3"}},{"e":["B4","B5"],"state":"examined"},{"v":"D3","state":"done"}]},{"say":"C4 starts at 1, when C2 finishes, and takes 2, so it finishes at 3. C5 already waits at least that long for another task.","ops":[{"v":"C4","state":"current"},{"panel":"finish","set":{"C4":"3"}},{"e":["C4","C5"],"state":"examined"},{"v":"B4","state":"done"}]},{"say":"D4 starts at 1, when D2 finishes, and takes 2, so it finishes at 3. D5 already waits at least that long for another task.","ops":[{"v":"D4","state":"current"},{"panel":"finish","set":{"D4":"3"}},{"e":["D4","D5"],"state":"examined"},{"v":"C4","state":"done"}]},{"say":"E3 starts at 3, when B3 finishes, and takes 4, so it finishes at 7. E8 can't start before 7.","ops":[{"v":"E3","state":"current"},{"panel":"finish","set":{"E3":"7"}},{"e":["E3","E8"],"state":"latest"},{"v":"D4","state":"done"},{"e":["G5","B6"],"state":"examined"}]},{"say":"B5 starts at 3, when B3 finishes, and takes 1, so it finishes at 4. B6 and B7 can't start before 4.","ops":[{"v":"B5","state":"current"},{"panel":"finish","set":{"B5":"4"}},{"e":["B5","B6"],"state":"latest"},{"e":["B5","B7"],"state":"latest"},{"v":"E3","state":"done"},{"e":["G5","C6"],"state":"examined"}]},{"say":"C5 starts at 3, when C3 finishes, and takes 1, so it finishes at 4. C6 and C7 can't start before 4.","ops":[{"v":"C5","state":"current"},{"panel":"finish","set":{"C5":"4"}},{"e":["C5","C6"],"state":"latest"},{"e":["C5","C7"],"state":"latest"},{"v":"B5","state":"done"},{"e":["G5","D6"],"state":"examined"}]},{"say":"D5 starts at 3, when D3 finishes, and takes 1, so it finishes at 4. D6 and D7 can't start before 4.","ops":[{"v":"D5","state":"current"},{"panel":"finish","set":{"D5":"4"}},{"e":["D5","D6"],"state":"latest"},{"e":["D5","D7"],"state":"latest"},{"v":"C5","state":"done"},{"e":["B5","B7"],"state":"examined"}]},{"say":"B6 starts at 4, when B5 finishes, and takes 3, so it finishes at 7. B7 can't start before 7.","ops":[{"v":"B6","state":"current"},{"panel":"finish","set":{"B6":"7"}},{"e":["B6","B7"],"state":"latest"},{"v":"D5","state":"done"},{"e":["C5","C7"],"state":"examined"}]},{"say":"C6 starts at 4, when C5 finishes, and takes 3, so it finishes at 7. C7 can't start before 7.","ops":[{"v":"C6","state":"current"},{"panel":"finish","set":{"C6":"7"}},{"e":["C6","C7"],"state":"latest"},{"v":"B6","state":"done"},{"e":["D5","D7"],"state":"examined"}]},{"say":"D6 starts at 4, when D5 finishes, and takes 3, so it finishes at 7. D7 can't start before 7.","ops":[{"v":"D6","state":"current"},{"panel":"finish","set":{"D6":"7"}},{"e":["D6","D7"],"state":"latest"},{"v":"C6","state":"done"}]},{"say":"B7 starts at 7, when B6 finishes, and takes 1, so it finishes at 8. E7 can't start before 8.","ops":[{"v":"B7","state":"current"},{"panel":"finish","set":{"B7":"8"}},{"e":["B7","E7"],"state":"latest"},{"v":"D6","state":"done"}]},{"say":"C7 starts at 7, when C6 finishes, and takes 1, so it finishes at 8. E7 already waits at least that long for another task.","ops":[{"v":"C7","state":"current"},{"panel":"finish","set":{"C7":"8"}},{"e":["C7","E7"],"state":"examined"},{"v":"B7","state":"done"}]},{"say":"D7 starts at 7, when D6 finishes, and takes 1, so it finishes at 8. E7 already waits at least that long for another task.","ops":[{"v":"D7","state":"current"},{"panel":"finish","set":{"D7":"8"}},{"e":["D7","E7"],"state":"examined"},{"v":"C7","state":"done"},{"e":["E3","E8"],"state":"examined"}]},{"say":"E7 starts at 8, when B7 finishes, and takes 4, so it finishes at 12. E8 can't start before 12.","ops":[{"v":"E7","state":"current"},{"panel":"finish","set":{"E7":"12"}},{"e":["E7","E8"],"state":"latest"},{"v":"D7","state":"done"}]},{"say":"E8 starts at 12, when E7 finishes, and takes 1, so it finishes at 13.","ops":[{"v":"E8","state":"current"},{"panel":"finish","set":{"E8":"13"}},{"v":"E7","state":"done"}]},{"say":"Of the tasks nothing depends on, E8 finishes last, at 13. Follow each task back to the dependency that set its start: E8, E7, B7, B6, B5, B3 and B2.","ops":[{"v":"E8","state":"done"},{"e":["G2","B3"],"state":"idle"},{"e":["G2","C3"],"state":"idle"},{"e":["G2","D3"],"state":"idle"},{"e":["G3","B4"],"state":"idle"},{"e":["G3","C4"],"state":"idle"},{"e":["G3","D4"],"state":"idle"},{"e":["G4","B5"],"state":"idle"},{"e":["G4","C5"],"state":"idle"},{"e":["C3","E3"],"state":"idle"},{"e":["G4","D5"],"state":"idle"},{"e":["D3","E3"],"state":"idle"},{"e":["B4","B5"],"state":"idle"},{"e":["C4","C5"],"state":"idle"},{"e":["D4","D5"],"state":"idle"},{"e":["G5","B6"],"state":"idle"},{"e":["G5","C6"],"state":"idle"},{"e":["G5","D6"],"state":"idle"},{"e":["B5","B7"],"state":"idle"},{"e":["C5","C7"],"state":"idle"},{"e":["D5","D7"],"state":"idle"},{"e":["C7","E7"],"state":"idle"},{"e":["D7","E7"],"state":"idle"},{"e":["E3","E8"],"state":"idle"},{"v":"B2","state":"critical"},{"v":"B3","state":"critical"},{"e":["B2","B3"],"state":"critical"},{"v":"B5","state":"critical"},{"e":["B3","B5"],"state":"critical"},{"v":"B6","state":"critical"},{"e":["B5","B6"],"state":"critical"},{"v":"B7","state":"critical"},{"e":["B6","B7"],"state":"critical"},{"v":"E7","state":"critical"},{"e":["B7","E7"],"state":"critical"},{"v":"E8","state":"critical"},{"e":["E7","E8"],"state":"critical"},{"panel":"order","list":[{"key":"B2","note":"takes 1"},{"key":"B3","note":"takes 2"},{"key":"B5","note":"takes 1"},{"key":"B6","note":"takes 3"},{"key":"B7","note":"takes 1"},{"key":"E7","note":"takes 4"},{"key":"E8","note":"takes 1"}]}]},{"say":"Done. The critical path takes 13, against 43 for every task one after another. The other tasks finish before anything on the path needs them."}],"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":"path, cost, err := dag.CriticalPath(g)\nif err != nil {\n\treturn err\n}\nfor _, v := range path {\n\tfmt.Println(v.Label(), v.Weight())\n}\nfmt.Println(cost)"}