{"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":"service-calls","name":"Microservice calls","description":"Nine services of an online shop. Each edge is a call from one service to another, and some services call each other back.","family":"cyclic","directed":true,"weighted":false,"acyclic":false,"vertices":[{"id":"Gateway","x":96,"y":384},{"id":"Auth","x":320,"y":128},{"id":"Users","x":608,"y":128},{"id":"Orders","x":384,"y":384},{"id":"Payments","x":640,"y":320},{"id":"Shipping","x":640,"y":544},{"id":"Inventory","x":448,"y":640},{"id":"Search","x":192,"y":640},{"id":"Notify","x":896,"y":320}],"edges":[{"from":"Gateway","to":"Auth"},{"from":"Gateway","to":"Orders"},{"from":"Gateway","to":"Search"},{"from":"Auth","to":"Users"},{"from":"Users","to":"Auth"},{"from":"Users","to":"Notify"},{"from":"Orders","to":"Users"},{"from":"Orders","to":"Inventory"},{"from":"Orders","to":"Payments"},{"from":"Payments","to":"Shipping"},{"from":"Payments","to":"Notify"},{"from":"Shipping","to":"Orders"},{"from":"Shipping","to":"Notify"},{"from":"Inventory","to":"Search"},{"from":"Search","to":"Inventory"}],"details":{"vertices":9,"edges":15,"directed":true,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.20833333333333334,"inDegree":{"min":0,"avg":1.6666666666666667,"max":3},"outDegree":{"min":0,"avg":1.6666666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Which groups of services call each other in a loop, so that each service in a group depends on all the others?","params":{},"result":{"kind":"groups","groups":[["Gateway"],["Orders","Payments","Shipping"],["Inventory","Search"],["Auth","Users"],["Notify"]]},"answer":"The graph has 5 strongly connected components. The ones with more than one vertex are Orders, Payments and Shipping; Inventory and Search; Auth and Users. The other 2 components have one vertex each: Gateway and Notify.","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-2","label":"Component 2, 3 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-3","label":"Component 3, 2 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-4","label":"Component 4, 2 vertices","color":"#E69F00","shape":"filled"},{"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 Gateway, the first vertex.","ops":[{"v":"Gateway","state":"current"}]},{"say":"Follow Gateway to Auth.","ops":[{"v":"Auth","state":"current"},{"e":["Gateway","Auth"],"state":"tree"}]},{"say":"Follow Auth to Users.","ops":[{"v":"Users","state":"current"},{"e":["Auth","Users"],"state":"tree"}]},{"say":"Follow Users to Notify.","ops":[{"v":"Notify","state":"current"},{"e":["Users","Notify"],"state":"tree"}]},{"say":"Notify has no unreached neighbors left, so it finishes, number 1. Push it on the finish stack. Back to Users.","ops":[{"v":"Notify","state":"waiting"},{"panel":"finished","list":[{"key":"Notify","note":"1"}]}]},{"say":"Users has no unreached neighbors left, so it finishes, number 2. Push it on the finish stack. Back to Auth.","ops":[{"v":"Users","state":"waiting"},{"panel":"finished","list":[{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Auth has no unreached neighbors left, so it finishes, number 3. Push it on the finish stack. Back to Gateway.","ops":[{"v":"Auth","state":"waiting"},{"panel":"finished","list":[{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Follow Gateway to Orders.","ops":[{"v":"Orders","state":"current"},{"e":["Gateway","Orders"],"state":"tree"}]},{"say":"Follow Orders to Inventory.","ops":[{"v":"Inventory","state":"current"},{"e":["Orders","Inventory"],"state":"tree"}]},{"say":"Follow Inventory to Search.","ops":[{"v":"Search","state":"current"},{"e":["Inventory","Search"],"state":"tree"}]},{"say":"Search has no unreached neighbors left, so it finishes, number 4. Push it on the finish stack. Back to Inventory.","ops":[{"v":"Search","state":"waiting"},{"panel":"finished","list":[{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Inventory has no unreached neighbors left, so it finishes, number 5. Push it on the finish stack. Back to Orders.","ops":[{"v":"Inventory","state":"waiting"},{"panel":"finished","list":[{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Follow Orders to Payments.","ops":[{"v":"Payments","state":"current"},{"e":["Orders","Payments"],"state":"tree"}]},{"say":"Follow Payments to Shipping.","ops":[{"v":"Shipping","state":"current"},{"e":["Payments","Shipping"],"state":"tree"}]},{"say":"Shipping has no unreached neighbors left, so it finishes, number 6. Push it on the finish stack. Back to Payments.","ops":[{"v":"Shipping","state":"waiting"},{"panel":"finished","list":[{"key":"Shipping","note":"6"},{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Payments has no unreached neighbors left, so it finishes, number 7. Push it on the finish stack. Back to Orders.","ops":[{"v":"Payments","state":"waiting"},{"panel":"finished","list":[{"key":"Payments","note":"7"},{"key":"Shipping","note":"6"},{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Orders has no unreached neighbors left, so it finishes, number 8. Push it on the finish stack. Back to Gateway.","ops":[{"v":"Orders","state":"waiting"},{"panel":"finished","list":[{"key":"Orders","note":"8"},{"key":"Payments","note":"7"},{"key":"Shipping","note":"6"},{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Gateway has no unreached neighbors left, so it finishes, number 9. Push it on the finish stack.","ops":[{"v":"Gateway","state":"waiting"},{"panel":"finished","list":[{"key":"Gateway","note":"9"},{"key":"Orders","note":"8"},{"key":"Payments","note":"7"},{"key":"Shipping","note":"6"},{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"The first pass is done. Gateway 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 Gateway 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":["Gateway","Auth"],"state":"idle"},{"e":["Auth","Users"],"state":"idle"},{"e":["Users","Notify"],"state":"idle"},{"e":["Gateway","Orders"],"state":"idle"},{"e":["Orders","Inventory"],"state":"idle"},{"e":["Inventory","Search"],"state":"idle"},{"e":["Orders","Payments"],"state":"idle"},{"e":["Payments","Shipping"],"state":"idle"}]},{"say":"Take Gateway 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":"Gateway","state":"current"},{"panel":"finished","list":[{"key":"Orders","note":"8"},{"key":"Payments","note":"7"},{"key":"Shipping","note":"6"},{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"No edge comes into Gateway. The search from Gateway is done. Gateway is component 1 on its own.","ops":[{"v":"Gateway","state":"done"},{"panel":"components","groups":[["Gateway"]]}]},{"say":"Take Orders 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":"Orders","state":"current"},{"panel":"finished","list":[{"key":"Payments","note":"7"},{"key":"Shipping","note":"6"},{"key":"Inventory","note":"5"},{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Shipping has an edge into Orders, so follow it backwards to Shipping, which joins component 2.","ops":[{"v":"Shipping","state":"current"},{"e":["Shipping","Orders"],"state":"reversed"}]},{"say":"Payments has an edge into Shipping, so follow it backwards to Payments, which joins component 2.","ops":[{"v":"Payments","state":"current"},{"e":["Payments","Shipping"],"state":"reversed"}]},{"say":"Every edge into Payments comes from a vertex the second pass has reached. Back to Shipping.","ops":[{"v":"Payments","state":"done"}]},{"say":"Every edge into Shipping comes from a vertex the second pass has reached. Back to Orders.","ops":[{"v":"Shipping","state":"done"}]},{"say":"Every edge into Orders comes from a vertex the second pass has reached. The search from Orders is done. Orders, Shipping and Payments form component 2.","ops":[{"v":"Orders","state":"done"},{"v":"Shipping","state":"done"},{"v":"Payments","state":"done"},{"panel":"components","groups":[["Gateway"],["Orders","Shipping","Payments"]]}]},{"say":"Take Payments and Shipping off the top of the finish stack. They are already in components. Take Inventory 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":"Inventory","state":"current"},{"panel":"finished","list":[{"key":"Search","note":"4"},{"key":"Auth","note":"3"},{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Search has an edge into Inventory, so follow it backwards to Search, which joins component 3.","ops":[{"v":"Search","state":"current"},{"e":["Search","Inventory"],"state":"reversed"}]},{"say":"Every edge into Search comes from a vertex the second pass has reached. Back to Inventory.","ops":[{"v":"Search","state":"done"}]},{"say":"Every edge into Inventory comes from a vertex the second pass has reached. The search from Inventory is done. Inventory and Search form component 3.","ops":[{"v":"Inventory","state":"done"},{"v":"Search","state":"done"},{"panel":"components","groups":[["Gateway"],["Orders","Shipping","Payments"],["Inventory","Search"]]}]},{"say":"Take Search off the top of the finish stack. It is already in a component. 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 4.","ops":[{"v":"Auth","state":"current"},{"panel":"finished","list":[{"key":"Users","note":"2"},{"key":"Notify","note":"1"}]}]},{"say":"Users has an edge into Auth, so follow it backwards to Users, which joins component 4.","ops":[{"v":"Users","state":"current"},{"e":["Users","Auth"],"state":"reversed"}]},{"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 and Users form component 4.","ops":[{"v":"Auth","state":"done"},{"v":"Users","state":"done"},{"panel":"components","groups":[["Gateway"],["Orders","Shipping","Payments"],["Inventory","Search"],["Auth","Users"]]}]},{"say":"Take Users off the top of the finish stack. It is already in a component. Take Notify 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":"Notify","state":"current"},{"panel":"finished","list":[]}]},{"say":"Every edge into Notify comes from a vertex the second pass has reached. The search from Notify is done. Notify is component 5 on its own.","ops":[{"v":"Notify","state":"done"},{"panel":"components","groups":[["Gateway"],["Orders","Shipping","Payments"],["Inventory","Search"],["Auth","Users"],["Notify"]]}]},{"say":"Done. Kosaraju found 5 strongly connected components, 2 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":"Gateway","state":"single"},{"v":"Orders","state":"component-2"},{"v":"Shipping","state":"component-2"},{"v":"Payments","state":"component-2"},{"v":"Inventory","state":"component-3"},{"v":"Search","state":"component-3"},{"v":"Auth","state":"component-4"},{"v":"Users","state":"component-4"},{"v":"Notify","state":"single"}]}],"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}"}
