{"algorithm":"ancestors","about":["Ancestors runs the same search backward. It follows edges in reverse from a vertex and collects every vertex that can reach it. With an edge from A to B read as B depending on A, these are everything the vertex depends on, directly or through others.","A gograph graph doesn't index incoming edges, so dag.Ancestors first reads every edge once to find them, then searches breadth first. It costs O(V+E) and returns the vertices nearest first. The vertex itself is in the result only when it's on a cycle.","Use it to find what has to finish before a job can start, which courses come before another, or why a module is in a build. In go mod graph, an edge goes from a module to one it requires, so the ancestors of a module are the modules that pull it in."],"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 cells does January's net profit in B7 depend on, directly or through other formulas?","params":{"vertex":"B7"},"result":{"kind":"set","vertices":["B2","B3","B4","B5","B6","G2","G3","G4","G5"]},"answer":"9 vertices can reach B7: B2, B3, B4, B5, B6, G2, G3, G4 and G5.","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":"Ancestor","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":"Ancestors","kind":"list"}]},"steps":[{"say":"The graph stores only the edges out of each vertex, so read every edge once, 41 in all, to find the edges into each one."},{"say":"Start at B7. It has edges from B5 and B6. Both are new, so they join the queue.","ops":[{"v":"B7","state":"start"},{"v":"B5","state":"waiting"},{"e":["B5","B7"],"state":"tree"},{"v":"B6","state":"waiting"},{"e":["B6","B7"],"state":"tree"},{"panel":"queue","list":[{"key":"B5"},{"key":"B6"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"}]}]},{"say":"Take B5 from the queue. It has edges from G4, B3 and B4. All 3 are new, so they join the queue.","ops":[{"v":"B5","state":"done"},{"v":"G4","state":"waiting"},{"e":["G4","B5"],"state":"tree"},{"v":"B3","state":"waiting"},{"e":["B3","B5"],"state":"tree"},{"v":"B4","state":"waiting"},{"e":["B4","B5"],"state":"tree"},{"panel":"queue","list":[{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"}]}]},{"say":"Take B6 from the queue. It has edges from G5 and B5. G5 is new, so it joins the queue. B5 was found before.","ops":[{"v":"B6","state":"done"},{"v":"G5","state":"waiting"},{"e":["G5","B6"],"state":"tree"},{"e":["B5","B6"],"state":"examined"},{"panel":"queue","list":[{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"}]}]},{"say":"Take G4 from the queue. It has no edges in.","ops":[{"v":"G4","state":"done"},{"panel":"queue","list":[{"key":"B3"},{"key":"B4"},{"key":"G5"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"}]}]},{"say":"Take B3 from the queue. It has edges from B2 and G2. Both are new, so they join the queue.","ops":[{"v":"B3","state":"done"},{"v":"B2","state":"waiting"},{"e":["B2","B3"],"state":"tree"},{"v":"G2","state":"waiting"},{"e":["G2","B3"],"state":"tree"},{"panel":"queue","list":[{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"}]}]},{"say":"Take B4 from the queue. It has edges from B2 and G3. G3 is new, so it joins the queue. B2 was found before.","ops":[{"v":"B4","state":"done"},{"e":["B2","B4"],"state":"examined"},{"v":"G3","state":"waiting"},{"e":["G3","B4"],"state":"tree"},{"panel":"queue","list":[{"key":"G5"},{"key":"B2"},{"key":"G2"},{"key":"G3"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"},{"key":"G3"}]}]},{"say":"Take G5 from the queue. It has no edges in.","ops":[{"v":"G5","state":"done"},{"panel":"queue","list":[{"key":"B2"},{"key":"G2"},{"key":"G3"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"},{"key":"G3"}]}]},{"say":"Take B2 from the queue. It has no edges in.","ops":[{"v":"B2","state":"done"},{"panel":"queue","list":[{"key":"G2"},{"key":"G3"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"},{"key":"G3"}]}]},{"say":"Take G2 from the queue. It has no edges in.","ops":[{"v":"G2","state":"done"},{"panel":"queue","list":[{"key":"G3"}]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"},{"key":"G3"}]}]},{"say":"Take G3 from the queue. It has no edges in.","ops":[{"v":"G3","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"B5"},{"key":"B6"},{"key":"G4"},{"key":"B3"},{"key":"B4"},{"key":"G5"},{"key":"B2"},{"key":"G2"},{"key":"G3"}]}]},{"say":"Done. 9 vertices can reach B7."}],"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.Ancestors(g, \"B7\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
