{"algorithm":"affected","about":["Affected takes the vertices that changed and returns them with every vertex reachable from any of them. It is one breadth-first search that starts from all the changed vertices at once, so a vertex reachable from several of them is listed once.","The changed vertices come first, in the order given, then the rest, nearest first. It costs O(V+E) for the part of the graph it reaches, however many vertices changed. Running Descendants once for each change finds the same vertices, but repeats the work wherever their descendants overlap.","Use it to decide what to rebuild, retest or redeploy after a commit, which cells a spreadsheet recomputes after an edit, or which targets a change to a shared library touches."],"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":"A commit changes the shared libraries T11 and T25. Which targets have to build and test again?","params":{"changed":["T11","T25"]},"result":{"kind":"set","vertices":["T11","T17","T25","T30","T45","T46","T47","T48","T55","T58","T60","T62","T81","T82","T83","T84","T91","T94","T95","T96","T97","T99","T100"]},"answer":"23 vertices are affected: T11 and T25, which changed, and T17, T30, T45, T46, T47, T48, T55, T58, T60, T62 and 11 more.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In queue","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"Affected","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":"Affected","kind":"list"}]},"steps":[{"say":"T11 and T25 changed, so they are affected. Put them in the queue.","ops":[{"v":"T11","state":"waiting"},{"v":"T25","state":"waiting"},{"panel":"queue","list":[{"key":"T11"},{"key":"T25"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"}]}]},{"say":"Take T11 from the queue. It has edges to T17, T30, T45, T46 and T47. All 5 are new, so they join the queue.","ops":[{"v":"T11","state":"done"},{"v":"T17","state":"waiting"},{"e":["T11","T17"],"state":"tree"},{"v":"T30","state":"waiting"},{"e":["T11","T30"],"state":"tree"},{"v":"T45","state":"waiting"},{"e":["T11","T45"],"state":"tree"},{"v":"T46","state":"waiting"},{"e":["T11","T46"],"state":"tree"},{"v":"T47","state":"waiting"},{"e":["T11","T47"],"state":"tree"},{"panel":"queue","list":[{"key":"T25"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"}]}]},{"say":"Take T25 from the queue. It has edges to T45, T55 and T58. T55 and T58 are new, so they join the queue. T45 was found before.","ops":[{"v":"T25","state":"done"},{"e":["T25","T45"],"state":"examined"},{"v":"T55","state":"waiting"},{"e":["T25","T55"],"state":"tree"},{"v":"T58","state":"waiting"},{"e":["T25","T58"],"state":"tree"},{"panel":"queue","list":[{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"}]}]},{"say":"Take T17 from the queue. It has edges to T60 and T62. Both are new, so they join the queue.","ops":[{"v":"T17","state":"done"},{"v":"T60","state":"waiting"},{"e":["T17","T60"],"state":"tree"},{"v":"T62","state":"waiting"},{"e":["T17","T62"],"state":"tree"},{"panel":"queue","list":[{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"}]}]},{"say":"Take T30 from the queue. It has an edge to T48, which is new, so it joins the queue.","ops":[{"v":"T30","state":"done"},{"v":"T48","state":"waiting"},{"e":["T30","T48"],"state":"tree"},{"panel":"queue","list":[{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"}]}]},{"say":"Take T45 from the queue. It has an edge to T81, which is new, so it joins the queue.","ops":[{"v":"T45","state":"done"},{"v":"T81","state":"waiting"},{"e":["T45","T81"],"state":"tree"},{"panel":"queue","list":[{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"}]}]},{"say":"Take T46 from the queue. It has an edge to T82, which is new, so it joins the queue.","ops":[{"v":"T46","state":"done"},{"v":"T82","state":"waiting"},{"e":["T46","T82"],"state":"tree"},{"panel":"queue","list":[{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"}]}]},{"say":"Take T47 from the queue. It has an edge to T83, which is new, so it joins the queue.","ops":[{"v":"T47","state":"done"},{"v":"T83","state":"waiting"},{"e":["T47","T83"],"state":"tree"},{"panel":"queue","list":[{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"}]}]},{"say":"Take T55 from the queue. It has an edge to T91, which is new, so it joins the queue.","ops":[{"v":"T55","state":"done"},{"v":"T91","state":"waiting"},{"e":["T55","T91"],"state":"tree"},{"panel":"queue","list":[{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"}]}]},{"say":"Take T58 from the queue. It has an edge to T94, which is new, so it joins the queue.","ops":[{"v":"T58","state":"done"},{"v":"T94","state":"waiting"},{"e":["T58","T94"],"state":"tree"},{"panel":"queue","list":[{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"}]}]},{"say":"Take T60 from the queue. It has an edge to T95, which is new, so it joins the queue.","ops":[{"v":"T60","state":"done"},{"v":"T95","state":"waiting"},{"e":["T60","T95"],"state":"tree"},{"panel":"queue","list":[{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"}]}]},{"say":"Take T62 from the queue. It has an edge to T95, which was found before.","ops":[{"v":"T62","state":"done"},{"e":["T62","T95"],"state":"examined"},{"panel":"queue","list":[{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"}]}]},{"say":"Take T48 from the queue. It has an edge to T84, which is new, so it joins the queue.","ops":[{"v":"T48","state":"done"},{"v":"T84","state":"waiting"},{"e":["T48","T84"],"state":"tree"},{"panel":"queue","list":[{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"}]}]},{"say":"Take T81 from the queue. It has an edge to T96, which is new, so it joins the queue.","ops":[{"v":"T81","state":"done"},{"v":"T96","state":"waiting"},{"e":["T81","T96"],"state":"tree"},{"panel":"queue","list":[{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T82 from the queue. It has an edge to T96, which was found before.","ops":[{"v":"T82","state":"done"},{"e":["T82","T96"],"state":"examined"},{"panel":"queue","list":[{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T83 from the queue. It has an edge to T96, which was found before.","ops":[{"v":"T83","state":"done"},{"e":["T83","T96"],"state":"examined"},{"panel":"queue","list":[{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T91 from the queue. It has an edge to T96, which was found before.","ops":[{"v":"T91","state":"done"},{"e":["T91","T96"],"state":"examined"},{"panel":"queue","list":[{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T94 from the queue. It has an edge to T96, which was found before.","ops":[{"v":"T94","state":"done"},{"e":["T94","T96"],"state":"examined"},{"panel":"queue","list":[{"key":"T95"},{"key":"T84"},{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T95 from the queue. It has an edge to T96, which was found before.","ops":[{"v":"T95","state":"done"},{"e":["T95","T96"],"state":"examined"},{"panel":"queue","list":[{"key":"T84"},{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T84 from the queue. It has an edge to T96, which was found before.","ops":[{"v":"T84","state":"done"},{"e":["T84","T96"],"state":"examined"},{"panel":"queue","list":[{"key":"T96"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"}]}]},{"say":"Take T96 from the queue. It has edges to T97 and T100. Both are new, so they join the queue.","ops":[{"v":"T96","state":"done"},{"v":"T97","state":"waiting"},{"e":["T96","T97"],"state":"tree"},{"v":"T100","state":"waiting"},{"e":["T96","T100"],"state":"tree"},{"panel":"queue","list":[{"key":"T97"},{"key":"T100"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"},{"key":"T97"},{"key":"T100"}]}]},{"say":"Take T97 from the queue. It has an edge to T99, which is new, so it joins the queue.","ops":[{"v":"T97","state":"done"},{"v":"T99","state":"waiting"},{"e":["T97","T99"],"state":"tree"},{"panel":"queue","list":[{"key":"T100"},{"key":"T99"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"},{"key":"T97"},{"key":"T100"},{"key":"T99"}]}]},{"say":"Take T100 from the queue. It has no edges out.","ops":[{"v":"T100","state":"done"},{"panel":"queue","list":[{"key":"T99"}]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"},{"key":"T97"},{"key":"T100"},{"key":"T99"}]}]},{"say":"Take T99 from the queue. It has an edge to T100, which was found before.","ops":[{"v":"T99","state":"done"},{"e":["T99","T100"],"state":"examined"},{"panel":"queue","list":[]},{"panel":"found","list":[{"key":"T11","note":"changed"},{"key":"T25","note":"changed"},{"key":"T17"},{"key":"T30"},{"key":"T45"},{"key":"T46"},{"key":"T47"},{"key":"T55"},{"key":"T58"},{"key":"T60"},{"key":"T62"},{"key":"T48"},{"key":"T81"},{"key":"T82"},{"key":"T83"},{"key":"T91"},{"key":"T94"},{"key":"T95"},{"key":"T84"},{"key":"T96"},{"key":"T97"},{"key":"T100"},{"key":"T99"}]}]},{"say":"Done. 23 vertices are affected: the 2 changed vertices and 21 more reachable from them."}],"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.Affected(g, \"T11\", \"T25\")\nif err != nil {\n\treturn err\n}\nfor _, v := range jobs {\n\tfmt.Println(v.Label())\n}"}
