{"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":"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":"Why does the pipeline take as long as it does, and which jobs are worth making faster?","params":{},"result":{"kind":"order","vertices":["Checkout","Install","Compile","Unit tests","Deploy"]},"answer":"The critical path is Checkout, Install, Compile, Unit tests and Deploy, 5 tasks taking 15 in all. Every task one after another takes 26, so running in parallel saves 11. 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. Checkout, the only task with no dependencies, starts at 0."},{"say":"Checkout depends on nothing. It starts at 0 and takes 1, so it finishes at 1. Install and Docker image can't start before 1.","ops":[{"v":"Checkout","state":"current"},{"panel":"finish","set":{"Checkout":"1"}},{"e":["Checkout","Install"],"state":"latest"},{"e":["Checkout","Docker image"],"state":"latest"}]},{"say":"Install starts at 1, when Checkout finishes, and takes 3, so it finishes at 4. Lint and Compile can't start before 4.","ops":[{"v":"Install","state":"current"},{"panel":"finish","set":{"Install":"4"}},{"e":["Install","Lint"],"state":"latest"},{"e":["Install","Compile"],"state":"latest"},{"v":"Checkout","state":"done"}]},{"say":"Lint starts at 4, when Install finishes, and takes 6, so it finishes at 10. Deploy can't start before 10.","ops":[{"v":"Lint","state":"current"},{"panel":"finish","set":{"Lint":"10"}},{"e":["Lint","Deploy"],"state":"latest"},{"v":"Install","state":"done"},{"e":["Checkout","Docker image"],"state":"examined"}]},{"say":"Compile starts at 4, when Install finishes, and takes 3, so it finishes at 7. Unit tests and Docker image can't start before 7.","ops":[{"v":"Compile","state":"current"},{"panel":"finish","set":{"Compile":"7"}},{"e":["Compile","Unit tests"],"state":"latest"},{"e":["Compile","Docker image"],"state":"latest"},{"v":"Lint","state":"done"},{"e":["Lint","Deploy"],"state":"examined"}]},{"say":"Unit tests starts at 7, when Compile finishes, and takes 6, so it finishes at 13. Deploy can't start before 13.","ops":[{"v":"Unit tests","state":"current"},{"panel":"finish","set":{"Unit tests":"13"}},{"e":["Unit tests","Deploy"],"state":"latest"},{"v":"Compile","state":"done"}]},{"say":"Docker image starts at 7, when Compile finishes, and takes 5, so it finishes at 12. Deploy already waits at least that long for another task.","ops":[{"v":"Docker image","state":"current"},{"panel":"finish","set":{"Docker image":"12"}},{"e":["Docker image","Deploy"],"state":"examined"},{"v":"Unit tests","state":"done"}]},{"say":"Deploy starts at 13, when Unit tests finishes, and takes 2, so it finishes at 15.","ops":[{"v":"Deploy","state":"current"},{"panel":"finish","set":{"Deploy":"15"}},{"v":"Docker image","state":"done"}]},{"say":"Of the tasks nothing depends on, Deploy finishes last, at 15. Follow each task back to the dependency that set its start: Deploy, Unit tests, Compile, Install and Checkout.","ops":[{"v":"Deploy","state":"done"},{"e":["Checkout","Docker image"],"state":"idle"},{"e":["Lint","Deploy"],"state":"idle"},{"e":["Docker image","Deploy"],"state":"idle"},{"v":"Checkout","state":"critical"},{"v":"Install","state":"critical"},{"e":["Checkout","Install"],"state":"critical"},{"v":"Compile","state":"critical"},{"e":["Install","Compile"],"state":"critical"},{"v":"Unit tests","state":"critical"},{"e":["Compile","Unit tests"],"state":"critical"},{"v":"Deploy","state":"critical"},{"e":["Unit tests","Deploy"],"state":"critical"},{"panel":"order","list":[{"key":"Checkout","note":"takes 1"},{"key":"Install","note":"takes 3"},{"key":"Compile","note":"takes 3"},{"key":"Unit tests","note":"takes 6"},{"key":"Deploy","note":"takes 2"}]}]},{"say":"Done. The critical path takes 15, against 26 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)"}