{"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":"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":"However many courses a student takes at once, how many semesters does the degree take at least, and which chain of courses sets that?","params":{},"result":{"kind":"order","vertices":["Programming 1","Programming 2","Data structures","Algorithms","Compilers"]},"answer":"The critical path is Programming 1, Programming 2, Data structures, Algorithms and Compilers, 5 tasks taking 5 in all. Every task one after another takes 14, so running in parallel saves 9. 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, Programming 1, Discrete math and Calculus 1, start at 0."},{"say":"Programming 1 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. Programming 2 can't start before 1.","ops":[{"v":"Programming 1","state":"current"},{"panel":"finish","set":{"Programming 1":"1"}},{"e":["Programming 1","Programming 2"],"state":"latest"}]},{"say":"Discrete math depends on nothing. It starts at 0 and takes 1, so it finishes at 1. Data structures, Probability and Algorithms can't start before 1.","ops":[{"v":"Discrete math","state":"current"},{"panel":"finish","set":{"Discrete math":"1"}},{"e":["Discrete math","Data structures"],"state":"latest"},{"e":["Discrete math","Probability"],"state":"latest"},{"e":["Discrete math","Algorithms"],"state":"latest"},{"v":"Programming 1","state":"done"}]},{"say":"Calculus 1 depends on nothing. It starts at 0 and takes 1, so it finishes at 1. Calculus 2 and Linear algebra can't start before 1.","ops":[{"v":"Calculus 1","state":"current"},{"panel":"finish","set":{"Calculus 1":"1"}},{"e":["Calculus 1","Calculus 2"],"state":"latest"},{"e":["Calculus 1","Linear algebra"],"state":"latest"},{"v":"Discrete math","state":"done"},{"e":["Discrete math","Data structures"],"state":"examined"}]},{"say":"Programming 2 starts at 1, when Programming 1 finishes, and takes 1, so it finishes at 2. Computer systems and Data structures can't start before 2.","ops":[{"v":"Programming 2","state":"current"},{"panel":"finish","set":{"Programming 2":"2"}},{"e":["Programming 2","Computer systems"],"state":"latest"},{"e":["Programming 2","Data structures"],"state":"latest"},{"v":"Calculus 1","state":"done"},{"e":["Discrete math","Probability"],"state":"examined"}]},{"say":"Calculus 2 starts at 1, when Calculus 1 finishes, and takes 1, so it finishes at 2. Probability can't start before 2.","ops":[{"v":"Calculus 2","state":"current"},{"panel":"finish","set":{"Calculus 2":"2"}},{"e":["Calculus 2","Probability"],"state":"latest"},{"v":"Programming 2","state":"done"}]},{"say":"Linear algebra starts at 1, when Calculus 1 finishes, and takes 1, so it finishes at 2. Machine learning can't start before 2.","ops":[{"v":"Linear algebra","state":"current"},{"panel":"finish","set":{"Linear algebra":"2"}},{"e":["Linear algebra","Machine learning"],"state":"latest"},{"v":"Calculus 2","state":"done"}]},{"say":"Computer systems starts at 2, when Programming 2 finishes, and takes 1, so it finishes at 3. Operating systems and Compilers can't start before 3.","ops":[{"v":"Computer systems","state":"current"},{"panel":"finish","set":{"Computer systems":"3"}},{"e":["Computer systems","Operating systems"],"state":"latest"},{"e":["Computer systems","Compilers"],"state":"latest"},{"v":"Linear algebra","state":"done"},{"e":["Discrete math","Algorithms"],"state":"examined"}]},{"say":"Data structures starts at 2, when Programming 2 finishes, and takes 1, so it finishes at 3. Databases and Algorithms can't start before 3. Operating systems already waits at least that long for another task.","ops":[{"v":"Data structures","state":"current"},{"panel":"finish","set":{"Data structures":"3"}},{"e":["Data structures","Databases"],"state":"latest"},{"e":["Data structures","Algorithms"],"state":"latest"},{"e":["Data structures","Operating systems"],"state":"examined"},{"v":"Computer systems","state":"done"},{"e":["Linear algebra","Machine learning"],"state":"examined"}]},{"say":"Probability starts at 2, when Calculus 2 finishes, and takes 1, so it finishes at 3. Machine learning can't start before 3.","ops":[{"v":"Probability","state":"current"},{"panel":"finish","set":{"Probability":"3"}},{"e":["Probability","Machine learning"],"state":"latest"},{"v":"Data structures","state":"done"}]},{"say":"Operating systems starts at 3, when Computer systems finishes, and takes 1, so it finishes at 4.","ops":[{"v":"Operating systems","state":"current"},{"panel":"finish","set":{"Operating systems":"4"}},{"v":"Probability","state":"done"}]},{"say":"Databases starts at 3, when Data structures finishes, and takes 1, so it finishes at 4.","ops":[{"v":"Databases","state":"current"},{"panel":"finish","set":{"Databases":"4"}},{"v":"Operating systems","state":"done"},{"e":["Computer systems","Compilers"],"state":"examined"},{"e":["Probability","Machine learning"],"state":"examined"}]},{"say":"Algorithms starts at 3, when Data structures finishes, and takes 1, so it finishes at 4. Compilers and Machine learning can't start before 4.","ops":[{"v":"Algorithms","state":"current"},{"panel":"finish","set":{"Algorithms":"4"}},{"e":["Algorithms","Compilers"],"state":"latest"},{"e":["Algorithms","Machine learning"],"state":"latest"},{"v":"Databases","state":"done"}]},{"say":"Compilers starts at 4, when Algorithms finishes, and takes 1, so it finishes at 5.","ops":[{"v":"Compilers","state":"current"},{"panel":"finish","set":{"Compilers":"5"}},{"v":"Algorithms","state":"done"}]},{"say":"Machine learning starts at 4, when Algorithms finishes, and takes 1, so it finishes at 5.","ops":[{"v":"Machine learning","state":"current"},{"panel":"finish","set":{"Machine learning":"5"}},{"v":"Compilers","state":"done"}]},{"say":"Of the tasks nothing depends on, Compilers finishes last, at 5. Follow each task back to the dependency that set its start: Compilers, Algorithms, Data structures, Programming 2 and Programming 1.","ops":[{"v":"Machine learning","state":"done"},{"e":["Discrete math","Data structures"],"state":"idle"},{"e":["Discrete math","Probability"],"state":"idle"},{"e":["Discrete math","Algorithms"],"state":"idle"},{"e":["Data structures","Operating systems"],"state":"idle"},{"e":["Linear algebra","Machine learning"],"state":"idle"},{"e":["Computer systems","Compilers"],"state":"idle"},{"e":["Probability","Machine learning"],"state":"idle"},{"v":"Programming 1","state":"critical"},{"v":"Programming 2","state":"critical"},{"e":["Programming 1","Programming 2"],"state":"critical"},{"v":"Data structures","state":"critical"},{"e":["Programming 2","Data structures"],"state":"critical"},{"v":"Algorithms","state":"critical"},{"e":["Data structures","Algorithms"],"state":"critical"},{"v":"Compilers","state":"critical"},{"e":["Algorithms","Compilers"],"state":"critical"},{"panel":"order","list":[{"key":"Programming 1","note":"takes 1"},{"key":"Programming 2","note":"takes 1"},{"key":"Data structures","note":"takes 1"},{"key":"Algorithms","note":"takes 1"},{"key":"Compilers","note":"takes 1"}]}]},{"say":"Done. The critical path takes 5, against 14 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)"}