{"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":"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":[["logging","utils"],["config"],["cache","db","models"],["cli"],["email","templates"],["auth","billing","invoices","session","users"],["handlers"],["middleware"],["api"],["main"]]},"answer":"The graph has 10 strongly connected components. The ones with more than one vertex are logging and utils; cache, db and models; email and templates; auth, billing, invoices, session and users. The other 6 components have one vertex each: config, cli, handlers, middleware, api and main.","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-1","label":"Component 1, 2 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-3","label":"Component 3, 3 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-5","label":"Component 5, 2 vertices","color":"#E69F00","shape":"filled"},{"id":"component-6","label":"Component 6, 5 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","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 main, the first vertex. main gets index 0 and lowlink 0 and goes on the stack.","ops":[{"v":"main","state":"current"},{"panel":"stack","list":[{"key":"main"}]},{"panel":"index","set":{"main":"0 / 0"}}]},{"say":"Follow main to cli. cli gets index 1 and lowlink 1 and goes on the stack.","ops":[{"e":["main","cli"],"state":"tree"},{"v":"cli","state":"current"},{"panel":"stack","list":[{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"cli":"1 / 1"}}]},{"say":"Follow cli to config. config gets index 2 and lowlink 2 and goes on the stack.","ops":[{"e":["cli","config"],"state":"tree"},{"v":"config","state":"current"},{"panel":"stack","list":[{"key":"config"},{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"config":"2 / 2"}}]},{"say":"Follow config to utils. utils gets index 3 and lowlink 3 and goes on the stack.","ops":[{"e":["config","utils"],"state":"tree"},{"v":"utils","state":"current"},{"panel":"stack","list":[{"key":"utils"},{"key":"config"},{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"utils":"3 / 3"}}]},{"say":"Follow utils to logging. logging gets index 4 and lowlink 4 and goes on the stack.","ops":[{"e":["utils","logging"],"state":"tree"},{"v":"logging","state":"current"},{"panel":"stack","list":[{"key":"logging"},{"key":"utils"},{"key":"config"},{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"logging":"4 / 4"}}]},{"say":"logging has an edge to utils, which is still on the stack with index 3. The lowlink of logging drops from 4 to 3.","ops":[{"panel":"index","set":{"logging":"4 / 3"}},{"e":["logging","utils"],"state":"examined"}]},{"say":"logging has no edges left to check. Its lowlink, 3, is lower than its index, 4, so it stays on the stack until the root of its component finishes. Back to utils, whose lowlink stays 3.","ops":[{"v":"logging","state":"waiting"}]},{"say":"utils has no edges left to check. Its lowlink equals its index, 3, so it is the root of a component. Pop the stack down to utils. logging and utils form component 1. Back to config.","ops":[{"panel":"stack","list":[{"key":"config"},{"key":"cli"},{"key":"main"}]},{"v":"logging","state":"done"},{"v":"utils","state":"done"},{"panel":"components","groups":[["logging","utils"]]}]},{"say":"config has no edges left to check. Its lowlink equals its index, 2, so it is the root of a component. Pop it off the stack. config is component 2 on its own. Back to cli.","ops":[{"panel":"stack","list":[{"key":"cli"},{"key":"main"}]},{"v":"config","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"]]}]},{"say":"Follow cli to db. db gets index 5 and lowlink 5 and goes on the stack.","ops":[{"e":["cli","db"],"state":"tree"},{"v":"db","state":"current"},{"panel":"stack","list":[{"key":"db"},{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"db":"5 / 5"}}]},{"say":"Follow db to cache. cache gets index 6 and lowlink 6 and goes on the stack.","ops":[{"e":["db","cache"],"state":"tree"},{"v":"cache","state":"current"},{"panel":"stack","list":[{"key":"cache"},{"key":"db"},{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"cache":"6 / 6"}}]},{"say":"Follow cache to models. models gets index 7 and lowlink 7 and goes on the stack.","ops":[{"e":["cache","models"],"state":"tree"},{"v":"models","state":"current"},{"panel":"stack","list":[{"key":"models"},{"key":"cache"},{"key":"db"},{"key":"cli"},{"key":"main"}]},{"panel":"index","set":{"models":"7 / 7"}}]},{"say":"models has an edge to db, which is still on the stack with index 5. The lowlink of models drops from 7 to 5.","ops":[{"panel":"index","set":{"models":"7 / 5"}},{"e":["models","db"],"state":"examined"}]},{"say":"models has no edges left to check. Its lowlink, 5, is lower than its index, 7, so it stays on the stack until the root of its component finishes. Back to cache, whose lowlink drops from 6 to 5.","ops":[{"v":"models","state":"waiting"},{"panel":"index","set":{"cache":"6 / 5"}}]},{"say":"cache 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 db, whose lowlink stays 5.","ops":[{"v":"cache","state":"waiting"}]},{"say":"db 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 db. models, cache and db form component 3. Back to cli.","ops":[{"panel":"stack","list":[{"key":"cli"},{"key":"main"}]},{"v":"models","state":"done"},{"v":"cache","state":"done"},{"v":"db","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"]]}]},{"say":"cli has no edges left to check. Its lowlink equals its index, 1, so it is the root of a component. Pop it off the stack. cli is component 4 on its own. Back to main.","ops":[{"panel":"stack","list":[{"key":"main"}]},{"v":"cli","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"]]}]},{"say":"Follow main to api. api gets index 8 and lowlink 8 and goes on the stack.","ops":[{"e":["main","api"],"state":"tree"},{"v":"api","state":"current"},{"panel":"stack","list":[{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"api":"8 / 8"}}]},{"say":"Follow api to handlers. handlers gets index 9 and lowlink 9 and goes on the stack.","ops":[{"e":["api","handlers"],"state":"tree"},{"v":"handlers","state":"current"},{"panel":"stack","list":[{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"handlers":"9 / 9"}}]},{"say":"Follow handlers to auth. auth gets index 10 and lowlink 10 and goes on the stack.","ops":[{"e":["handlers","auth"],"state":"tree"},{"v":"auth","state":"current"},{"panel":"stack","list":[{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"auth":"10 / 10"}}]},{"say":"Follow auth to session. session gets index 11 and lowlink 11 and goes on the stack.","ops":[{"e":["auth","session"],"state":"tree"},{"v":"session","state":"current"},{"panel":"stack","list":[{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"session":"11 / 11"}}]},{"say":"Follow session to users. users gets index 12 and lowlink 12 and goes on the stack.","ops":[{"e":["session","users"],"state":"tree"},{"v":"users","state":"current"},{"panel":"stack","list":[{"key":"users"},{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"users":"12 / 12"}}]},{"say":"users has an edge to auth, which is still on the stack with index 10. The lowlink of users drops from 12 to 10.","ops":[{"panel":"index","set":{"users":"12 / 10"}},{"e":["users","auth"],"state":"examined"}]},{"say":"Follow users to billing. billing gets index 13 and lowlink 13 and goes on the stack.","ops":[{"e":["users","billing"],"state":"tree"},{"v":"billing","state":"current"},{"panel":"stack","list":[{"key":"billing"},{"key":"users"},{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"billing":"13 / 13"}}]},{"say":"Follow billing to invoices. invoices gets index 14 and lowlink 14 and goes on the stack.","ops":[{"e":["billing","invoices"],"state":"tree"},{"v":"invoices","state":"current"},{"panel":"stack","list":[{"key":"invoices"},{"key":"billing"},{"key":"users"},{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"invoices":"14 / 14"}}]},{"say":"invoices has an edge to users, which is still on the stack with index 12. The lowlink of invoices drops from 14 to 12.","ops":[{"panel":"index","set":{"invoices":"14 / 12"}},{"e":["invoices","users"],"state":"examined"}]},{"say":"The edge from invoices to models leads to a vertex already in a component, so it is skipped. Follow invoices to email. email gets index 15 and lowlink 15 and goes on the stack.","ops":[{"e":["invoices","email"],"state":"tree"},{"v":"email","state":"current"},{"panel":"stack","list":[{"key":"email"},{"key":"invoices"},{"key":"billing"},{"key":"users"},{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"email":"15 / 15"}}]},{"say":"Follow email to templates. templates gets index 16 and lowlink 16 and goes on the stack.","ops":[{"e":["email","templates"],"state":"tree"},{"v":"templates","state":"current"},{"panel":"stack","list":[{"key":"templates"},{"key":"email"},{"key":"invoices"},{"key":"billing"},{"key":"users"},{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"templates":"16 / 16"}}]},{"say":"templates has an edge to email, which is still on the stack with index 15. The lowlink of templates drops from 16 to 15.","ops":[{"panel":"index","set":{"templates":"16 / 15"}},{"e":["templates","email"],"state":"examined"}]},{"say":"templates has no edges left to check. Its lowlink, 15, is lower than its index, 16, so it stays on the stack until the root of its component finishes. Back to email, whose lowlink stays 15.","ops":[{"v":"templates","state":"waiting"}]},{"say":"email has no edges left to check. Its lowlink equals its index, 15, so it is the root of a component. Pop the stack down to email. templates and email form component 5. Back to invoices.","ops":[{"panel":"stack","list":[{"key":"invoices"},{"key":"billing"},{"key":"users"},{"key":"session"},{"key":"auth"},{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"v":"templates","state":"done"},{"v":"email","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"],["templates","email"]]}]},{"say":"invoices has no edges left to check. Its lowlink, 12, is lower than its index, 14, so it stays on the stack until the root of its component finishes. Back to billing, whose lowlink drops from 13 to 12.","ops":[{"v":"invoices","state":"waiting"},{"panel":"index","set":{"billing":"13 / 12"}}]},{"say":"billing has no edges left to check. Its lowlink, 12, is lower than its index, 13, so it stays on the stack until the root of its component finishes. Back to users, whose lowlink stays 10.","ops":[{"v":"billing","state":"waiting"}]},{"say":"The edge from users to models leads to a vertex already in a component, so it is skipped. users has no edges left to check. Its lowlink, 10, is lower than its index, 12, so it stays on the stack until the root of its component finishes. Back to session, whose lowlink drops from 11 to 10.","ops":[{"v":"users","state":"waiting"},{"panel":"index","set":{"session":"11 / 10"}}]},{"say":"session has no edges left to check. Its lowlink, 10, is lower than its index, 11, so it stays on the stack until the root of its component finishes. Back to auth, whose lowlink stays 10.","ops":[{"v":"session","state":"waiting"}]},{"say":"auth has no edges left to check. Its lowlink equals its index, 10, so it is the root of a component. Pop the stack down to auth. invoices, billing, users, session and auth form component 6. Back to handlers.","ops":[{"panel":"stack","list":[{"key":"handlers"},{"key":"api"},{"key":"main"}]},{"v":"invoices","state":"done"},{"v":"billing","state":"done"},{"v":"users","state":"done"},{"v":"session","state":"done"},{"v":"auth","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"],["templates","email"],["invoices","billing","users","session","auth"]]}]},{"say":"The edges from handlers to users and billing lead to vertices already in components, so they are skipped. handlers has no edges left to check. Its lowlink equals its index, 9, so it is the root of a component. Pop it off the stack. handlers is component 7 on its own. Back to api.","ops":[{"panel":"stack","list":[{"key":"api"},{"key":"main"}]},{"v":"handlers","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"],["templates","email"],["invoices","billing","users","session","auth"],["handlers"]]}]},{"say":"Follow api to middleware. middleware gets index 17 and lowlink 17 and goes on the stack.","ops":[{"e":["api","middleware"],"state":"tree"},{"v":"middleware","state":"current"},{"panel":"stack","list":[{"key":"middleware"},{"key":"api"},{"key":"main"}]},{"panel":"index","set":{"middleware":"17 / 17"}}]},{"say":"The edges from middleware to auth and logging lead to vertices already in components, so they are skipped. middleware has no edges left to check. Its lowlink equals its index, 17, so it is the root of a component. Pop it off the stack. middleware is component 8 on its own. Back to api.","ops":[{"panel":"stack","list":[{"key":"api"},{"key":"main"}]},{"v":"middleware","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"],["templates","email"],["invoices","billing","users","session","auth"],["handlers"],["middleware"]]}]},{"say":"The edge from api to config leads to a vertex already in a component, so it is skipped. api has no edges left to check. Its lowlink equals its index, 8, so it is the root of a component. Pop it off the stack. api is component 9 on its own. Back to main.","ops":[{"panel":"stack","list":[{"key":"main"}]},{"v":"api","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"],["templates","email"],["invoices","billing","users","session","auth"],["handlers"],["middleware"],["api"]]}]},{"say":"The edge from main to config leads to a vertex already in a component, so it is skipped. main 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. main is component 10 on its own.","ops":[{"panel":"stack","list":[]},{"v":"main","state":"done"},{"panel":"components","groups":[["logging","utils"],["config"],["models","cache","db"],["cli"],["templates","email"],["invoices","billing","users","session","auth"],["handlers"],["middleware"],["api"],["main"]]}]},{"say":"Done. Tarjan found 10 strongly connected components, 6 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":"logging","state":"component-1"},{"v":"utils","state":"component-1"},{"v":"config","state":"single"},{"v":"models","state":"component-3"},{"v":"cache","state":"component-3"},{"v":"db","state":"component-3"},{"v":"cli","state":"single"},{"v":"templates","state":"component-5"},{"v":"email","state":"component-5"},{"v":"invoices","state":"component-6"},{"v":"billing","state":"component-6"},{"v":"users","state":"component-6"},{"v":"session","state":"component-6"},{"v":"auth","state":"component-6"},{"v":"handlers","state":"single"},{"v":"middleware","state":"single"},{"v":"api","state":"single"},{"v":"main","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}"}
