{"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":"linked-pages","name":"Linked web pages","description":"Forty pages of a product website, P1 to P40, where P stands for page: the main site (P1 to P13), the blog (P14 to P19), landing pages (P20 to P24), the help center (P25 to P28), the docs (P29 to P38) and the status pages (P39 and P40). Each edge counts the links from one page to another. Only ads and emails lead to the landing pages, and the help center, docs and status pages never link back to the main site.","family":"cyclic","directed":true,"weighted":true,"acyclic":false,"vertices":[{"id":"P1","x":225,"y":687},{"id":"P2","x":134,"y":683},{"id":"P3","x":239,"y":604},{"id":"P4","x":206,"y":763},{"id":"P5","x":112,"y":601},{"id":"P6","x":312,"y":664},{"id":"P7","x":103,"y":760},{"id":"P8","x":200,"y":532},{"id":"P9","x":288,"y":782},{"id":"P10","x":40,"y":650},{"id":"P11","x":327,"y":576},{"id":"P12","x":157,"y":836},{"id":"P13","x":105,"y":516},{"id":"P14","x":324,"y":298},{"id":"P15","x":258,"y":341},{"id":"P16","x":189,"y":305},{"id":"P17","x":185,"y":228},{"id":"P18","x":250,"y":185},{"id":"P19","x":320,"y":221},{"id":"P20","x":483,"y":182},{"id":"P21","x":503,"y":107},{"id":"P22","x":580,"y":102},{"id":"P23","x":609,"y":174},{"id":"P24","x":549,"y":224},{"id":"P25","x":822,"y":255},{"id":"P26","x":840,"y":330},{"id":"P27","x":765,"y":349},{"id":"P28","x":746,"y":274},{"id":"P29","x":855,"y":670},{"id":"P30","x":777,"y":716},{"id":"P31","x":823,"y":592},{"id":"P32","x":881,"y":744},{"id":"P33","x":714,"y":658},{"id":"P34","x":916,"y":604},{"id":"P35","x":793,"y":797},{"id":"P36","x":751,"y":553},{"id":"P37","x":960,"y":715},{"id":"P38","x":680,"y":738},{"id":"P39","x":531,"y":898},{"id":"P40","x":506,"y":824}],"edges":[{"from":"P1","to":"P2","weight":2},{"from":"P1","to":"P3","weight":2},{"from":"P1","to":"P4","weight":1},{"from":"P1","to":"P6","weight":1},{"from":"P1","to":"P14","weight":1},{"from":"P1","to":"P29","weight":1},{"from":"P1","to":"P9","weight":3},{"from":"P1","to":"P10","weight":1},{"from":"P1","to":"P25","weight":1},{"from":"P1","to":"P39","weight":1},{"from":"P2","to":"P1","weight":1},{"from":"P2","to":"P3","weight":2},{"from":"P2","to":"P5","weight":1},{"from":"P2","to":"P9","weight":2},{"from":"P2","to":"P29","weight":1},{"from":"P3","to":"P1","weight":1},{"from":"P3","to":"P9","weight":3},{"from":"P3","to":"P8","weight":1},{"from":"P3","to":"P26","weight":1},{"from":"P3","to":"P11","weight":1},{"from":"P4","to":"P1","weight":1},{"from":"P4","to":"P17","weight":2},{"from":"P4","to":"P9","weight":1},{"from":"P5","to":"P2","weight":1},{"from":"P5","to":"P33","weight":2},{"from":"P6","to":"P1","weight":1},{"from":"P6","to":"P7","weight":2},{"from":"P6","to":"P8","weight":1},{"from":"P6","to":"P14","weight":1},{"from":"P7","to":"P6","weight":1},{"from":"P7","to":"P18","weight":1},{"from":"P8","to":"P1","weight":1},{"from":"P8","to":"P25","weight":1},{"from":"P9","to":"P1","weight":1},{"from":"P9","to":"P10","weight":1},{"from":"P9","to":"P13","weight":1},{"from":"P9","to":"P12","weight":1},{"from":"P10","to":"P9","weight":1},{"from":"P10","to":"P28","weight":1},{"from":"P11","to":"P1","weight":1},{"from":"P11","to":"P12","weight":1},{"from":"P11","to":"P39","weight":1},{"from":"P12","to":"P1","weight":1},{"from":"P12","to":"P13","weight":1},{"from":"P13","to":"P1","weight":1},{"from":"P13","to":"P12","weight":1},{"from":"P14","to":"P1","weight":1},{"from":"P14","to":"P15","weight":1},{"from":"P14","to":"P16","weight":1},{"from":"P14","to":"P17","weight":1},{"from":"P14","to":"P18","weight":1},{"from":"P15","to":"P14","weight":1},{"from":"P15","to":"P16","weight":1},{"from":"P15","to":"P9","weight":1},{"from":"P16","to":"P14","weight":1},{"from":"P16","to":"P15","weight":1},{"from":"P16","to":"P38","weight":2},{"from":"P16","to":"P2","weight":1},{"from":"P17","to":"P14","weight":1},{"from":"P17","to":"P4","weight":1},{"from":"P17","to":"P3","weight":1},{"from":"P18","to":"P14","weight":1},{"from":"P18","to":"P7","weight":3},{"from":"P19","to":"P14","weight":1},{"from":"P19","to":"P16","weight":1},{"from":"P20","to":"P3","weight":2},{"from":"P20","to":"P9","weight":3},{"from":"P21","to":"P9","weight":1},{"from":"P21","to":"P16","weight":1},{"from":"P22","to":"P3","weight":1},{"from":"P22","to":"P9","weight":2},{"from":"P22","to":"P4","weight":1},{"from":"P23","to":"P9","weight":2},{"from":"P23","to":"P31","weight":1},{"from":"P24","to":"P1","weight":1},{"from":"P24","to":"P12","weight":1},{"from":"P25","to":"P26","weight":1},{"from":"P25","to":"P27","weight":1},{"from":"P25","to":"P28","weight":1},{"from":"P25","to":"P37","weight":1},{"from":"P26","to":"P25","weight":1},{"from":"P26","to":"P27","weight":1},{"from":"P27","to":"P25","weight":1},{"from":"P27","to":"P28","weight":2},{"from":"P28","to":"P25","weight":1},{"from":"P28","to":"P27","weight":1},{"from":"P29","to":"P30","weight":2},{"from":"P29","to":"P31","weight":1},{"from":"P29","to":"P33","weight":1},{"from":"P29","to":"P36","weight":1},{"from":"P29","to":"P37","weight":1},{"from":"P30","to":"P29","weight":1},{"from":"P30","to":"P31","weight":2},{"from":"P30","to":"P38","weight":1},{"from":"P31","to":"P29","weight":1},{"from":"P31","to":"P32","weight":2},{"from":"P31","to":"P36","weight":1},{"from":"P32","to":"P31","weight":1},{"from":"P32","to":"P33","weight":1},{"from":"P33","to":"P29","weight":1},{"from":"P33","to":"P34","weight":2},{"from":"P33","to":"P35","weight":2},{"from":"P34","to":"P33","weight":1},{"from":"P34","to":"P35","weight":1},{"from":"P35","to":"P33","weight":1},{"from":"P35","to":"P37","weight":1},{"from":"P36","to":"P29","weight":1},{"from":"P36","to":"P32","weight":1},{"from":"P37","to":"P29","weight":1},{"from":"P37","to":"P30","weight":1},{"from":"P38","to":"P30","weight":1},{"from":"P38","to":"P32","weight":1},{"from":"P39","to":"P40","weight":2},{"from":"P40","to":"P39","weight":1}],"details":{"vertices":40,"edges":114,"directed":true,"weighted":true,"acyclic":false,"weightMin":1,"weightMax":3,"negativeWeights":false,"density":0.07307692307692308,"inDegree":{"min":0,"avg":2.85,"max":11},"outDegree":{"min":1,"avg":2.85,"max":10},"selfLoops":0,"components":1}},"problem":"Once each group of pages that link to each other in a loop counts as one page, which way do the links between the groups go?","params":{},"result":{"kind":"groups","groups":[["P24"],["P23"],["P22"],["P21"],["P20"],["P19"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18"],["P39","P40"],["P25","P26","P27","P28"],["P29","P30","P31","P32","P33","P34","P35","P36","P37","P38"]]},"answer":"The 40 vertices condense into 10 components joined by 11 edges, with no cycle left. The largest component has 18 vertices: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 8 more. 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-7","label":"Component 7, 18 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-8","label":"Component 8, 2 vertices","color":"#CC79A7","shape":"dashed-square"},{"id":"component-9","label":"Component 9, 4 vertices","color":"#E69F00","shape":"filled"},{"id":"component-10","label":"Component 10, 10 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 6: P24, P23, P22, P21, P20 and P19 each reach no vertex that reaches them back, so each is a component on its own.","ops":[{"v":"P24","state":"single"},{"v":"P23","state":"single"},{"v":"P22","state":"single"},{"v":"P21","state":"single"},{"v":"P20","state":"single"},{"v":"P19","state":"single"},{"panel":"components","groups":[["P24"],["P23"],["P22"],["P21"],["P20"],["P19"]]}]},{"say":"Component 7: P1, P2, P3, P4, P5, P6, P7, P8, P9, P10 and 8 more can all reach each other, so they become one vertex. The 53 edges among them drop out.","ops":[{"e":["P1","P2"],"state":"inside"},{"e":["P1","P3"],"state":"inside"},{"e":["P1","P4"],"state":"inside"},{"e":["P1","P6"],"state":"inside"},{"e":["P1","P14"],"state":"inside"},{"e":["P1","P9"],"state":"inside"},{"e":["P1","P10"],"state":"inside"},{"e":["P2","P1"],"state":"inside"},{"e":["P2","P3"],"state":"inside"},{"e":["P2","P5"],"state":"inside"},{"e":["P2","P9"],"state":"inside"},{"e":["P3","P1"],"state":"inside"},{"e":["P3","P9"],"state":"inside"},{"e":["P3","P8"],"state":"inside"},{"e":["P3","P11"],"state":"inside"},{"e":["P4","P1"],"state":"inside"},{"e":["P4","P17"],"state":"inside"},{"e":["P4","P9"],"state":"inside"},{"e":["P5","P2"],"state":"inside"},{"e":["P6","P1"],"state":"inside"},{"e":["P6","P7"],"state":"inside"},{"e":["P6","P8"],"state":"inside"},{"e":["P6","P14"],"state":"inside"},{"e":["P7","P6"],"state":"inside"},{"e":["P7","P18"],"state":"inside"},{"e":["P8","P1"],"state":"inside"},{"e":["P9","P1"],"state":"inside"},{"e":["P9","P10"],"state":"inside"},{"e":["P9","P13"],"state":"inside"},{"e":["P9","P12"],"state":"inside"},{"e":["P10","P9"],"state":"inside"},{"e":["P11","P1"],"state":"inside"},{"e":["P11","P12"],"state":"inside"},{"e":["P12","P1"],"state":"inside"},{"e":["P12","P13"],"state":"inside"},{"e":["P13","P1"],"state":"inside"},{"e":["P13","P12"],"state":"inside"},{"e":["P14","P1"],"state":"inside"},{"e":["P14","P15"],"state":"inside"},{"e":["P14","P16"],"state":"inside"},{"e":["P14","P17"],"state":"inside"},{"e":["P14","P18"],"state":"inside"},{"e":["P15","P14"],"state":"inside"},{"e":["P15","P16"],"state":"inside"},{"e":["P15","P9"],"state":"inside"},{"e":["P16","P14"],"state":"inside"},{"e":["P16","P15"],"state":"inside"},{"e":["P16","P2"],"state":"inside"},{"e":["P17","P14"],"state":"inside"},{"e":["P17","P4"],"state":"inside"},{"e":["P17","P3"],"state":"inside"},{"e":["P18","P14"],"state":"inside"},{"e":["P18","P7"],"state":"inside"},{"v":"P1","state":"component-7"},{"v":"P2","state":"component-7"},{"v":"P3","state":"component-7"},{"v":"P4","state":"component-7"},{"v":"P5","state":"component-7"},{"v":"P6","state":"component-7"},{"v":"P7","state":"component-7"},{"v":"P8","state":"component-7"},{"v":"P9","state":"component-7"},{"v":"P10","state":"component-7"},{"v":"P11","state":"component-7"},{"v":"P12","state":"component-7"},{"v":"P13","state":"component-7"},{"v":"P14","state":"component-7"},{"v":"P15","state":"component-7"},{"v":"P16","state":"component-7"},{"v":"P17","state":"component-7"},{"v":"P18","state":"component-7"},{"panel":"components","groups":[["P24"],["P23"],["P22"],["P21"],["P20"],["P19"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18"]]}]},{"say":"Component 8: P39 and P40 reach each other, so they become one vertex. The 2 edges among them drop out.","ops":[{"e":["P39","P40"],"state":"inside"},{"e":["P40","P39"],"state":"inside"},{"v":"P39","state":"component-8"},{"v":"P40","state":"component-8"},{"panel":"components","groups":[["P24"],["P23"],["P22"],["P21"],["P20"],["P19"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18"],["P39","P40"]]}]},{"say":"Component 9: P25, P26, P27 and P28 can all reach each other, so they become one vertex. The 9 edges among them drop out.","ops":[{"e":["P25","P26"],"state":"inside"},{"e":["P25","P27"],"state":"inside"},{"e":["P25","P28"],"state":"inside"},{"e":["P26","P25"],"state":"inside"},{"e":["P26","P27"],"state":"inside"},{"e":["P27","P25"],"state":"inside"},{"e":["P27","P28"],"state":"inside"},{"e":["P28","P25"],"state":"inside"},{"e":["P28","P27"],"state":"inside"},{"v":"P25","state":"component-9"},{"v":"P26","state":"component-9"},{"v":"P27","state":"component-9"},{"v":"P28","state":"component-9"},{"panel":"components","groups":[["P24"],["P23"],["P22"],["P21"],["P20"],["P19"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18"],["P39","P40"],["P25","P26","P27","P28"]]}]},{"say":"Component 10: P29, P30, P31, P32, P33, P34, P35, P36, P37 and P38 can all reach each other, so they become one vertex. The 26 edges among them drop out.","ops":[{"e":["P29","P30"],"state":"inside"},{"e":["P29","P31"],"state":"inside"},{"e":["P29","P33"],"state":"inside"},{"e":["P29","P36"],"state":"inside"},{"e":["P29","P37"],"state":"inside"},{"e":["P30","P29"],"state":"inside"},{"e":["P30","P31"],"state":"inside"},{"e":["P30","P38"],"state":"inside"},{"e":["P31","P29"],"state":"inside"},{"e":["P31","P32"],"state":"inside"},{"e":["P31","P36"],"state":"inside"},{"e":["P32","P31"],"state":"inside"},{"e":["P32","P33"],"state":"inside"},{"e":["P33","P29"],"state":"inside"},{"e":["P33","P34"],"state":"inside"},{"e":["P33","P35"],"state":"inside"},{"e":["P34","P33"],"state":"inside"},{"e":["P34","P35"],"state":"inside"},{"e":["P35","P33"],"state":"inside"},{"e":["P35","P37"],"state":"inside"},{"e":["P36","P29"],"state":"inside"},{"e":["P36","P32"],"state":"inside"},{"e":["P37","P29"],"state":"inside"},{"e":["P37","P30"],"state":"inside"},{"e":["P38","P30"],"state":"inside"},{"e":["P38","P32"],"state":"inside"},{"v":"P29","state":"component-10"},{"v":"P30","state":"component-10"},{"v":"P31","state":"component-10"},{"v":"P32","state":"component-10"},{"v":"P33","state":"component-10"},{"v":"P34","state":"component-10"},{"v":"P35","state":"component-10"},{"v":"P36","state":"component-10"},{"v":"P37","state":"component-10"},{"v":"P38","state":"component-10"},{"panel":"components","groups":[["P24"],["P23"],["P22"],["P21"],["P20"],["P19"],["P1","P2","P3","P4","P5","P6","P7","P8","P9","P10","P11","P12","P13","P14","P15","P16","P17","P18"],["P39","P40"],["P25","P26","P27","P28"],["P29","P30","P31","P32","P33","P34","P35","P36","P37","P38"]]}]},{"say":"Out of component 1: The 2 edges P24 to P1 and P24 to P12 become one edge, 1 to 7.","ops":[{"e":["P24","P1"],"state":"between"},{"e":["P24","P12"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"}]}]},{"say":"Out of component 2: P23 to P9 becomes the edge 2 to 7. P23 to P31 becomes the edge 2 to 10.","ops":[{"e":["P23","P9"],"state":"between"},{"e":["P23","P31"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"}]}]},{"say":"Out of component 3: The 3 edges P22 to P3, P22 to P4 and P22 to P9 become one edge, 3 to 7.","ops":[{"e":["P22","P3"],"state":"between"},{"e":["P22","P9"],"state":"merged"},{"e":["P22","P4"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"},{"key":"3 to 7","note":"3 edges"}]}]},{"say":"Out of component 4: The 2 edges P21 to P9 and P21 to P16 become one edge, 4 to 7.","ops":[{"e":["P21","P9"],"state":"between"},{"e":["P21","P16"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"},{"key":"3 to 7","note":"3 edges"},{"key":"4 to 7","note":"2 edges"}]}]},{"say":"Out of component 5: The 2 edges P20 to P3 and P20 to P9 become one edge, 5 to 7.","ops":[{"e":["P20","P3"],"state":"between"},{"e":["P20","P9"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"},{"key":"3 to 7","note":"3 edges"},{"key":"4 to 7","note":"2 edges"},{"key":"5 to 7","note":"2 edges"}]}]},{"say":"Out of component 6: The 2 edges P19 to P14 and P19 to P16 become one edge, 6 to 7.","ops":[{"e":["P19","P14"],"state":"between"},{"e":["P19","P16"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"},{"key":"3 to 7","note":"3 edges"},{"key":"4 to 7","note":"2 edges"},{"key":"5 to 7","note":"2 edges"},{"key":"6 to 7","note":"2 edges"}]}]},{"say":"Out of component 7: The 2 edges P1 to P39 and P11 to P39 become one edge, 7 to 8. The 4 edges P1 to P25, P3 to P26, P8 to P25 and P10 to P28 become one edge, 7 to 9. The 4 edges P1 to P29, P2 to P29, P5 to P33 and P16 to P38 become one edge, 7 to 10.","ops":[{"e":["P1","P39"],"state":"between"},{"e":["P11","P39"],"state":"merged"},{"e":["P1","P25"],"state":"between"},{"e":["P3","P26"],"state":"merged"},{"e":["P8","P25"],"state":"merged"},{"e":["P10","P28"],"state":"merged"},{"e":["P1","P29"],"state":"between"},{"e":["P2","P29"],"state":"merged"},{"e":["P5","P33"],"state":"merged"},{"e":["P16","P38"],"state":"merged"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"},{"key":"3 to 7","note":"3 edges"},{"key":"4 to 7","note":"2 edges"},{"key":"5 to 7","note":"2 edges"},{"key":"6 to 7","note":"2 edges"},{"key":"7 to 8","note":"2 edges"},{"key":"7 to 9","note":"4 edges"},{"key":"7 to 10","note":"4 edges"}]}]},{"say":"Out of component 9: The only edge, P25 to P37, becomes the edge 9 to 10.","ops":[{"e":["P25","P37"],"state":"between"},{"panel":"edges","list":[{"key":"1 to 7","note":"2 edges"},{"key":"2 to 7","note":"1 edge"},{"key":"2 to 10","note":"1 edge"},{"key":"3 to 7","note":"3 edges"},{"key":"4 to 7","note":"2 edges"},{"key":"5 to 7","note":"2 edges"},{"key":"6 to 7","note":"2 edges"},{"key":"7 to 8","note":"2 edges"},{"key":"7 to 9","note":"4 edges"},{"key":"7 to 10","note":"4 edges"},{"key":"9 to 10","note":"1 edge"}]}]},{"say":"Done. The 40 vertices condense into 10 components and 11 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}"}