{"algorithm":"tarjan","about":["A strongly connected component is a group of vertices in a directed graph where each one can reach every other. Tarjan's algorithm finds them all in one depth-first search. It numbers the vertices in the order it reaches them and keeps them on a stack. Each vertex also tracks its lowlink, the smallest number it can reach through the vertices below it in the search and one more edge to a vertex still on the stack.","When the search finishes a vertex whose lowlink is still its own number, nothing it leads to can reach back to an earlier vertex on the stack. That vertex and every vertex above it on the stack form one component, and they leave the stack together. So a component comes out before any component that can reach it.","gograph keeps the search path in a slice instead of recursing, so a long chain doesn't grow the goroutine stack. It costs O(V+E). Use it to find services that call each other in a loop, modules that require each other, or the states of a machine that can all reach each other."],"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":[["Notify"],["Auth","Users"],["Inventory","Search"],["Orders","Payments","Shipping"],["Gateway"]]},"answer":"The graph has 5 strongly connected components. The ones with more than one vertex are Auth and Users; Inventory and Search; Orders, Payments and Shipping. The other 2 components have one vertex each: Notify and Gateway.","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, still on the stack","color":"#E69F00","shape":"dashed-square"},{"id":"done","label":"In a component","color":"#009E73","shape":"filled"},{"id":"component-2","label":"Component 2, 2 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-3","label":"Component 3, 2 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-4","label":"Component 4, 3 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","color":"#009E73","shape":"thick"},{"id":"examined","label":"Leads to a vertex on the stack","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"index","title":"Index / lowlink","kind":"table"},{"id":"stack","title":"Stack, top first","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"Tarjan searches depth-first from each vertex no earlier search has reached, in the graph's vertex order. It gives each vertex an index, the order the search reached it in, and a lowlink, the lowest index the vertex is known to reach among the vertices still on the stack. Every vertex goes on the stack when the search reaches it. When a vertex finishes with a lowlink equal to its own index, it is the root of a component: it and the vertices above it on the stack form one strongly connected component."},{"say":"Start at Gateway, the first vertex. Gateway gets index 0 and lowlink 0 and goes on the stack.","ops":[{"v":"Gateway","state":"current"},{"panel":"stack","list":[{"key":"Gateway"}]},{"panel":"index","set":{"Gateway":"0 / 0"}}]},{"say":"Follow Gateway to Auth. Auth gets index 1 and lowlink 1 and goes on the stack.","ops":[{"e":["Gateway","Auth"],"state":"tree"},{"v":"Auth","state":"current"},{"panel":"stack","list":[{"key":"Auth"},{"key":"Gateway"}]},{"panel":"index","set":{"Auth":"1 / 1"}}]},{"say":"Follow Auth to Users. Users gets index 2 and lowlink 2 and goes on the stack.","ops":[{"e":["Auth","Users"],"state":"tree"},{"v":"Users","state":"current"},{"panel":"stack","list":[{"key":"Users"},{"key":"Auth"},{"key":"Gateway"}]},{"panel":"index","set":{"Users":"2 / 2"}}]},{"say":"Users has an edge to Auth, which is still on the stack with index 1. The lowlink of Users drops from 2 to 1.","ops":[{"panel":"index","set":{"Users":"2 / 1"}},{"e":["Users","Auth"],"state":"examined"}]},{"say":"Follow Users to Notify. Notify gets index 3 and lowlink 3 and goes on the stack.","ops":[{"e":["Users","Notify"],"state":"tree"},{"v":"Notify","state":"current"},{"panel":"stack","list":[{"key":"Notify"},{"key":"Users"},{"key":"Auth"},{"key":"Gateway"}]},{"panel":"index","set":{"Notify":"3 / 3"}}]},{"say":"Notify has no edges left to check. Its lowlink equals its index, 3, so it is the root of a component. Pop it off the stack. Notify is component 1 on its own. Back to Users.","ops":[{"panel":"stack","list":[{"key":"Users"},{"key":"Auth"},{"key":"Gateway"}]},{"v":"Notify","state":"done"},{"panel":"components","groups":[["Notify"]]}]},{"say":"Users has no edges left to check. Its lowlink, 1, is lower than its index, 2, so it stays on the stack until the root of its component finishes. Back to Auth, whose lowlink stays 1.","ops":[{"v":"Users","state":"waiting"}]},{"say":"Auth has no edges left to check. Its lowlink equals its index, 1, so it is the root of a component. Pop the stack down to Auth. Users and Auth form component 2. Back to Gateway.","ops":[{"panel":"stack","list":[{"key":"Gateway"}]},{"v":"Users","state":"done"},{"v":"Auth","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"]]}]},{"say":"Follow Gateway to Orders. Orders gets index 4 and lowlink 4 and goes on the stack.","ops":[{"e":["Gateway","Orders"],"state":"tree"},{"v":"Orders","state":"current"},{"panel":"stack","list":[{"key":"Orders"},{"key":"Gateway"}]},{"panel":"index","set":{"Orders":"4 / 4"}}]},{"say":"The edge from Orders to Users leads to a vertex already in a component, so it is skipped. Follow Orders to Inventory. Inventory gets index 5 and lowlink 5 and goes on the stack.","ops":[{"e":["Orders","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"stack","list":[{"key":"Inventory"},{"key":"Orders"},{"key":"Gateway"}]},{"panel":"index","set":{"Inventory":"5 / 5"}}]},{"say":"Follow Inventory to Search. Search gets index 6 and lowlink 6 and goes on the stack.","ops":[{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"stack","list":[{"key":"Search"},{"key":"Inventory"},{"key":"Orders"},{"key":"Gateway"}]},{"panel":"index","set":{"Search":"6 / 6"}}]},{"say":"Search has an edge to Inventory, which is still on the stack with index 5. The lowlink of Search drops from 6 to 5.","ops":[{"panel":"index","set":{"Search":"6 / 5"}},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"Search has no edges left to check. Its lowlink, 5, is lower than its index, 6, so it stays on the stack until the root of its component finishes. Back to Inventory, whose lowlink stays 5.","ops":[{"v":"Search","state":"waiting"}]},{"say":"Inventory has no edges left to check. Its lowlink equals its index, 5, so it is the root of a component. Pop the stack down to Inventory. Search and Inventory form component 3. Back to Orders.","ops":[{"panel":"stack","list":[{"key":"Orders"},{"key":"Gateway"}]},{"v":"Search","state":"done"},{"v":"Inventory","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"],["Search","Inventory"]]}]},{"say":"Follow Orders to Payments. Payments gets index 7 and lowlink 7 and goes on the stack.","ops":[{"e":["Orders","Payments"],"state":"tree"},{"v":"Payments","state":"current"},{"panel":"stack","list":[{"key":"Payments"},{"key":"Orders"},{"key":"Gateway"}]},{"panel":"index","set":{"Payments":"7 / 7"}}]},{"say":"Follow Payments to Shipping. Shipping gets index 8 and lowlink 8 and goes on the stack.","ops":[{"e":["Payments","Shipping"],"state":"tree"},{"v":"Shipping","state":"current"},{"panel":"stack","list":[{"key":"Shipping"},{"key":"Payments"},{"key":"Orders"},{"key":"Gateway"}]},{"panel":"index","set":{"Shipping":"8 / 8"}}]},{"say":"Shipping has an edge to Orders, which is still on the stack with index 4. The lowlink of Shipping drops from 8 to 4.","ops":[{"panel":"index","set":{"Shipping":"8 / 4"}},{"e":["Shipping","Orders"],"state":"examined"}]},{"say":"The edge from Shipping to Notify leads to a vertex already in a component, so it is skipped. Shipping has no edges left to check. Its lowlink, 4, is lower than its index, 8, so it stays on the stack until the root of its component finishes. Back to Payments, whose lowlink drops from 7 to 4.","ops":[{"v":"Shipping","state":"waiting"},{"panel":"index","set":{"Payments":"7 / 4"}}]},{"say":"The edge from Payments to Notify leads to a vertex already in a component, so it is skipped. Payments has no edges left to check. Its lowlink, 4, is lower than its index, 7, so it stays on the stack until the root of its component finishes. Back to Orders, whose lowlink stays 4.","ops":[{"v":"Payments","state":"waiting"}]},{"say":"Orders has no edges left to check. Its lowlink equals its index, 4, so it is the root of a component. Pop the stack down to Orders. Shipping, Payments and Orders form component 4. Back to Gateway.","ops":[{"panel":"stack","list":[{"key":"Gateway"}]},{"v":"Shipping","state":"done"},{"v":"Payments","state":"done"},{"v":"Orders","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"],["Search","Inventory"],["Shipping","Payments","Orders"]]}]},{"say":"The edge from Gateway to Search leads to a vertex already in a component, so it is skipped. Gateway has no edges left to check. Its lowlink equals its index, 0, so it is the root of a component. Pop it off the stack. Gateway is component 5 on its own.","ops":[{"panel":"stack","list":[]},{"v":"Gateway","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"],["Search","Inventory"],["Shipping","Payments","Orders"],["Gateway"]]}]},{"say":"Done. Tarjan found 5 strongly connected components, 2 of them with one vertex. Each component is listed after every component it has an edge into. Every vertex now shows the component it belongs to.","ops":[{"v":"Notify","state":"single"},{"v":"Users","state":"component-2"},{"v":"Auth","state":"component-2"},{"v":"Search","state":"component-3"},{"v":"Inventory","state":"component-3"},{"v":"Shipping","state":"component-4"},{"v":"Payments","state":"component-4"},{"v":"Orders","state":"component-4"},{"v":"Gateway","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.Tarjan(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}"}
