{"algorithm":"affected","about":["Affected takes the vertices that changed and returns them with every vertex reachable from any of them. It is one breadth-first search that starts from all the changed vertices at once, so a vertex reachable from several of them is listed once.","The changed vertices come first, in the order given, then the rest, nearest first. It costs O(V+E) for the part of the graph it reaches, however many vertices changed. Running Descendants once for each change finds the same vertices, but repeats the work wherever their descendants overlap.","Use it to decide what to rebuild, retest or redeploy after a commit, which cells a spreadsheet recomputes after an edit, or which targets a change to a shared library touches."],"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":"The department rewrites Computer systems and Linear algebra. Which courses may need to change too, because they build on them?","params":{"changed":["Computer systems","Linear algebra"]},"result":{"kind":"set","vertices":["Compilers","Computer systems","Linear algebra","Machine learning","Operating systems"]},"answer":"5 vertices are affected: Computer systems and Linear algebra, which changed, and Compilers, Machine learning and Operating systems.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"Affected","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Found a new vertex","color":"#009E73","shape":"thick"},{"id":"examined","label":"Found nothing new","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"queue","title":"Queue","kind":"list"},{"id":"found","title":"Affected","kind":"list"}]},"steps":[{"say":"Computer systems and Linear algebra changed, so they are affected. Put them in the queue.","ops":[{"v":"Computer systems","state":"waiting"},{"v":"Linear algebra","state":"waiting"},{"panel":"queue","list":[{"key":"Computer systems"},{"key":"Linear algebra"}]},{"panel":"found","list":[{"key":"Computer systems","note":"changed"},{"key":"Linear algebra","note":"changed"}]}]},{"say":"Take Computer systems from the queue. It has edges to Operating systems and Compilers. Both are new, so they join the queue.","ops":[{"v":"Computer systems","state":"done"},{"v":"Operating systems","state":"waiting"},{"e":["Computer systems","Operating systems"],"state":"tree"},{"v":"Compilers","state":"waiting"},{"e":["Computer systems","Compilers"],"state":"tree"},{"panel":"queue","list":[{"key":"Linear algebra"},{"key":"Operating systems"},{"key":"Compilers"}]},{"panel":"found","list":[{"key":"Computer systems","note":"changed"},{"key":"Linear algebra","note":"changed"},{"key":"Operating systems"},{"key":"Compilers"}]}]},{"say":"Take Linear algebra from the queue. It has an edge to Machine learning, which is new, so it joins the queue.","ops":[{"v":"Linear algebra","state":"done"},{"v":"Machine learning","state":"waiting"},{"e":["Linear algebra","Machine learning"],"state":"tree"},{"panel":"queue","list":[{"key":"Operating systems"},{"key":"Compilers"},{"key":"Machine learning"}]},{"panel":"found","list":[{"key":"Computer systems","note":"changed"},{"key":"Linear algebra","note":"changed"},{"key":"Operating systems"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Take Operating systems from the queue. It has no edges out.","ops":[{"v":"Operating systems","state":"done"},{"panel":"queue","list":[{"key":"Compilers"},{"key":"Machine learning"}]},{"panel":"found","list":[{"key":"Computer systems","note":"changed"},{"key":"Linear algebra","note":"changed"},{"key":"Operating systems"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Take Compilers from the queue. It has no edges out.","ops":[{"v":"Compilers","state":"done"},{"panel":"queue","list":[{"key":"Machine learning"}]},{"panel":"found","list":[{"key":"Computer systems","note":"changed"},{"key":"Linear algebra","note":"changed"},{"key":"Operating systems"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Take Machine learning from the queue. It has no edges out.","ops":[{"v":"Machine learning","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"Computer systems","note":"changed"},{"key":"Linear algebra","note":"changed"},{"key":"Operating systems"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Done. 5 vertices are affected: the 2 changed vertices and 3 more reachable from 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":"jobs, err := dag.Affected(g, \"Computer systems\", \"Linear algebra\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
