{"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":"course-prereqs","name":"Course prerequisites","description":"Fourteen courses of a computer science degree, each one semester long. Each edge points from a course to a course that requires it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"Programming 1","x":100,"y":200},{"id":"Discrete math","x":100,"y":500},{"id":"Calculus 1","x":100,"y":800},{"id":"Programming 2","x":300,"y":200},{"id":"Calculus 2","x":300,"y":720},{"id":"Linear algebra","x":300,"y":880},{"id":"Computer systems","x":500,"y":120},{"id":"Data structures","x":500,"y":360},{"id":"Probability","x":500,"y":700},{"id":"Operating systems","x":700,"y":260},{"id":"Databases","x":700,"y":420},{"id":"Algorithms","x":700,"y":580},{"id":"Compilers","x":900,"y":240},{"id":"Machine learning","x":900,"y":600}],"edges":[{"from":"Programming 1","to":"Programming 2"},{"from":"Discrete math","to":"Data structures"},{"from":"Discrete math","to":"Probability"},{"from":"Discrete math","to":"Algorithms"},{"from":"Calculus 1","to":"Calculus 2"},{"from":"Calculus 1","to":"Linear algebra"},{"from":"Programming 2","to":"Computer systems"},{"from":"Programming 2","to":"Data structures"},{"from":"Calculus 2","to":"Probability"},{"from":"Linear algebra","to":"Machine learning"},{"from":"Computer systems","to":"Operating systems"},{"from":"Computer systems","to":"Compilers"},{"from":"Data structures","to":"Operating systems"},{"from":"Data structures","to":"Databases"},{"from":"Data structures","to":"Algorithms"},{"from":"Probability","to":"Machine learning"},{"from":"Algorithms","to":"Compilers"},{"from":"Algorithms","to":"Machine learning"}],"durations":{"Algorithms":1,"Calculus 1":1,"Calculus 2":1,"Compilers":1,"Computer systems":1,"Data structures":1,"Databases":1,"Discrete math":1,"Linear algebra":1,"Machine learning":1,"Operating systems":1,"Probability":1,"Programming 1":1,"Programming 2":1},"durationUnit":"semesters","details":{"vertices":14,"edges":18,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.0989010989010989,"inDegree":{"min":0,"avg":1.2857142857142858,"max":3},"outDegree":{"min":0,"avg":1.2857142857142858,"max":3},"selfLoops":0,"components":1}},"problem":"Which courses can a student take only after passing Data structures, directly or through other courses?","params":{"vertex":"Data structures"},"result":{"kind":"set","vertices":["Algorithms","Compilers","Databases","Machine learning","Operating systems"]},"answer":"5 vertices are reachable from Data structures: Algorithms, Compilers, Databases, Machine learning and Operating systems.","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 Data structures. It has edges to Operating systems, Databases and Algorithms. All 3 are new, so they join the queue.","ops":[{"v":"Data structures","state":"start"},{"v":"Operating systems","state":"waiting"},{"e":["Data structures","Operating systems"],"state":"tree"},{"v":"Databases","state":"waiting"},{"e":["Data structures","Databases"],"state":"tree"},{"v":"Algorithms","state":"waiting"},{"e":["Data structures","Algorithms"],"state":"tree"},{"panel":"queue","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]},{"panel":"found","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]}]},{"say":"Take Operating systems from the queue. It has no edges out.","ops":[{"v":"Operating systems","state":"done"},{"panel":"queue","list":[{"key":"Databases"},{"key":"Algorithms"}]},{"panel":"found","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]}]},{"say":"Take Databases from the queue. It has no edges out.","ops":[{"v":"Databases","state":"done"},{"panel":"queue","list":[{"key":"Algorithms"}]},{"panel":"found","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"}]}]},{"say":"Take Algorithms from the queue. It has edges to Compilers and Machine learning. Both are new, so they join the queue.","ops":[{"v":"Algorithms","state":"done"},{"v":"Compilers","state":"waiting"},{"e":["Algorithms","Compilers"],"state":"tree"},{"v":"Machine learning","state":"waiting"},{"e":["Algorithms","Machine learning"],"state":"tree"},{"panel":"queue","list":[{"key":"Compilers"},{"key":"Machine learning"}]},{"panel":"found","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Take Compilers from the queue. It has no edges out.","ops":[{"v":"Compilers","state":"done"},{"panel":"queue","list":[{"key":"Machine learning"}]},{"panel":"found","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Take Machine learning from the queue. It has no edges out.","ops":[{"v":"Machine learning","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"Operating systems"},{"key":"Databases"},{"key":"Algorithms"},{"key":"Compilers"},{"key":"Machine learning"}]}]},{"say":"Done. 5 vertices are reachable from Data structures."}],"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, \"Data structures\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
