{"algorithm":"kosaraju","about":["Kosaraju's algorithm finds the strongly connected components with two depth-first searches. The first runs over the whole graph and notes each vertex as it finishes, after everything it leads to. The second runs on a copy of the graph with every edge reversed, and takes its start vertices from the last one to finish to the first.","The vertex that finishes last is in a component that no other component can reach. With the edges reversed, a search from it can't leave that component, so it collects exactly that component. Each later search does the same with what is left, so a component comes out before any component it can reach.","Both searches cost O(V+E), and the reversed copy takes O(V+E) more memory than Tarjan or Gabow need. In exchange, each search is a plain depth-first search with nothing more to track."],"template":{"id":"import-cycles","name":"Import cycles","description":"Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"main","x":500,"y":80},{"id":"cli","x":180,"y":240},{"id":"api","x":560,"y":200},{"id":"config","x":860,"y":320},{"id":"handlers","x":420,"y":340},{"id":"middleware","x":680,"y":370},{"id":"auth","x":720,"y":470},{"id":"session","x":700,"y":640},{"id":"users","x":480,"y":540},{"id":"billing","x":280,"y":470},{"id":"invoices","x":300,"y":650},{"id":"models","x":480,"y":790},{"id":"db","x":180,"y":800},{"id":"cache","x":320,"y":900},{"id":"email","x":700,"y":800},{"id":"templates","x":880,"y":860},{"id":"utils","x":900,"y":480},{"id":"logging","x":900,"y":660}],"edges":[{"from":"main","to":"cli"},{"from":"main","to":"api"},{"from":"main","to":"config"},{"from":"cli","to":"config"},{"from":"cli","to":"db"},{"from":"api","to":"handlers"},{"from":"api","to":"middleware"},{"from":"api","to":"config"},{"from":"handlers","to":"auth"},{"from":"handlers","to":"users"},{"from":"handlers","to":"billing"},{"from":"middleware","to":"auth"},{"from":"middleware","to":"logging"},{"from":"auth","to":"session"},{"from":"session","to":"users"},{"from":"users","to":"auth"},{"from":"users","to":"billing"},{"from":"users","to":"models"},{"from":"billing","to":"invoices"},{"from":"invoices","to":"users"},{"from":"invoices","to":"models"},{"from":"invoices","to":"email"},{"from":"models","to":"db"},{"from":"db","to":"cache"},{"from":"cache","to":"models"},{"from":"email","to":"templates"},{"from":"templates","to":"email"},{"from":"config","to":"utils"},{"from":"utils","to":"logging"},{"from":"logging","to":"utils"}],"details":{"vertices":18,"edges":30,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.09803921568627451,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":1,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Which groups of packages import each other in a loop, so that none of them can load without the others?","params":{},"result":{"kind":"groups","groups":[["main"],["api"],["middleware"],["handlers"],["auth","billing","invoices","session","users"],["email","templates"],["cli"],["cache","db","models"],["config"],["logging","utils"]]},"answer":"The graph has 10 strongly connected components. The ones with more than one vertex are auth, billing, invoices, session and users; email and templates; cache, db and models; logging and utils. The other 6 components have one vertex each: main, api, middleware, handlers, cli and config.","legend":{"vertex":[{"id":"idle","label":"Not reached","color":"#64748B","shape":"hollow"},{"id":"current","label":"On the search path","color":"#56B4E9","shape":"ring"},{"id":"waiting","label":"Finished, waits for the second pass","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"In a component","color":"#009E73","shape":"filled"},{"id":"component-5","label":"Component 5, 5 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-6","label":"Component 6, 2 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-8","label":"Component 8, 3 vertices","color":"#E69F00","shape":"filled"},{"id":"component-10","label":"Component 10, 2 vertices","color":"#F0E442","shape":"dashed-square"},{"id":"single","label":"A component of one vertex","color":"#CBD5E1","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Used to reach a vertex in the first pass","color":"#009E73","shape":"thick"},{"id":"reversed","label":"Followed backwards in the second pass","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"finished","title":"Finish stack, last finished on top","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"Kosaraju makes two passes. The first searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and pushes each vertex on a stack when it finishes, once every vertex it has an edge to has been reached. The second pass reverses every edge and searches again, taking its starts from the top of that stack. Each search in the second pass reaches exactly one strongly connected component."},{"say":"Start the first pass at main, the first vertex.","ops":[{"v":"main","state":"current"}]},{"say":"Follow main to cli.","ops":[{"v":"cli","state":"current"},{"e":["main","cli"],"state":"tree"}]},{"say":"Follow cli to config.","ops":[{"v":"config","state":"current"},{"e":["cli","config"],"state":"tree"}]},{"say":"Follow config to utils.","ops":[{"v":"utils","state":"current"},{"e":["config","utils"],"state":"tree"}]},{"say":"Follow utils to logging.","ops":[{"v":"logging","state":"current"},{"e":["utils","logging"],"state":"tree"}]},{"say":"logging has no unreached neighbors left, so it finishes, number 1. Push it on the finish stack. Back to utils.","ops":[{"v":"logging","state":"waiting"},{"panel":"finished","list":[{"key":"logging","note":"1"}]}]},{"say":"utils has no unreached neighbors left, so it finishes, number 2. Push it on the finish stack. Back to config.","ops":[{"v":"utils","state":"waiting"},{"panel":"finished","list":[{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"config has no unreached neighbors left, so it finishes, number 3. Push it on the finish stack. Back to cli.","ops":[{"v":"config","state":"waiting"},{"panel":"finished","list":[{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Follow cli to db.","ops":[{"v":"db","state":"current"},{"e":["cli","db"],"state":"tree"}]},{"say":"Follow db to cache.","ops":[{"v":"cache","state":"current"},{"e":["db","cache"],"state":"tree"}]},{"say":"Follow cache to models.","ops":[{"v":"models","state":"current"},{"e":["cache","models"],"state":"tree"}]},{"say":"models has no unreached neighbors left, so it finishes, number 4. Push it on the finish stack. Back to cache.","ops":[{"v":"models","state":"waiting"},{"panel":"finished","list":[{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"cache has no unreached neighbors left, so it finishes, number 5. Push it on the finish stack. Back to db.","ops":[{"v":"cache","state":"waiting"},{"panel":"finished","list":[{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"db has no unreached neighbors left, so it finishes, number 6. Push it on the finish stack. Back to cli.","ops":[{"v":"db","state":"waiting"},{"panel":"finished","list":[{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"cli has no unreached neighbors left, so it finishes, number 7. Push it on the finish stack. Back to main.","ops":[{"v":"cli","state":"waiting"},{"panel":"finished","list":[{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Follow main to api.","ops":[{"v":"api","state":"current"},{"e":["main","api"],"state":"tree"}]},{"say":"Follow api to handlers.","ops":[{"v":"handlers","state":"current"},{"e":["api","handlers"],"state":"tree"}]},{"say":"Follow handlers to auth.","ops":[{"v":"auth","state":"current"},{"e":["handlers","auth"],"state":"tree"}]},{"say":"Follow auth to session.","ops":[{"v":"session","state":"current"},{"e":["auth","session"],"state":"tree"}]},{"say":"Follow session to users.","ops":[{"v":"users","state":"current"},{"e":["session","users"],"state":"tree"}]},{"say":"Follow users to billing.","ops":[{"v":"billing","state":"current"},{"e":["users","billing"],"state":"tree"}]},{"say":"Follow billing to invoices.","ops":[{"v":"invoices","state":"current"},{"e":["billing","invoices"],"state":"tree"}]},{"say":"Follow invoices to email.","ops":[{"v":"email","state":"current"},{"e":["invoices","email"],"state":"tree"}]},{"say":"Follow email to templates.","ops":[{"v":"templates","state":"current"},{"e":["email","templates"],"state":"tree"}]},{"say":"templates has no unreached neighbors left, so it finishes, number 8. Push it on the finish stack. Back to email.","ops":[{"v":"templates","state":"waiting"},{"panel":"finished","list":[{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"email has no unreached neighbors left, so it finishes, number 9. Push it on the finish stack. Back to invoices.","ops":[{"v":"email","state":"waiting"},{"panel":"finished","list":[{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"invoices has no unreached neighbors left, so it finishes, number 10. Push it on the finish stack. Back to billing.","ops":[{"v":"invoices","state":"waiting"},{"panel":"finished","list":[{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"billing has no unreached neighbors left, so it finishes, number 11. Push it on the finish stack. Back to users.","ops":[{"v":"billing","state":"waiting"},{"panel":"finished","list":[{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"users has no unreached neighbors left, so it finishes, number 12. Push it on the finish stack. Back to session.","ops":[{"v":"users","state":"waiting"},{"panel":"finished","list":[{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"session has no unreached neighbors left, so it finishes, number 13. Push it on the finish stack. Back to auth.","ops":[{"v":"session","state":"waiting"},{"panel":"finished","list":[{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"auth has no unreached neighbors left, so it finishes, number 14. Push it on the finish stack. Back to handlers.","ops":[{"v":"auth","state":"waiting"},{"panel":"finished","list":[{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"handlers has no unreached neighbors left, so it finishes, number 15. Push it on the finish stack. Back to api.","ops":[{"v":"handlers","state":"waiting"},{"panel":"finished","list":[{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Follow api to middleware.","ops":[{"v":"middleware","state":"current"},{"e":["api","middleware"],"state":"tree"}]},{"say":"middleware has no unreached neighbors left, so it finishes, number 16. Push it on the finish stack. Back to api.","ops":[{"v":"middleware","state":"waiting"},{"panel":"finished","list":[{"key":"middleware","note":"16"},{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"api has no unreached neighbors left, so it finishes, number 17. Push it on the finish stack. Back to main.","ops":[{"v":"api","state":"waiting"},{"panel":"finished","list":[{"key":"api","note":"17"},{"key":"middleware","note":"16"},{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"main has no unreached neighbors left, so it finishes, number 18. Push it on the finish stack.","ops":[{"v":"main","state":"waiting"},{"panel":"finished","list":[{"key":"main","note":"18"},{"key":"api","note":"17"},{"key":"middleware","note":"16"},{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"The first pass is done. main finished last, so no edge comes into its component from another component. The second pass follows every edge backwards, taking its starts from the top of the finish stack. A backwards search from main can't leave its component, and each later start is in a component whose other incoming edges come from components already found, so every search reaches exactly one component.","ops":[{"e":["main","cli"],"state":"idle"},{"e":["cli","config"],"state":"idle"},{"e":["config","utils"],"state":"idle"},{"e":["utils","logging"],"state":"idle"},{"e":["cli","db"],"state":"idle"},{"e":["db","cache"],"state":"idle"},{"e":["cache","models"],"state":"idle"},{"e":["main","api"],"state":"idle"},{"e":["api","handlers"],"state":"idle"},{"e":["handlers","auth"],"state":"idle"},{"e":["auth","session"],"state":"idle"},{"e":["session","users"],"state":"idle"},{"e":["users","billing"],"state":"idle"},{"e":["billing","invoices"],"state":"idle"},{"e":["invoices","email"],"state":"idle"},{"e":["email","templates"],"state":"idle"},{"e":["api","middleware"],"state":"idle"}]},{"say":"Take main off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 1.","ops":[{"v":"main","state":"current"},{"panel":"finished","list":[{"key":"api","note":"17"},{"key":"middleware","note":"16"},{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"No edge comes into main. The search from main is done. main is component 1 on its own.","ops":[{"v":"main","state":"done"},{"panel":"components","groups":[["main"]]}]},{"say":"Take api off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 2.","ops":[{"v":"api","state":"current"},{"panel":"finished","list":[{"key":"middleware","note":"16"},{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Every edge into api comes from a vertex the second pass has reached. The search from api is done. api is component 2 on its own.","ops":[{"v":"api","state":"done"},{"panel":"components","groups":[["main"],["api"]]}]},{"say":"Take middleware off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 3.","ops":[{"v":"middleware","state":"current"},{"panel":"finished","list":[{"key":"handlers","note":"15"},{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Every edge into middleware comes from a vertex the second pass has reached. The search from middleware is done. middleware is component 3 on its own.","ops":[{"v":"middleware","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"]]}]},{"say":"Take handlers off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 4.","ops":[{"v":"handlers","state":"current"},{"panel":"finished","list":[{"key":"auth","note":"14"},{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Every edge into handlers comes from a vertex the second pass has reached. The search from handlers is done. handlers is component 4 on its own.","ops":[{"v":"handlers","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"]]}]},{"say":"Take auth off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 5.","ops":[{"v":"auth","state":"current"},{"panel":"finished","list":[{"key":"session","note":"13"},{"key":"users","note":"12"},{"key":"billing","note":"11"},{"key":"invoices","note":"10"},{"key":"email","note":"9"},{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"users has an edge into auth, so follow it backwards to users, which joins component 5.","ops":[{"v":"users","state":"current"},{"e":["users","auth"],"state":"reversed"}]},{"say":"session has an edge into users, so follow it backwards to session, which joins component 5.","ops":[{"v":"session","state":"current"},{"e":["session","users"],"state":"reversed"}]},{"say":"Every edge into session comes from a vertex the second pass has reached. Back to users.","ops":[{"v":"session","state":"done"}]},{"say":"invoices has an edge into users, so follow it backwards to invoices, which joins component 5.","ops":[{"v":"invoices","state":"current"},{"e":["invoices","users"],"state":"reversed"}]},{"say":"billing has an edge into invoices, so follow it backwards to billing, which joins component 5.","ops":[{"v":"billing","state":"current"},{"e":["billing","invoices"],"state":"reversed"}]},{"say":"Every edge into billing comes from a vertex the second pass has reached. Back to invoices.","ops":[{"v":"billing","state":"done"}]},{"say":"Every edge into invoices comes from a vertex the second pass has reached. Back to users.","ops":[{"v":"invoices","state":"done"}]},{"say":"Every edge into users comes from a vertex the second pass has reached. Back to auth.","ops":[{"v":"users","state":"done"}]},{"say":"Every edge into auth comes from a vertex the second pass has reached. The search from auth is done. auth, users, session, invoices and billing form component 5.","ops":[{"v":"auth","state":"done"},{"v":"users","state":"done"},{"v":"session","state":"done"},{"v":"invoices","state":"done"},{"v":"billing","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","users","session","invoices","billing"]]}]},{"say":"Take session, users, billing and invoices off the top of the finish stack. They are already in components. Take email off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 6.","ops":[{"v":"email","state":"current"},{"panel":"finished","list":[{"key":"templates","note":"8"},{"key":"cli","note":"7"},{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"templates has an edge into email, so follow it backwards to templates, which joins component 6.","ops":[{"v":"templates","state":"current"},{"e":["templates","email"],"state":"reversed"}]},{"say":"Every edge into templates comes from a vertex the second pass has reached. Back to email.","ops":[{"v":"templates","state":"done"}]},{"say":"Every edge into email comes from a vertex the second pass has reached. The search from email is done. email and templates form component 6.","ops":[{"v":"email","state":"done"},{"v":"templates","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","users","session","invoices","billing"],["email","templates"]]}]},{"say":"Take templates off the top of the finish stack. It is already in a component. Take cli off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 7.","ops":[{"v":"cli","state":"current"},{"panel":"finished","list":[{"key":"db","note":"6"},{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Every edge into cli comes from a vertex the second pass has reached. The search from cli is done. cli is component 7 on its own.","ops":[{"v":"cli","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","users","session","invoices","billing"],["email","templates"],["cli"]]}]},{"say":"Take db off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 8.","ops":[{"v":"db","state":"current"},{"panel":"finished","list":[{"key":"cache","note":"5"},{"key":"models","note":"4"},{"key":"config","note":"3"},{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"models has an edge into db, so follow it backwards to models, which joins component 8.","ops":[{"v":"models","state":"current"},{"e":["models","db"],"state":"reversed"}]},{"say":"cache has an edge into models, so follow it backwards to cache, which joins component 8.","ops":[{"v":"cache","state":"current"},{"e":["cache","models"],"state":"reversed"}]},{"say":"Every edge into cache comes from a vertex the second pass has reached. Back to models.","ops":[{"v":"cache","state":"done"}]},{"say":"Every edge into models comes from a vertex the second pass has reached. Back to db.","ops":[{"v":"models","state":"done"}]},{"say":"Every edge into db comes from a vertex the second pass has reached. The search from db is done. db, models and cache form component 8.","ops":[{"v":"db","state":"done"},{"v":"models","state":"done"},{"v":"cache","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","users","session","invoices","billing"],["email","templates"],["cli"],["db","models","cache"]]}]},{"say":"Take cache and models off the top of the finish stack. They are already in components. Take config off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 9.","ops":[{"v":"config","state":"current"},{"panel":"finished","list":[{"key":"utils","note":"2"},{"key":"logging","note":"1"}]}]},{"say":"Every edge into config comes from a vertex the second pass has reached. The search from config is done. config is component 9 on its own.","ops":[{"v":"config","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","users","session","invoices","billing"],["email","templates"],["cli"],["db","models","cache"],["config"]]}]},{"say":"Take utils off the top of the finish stack. The second pass hasn't reached it, so search backwards from it. Every vertex this search reaches is in component 10.","ops":[{"v":"utils","state":"current"},{"panel":"finished","list":[{"key":"logging","note":"1"}]}]},{"say":"logging has an edge into utils, so follow it backwards to logging, which joins component 10.","ops":[{"v":"logging","state":"current"},{"e":["logging","utils"],"state":"reversed"}]},{"say":"Every edge into logging comes from a vertex the second pass has reached. Back to utils.","ops":[{"v":"logging","state":"done"}]},{"say":"Every edge into utils comes from a vertex the second pass has reached. The search from utils is done. utils and logging form component 10.","ops":[{"v":"utils","state":"done"},{"v":"logging","state":"done"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","users","session","invoices","billing"],["email","templates"],["cli"],["db","models","cache"],["config"],["utils","logging"]]}]},{"say":"Take logging off the top of the finish stack. It is already in a component. Done. Kosaraju found 10 strongly connected components, 6 of them with one vertex. Each component is listed before every component it has an edge into. Every vertex now shows the component it belongs to.","ops":[{"v":"main","state":"single"},{"v":"api","state":"single"},{"v":"middleware","state":"single"},{"v":"handlers","state":"single"},{"v":"auth","state":"component-5"},{"v":"users","state":"component-5"},{"v":"session","state":"component-5"},{"v":"invoices","state":"component-5"},{"v":"billing","state":"component-5"},{"v":"email","state":"component-6"},{"v":"templates","state":"component-6"},{"v":"cli","state":"single"},{"v":"db","state":"component-8"},{"v":"models","state":"component-8"},{"v":"cache","state":"component-8"},{"v":"config","state":"single"},{"v":"utils","state":"component-10"},{"v":"logging","state":"component-10"},{"panel":"finished","list":[]}]}],"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":"for _, component := range connectivity.Kosaraju(g) {\n\tvar names []string\n\tfor _, v := range component {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(strings.Join(names, \", \"))\n}"}
