{"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":"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":"Which jobs have to finish before the Docker image job can start?","params":{"vertex":"Docker image"},"result":{"kind":"set","vertices":["Checkout","Compile","Install"]},"answer":"3 vertices can reach Docker image: Checkout, Compile and Install.","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, 9 in all, to find the edges into each one."},{"say":"Start at Docker image. It has edges from Checkout and Compile. Both are new, so they join the queue.","ops":[{"v":"Docker image","state":"start"},{"v":"Checkout","state":"waiting"},{"e":["Checkout","Docker image"],"state":"tree"},{"v":"Compile","state":"waiting"},{"e":["Compile","Docker image"],"state":"tree"},{"panel":"queue","list":[{"key":"Checkout"},{"key":"Compile"}]},{"panel":"found","list":[{"key":"Checkout"},{"key":"Compile"}]}]},{"say":"Take Checkout from the queue. It has no edges in.","ops":[{"v":"Checkout","state":"done"},{"panel":"queue","list":[{"key":"Compile"}]},{"panel":"found","list":[{"key":"Checkout"},{"key":"Compile"}]}]},{"say":"Take Compile from the queue. It has an edge from Install, which is new, so it joins the queue.","ops":[{"v":"Compile","state":"done"},{"v":"Install","state":"waiting"},{"e":["Install","Compile"],"state":"tree"},{"panel":"queue","list":[{"key":"Install"}]},{"panel":"found","list":[{"key":"Checkout"},{"key":"Compile"},{"key":"Install"}]}]},{"say":"Take Install from the queue. It has an edge from Checkout, which was found before.","ops":[{"v":"Install","state":"done"},{"e":["Checkout","Install"],"state":"examined"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"Checkout"},{"key":"Compile"},{"key":"Install"}]}]},{"say":"Done. 3 vertices can reach Docker image."}],"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, \"Docker image\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
