{"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":"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 must a student pass before taking Compilers?","params":{"vertex":"Compilers"},"result":{"kind":"set","vertices":["Algorithms","Computer systems","Data structures","Discrete math","Programming 1","Programming 2"]},"answer":"6 vertices can reach Compilers: Algorithms, Computer systems, Data structures, Discrete math, Programming 1 and Programming 2.","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, 18 in all, to find the edges into each one."},{"say":"Start at Compilers. It has edges from Computer systems and Algorithms. Both are new, so they join the queue.","ops":[{"v":"Compilers","state":"start"},{"v":"Computer systems","state":"waiting"},{"e":["Computer systems","Compilers"],"state":"tree"},{"v":"Algorithms","state":"waiting"},{"e":["Algorithms","Compilers"],"state":"tree"},{"panel":"queue","list":[{"key":"Computer systems"},{"key":"Algorithms"}]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"}]}]},{"say":"Take Computer systems from the queue. It has an edge from Programming 2, which is new, so it joins the queue.","ops":[{"v":"Computer systems","state":"done"},{"v":"Programming 2","state":"waiting"},{"e":["Programming 2","Computer systems"],"state":"tree"},{"panel":"queue","list":[{"key":"Algorithms"},{"key":"Programming 2"}]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"},{"key":"Programming 2"}]}]},{"say":"Take Algorithms from the queue. It has edges from Discrete math and Data structures. Both are new, so they join the queue.","ops":[{"v":"Algorithms","state":"done"},{"v":"Discrete math","state":"waiting"},{"e":["Discrete math","Algorithms"],"state":"tree"},{"v":"Data structures","state":"waiting"},{"e":["Data structures","Algorithms"],"state":"tree"},{"panel":"queue","list":[{"key":"Programming 2"},{"key":"Discrete math"},{"key":"Data structures"}]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"},{"key":"Programming 2"},{"key":"Discrete math"},{"key":"Data structures"}]}]},{"say":"Take Programming 2 from the queue. It has an edge from Programming 1, which is new, so it joins the queue.","ops":[{"v":"Programming 2","state":"done"},{"v":"Programming 1","state":"waiting"},{"e":["Programming 1","Programming 2"],"state":"tree"},{"panel":"queue","list":[{"key":"Discrete math"},{"key":"Data structures"},{"key":"Programming 1"}]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"},{"key":"Programming 2"},{"key":"Discrete math"},{"key":"Data structures"},{"key":"Programming 1"}]}]},{"say":"Take Discrete math from the queue. It has no edges in.","ops":[{"v":"Discrete math","state":"done"},{"panel":"queue","list":[{"key":"Data structures"},{"key":"Programming 1"}]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"},{"key":"Programming 2"},{"key":"Discrete math"},{"key":"Data structures"},{"key":"Programming 1"}]}]},{"say":"Take Data structures from the queue. It has edges from Discrete math and Programming 2. Both were found before.","ops":[{"v":"Data structures","state":"done"},{"e":["Discrete math","Data structures"],"state":"examined"},{"e":["Programming 2","Data structures"],"state":"examined"},{"panel":"queue","list":[{"key":"Programming 1"}]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"},{"key":"Programming 2"},{"key":"Discrete math"},{"key":"Data structures"},{"key":"Programming 1"}]}]},{"say":"Take Programming 1 from the queue. It has no edges in.","ops":[{"v":"Programming 1","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"Computer systems"},{"key":"Algorithms"},{"key":"Programming 2"},{"key":"Discrete math"},{"key":"Data structures"},{"key":"Programming 1"}]}]},{"say":"Done. 6 vertices can reach Compilers."}],"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, \"Compilers\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
