{"algorithm":"tracker","about":["A Tracker runs a dependency graph the way a build system does. Ready returns the tasks that can start, and Done marks tasks as finished, which makes ready every task that was waiting only on them. An edge from A to B means B depends on A, so Ready returns B once A is done.","Levels split the same graph into rounds, and each round waits for its slowest task. The tracker starts a task the moment its own dependencies finish, so a long task in one round doesn't hold up the tasks of the next round that never waited for it.","The tracker leaves running the tasks to the caller, and with them how many run at once. This page uses two workers that take the ready tasks first in, first out, and each task takes its weight in time. NewTracker copies the graph in O(V+E), and all the Ready and Done calls of a run add up to O(V+E) too. It returns ErrDAGHasCycle for a graph with a cycle, and Done returns ErrNotReady for a task Ready hasn't returned."],"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":"Taking two courses a semester, each as soon as its prerequisites are passed, how many semesters does the degree take?","params":{"workers":2},"result":{"kind":"order","vertices":["Programming 1","Discrete math","Calculus 1","Programming 2","Calculus 2","Linear algebra","Computer systems","Data structures","Probability","Operating systems","Databases","Algorithms","Compilers","Machine learning"]},"answer":"With 2 workers, the last of the 14 tasks finishes at time 7. Running the levels one after another on the same workers takes 9, since each level waits for its slowest task. One task at a time would take 14.","legend":{"vertex":[{"id":"idle","label":"Waiting on a task it depends on","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"Ready, waiting for a worker","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"Running","color":"#56B4E9","shape":"ring"},{"id":"done","label":"Done","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Its start is done","color":"#009E73","shape":"thick"}],"panels":[{"id":"ends","title":"Ends at","kind":"table"},{"id":"running","title":"Running","kind":"list"},{"id":"ready","title":"Ready, first in first out","kind":"list"},{"id":"order","title":"Start order","kind":"list"}]},"steps":[{"say":"The tracker hands out a task once every task it depends on is done, and 2 workers take the ready tasks in the order it returns them. Each task takes its weight in time, and the time it ends shows next to its name once it starts. The first call to Ready returns the 3 tasks that depend on nothing: Programming 1, Discrete math and Calculus 1.","ops":[{"v":"Programming 1","state":"waiting"},{"v":"Discrete math","state":"waiting"},{"v":"Calculus 1","state":"waiting"},{"panel":"ready","list":[{"key":"Programming 1"},{"key":"Discrete math"},{"key":"Calculus 1"}]}]},{"say":"At time 0, Programming 1 and Discrete math start, to end at 1 and 1. Every worker is busy, so 1 ready task waits for one to come free.","ops":[{"v":"Programming 1","state":"current"},{"panel":"ends","set":{"Programming 1":"1"}},{"v":"Discrete math","state":"current"},{"panel":"ends","set":{"Discrete math":"1"}},{"panel":"running","list":[{"key":"Programming 1","note":"until 1"},{"key":"Discrete math","note":"until 1"}]},{"panel":"ready","list":[{"key":"Calculus 1"}]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"}]}]},{"say":"At time 1, Programming 1 and Discrete math finish. Done makes Programming 2 ready. Calculus 1 and Programming 2 start, to end at 2 and 2.","ops":[{"v":"Programming 1","state":"done"},{"e":["Programming 1","Programming 2"],"state":"tree"},{"v":"Discrete math","state":"done"},{"e":["Discrete math","Data structures"],"state":"tree"},{"e":["Discrete math","Probability"],"state":"tree"},{"e":["Discrete math","Algorithms"],"state":"tree"},{"v":"Programming 2","state":"waiting"},{"v":"Calculus 1","state":"current"},{"panel":"ends","set":{"Calculus 1":"2"}},{"v":"Programming 2","state":"current"},{"panel":"ends","set":{"Programming 2":"2"}},{"panel":"running","list":[{"key":"Calculus 1","note":"until 2"},{"key":"Programming 2","note":"until 2"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"},{"key":"Calculus 1","note":"at 1"},{"key":"Programming 2","note":"at 1"}]}]},{"say":"At time 2, Calculus 1 and Programming 2 finish. Done makes Calculus 2, Linear algebra, Computer systems and Data structures ready. Calculus 2 and Linear algebra start, to end at 3 and 3. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"Calculus 1","state":"done"},{"e":["Calculus 1","Calculus 2"],"state":"tree"},{"e":["Calculus 1","Linear algebra"],"state":"tree"},{"v":"Programming 2","state":"done"},{"e":["Programming 2","Computer systems"],"state":"tree"},{"e":["Programming 2","Data structures"],"state":"tree"},{"v":"Calculus 2","state":"waiting"},{"v":"Linear algebra","state":"waiting"},{"v":"Computer systems","state":"waiting"},{"v":"Data structures","state":"waiting"},{"v":"Calculus 2","state":"current"},{"panel":"ends","set":{"Calculus 2":"3"}},{"v":"Linear algebra","state":"current"},{"panel":"ends","set":{"Linear algebra":"3"}},{"panel":"running","list":[{"key":"Calculus 2","note":"until 3"},{"key":"Linear algebra","note":"until 3"}]},{"panel":"ready","list":[{"key":"Computer systems"},{"key":"Data structures"}]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"},{"key":"Calculus 1","note":"at 1"},{"key":"Programming 2","note":"at 1"},{"key":"Calculus 2","note":"at 2"},{"key":"Linear algebra","note":"at 2"}]}]},{"say":"At time 3, Calculus 2 and Linear algebra finish. Done makes Probability ready. Computer systems and Data structures start, to end at 4 and 4. Every worker is busy, so 1 ready task waits for one to come free.","ops":[{"v":"Calculus 2","state":"done"},{"e":["Calculus 2","Probability"],"state":"tree"},{"v":"Linear algebra","state":"done"},{"e":["Linear algebra","Machine learning"],"state":"tree"},{"v":"Probability","state":"waiting"},{"v":"Computer systems","state":"current"},{"panel":"ends","set":{"Computer systems":"4"}},{"v":"Data structures","state":"current"},{"panel":"ends","set":{"Data structures":"4"}},{"panel":"running","list":[{"key":"Computer systems","note":"until 4"},{"key":"Data structures","note":"until 4"}]},{"panel":"ready","list":[{"key":"Probability"}]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"},{"key":"Calculus 1","note":"at 1"},{"key":"Programming 2","note":"at 1"},{"key":"Calculus 2","note":"at 2"},{"key":"Linear algebra","note":"at 2"},{"key":"Computer systems","note":"at 3"},{"key":"Data structures","note":"at 3"}]}]},{"say":"At time 4, Computer systems and Data structures finish. Done makes Operating systems, Databases and Algorithms ready. Probability and Operating systems start, to end at 5 and 5. Every worker is busy, so 2 ready tasks wait for one to come free.","ops":[{"v":"Computer systems","state":"done"},{"e":["Computer systems","Operating systems"],"state":"tree"},{"e":["Computer systems","Compilers"],"state":"tree"},{"v":"Data structures","state":"done"},{"e":["Data structures","Operating systems"],"state":"tree"},{"e":["Data structures","Databases"],"state":"tree"},{"e":["Data structures","Algorithms"],"state":"tree"},{"v":"Operating systems","state":"waiting"},{"v":"Databases","state":"waiting"},{"v":"Algorithms","state":"waiting"},{"v":"Probability","state":"current"},{"panel":"ends","set":{"Probability":"5"}},{"v":"Operating systems","state":"current"},{"panel":"ends","set":{"Operating systems":"5"}},{"panel":"running","list":[{"key":"Probability","note":"until 5"},{"key":"Operating systems","note":"until 5"}]},{"panel":"ready","list":[{"key":"Databases"},{"key":"Algorithms"}]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"},{"key":"Calculus 1","note":"at 1"},{"key":"Programming 2","note":"at 1"},{"key":"Calculus 2","note":"at 2"},{"key":"Linear algebra","note":"at 2"},{"key":"Computer systems","note":"at 3"},{"key":"Data structures","note":"at 3"},{"key":"Probability","note":"at 4"},{"key":"Operating systems","note":"at 4"}]}]},{"say":"At time 5, Probability and Operating systems finish. Done makes no new task ready. Databases and Algorithms start, to end at 6 and 6.","ops":[{"v":"Probability","state":"done"},{"e":["Probability","Machine learning"],"state":"tree"},{"v":"Operating systems","state":"done"},{"v":"Databases","state":"current"},{"panel":"ends","set":{"Databases":"6"}},{"v":"Algorithms","state":"current"},{"panel":"ends","set":{"Algorithms":"6"}},{"panel":"running","list":[{"key":"Databases","note":"until 6"},{"key":"Algorithms","note":"until 6"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"},{"key":"Calculus 1","note":"at 1"},{"key":"Programming 2","note":"at 1"},{"key":"Calculus 2","note":"at 2"},{"key":"Linear algebra","note":"at 2"},{"key":"Computer systems","note":"at 3"},{"key":"Data structures","note":"at 3"},{"key":"Probability","note":"at 4"},{"key":"Operating systems","note":"at 4"},{"key":"Databases","note":"at 5"},{"key":"Algorithms","note":"at 5"}]}]},{"say":"At time 6, Databases and Algorithms finish. Done makes Compilers and Machine learning ready. Compilers and Machine learning start, to end at 7 and 7.","ops":[{"v":"Databases","state":"done"},{"v":"Algorithms","state":"done"},{"e":["Algorithms","Compilers"],"state":"tree"},{"e":["Algorithms","Machine learning"],"state":"tree"},{"v":"Compilers","state":"waiting"},{"v":"Machine learning","state":"waiting"},{"v":"Compilers","state":"current"},{"panel":"ends","set":{"Compilers":"7"}},{"v":"Machine learning","state":"current"},{"panel":"ends","set":{"Machine learning":"7"}},{"panel":"running","list":[{"key":"Compilers","note":"until 7"},{"key":"Machine learning","note":"until 7"}]},{"panel":"ready","list":[]},{"panel":"order","list":[{"key":"Programming 1","note":"at 0"},{"key":"Discrete math","note":"at 0"},{"key":"Calculus 1","note":"at 1"},{"key":"Programming 2","note":"at 1"},{"key":"Calculus 2","note":"at 2"},{"key":"Linear algebra","note":"at 2"},{"key":"Computer systems","note":"at 3"},{"key":"Data structures","note":"at 3"},{"key":"Probability","note":"at 4"},{"key":"Operating systems","note":"at 4"},{"key":"Databases","note":"at 5"},{"key":"Algorithms","note":"at 5"},{"key":"Compilers","note":"at 6"},{"key":"Machine learning","note":"at 6"}]}]},{"say":"Done. At time 7, Compilers and Machine learning finish, the last of the 14 tasks. Running the levels one after another on 2 workers would take 9, and one task at a time 14.","ops":[{"v":"Compilers","state":"done"},{"v":"Machine learning","state":"done"},{"panel":"running","list":[]}]}],"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":"t, err := dag.NewTracker(g)\nif err != nil {\n\treturn err\n}\nworkers := make(chan struct{}, 2)\nfinished := make(chan string, g.Order())\nfor t.Remaining() > 0 {\n\tfor _, task := range t.Ready() {\n\t\tgo func() {\n\t\t\tworkers <- struct{}{}\n\t\t\trun(task) // task.Weight() is how long it takes\n\t\t\t<-workers\n\t\t\tfinished <- task.Label()\n\t\t}()\n\t}\n\tif err := t.Done(<-finished); err != nil {\n\t\treturn err\n\t}\n}"}