{"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":"spreadsheet","name":"Spreadsheet formulas","description":"A sheet that works out the profit of one quarter. Row 2 holds the units sold from January to March, and G2 to G5 hold the price, unit cost, monthly fixed costs and tax rate. Rows 3 to 7 work out revenue, cost, profit before tax, tax and net profit, and E3, E7 and E8 hold the quarter's revenue, net profit and margin. Each cell takes 1 to 4 milliseconds to work out. Each edge points from a cell to a formula that reads it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"B2","x":41,"y":195},{"id":"C2","x":41,"y":561},{"id":"D2","x":41,"y":884},{"id":"G2","x":41,"y":714},{"id":"G3","x":41,"y":408},{"id":"G4","x":194,"y":195},{"id":"G5","x":347,"y":302},{"id":"B3","x":194,"y":348},{"id":"C3","x":194,"y":654},{"id":"D3","x":194,"y":960},{"id":"B4","x":194,"y":42},{"id":"C4","x":194,"y":501},{"id":"D4","x":194,"y":807},{"id":"B5","x":347,"y":149},{"id":"C5","x":347,"y":455},{"id":"D5","x":347,"y":608},{"id":"B6","x":500,"y":218},{"id":"C6","x":500,"y":371},{"id":"D6","x":500,"y":524},{"id":"B7","x":653,"y":242},{"id":"C7","x":653,"y":395},{"id":"D7","x":653,"y":548},{"id":"E3","x":347,"y":761},{"id":"E7","x":806,"y":418},{"id":"E8","x":959,"y":487}],"edges":[{"from":"B2","to":"B3"},{"from":"G2","to":"B3"},{"from":"C2","to":"C3"},{"from":"G2","to":"C3"},{"from":"D2","to":"D3"},{"from":"G2","to":"D3"},{"from":"B2","to":"B4"},{"from":"G3","to":"B4"},{"from":"C2","to":"C4"},{"from":"G3","to":"C4"},{"from":"D2","to":"D4"},{"from":"G3","to":"D4"},{"from":"B3","to":"B5"},{"from":"B4","to":"B5"},{"from":"G4","to":"B5"},{"from":"C3","to":"C5"},{"from":"C4","to":"C5"},{"from":"G4","to":"C5"},{"from":"D3","to":"D5"},{"from":"D4","to":"D5"},{"from":"G4","to":"D5"},{"from":"B5","to":"B6"},{"from":"G5","to":"B6"},{"from":"C5","to":"C6"},{"from":"G5","to":"C6"},{"from":"D5","to":"D6"},{"from":"G5","to":"D6"},{"from":"B5","to":"B7"},{"from":"B6","to":"B7"},{"from":"C5","to":"C7"},{"from":"C6","to":"C7"},{"from":"D5","to":"D7"},{"from":"D6","to":"D7"},{"from":"B3","to":"E3"},{"from":"C3","to":"E3"},{"from":"D3","to":"E3"},{"from":"B7","to":"E7"},{"from":"C7","to":"E7"},{"from":"D7","to":"E7"},{"from":"E7","to":"E8"},{"from":"E3","to":"E8"}],"durations":{"B2":1,"B3":2,"B4":2,"B5":1,"B6":3,"B7":1,"C2":1,"C3":2,"C4":2,"C5":1,"C6":3,"C7":1,"D2":1,"D3":2,"D4":2,"D5":1,"D6":3,"D7":1,"E3":4,"E7":4,"E8":1,"G2":1,"G3":1,"G4":1,"G5":1},"durationUnit":"milliseconds","details":{"vertices":25,"edges":41,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.06833333333333333,"inDegree":{"min":0,"avg":1.64,"max":3},"outDegree":{"min":0,"avg":1.64,"max":3},"selfLoops":0,"components":1}},"problem":"The March units in D2 and the tax rate in G5 change. Which cells does the sheet have to recompute?","params":{"changed":["D2","G5"]},"result":{"kind":"set","vertices":["B6","B7","C6","C7","D2","D3","D4","D5","D6","D7","E3","E7","E8","G5"]},"answer":"14 vertices are affected: D2 and G5, which changed, and B6, B7, C6, C7, D3, D4, D5, D6, D7, E3 and 2 more.","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":"D2 and G5 changed, so they are affected. Put them in the queue.","ops":[{"v":"D2","state":"waiting"},{"v":"G5","state":"waiting"},{"panel":"queue","list":[{"key":"D2"},{"key":"G5"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"}]}]},{"say":"Take D2 from the queue. It has edges to D3 and D4. Both are new, so they join the queue.","ops":[{"v":"D2","state":"done"},{"v":"D3","state":"waiting"},{"e":["D2","D3"],"state":"tree"},{"v":"D4","state":"waiting"},{"e":["D2","D4"],"state":"tree"},{"panel":"queue","list":[{"key":"G5"},{"key":"D3"},{"key":"D4"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"}]}]},{"say":"Take G5 from the queue. It has edges to B6, C6 and D6. All 3 are new, so they join the queue.","ops":[{"v":"G5","state":"done"},{"v":"B6","state":"waiting"},{"e":["G5","B6"],"state":"tree"},{"v":"C6","state":"waiting"},{"e":["G5","C6"],"state":"tree"},{"v":"D6","state":"waiting"},{"e":["G5","D6"],"state":"tree"},{"panel":"queue","list":[{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"}]}]},{"say":"Take D3 from the queue. It has edges to D5 and E3. Both are new, so they join the queue.","ops":[{"v":"D3","state":"done"},{"v":"D5","state":"waiting"},{"e":["D3","D5"],"state":"tree"},{"v":"E3","state":"waiting"},{"e":["D3","E3"],"state":"tree"},{"panel":"queue","list":[{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"}]}]},{"say":"Take D4 from the queue. It has an edge to D5, which was found before.","ops":[{"v":"D4","state":"done"},{"e":["D4","D5"],"state":"examined"},{"panel":"queue","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"}]}]},{"say":"Take B6 from the queue. It has an edge to B7, which is new, so it joins the queue.","ops":[{"v":"B6","state":"done"},{"v":"B7","state":"waiting"},{"e":["B6","B7"],"state":"tree"},{"panel":"queue","list":[{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"}]}]},{"say":"Take C6 from the queue. It has an edge to C7, which is new, so it joins the queue.","ops":[{"v":"C6","state":"done"},{"v":"C7","state":"waiting"},{"e":["C6","C7"],"state":"tree"},{"panel":"queue","list":[{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"}]}]},{"say":"Take D6 from the queue. It has an edge to D7, which is new, so it joins the queue.","ops":[{"v":"D6","state":"done"},{"v":"D7","state":"waiting"},{"e":["D6","D7"],"state":"tree"},{"panel":"queue","list":[{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"}]}]},{"say":"Take D5 from the queue. It has edges to D6 and D7. Both were found before.","ops":[{"v":"D5","state":"done"},{"e":["D5","D6"],"state":"examined"},{"e":["D5","D7"],"state":"examined"},{"panel":"queue","list":[{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"}]}]},{"say":"Take E3 from the queue. It has an edge to E8, which is new, so it joins the queue.","ops":[{"v":"E3","state":"done"},{"v":"E8","state":"waiting"},{"e":["E3","E8"],"state":"tree"},{"panel":"queue","list":[{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"}]}]},{"say":"Take B7 from the queue. It has an edge to E7, which is new, so it joins the queue.","ops":[{"v":"B7","state":"done"},{"v":"E7","state":"waiting"},{"e":["B7","E7"],"state":"tree"},{"panel":"queue","list":[{"key":"C7"},{"key":"D7"},{"key":"E8"},{"key":"E7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"},{"key":"E7"}]}]},{"say":"Take C7 from the queue. It has an edge to E7, which was found before.","ops":[{"v":"C7","state":"done"},{"e":["C7","E7"],"state":"examined"},{"panel":"queue","list":[{"key":"D7"},{"key":"E8"},{"key":"E7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"},{"key":"E7"}]}]},{"say":"Take D7 from the queue. It has an edge to E7, which was found before.","ops":[{"v":"D7","state":"done"},{"e":["D7","E7"],"state":"examined"},{"panel":"queue","list":[{"key":"E8"},{"key":"E7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"},{"key":"E7"}]}]},{"say":"Take E8 from the queue. It has no edges out.","ops":[{"v":"E8","state":"done"},{"panel":"queue","list":[{"key":"E7"}]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"},{"key":"E7"}]}]},{"say":"Take E7 from the queue. It has an edge to E8, which was found before.","ops":[{"v":"E7","state":"done"},{"e":["E7","E8"],"state":"examined"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"D2","note":"changed"},{"key":"G5","note":"changed"},{"key":"D3"},{"key":"D4"},{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"D5"},{"key":"E3"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E8"},{"key":"E7"}]}]},{"say":"Done. 14 vertices are affected: the 2 changed vertices and 12 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, \"D2\", \"G5\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
