{"algorithm":"gabow","about":["Gabow's algorithm finds the strongly connected components in one depth-first search, as Tarjan's does, but without lowlink values. It keeps two stacks. The first holds the vertices the search has reached that aren't in a component yet. The second holds the vertices on the current path that could still be the first vertex of a component.","When an edge leads to a vertex still on the first stack, every vertex on the path after it is in the same component, so the second stack is popped back to it. When the search finishes a vertex that is still on top of the second stack, that vertex starts a component. The first stack is popped down to it, and those vertices form the component.","It costs O(V+E). On the same graph, Tarjan's and Gabow's algorithms find the same components in the same order. They differ only in how they tell that the search has finished one."],"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 S","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 S","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"s","title":"S, reached and not placed, top first","kind":"list"},{"id":"p","title":"P, possible roots, top first","kind":"list"},{"id":"components","title":"Components found","kind":"groups"}]},"steps":[{"say":"Gabow's path-based algorithm searches depth-first from each vertex no earlier search has reached, in the graph's vertex order, and numbers the vertices in the order it reaches them. Stack S holds every vertex reached but not yet placed in a component. Stack P holds the vertices on the search path that can still be the root of a component. An edge to a vertex still on S closes a cycle, so P loses every vertex numbered above that vertex. When a vertex finishes on top of P, it is the root of a component: it and the vertices above it on S form one strongly connected component."},{"say":"Start at Gateway, the first vertex. Gateway gets number 0 and goes on S and P.","ops":[{"v":"Gateway","state":"current"},{"panel":"s","list":[{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Gateway","note":"0"}]}]},{"say":"Follow Gateway to Auth. Auth gets number 1 and goes on S and P.","ops":[{"e":["Gateway","Auth"],"state":"tree"},{"v":"Auth","state":"current"},{"panel":"s","list":[{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]}]},{"say":"Follow Auth to Users. Users gets number 2 and goes on S and P.","ops":[{"e":["Auth","Users"],"state":"tree"},{"v":"Users","state":"current"},{"panel":"s","list":[{"key":"Users","note":"2"},{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Users","note":"2"},{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]}]},{"say":"Users has an edge to Auth, which is still on S with number 1. That closes a cycle through Auth, so every vertex on P numbered above 1 is in the same component as Auth and can't be its root. Pop Users off P.","ops":[{"panel":"p","list":[{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]},{"e":["Users","Auth"],"state":"examined"}]},{"say":"Follow Users to Notify. Notify gets number 3 and goes on S and P.","ops":[{"e":["Users","Notify"],"state":"tree"},{"v":"Notify","state":"current"},{"panel":"s","list":[{"key":"Notify","note":"3"},{"key":"Users","note":"2"},{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Notify","note":"3"},{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]}]},{"say":"Notify has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P and S. Notify is component 1 on its own. Back to Users.","ops":[{"panel":"s","list":[{"key":"Users","note":"2"},{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Auth","note":"1"},{"key":"Gateway","note":"0"}]},{"v":"Notify","state":"done"},{"panel":"components","groups":[["Notify"]]}]},{"say":"Users has no edges left to check. The top of P is Auth, so Users is not a root and stays on S. Back to Auth.","ops":[{"v":"Users","state":"waiting"}]},{"say":"Auth has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to Auth. Users and Auth form component 2. Back to Gateway.","ops":[{"panel":"s","list":[{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Gateway","note":"0"}]},{"v":"Users","state":"done"},{"v":"Auth","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"]]}]},{"say":"Follow Gateway to Orders. Orders gets number 4 and goes on S and P.","ops":[{"e":["Gateway","Orders"],"state":"tree"},{"v":"Orders","state":"current"},{"panel":"s","list":[{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]}]},{"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 number 5 and goes on S and P.","ops":[{"e":["Orders","Inventory"],"state":"tree"},{"v":"Inventory","state":"current"},{"panel":"s","list":[{"key":"Inventory","note":"5"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Inventory","note":"5"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]}]},{"say":"Follow Inventory to Search. Search gets number 6 and goes on S and P.","ops":[{"e":["Inventory","Search"],"state":"tree"},{"v":"Search","state":"current"},{"panel":"s","list":[{"key":"Search","note":"6"},{"key":"Inventory","note":"5"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Search","note":"6"},{"key":"Inventory","note":"5"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]}]},{"say":"Search has an edge to Inventory, which is still on S with number 5. That closes a cycle through Inventory, so every vertex on P numbered above 5 is in the same component as Inventory and can't be its root. Pop Search off P.","ops":[{"panel":"p","list":[{"key":"Inventory","note":"5"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"e":["Search","Inventory"],"state":"examined"}]},{"say":"Search has no edges left to check. The top of P is Inventory, so Search is not a root and stays on S. Back to Inventory.","ops":[{"v":"Search","state":"waiting"}]},{"say":"Inventory has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to Inventory. Search and Inventory form component 3. Back to Orders.","ops":[{"panel":"s","list":[{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"v":"Search","state":"done"},{"v":"Inventory","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"],["Search","Inventory"]]}]},{"say":"Follow Orders to Payments. Payments gets number 7 and goes on S and P.","ops":[{"e":["Orders","Payments"],"state":"tree"},{"v":"Payments","state":"current"},{"panel":"s","list":[{"key":"Payments","note":"7"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Payments","note":"7"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]}]},{"say":"Follow Payments to Shipping. Shipping gets number 8 and goes on S and P.","ops":[{"e":["Payments","Shipping"],"state":"tree"},{"v":"Shipping","state":"current"},{"panel":"s","list":[{"key":"Shipping","note":"8"},{"key":"Payments","note":"7"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Shipping","note":"8"},{"key":"Payments","note":"7"},{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]}]},{"say":"Shipping has an edge to Orders, which is still on S with number 4. That closes a cycle through Orders, so every vertex on P numbered above 4 is in the same component as Orders and can't be its root. Pop Shipping and Payments off P.","ops":[{"panel":"p","list":[{"key":"Orders","note":"4"},{"key":"Gateway","note":"0"}]},{"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. The top of P is Orders, so Shipping is not a root and stays on S. Back to Payments.","ops":[{"v":"Shipping","state":"waiting"}]},{"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. The top of P is Orders, so Payments is not a root and stays on S. Back to Orders.","ops":[{"v":"Payments","state":"waiting"}]},{"say":"Orders has no edges left to check. It is on top of P, so it is the root of a component. Pop it off P, and pop S down to Orders. Shipping, Payments and Orders form component 4. Back to Gateway.","ops":[{"panel":"s","list":[{"key":"Gateway","note":"0"}]},{"panel":"p","list":[{"key":"Gateway","note":"0"}]},{"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. It is on top of P, so it is the root of a component. Pop it off P and S. Gateway is component 5 on its own.","ops":[{"panel":"s","list":[]},{"panel":"p","list":[]},{"v":"Gateway","state":"done"},{"panel":"components","groups":[["Notify"],["Users","Auth"],["Search","Inventory"],["Shipping","Payments","Orders"],["Gateway"]]}]},{"say":"Done. Gabow 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.Gabow(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}"}
