{"algorithm":"condensation","about":["A strongly connected component is a group of vertices that can all reach each other. The condensation replaces each one with a single vertex, and all the edges from one component to another with a single edge. A cycle never leaves its component, so the condensed graph has none.","connectivity.Condense runs Tarjan once and numbers the components so that every edge between two of them goes from a lower number to a higher one, which is a topological order. The members of each component keep the graph's vertex order, and Members and ComponentOf map between the two graphs. It costs O(V+E).","WithComponentWeight gives each component a weight from its members, such as the sum of their weights, and WithCrossingWeight gives each condensed edge a weight from the edges it stands for. A build tool does this with packages that import each other: each loop is built as one unit, and the units are sorted like any other dependency graph."],"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 packages have to be built together because they import each other, and in what order can the groups be built, each after the groups it imports?","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 18 vertices condense into 10 components joined by 14 edges, with no cycle left. The largest component has 5 vertices: auth, billing, invoices, session and users. The components are listed in topological order: every edge between two of them goes from an earlier one to a later one, so in reverse, each component comes after every component it has an edge into.","legend":{"vertex":[{"id":"idle","label":"Not in a component yet","color":"#64748B","shape":"hollow"},{"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":"inside","label":"Inside a component, dropped","color":"#475569","shape":"dashed"},{"id":"between","label":"Stands for the edges between two components","color":"#009E73","shape":"thick"},{"id":"merged","label":"Merged into the edge between the same components","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"components","title":"Components, in order","kind":"groups"},{"id":"edges","title":"Edges between components","kind":"list"}]},"steps":[{"say":"Condense runs Tarjan once to find the strongly connected components, the groups of vertices that can all reach each other. It numbers them so that every edge between two components goes from a lower number to a higher one. Then each component becomes one vertex, and the edges from one component to another become one edge."},{"say":"Components 1 to 4: main, api, middleware and handlers each reach no vertex that reaches them back, so each is a component on its own.","ops":[{"v":"main","state":"single"},{"v":"api","state":"single"},{"v":"middleware","state":"single"},{"v":"handlers","state":"single"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"]]}]},{"say":"Component 5: auth, session, users, billing and invoices can all reach each other, so they become one vertex. The 6 edges among them drop out.","ops":[{"e":["auth","session"],"state":"inside"},{"e":["session","users"],"state":"inside"},{"e":["users","auth"],"state":"inside"},{"e":["users","billing"],"state":"inside"},{"e":["billing","invoices"],"state":"inside"},{"e":["invoices","users"],"state":"inside"},{"v":"auth","state":"component-5"},{"v":"session","state":"component-5"},{"v":"users","state":"component-5"},{"v":"billing","state":"component-5"},{"v":"invoices","state":"component-5"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","session","users","billing","invoices"]]}]},{"say":"Component 6: email and templates reach each other, so they become one vertex. The 2 edges among them drop out.","ops":[{"e":["email","templates"],"state":"inside"},{"e":["templates","email"],"state":"inside"},{"v":"email","state":"component-6"},{"v":"templates","state":"component-6"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","session","users","billing","invoices"],["email","templates"]]}]},{"say":"Component 7: cli reaches no vertex that reaches it back, so it is a component on its own.","ops":[{"v":"cli","state":"single"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","session","users","billing","invoices"],["email","templates"],["cli"]]}]},{"say":"Component 8: models, db and cache can all reach each other, so they become one vertex. The 3 edges among them drop out.","ops":[{"e":["models","db"],"state":"inside"},{"e":["db","cache"],"state":"inside"},{"e":["cache","models"],"state":"inside"},{"v":"models","state":"component-8"},{"v":"db","state":"component-8"},{"v":"cache","state":"component-8"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","session","users","billing","invoices"],["email","templates"],["cli"],["models","db","cache"]]}]},{"say":"Component 9: config reaches no vertex that reaches it back, so it is a component on its own.","ops":[{"v":"config","state":"single"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","session","users","billing","invoices"],["email","templates"],["cli"],["models","db","cache"],["config"]]}]},{"say":"Component 10: utils and logging reach each other, so they become one vertex. The 2 edges among them drop out.","ops":[{"e":["utils","logging"],"state":"inside"},{"e":["logging","utils"],"state":"inside"},{"v":"utils","state":"component-10"},{"v":"logging","state":"component-10"},{"panel":"components","groups":[["main"],["api"],["middleware"],["handlers"],["auth","session","users","billing","invoices"],["email","templates"],["cli"],["models","db","cache"],["config"],["utils","logging"]]}]},{"say":"Out of component 1: main to api becomes the edge 1 to 2. main to cli becomes the edge 1 to 7. main to config becomes the edge 1 to 9.","ops":[{"e":["main","api"],"state":"between"},{"e":["main","cli"],"state":"between"},{"e":["main","config"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"}]}]},{"say":"Out of component 2: api to middleware becomes the edge 2 to 3. api to handlers becomes the edge 2 to 4. api to config becomes the edge 2 to 9.","ops":[{"e":["api","middleware"],"state":"between"},{"e":["api","handlers"],"state":"between"},{"e":["api","config"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"},{"key":"2 to 3","note":"1 edge"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 9","note":"1 edge"}]}]},{"say":"Out of component 3: middleware to auth becomes the edge 3 to 5. middleware to logging becomes the edge 3 to 10.","ops":[{"e":["middleware","auth"],"state":"between"},{"e":["middleware","logging"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"},{"key":"2 to 3","note":"1 edge"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 9","note":"1 edge"},{"key":"3 to 5","note":"1 edge"},{"key":"3 to 10","note":"1 edge"}]}]},{"say":"Out of component 4: The 3 edges handlers to auth, handlers to billing and handlers to users become one edge, 4 to 5.","ops":[{"e":["handlers","auth"],"state":"between"},{"e":["handlers","users"],"state":"merged"},{"e":["handlers","billing"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"},{"key":"2 to 3","note":"1 edge"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 9","note":"1 edge"},{"key":"3 to 5","note":"1 edge"},{"key":"3 to 10","note":"1 edge"},{"key":"4 to 5","note":"3 edges"}]}]},{"say":"Out of component 5: invoices to email becomes the edge 5 to 6. The 2 edges invoices to models and users to models become one edge, 5 to 8.","ops":[{"e":["invoices","email"],"state":"between"},{"e":["users","models"],"state":"between"},{"e":["invoices","models"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"},{"key":"2 to 3","note":"1 edge"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 9","note":"1 edge"},{"key":"3 to 5","note":"1 edge"},{"key":"3 to 10","note":"1 edge"},{"key":"4 to 5","note":"3 edges"},{"key":"5 to 6","note":"1 edge"},{"key":"5 to 8","note":"2 edges"}]}]},{"say":"Out of component 7: cli to db becomes the edge 7 to 8. cli to config becomes the edge 7 to 9.","ops":[{"e":["cli","db"],"state":"between"},{"e":["cli","config"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"},{"key":"2 to 3","note":"1 edge"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 9","note":"1 edge"},{"key":"3 to 5","note":"1 edge"},{"key":"3 to 10","note":"1 edge"},{"key":"4 to 5","note":"3 edges"},{"key":"5 to 6","note":"1 edge"},{"key":"5 to 8","note":"2 edges"},{"key":"7 to 8","note":"1 edge"},{"key":"7 to 9","note":"1 edge"}]}]},{"say":"Out of component 9: The only edge, config to utils, becomes the edge 9 to 10.","ops":[{"e":["config","utils"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 2","note":"1 edge"},{"key":"1 to 7","note":"1 edge"},{"key":"1 to 9","note":"1 edge"},{"key":"2 to 3","note":"1 edge"},{"key":"2 to 4","note":"1 edge"},{"key":"2 to 9","note":"1 edge"},{"key":"3 to 5","note":"1 edge"},{"key":"3 to 10","note":"1 edge"},{"key":"4 to 5","note":"3 edges"},{"key":"5 to 6","note":"1 edge"},{"key":"5 to 8","note":"2 edges"},{"key":"7 to 8","note":"1 edge"},{"key":"7 to 9","note":"1 edge"},{"key":"9 to 10","note":"1 edge"}]}]},{"say":"Done. The 18 vertices condense into 10 components and 14 edges between them. The condensed graph has no cycle, and its vertices are listed in topological order."}],"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":"sum := func(members []*gograph.Vertex[string]) float64 {\n\tvar total float64\n\tfor _, v := range members {\n\t\ttotal += v.Weight()\n\t}\n\treturn total\n}\nc, err := connectivity.Condense(g, connectivity.WithComponentWeight(sum))\nif err != nil {\n\treturn err\n}\nfor i, members := range c.Members {\n\tvar names []string\n\tfor _, v := range members {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(i, strings.Join(names, \", \"), c.Graph.GetVertexByID(i).Weight())\n}\nfor _, e := range c.Graph.AllEdges() {\n\tfmt.Println(e.Source().Label(), \"->\", e.Destination().Label())\n}"}