{"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":"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":"A commit changes the Lint and Docker image jobs. Which jobs have to run again?","params":{"changed":["Lint","Docker image"]},"result":{"kind":"set","vertices":["Deploy","Docker image","Lint"]},"answer":"3 vertices are affected: Docker image and Lint, which changed, and Deploy.","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":"Lint and Docker image changed, so they are affected. Put them in the queue.","ops":[{"v":"Lint","state":"waiting"},{"v":"Docker image","state":"waiting"},{"panel":"queue","list":[{"key":"Lint"},{"key":"Docker image"}]},{"panel":"found","list":[{"key":"Lint","note":"changed"},{"key":"Docker image","note":"changed"}]}]},{"say":"Take Lint from the queue. It has an edge to Deploy, which is new, so it joins the queue.","ops":[{"v":"Lint","state":"done"},{"v":"Deploy","state":"waiting"},{"e":["Lint","Deploy"],"state":"tree"},{"panel":"queue","list":[{"key":"Docker image"},{"key":"Deploy"}]},{"panel":"found","list":[{"key":"Lint","note":"changed"},{"key":"Docker image","note":"changed"},{"key":"Deploy"}]}]},{"say":"Take Docker image from the queue. It has an edge to Deploy, which was found before.","ops":[{"v":"Docker image","state":"done"},{"e":["Docker image","Deploy"],"state":"examined"},{"panel":"queue","list":[{"key":"Deploy"}]},{"panel":"found","list":[{"key":"Lint","note":"changed"},{"key":"Docker image","note":"changed"},{"key":"Deploy"}]}]},{"say":"Take Deploy from the queue. It has no edges out.","ops":[{"v":"Deploy","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"Lint","note":"changed"},{"key":"Docker image","note":"changed"},{"key":"Deploy"}]}]},{"say":"Done. 3 vertices are affected: the 2 changed vertices and 1 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, \"Lint\", \"Docker image\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
