{"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":"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":"If the Compile job fails, which jobs can't run, because they wait for it directly or through other jobs?","params":{"vertex":"Compile"},"result":{"kind":"set","vertices":["Deploy","Docker image","Unit tests"]},"answer":"3 vertices are reachable from Compile: Deploy, Docker image and Unit tests.","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 Compile. It has edges to Unit tests and Docker image. Both are new, so they join the queue.","ops":[{"v":"Compile","state":"start"},{"v":"Unit tests","state":"waiting"},{"e":["Compile","Unit tests"],"state":"tree"},{"v":"Docker image","state":"waiting"},{"e":["Compile","Docker image"],"state":"tree"},{"panel":"queue","list":[{"key":"Unit tests"},{"key":"Docker image"}]},{"panel":"found","list":[{"key":"Unit tests"},{"key":"Docker image"}]}]},{"say":"Take Unit tests from the queue. It has an edge to Deploy, which is new, so it joins the queue.","ops":[{"v":"Unit tests","state":"done"},{"v":"Deploy","state":"waiting"},{"e":["Unit tests","Deploy"],"state":"tree"},{"panel":"queue","list":[{"key":"Docker image"},{"key":"Deploy"}]},{"panel":"found","list":[{"key":"Unit tests"},{"key":"Docker image"},{"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":"Unit tests"},{"key":"Docker image"},{"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":"Unit tests"},{"key":"Docker image"},{"key":"Deploy"}]}]},{"say":"Done. 3 vertices are reachable from Compile."}],"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, \"Compile\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
