{"algorithm":"descendants","about":["Descendants follows edges forward from a vertex and collects every vertex it can reach. gograph reads an edge from A to B as B depending on A, so these are all the vertices that depend on it, directly or through others.","dag.Descendants searches breadth first, so the result is nearest first, and it costs O(V+E) for the part of the graph it reaches. The vertex itself is in the result only when it's on a cycle. The graph has to be directed, but despite the package's name it may have cycles.","Use it to find the jobs that wait for one step of a pipeline, the courses that build on a course, or the cells that read a value. If a graph stores its edges the other way, as A requires B, the meanings swap and Ancestors gives the dependents."],"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":"Which formulas read the tax rate in G5, directly or through other cells?","params":{"vertex":"G5"},"result":{"kind":"set","vertices":["B6","B7","C6","C7","D6","D7","E7","E8"]},"answer":"8 vertices are reachable from G5: B6, B7, C6, C7, D6, D7, E7 and E8.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"start","label":"Start","color":"#56B4E9","shape":"ring"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"Descendant","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":"Descendants","kind":"list"}]},"steps":[{"say":"Start at G5. It has edges to B6, C6 and D6. All 3 are new, so they join the queue.","ops":[{"v":"G5","state":"start"},{"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":"B6"},{"key":"C6"},{"key":"D6"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"}]}]},{"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":"B7"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"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":"B7"},{"key":"C7"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"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":"B7"},{"key":"C7"},{"key":"D7"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"}]}]},{"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":"E7"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"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":"E7"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"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":"E7"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E7"}]}]},{"say":"Take E7 from the queue. It has an edge to E8, which is new, so it joins the queue.","ops":[{"v":"E7","state":"done"},{"v":"E8","state":"waiting"},{"e":["E7","E8"],"state":"tree"},{"panel":"queue","list":[{"key":"E8"}]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E7"},{"key":"E8"}]}]},{"say":"Take E8 from the queue. It has no edges out.","ops":[{"v":"E8","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"B6"},{"key":"C6"},{"key":"D6"},{"key":"B7"},{"key":"C7"},{"key":"D7"},{"key":"E7"},{"key":"E8"}]}]},{"say":"Done. 8 vertices are reachable from G5."}],"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.Descendants(g, \"G5\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
