{"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":"monorepo-build","name":"Monorepo build","description":"One hundred build targets, T1 to T100, in the repository of an online shop. T1 to T32 are shared libraries, T33 to T41 the code generator and API definitions, T42 to T58 services, T59 to T63 batch jobs, T64 to T71 the API client and UI packages, T72 to T76 apps, T77 to T95 container images, and T96 to T100 the deploys and the contract and end-to-end tests. A target takes 1 to 20 minutes to build. Each edge points from a target to a target that builds on it.","family":"dag","directed":true,"weighted":false,"acyclic":true,"vertices":[{"id":"T1","x":44,"y":294},{"id":"T2","x":127,"y":199},{"id":"T3","x":210,"y":285},{"id":"T4","x":127,"y":313},{"id":"T5","x":127,"y":256},{"id":"T6","x":210,"y":228},{"id":"T7","x":293,"y":229},{"id":"T8","x":210,"y":171},{"id":"T9","x":293,"y":58},{"id":"T10","x":210,"y":114},{"id":"T11","x":210,"y":449},{"id":"T12","x":210,"y":392},{"id":"T13","x":293,"y":514},{"id":"T14","x":376,"y":553},{"id":"T15","x":127,"y":427},{"id":"T16","x":127,"y":142},{"id":"T17","x":293,"y":457},{"id":"T18","x":293,"y":172},{"id":"T19","x":376,"y":211},{"id":"T20","x":293,"y":343},{"id":"T21","x":376,"y":268},{"id":"T22","x":376,"y":325},{"id":"T23","x":376,"y":439},{"id":"T24","x":459,"y":211},{"id":"T25","x":376,"y":496},{"id":"T26","x":293,"y":115},{"id":"T27","x":293,"y":286},{"id":"T28","x":293,"y":400},{"id":"T29","x":459,"y":154},{"id":"T30","x":459,"y":97},{"id":"T31","x":376,"y":97},{"id":"T32","x":459,"y":40},{"id":"T33","x":44,"y":602},{"id":"T34","x":127,"y":602},{"id":"T35","x":293,"y":742},{"id":"T36","x":210,"y":610},{"id":"T37","x":293,"y":685},{"id":"T38","x":293,"y":628},{"id":"T39","x":293,"y":571},{"id":"T40","x":376,"y":610},{"id":"T41","x":210,"y":533},{"id":"T42","x":542,"y":439},{"id":"T43","x":459,"y":496},{"id":"T44","x":459,"y":268},{"id":"T45","x":459,"y":610},{"id":"T46","x":459,"y":781},{"id":"T47","x":459,"y":553},{"id":"T48","x":542,"y":268},{"id":"T49","x":459,"y":439},{"id":"T50","x":459,"y":325},{"id":"T51","x":542,"y":382},{"id":"T52","x":459,"y":667},{"id":"T53","x":459,"y":838},{"id":"T54","x":542,"y":211},{"id":"T55","x":459,"y":724},{"id":"T56","x":542,"y":97},{"id":"T57","x":542,"y":40},{"id":"T58","x":542,"y":553},{"id":"T59","x":542,"y":154},{"id":"T60","x":376,"y":154},{"id":"T61","x":542,"y":325},{"id":"T62","x":376,"y":382},{"id":"T63","x":376,"y":40},{"id":"T64","x":376,"y":765},{"id":"T65","x":44,"y":926},{"id":"T66","x":44,"y":812},{"id":"T67","x":44,"y":869},{"id":"T68","x":127,"y":847},{"id":"T69","x":210,"y":837},{"id":"T70","x":127,"y":932},{"id":"T71","x":210,"y":894},{"id":"T72","x":459,"y":895},{"id":"T73","x":459,"y":952},{"id":"T74","x":708,"y":804},{"id":"T75","x":293,"y":873},{"id":"T76","x":708,"y":747},{"id":"T77","x":459,"y":382},{"id":"T78","x":625,"y":403},{"id":"T79","x":625,"y":574},{"id":"T80","x":625,"y":346},{"id":"T81","x":542,"y":610},{"id":"T82","x":625,"y":688},{"id":"T83","x":625,"y":631},{"id":"T84","x":625,"y":289},{"id":"T85","x":542,"y":496},{"id":"T86","x":625,"y":517},{"id":"T87","x":625,"y":460},{"id":"T88","x":542,"y":667},{"id":"T89","x":542,"y":781},{"id":"T90","x":625,"y":232},{"id":"T91","x":542,"y":724},{"id":"T92","x":625,"y":175},{"id":"T93","x":625,"y":118},{"id":"T94","x":625,"y":745},{"id":"T95","x":625,"y":61},{"id":"T96","x":708,"y":438},{"id":"T97","x":791,"y":459},{"id":"T98","x":708,"y":495},{"id":"T99","x":874,"y":469},{"id":"T100","x":957,"y":454}],"edges":[{"from":"T1","to":"T4"},{"from":"T1","to":"T5"},{"from":"T5","to":"T6"},{"from":"T5","to":"T7"},{"from":"T6","to":"T7"},{"from":"T2","to":"T8"},{"from":"T1","to":"T8"},{"from":"T2","to":"T9"},{"from":"T6","to":"T9"},{"from":"T1","to":"T10"},{"from":"T1","to":"T11"},{"from":"T4","to":"T12"},{"from":"T1","to":"T13"},{"from":"T12","to":"T13"},{"from":"T1","to":"T14"},{"from":"T1","to":"T15"},{"from":"T1","to":"T16"},{"from":"T12","to":"T17"},{"from":"T11","to":"T17"},{"from":"T4","to":"T18"},{"from":"T5","to":"T18"},{"from":"T6","to":"T18"},{"from":"T8","to":"T18"},{"from":"T3","to":"T18"},{"from":"T18","to":"T19"},{"from":"T4","to":"T20"},{"from":"T6","to":"T20"},{"from":"T8","to":"T20"},{"from":"T4","to":"T21"},{"from":"T7","to":"T21"},{"from":"T8","to":"T21"},{"from":"T3","to":"T21"},{"from":"T4","to":"T22"},{"from":"T7","to":"T22"},{"from":"T9","to":"T22"},{"from":"T13","to":"T22"},{"from":"T4","to":"T23"},{"from":"T7","to":"T23"},{"from":"T34","to":"T23"},{"from":"T10","to":"T24"},{"from":"T20","to":"T24"},{"from":"T22","to":"T24"},{"from":"T23","to":"T24"},{"from":"T4","to":"T25"},{"from":"T20","to":"T25"},{"from":"T4","to":"T26"},{"from":"T8","to":"T26"},{"from":"T6","to":"T26"},{"from":"T4","to":"T27"},{"from":"T8","to":"T27"},{"from":"T12","to":"T27"},{"from":"T4","to":"T28"},{"from":"T8","to":"T28"},{"from":"T12","to":"T28"},{"from":"T22","to":"T29"},{"from":"T8","to":"T29"},{"from":"T14","to":"T29"},{"from":"T22","to":"T30"},{"from":"T11","to":"T30"},{"from":"T10","to":"T30"},{"from":"T26","to":"T31"},{"from":"T18","to":"T32"},{"from":"T20","to":"T32"},{"from":"T21","to":"T32"},{"from":"T22","to":"T32"},{"from":"T33","to":"T34"},{"from":"T34","to":"T35"},{"from":"T34","to":"T36"},{"from":"T34","to":"T37"},{"from":"T36","to":"T37"},{"from":"T34","to":"T38"},{"from":"T34","to":"T39"},{"from":"T36","to":"T39"},{"from":"T34","to":"T40"},{"from":"T37","to":"T40"},{"from":"T34","to":"T41"},{"from":"T18","to":"T42"},{"from":"T23","to":"T42"},{"from":"T24","to":"T42"},{"from":"T13","to":"T42"},{"from":"T35","to":"T42"},{"from":"T18","to":"T43"},{"from":"T23","to":"T43"},{"from":"T20","to":"T43"},{"from":"T14","to":"T43"},{"from":"T36","to":"T43"},{"from":"T18","to":"T44"},{"from":"T23","to":"T44"},{"from":"T21","to":"T44"},{"from":"T39","to":"T44"},{"from":"T23","to":"T45"},{"from":"T20","to":"T45"},{"from":"T11","to":"T45"},{"from":"T25","to":"T45"},{"from":"T36","to":"T45"},{"from":"T23","to":"T46"},{"from":"T20","to":"T46"},{"from":"T11","to":"T46"},{"from":"T37","to":"T46"},{"from":"T18","to":"T47"},{"from":"T23","to":"T47"},{"from":"T21","to":"T47"},{"from":"T11","to":"T47"},{"from":"T37","to":"T47"},{"from":"T38","to":"T47"},{"from":"T18","to":"T48"},{"from":"T23","to":"T48"},{"from":"T21","to":"T48"},{"from":"T30","to":"T48"},{"from":"T38","to":"T48"},{"from":"T18","to":"T49"},{"from":"T23","to":"T49"},{"from":"T21","to":"T49"},{"from":"T15","to":"T49"},{"from":"T40","to":"T49"},{"from":"T23","to":"T50"},{"from":"T21","to":"T50"},{"from":"T27","to":"T50"},{"from":"T28","to":"T50"},{"from":"T41","to":"T50"},{"from":"T23","to":"T51"},{"from":"T21","to":"T51"},{"from":"T29","to":"T51"},{"from":"T36","to":"T51"},{"from":"T18","to":"T52"},{"from":"T23","to":"T52"},{"from":"T13","to":"T52"},{"from":"T14","to":"T52"},{"from":"T36","to":"T52"},{"from":"T23","to":"T53"},{"from":"T20","to":"T53"},{"from":"T36","to":"T53"},{"from":"T35","to":"T53"},{"from":"T22","to":"T54"},{"from":"T24","to":"T54"},{"from":"T31","to":"T54"},{"from":"T23","to":"T55"},{"from":"T25","to":"T55"},{"from":"T38","to":"T55"},{"from":"T18","to":"T56"},{"from":"T21","to":"T56"},{"from":"T26","to":"T56"},{"from":"T18","to":"T57"},{"from":"T21","to":"T57"},{"from":"T2","to":"T57"},{"from":"T22","to":"T58"},{"from":"T24","to":"T58"},{"from":"T9","to":"T58"},{"from":"T25","to":"T58"},{"from":"T35","to":"T58"},{"from":"T36","to":"T58"},{"from":"T37","to":"T58"},{"from":"T19","to":"T59"},{"from":"T18","to":"T60"},{"from":"T26","to":"T60"},{"from":"T16","to":"T60"},{"from":"T17","to":"T60"},{"from":"T18","to":"T61"},{"from":"T29","to":"T61"},{"from":"T36","to":"T61"},{"from":"T18","to":"T62"},{"from":"T27","to":"T62"},{"from":"T17","to":"T62"},{"from":"T38","to":"T62"},{"from":"T18","to":"T63"},{"from":"T26","to":"T63"},{"from":"T2","to":"T63"},{"from":"T35","to":"T64"},{"from":"T36","to":"T64"},{"from":"T37","to":"T64"},{"from":"T38","to":"T64"},{"from":"T65","to":"T68"},{"from":"T66","to":"T68"},{"from":"T68","to":"T69"},{"from":"T67","to":"T69"},{"from":"T65","to":"T70"},{"from":"T68","to":"T71"},{"from":"T67","to":"T71"},{"from":"T68","to":"T72"},{"from":"T69","to":"T72"},{"from":"T67","to":"T72"},{"from":"T64","to":"T72"},{"from":"T68","to":"T73"},{"from":"T69","to":"T73"},{"from":"T70","to":"T73"},{"from":"T71","to":"T73"},{"from":"T64","to":"T73"},{"from":"T65","to":"T74"},{"from":"T67","to":"T74"},{"from":"T64","to":"T74"},{"from":"T68","to":"T75"},{"from":"T69","to":"T75"},{"from":"T70","to":"T75"},{"from":"T71","to":"T75"},{"from":"T68","to":"T76"},{"from":"T64","to":"T76"},{"from":"T77","to":"T78"},{"from":"T42","to":"T78"},{"from":"T77","to":"T79"},{"from":"T43","to":"T79"},{"from":"T77","to":"T80"},{"from":"T44","to":"T80"},{"from":"T77","to":"T81"},{"from":"T45","to":"T81"},{"from":"T77","to":"T82"},{"from":"T46","to":"T82"},{"from":"T77","to":"T83"},{"from":"T47","to":"T83"},{"from":"T77","to":"T84"},{"from":"T48","to":"T84"},{"from":"T77","to":"T85"},{"from":"T49","to":"T85"},{"from":"T77","to":"T86"},{"from":"T50","to":"T86"},{"from":"T77","to":"T87"},{"from":"T51","to":"T87"},{"from":"T77","to":"T88"},{"from":"T52","to":"T88"},{"from":"T77","to":"T89"},{"from":"T53","to":"T89"},{"from":"T77","to":"T90"},{"from":"T54","to":"T90"},{"from":"T77","to":"T91"},{"from":"T55","to":"T91"},{"from":"T77","to":"T92"},{"from":"T56","to":"T92"},{"from":"T77","to":"T93"},{"from":"T57","to":"T93"},{"from":"T77","to":"T94"},{"from":"T58","to":"T94"},{"from":"T72","to":"T94"},{"from":"T73","to":"T94"},{"from":"T77","to":"T95"},{"from":"T59","to":"T95"},{"from":"T60","to":"T95"},{"from":"T61","to":"T95"},{"from":"T62","to":"T95"},{"from":"T63","to":"T95"},{"from":"T78","to":"T96"},{"from":"T79","to":"T96"},{"from":"T80","to":"T96"},{"from":"T81","to":"T96"},{"from":"T82","to":"T96"},{"from":"T83","to":"T96"},{"from":"T84","to":"T96"},{"from":"T85","to":"T96"},{"from":"T86","to":"T96"},{"from":"T87","to":"T96"},{"from":"T88","to":"T96"},{"from":"T89","to":"T96"},{"from":"T90","to":"T96"},{"from":"T91","to":"T96"},{"from":"T92","to":"T96"},{"from":"T93","to":"T96"},{"from":"T94","to":"T96"},{"from":"T95","to":"T96"},{"from":"T96","to":"T97"},{"from":"T32","to":"T98"},{"from":"T35","to":"T98"},{"from":"T36","to":"T98"},{"from":"T37","to":"T98"},{"from":"T38","to":"T98"},{"from":"T97","to":"T99"},{"from":"T98","to":"T99"},{"from":"T96","to":"T100"},{"from":"T99","to":"T100"}],"durations":{"T1":2,"T10":2,"T100":4,"T11":2,"T12":2,"T13":2,"T14":2,"T15":2,"T16":2,"T17":2,"T18":4,"T19":2,"T2":2,"T20":2,"T21":2,"T22":4,"T23":4,"T24":3,"T25":2,"T26":2,"T27":2,"T28":2,"T29":2,"T3":2,"T30":2,"T31":2,"T32":5,"T33":3,"T34":1,"T35":1,"T36":1,"T37":1,"T38":1,"T39":1,"T4":2,"T40":1,"T41":1,"T42":6,"T43":6,"T44":6,"T45":6,"T46":6,"T47":6,"T48":6,"T49":6,"T5":2,"T50":6,"T51":6,"T52":6,"T53":6,"T54":6,"T55":6,"T56":6,"T57":6,"T58":6,"T59":3,"T6":2,"T60":3,"T61":3,"T62":3,"T63":3,"T64":2,"T65":2,"T66":2,"T67":2,"T68":2,"T69":2,"T7":2,"T70":2,"T71":2,"T72":8,"T73":8,"T74":8,"T75":8,"T76":8,"T77":4,"T78":2,"T79":2,"T8":2,"T80":2,"T81":2,"T82":2,"T83":2,"T84":2,"T85":2,"T86":2,"T87":2,"T88":2,"T89":2,"T9":2,"T90":2,"T91":2,"T92":2,"T93":2,"T94":2,"T95":2,"T96":1,"T97":4,"T98":10,"T99":20},"durationUnit":"minutes","details":{"vertices":100,"edges":266,"directed":true,"weighted":false,"acyclic":true,"negativeWeights":false,"density":0.026868686868686868,"inDegree":{"min":0,"avg":2.66,"max":18},"outDegree":{"min":0,"avg":2.66,"max":18},"selfLoops":0,"components":1}},"problem":"Which targets does the service T58 build on, directly or through other targets?","params":{"vertex":"T58"},"result":{"kind":"set","vertices":["T1","T2","T4","T5","T6","T7","T8","T9","T10","T12","T13","T20","T22","T23","T24","T25","T33","T34","T35","T36","T37"]},"answer":"21 vertices can reach T58: T1, T2, T4, T5, T6, T7, T8, T9, T10, T12 and 11 more.","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, 266 in all, to find the edges into each one."},{"say":"Start at T58. It has edges from T9, T22, T24, T25, T35, T36 and T37. All 7 are new, so they join the queue.","ops":[{"v":"T58","state":"start"},{"v":"T9","state":"waiting"},{"e":["T9","T58"],"state":"tree"},{"v":"T22","state":"waiting"},{"e":["T22","T58"],"state":"tree"},{"v":"T24","state":"waiting"},{"e":["T24","T58"],"state":"tree"},{"v":"T25","state":"waiting"},{"e":["T25","T58"],"state":"tree"},{"v":"T35","state":"waiting"},{"e":["T35","T58"],"state":"tree"},{"v":"T36","state":"waiting"},{"e":["T36","T58"],"state":"tree"},{"v":"T37","state":"waiting"},{"e":["T37","T58"],"state":"tree"},{"panel":"queue","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"}]}]},{"say":"Take T9 from the queue. It has edges from T2 and T6. Both are new, so they join the queue.","ops":[{"v":"T9","state":"done"},{"v":"T2","state":"waiting"},{"e":["T2","T9"],"state":"tree"},{"v":"T6","state":"waiting"},{"e":["T6","T9"],"state":"tree"},{"panel":"queue","list":[{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"}]}]},{"say":"Take T22 from the queue. It has edges from T4, T7, T9 and T13. T4, T7 and T13 are new, so they join the queue. T9 was found before.","ops":[{"v":"T22","state":"done"},{"v":"T4","state":"waiting"},{"e":["T4","T22"],"state":"tree"},{"v":"T7","state":"waiting"},{"e":["T7","T22"],"state":"tree"},{"e":["T9","T22"],"state":"examined"},{"v":"T13","state":"waiting"},{"e":["T13","T22"],"state":"tree"},{"panel":"queue","list":[{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"}]}]},{"say":"Take T24 from the queue. It has edges from T10, T20, T22 and T23. T10, T20 and T23 are new, so they join the queue. T22 was found before.","ops":[{"v":"T24","state":"done"},{"v":"T10","state":"waiting"},{"e":["T10","T24"],"state":"tree"},{"v":"T20","state":"waiting"},{"e":["T20","T24"],"state":"tree"},{"e":["T22","T24"],"state":"examined"},{"v":"T23","state":"waiting"},{"e":["T23","T24"],"state":"tree"},{"panel":"queue","list":[{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"}]}]},{"say":"Take T25 from the queue. It has edges from T4 and T20. Both were found before.","ops":[{"v":"T25","state":"done"},{"e":["T4","T25"],"state":"examined"},{"e":["T20","T25"],"state":"examined"},{"panel":"queue","list":[{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"}]}]},{"say":"Take T35 from the queue. It has an edge from T34, which is new, so it joins the queue.","ops":[{"v":"T35","state":"done"},{"v":"T34","state":"waiting"},{"e":["T34","T35"],"state":"tree"},{"panel":"queue","list":[{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]}]},{"say":"Take T36 from the queue. It has an edge from T34, which was found before.","ops":[{"v":"T36","state":"done"},{"e":["T34","T36"],"state":"examined"},{"panel":"queue","list":[{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]}]},{"say":"Take T37 from the queue. It has edges from T34 and T36. Both were found before.","ops":[{"v":"T37","state":"done"},{"e":["T34","T37"],"state":"examined"},{"e":["T36","T37"],"state":"examined"},{"panel":"queue","list":[{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]}]},{"say":"Take T2 from the queue. It has no edges in.","ops":[{"v":"T2","state":"done"},{"panel":"queue","list":[{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"}]}]},{"say":"Take T6 from the queue. It has an edge from T5, which is new, so it joins the queue.","ops":[{"v":"T6","state":"done"},{"v":"T5","state":"waiting"},{"e":["T5","T6"],"state":"tree"},{"panel":"queue","list":[{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"}]}]},{"say":"Take T4 from the queue. It has an edge from T1, which is new, so it joins the queue.","ops":[{"v":"T4","state":"done"},{"v":"T1","state":"waiting"},{"e":["T1","T4"],"state":"tree"},{"panel":"queue","list":[{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"}]}]},{"say":"Take T7 from the queue. It has edges from T5 and T6. Both were found before.","ops":[{"v":"T7","state":"done"},{"e":["T5","T7"],"state":"examined"},{"e":["T6","T7"],"state":"examined"},{"panel":"queue","list":[{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"}]}]},{"say":"Take T13 from the queue. It has edges from T1 and T12. T12 is new, so it joins the queue. T1 was found before.","ops":[{"v":"T13","state":"done"},{"e":["T1","T13"],"state":"examined"},{"v":"T12","state":"waiting"},{"e":["T12","T13"],"state":"tree"},{"panel":"queue","list":[{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"}]}]},{"say":"Take T10 from the queue. It has an edge from T1, which was found before.","ops":[{"v":"T10","state":"done"},{"e":["T1","T10"],"state":"examined"},{"panel":"queue","list":[{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"}]}]},{"say":"Take T20 from the queue. It has edges from T4, T6 and T8. T8 is new, so it joins the queue. T4 and T6 were found before.","ops":[{"v":"T20","state":"done"},{"e":["T4","T20"],"state":"examined"},{"e":["T6","T20"],"state":"examined"},{"v":"T8","state":"waiting"},{"e":["T8","T20"],"state":"tree"},{"panel":"queue","list":[{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"}]}]},{"say":"Take T23 from the queue. It has edges from T4, T7 and T34. All 3 were found before.","ops":[{"v":"T23","state":"done"},{"e":["T4","T23"],"state":"examined"},{"e":["T7","T23"],"state":"examined"},{"e":["T34","T23"],"state":"examined"},{"panel":"queue","list":[{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"}]}]},{"say":"Take T34 from the queue. It has an edge from T33, which is new, so it joins the queue.","ops":[{"v":"T34","state":"done"},{"v":"T33","state":"waiting"},{"e":["T33","T34"],"state":"tree"},{"panel":"queue","list":[{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]}]},{"say":"Take T5 from the queue. It has an edge from T1, which was found before.","ops":[{"v":"T5","state":"done"},{"e":["T1","T5"],"state":"examined"},{"panel":"queue","list":[{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]}]},{"say":"Take T1 from the queue. It has no edges in.","ops":[{"v":"T1","state":"done"},{"panel":"queue","list":[{"key":"T12"},{"key":"T8"},{"key":"T33"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]}]},{"say":"Take T12 from the queue. It has an edge from T4, which was found before.","ops":[{"v":"T12","state":"done"},{"e":["T4","T12"],"state":"examined"},{"panel":"queue","list":[{"key":"T8"},{"key":"T33"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]}]},{"say":"Take T8 from the queue. It has edges from T1 and T2. Both were found before.","ops":[{"v":"T8","state":"done"},{"e":["T1","T8"],"state":"examined"},{"e":["T2","T8"],"state":"examined"},{"panel":"queue","list":[{"key":"T33"}]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]}]},{"say":"Take T33 from the queue. It has no edges in.","ops":[{"v":"T33","state":"done"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"T9"},{"key":"T22"},{"key":"T24"},{"key":"T25"},{"key":"T35"},{"key":"T36"},{"key":"T37"},{"key":"T2"},{"key":"T6"},{"key":"T4"},{"key":"T7"},{"key":"T13"},{"key":"T10"},{"key":"T20"},{"key":"T23"},{"key":"T34"},{"key":"T5"},{"key":"T1"},{"key":"T12"},{"key":"T8"},{"key":"T33"}]}]},{"say":"Done. 21 vertices can reach T58."}],"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, \"T58\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
