{"algorithm":"randomized-k-cut","about":["The randomized k-cut starts with each vertex in its own group. It picks an edge at random, merges the groups at its two ends, and drops the edges that now run inside one group. It repeats until k groups are left. The edges still running between groups are the cut.","This is Karger's contraction method for the minimum cut, applied to k groups. A dense cluster has many edges, so a random edge is more likely to fall inside one, and clusters tend to merge before the few edges between them are picked. One run can still miss the smallest cut, so repeat it and keep the cut with the fewest edges.","One run costs O(V·E). k must be at least 2 and no more than the number of vertices. If the graph has more than k connected components, the edges run out first and each component is its own group. Use it to split a network into parts with few links between them, such as friend groups or shards of a service map."],"template":{"id":"karate-club","name":"Karate club","description":"The 34 members of a university karate club, numbered 1 to 34 as in the study. Each edge joins two members who also spent time together outside the club's classes and meetings. A dispute between the instructor (1) and an officer (34) split the club in two, and most members sit near the side they joined.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"1","x":590,"y":680},{"id":"2","x":640,"y":560},{"id":"3","x":420,"y":520},{"id":"4","x":470,"y":760},{"id":"5","x":680,"y":850},{"id":"6","x":750,"y":860},{"id":"7","x":820,"y":760},{"id":"8","x":390,"y":660},{"id":"9","x":520,"y":430},{"id":"10","x":590,"y":230},{"id":"11","x":590,"y":930},{"id":"12","x":400,"y":900},{"id":"13","x":490,"y":890},{"id":"14","x":590,"y":480},{"id":"15","x":460,"y":80},{"id":"16","x":380,"y":70},{"id":"17","x":950,"y":940},{"id":"18","x":830,"y":560},{"id":"19","x":540,"y":110},{"id":"20","x":770,"y":450},{"id":"21","x":90,"y":220},{"id":"22","x":820,"y":640},{"id":"23","x":290,"y":70},{"id":"24","x":120,"y":300},{"id":"25","x":120,"y":690},{"id":"26","x":50,"y":570},{"id":"27","x":220,"y":60},{"id":"28","x":210,"y":490},{"id":"29","x":390,"y":440},{"id":"30","x":170,"y":190},{"id":"31","x":640,"y":300},{"id":"32","x":280,"y":570},{"id":"33","x":250,"y":340},{"id":"34","x":440,"y":260}],"edges":[{"from":"1","to":"2"},{"from":"1","to":"3"},{"from":"1","to":"4"},{"from":"1","to":"5"},{"from":"1","to":"6"},{"from":"1","to":"7"},{"from":"1","to":"8"},{"from":"1","to":"9"},{"from":"1","to":"11"},{"from":"1","to":"12"},{"from":"1","to":"13"},{"from":"1","to":"14"},{"from":"1","to":"18"},{"from":"1","to":"20"},{"from":"1","to":"22"},{"from":"1","to":"32"},{"from":"2","to":"3"},{"from":"2","to":"4"},{"from":"2","to":"8"},{"from":"2","to":"14"},{"from":"2","to":"18"},{"from":"2","to":"20"},{"from":"2","to":"22"},{"from":"2","to":"31"},{"from":"3","to":"4"},{"from":"3","to":"8"},{"from":"3","to":"9"},{"from":"3","to":"10"},{"from":"3","to":"14"},{"from":"3","to":"28"},{"from":"3","to":"29"},{"from":"3","to":"33"},{"from":"4","to":"8"},{"from":"4","to":"13"},{"from":"4","to":"14"},{"from":"5","to":"7"},{"from":"5","to":"11"},{"from":"6","to":"7"},{"from":"6","to":"11"},{"from":"6","to":"17"},{"from":"7","to":"17"},{"from":"9","to":"31"},{"from":"9","to":"33"},{"from":"9","to":"34"},{"from":"10","to":"34"},{"from":"14","to":"34"},{"from":"15","to":"33"},{"from":"15","to":"34"},{"from":"16","to":"33"},{"from":"16","to":"34"},{"from":"19","to":"33"},{"from":"19","to":"34"},{"from":"20","to":"34"},{"from":"21","to":"33"},{"from":"21","to":"34"},{"from":"23","to":"33"},{"from":"23","to":"34"},{"from":"24","to":"26"},{"from":"24","to":"28"},{"from":"24","to":"30"},{"from":"24","to":"33"},{"from":"24","to":"34"},{"from":"25","to":"26"},{"from":"25","to":"28"},{"from":"25","to":"32"},{"from":"26","to":"32"},{"from":"27","to":"30"},{"from":"27","to":"34"},{"from":"28","to":"34"},{"from":"29","to":"32"},{"from":"29","to":"34"},{"from":"30","to":"33"},{"from":"30","to":"34"},{"from":"31","to":"33"},{"from":"31","to":"34"},{"from":"32","to":"33"},{"from":"32","to":"34"},{"from":"33","to":"34"}],"source":"W. W. Zachary, \"An information flow model for conflict and fission in small groups\", Journal of Anthropological Research 33 (1977).","details":{"vertices":34,"edges":78,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.13903743315508021,"degree":{"min":1,"avg":4.588235294117647,"max":17},"selfLoops":0,"components":1}},"problem":"Split the club in two and try to break as few ties between members as possible.","params":{"k":2},"result":{"kind":"cut","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34"],["12"]],"edges":[["1","12"]]},"answer":"On this run, the cut splits the vertices into 2 groups, of 33 and 1 vertices, and cuts 1 edge: 1 and 12.","legend":{"vertex":[{"id":"idle","label":"A supernode of its own","color":"#64748B","shape":"hollow"},{"id":"current","label":"End of the contracted edge","color":"#56B4E9","shape":"ring"},{"id":"done","label":"In a merged supernode","color":"#009E73","shape":"filled"},{"id":"component-1","label":"Supernode 1, 33 vertices","color":"#56B4E9","shape":"filled"},{"id":"single","label":"A supernode of one vertex","color":"#CBD5E1","shape":"hollow"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Contracted","color":"#009E73","shape":"thick"},{"id":"cut","label":"In the cut, between two supernodes","color":"#D55E00","shape":"dashed"}],"panels":[{"id":"supernodes","title":"Supernodes","kind":"groups"}]},"steps":[{"say":"Randomized k-cut starts with each of the 34 vertices as a supernode of its own. gograph shuffles the edges and takes them in that order. An edge between two supernodes is contracted: the two merge into one, and the edges between them now lie inside it and are dropped. It stops when k = 2 supernodes are left, and the edges between them form the cut. These steps contract only edges inside the supernodes gograph ended with, in the graph's edge order, so they end in the same cut.","ops":[{"panel":"supernodes","groups":[["1"],["2"],["3"],["4"],["5"],["6"],["7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 2. 1 and 2 form a supernode of 2 vertices. 33 supernodes are left.","ops":[{"v":"1","state":"current"},{"v":"2","state":"current"},{"e":["1","2"],"state":"tree"},{"panel":"supernodes","groups":[["1","2"],["3"],["4"],["5"],["6"],["7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 3. 3 joins the supernode of 1 and 2, which now has 3 vertices. The edge between 2 and 3 joined the same two supernodes, so it now lies inside the new one and is dropped. 32 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"2","state":"done"},{"v":"1","state":"current"},{"v":"3","state":"current"},{"e":["1","3"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3"],["4"],["5"],["6"],["7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 4. 4 joins the supernode of 1, 2 and 3, which now has 4 vertices. The 2 other edges between the two supernodes now lie inside the new one and are dropped. 31 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"3","state":"done"},{"v":"1","state":"current"},{"v":"4","state":"current"},{"e":["1","4"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4"],["5"],["6"],["7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 5. 5 joins the supernode that holds 1, which now has 5 vertices. 30 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"4","state":"done"},{"v":"1","state":"current"},{"v":"5","state":"current"},{"e":["1","5"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5"],["6"],["7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 6. 6 joins the supernode that holds 1, which now has 6 vertices. 29 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"5","state":"done"},{"v":"1","state":"current"},{"v":"6","state":"current"},{"e":["1","6"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6"],["7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 7. 7 joins the supernode that holds 1, which now has 7 vertices. The 2 other edges between the two supernodes now lie inside the new one and are dropped. 28 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"6","state":"done"},{"v":"1","state":"current"},{"v":"7","state":"current"},{"e":["1","7"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7"],["8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 8. 8 joins the supernode that holds 1, which now has 8 vertices. The 3 other edges between the two supernodes now lie inside the new one and are dropped. 27 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"7","state":"done"},{"v":"1","state":"current"},{"v":"8","state":"current"},{"e":["1","8"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8"],["9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 9. 9 joins the supernode that holds 1, which now has 9 vertices. The edge between 3 and 9 joined the same two supernodes, so it now lies inside the new one and is dropped. 26 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"8","state":"done"},{"v":"1","state":"current"},{"v":"9","state":"current"},{"e":["1","9"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9"],["10"],["11"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 11. 11 joins the supernode that holds 1, which now has 10 vertices. The 2 other edges between the two supernodes now lie inside the new one and are dropped. 25 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"9","state":"done"},{"v":"1","state":"current"},{"v":"11","state":"current"},{"e":["1","11"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11"],["10"],["12"],["13"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 13. 13 joins the supernode that holds 1, which now has 11 vertices. The edge between 4 and 13 joined the same two supernodes, so it now lies inside the new one and is dropped. 24 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"11","state":"done"},{"v":"1","state":"current"},{"v":"13","state":"current"},{"e":["1","13"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13"],["10"],["12"],["14"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 14. 14 joins the supernode that holds 1, which now has 12 vertices. The 3 other edges between the two supernodes now lie inside the new one and are dropped. 23 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"13","state":"done"},{"v":"1","state":"current"},{"v":"14","state":"current"},{"e":["1","14"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13","14"],["10"],["12"],["15"],["16"],["17"],["18"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 18. 18 joins the supernode that holds 1, which now has 13 vertices. The edge between 2 and 18 joined the same two supernodes, so it now lies inside the new one and is dropped. 22 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"14","state":"done"},{"v":"1","state":"current"},{"v":"18","state":"current"},{"e":["1","18"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13","14","18"],["10"],["12"],["15"],["16"],["17"],["19"],["20"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 20. 20 joins the supernode that holds 1, which now has 14 vertices. The edge between 2 and 20 joined the same two supernodes, so it now lies inside the new one and is dropped. 21 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"18","state":"done"},{"v":"1","state":"current"},{"v":"20","state":"current"},{"e":["1","20"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13","14","18","20"],["10"],["12"],["15"],["16"],["17"],["19"],["21"],["22"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 22. 22 joins the supernode that holds 1, which now has 15 vertices. The edge between 2 and 22 joined the same two supernodes, so it now lies inside the new one and is dropped. 20 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"20","state":"done"},{"v":"1","state":"current"},{"v":"22","state":"current"},{"e":["1","22"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13","14","18","20","22"],["10"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["32"],["33"],["34"]]}]},{"say":"Contract the edge between 1 and 32. 32 joins the supernode that holds 1, which now has 16 vertices. 19 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"22","state":"done"},{"v":"1","state":"current"},{"v":"32","state":"current"},{"e":["1","32"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13","14","18","20","22","32"],["10"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["31"],["33"],["34"]]}]},{"say":"Contract the edge between 2 and 31. 31 joins the supernode that holds 2, which now has 17 vertices. The edge between 9 and 31 joined the same two supernodes, so it now lies inside the new one and is dropped. 18 supernodes are left.","ops":[{"v":"1","state":"done"},{"v":"32","state":"done"},{"v":"2","state":"current"},{"v":"31","state":"current"},{"e":["2","31"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","11","13","14","18","20","22","31","32"],["10"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["33"],["34"]]}]},{"say":"Contract the edge between 3 and 10. 10 joins the supernode that holds 3, which now has 18 vertices. 17 supernodes are left.","ops":[{"v":"2","state":"done"},{"v":"31","state":"done"},{"v":"3","state":"current"},{"v":"10","state":"current"},{"e":["3","10"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","18","20","22","31","32"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["28"],["29"],["30"],["33"],["34"]]}]},{"say":"Contract the edge between 3 and 28. 28 joins the supernode that holds 3, which now has 19 vertices. 16 supernodes are left.","ops":[{"v":"3","state":"done"},{"v":"10","state":"done"},{"v":"3","state":"current"},{"v":"28","state":"current"},{"e":["3","28"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","18","20","22","28","31","32"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["29"],["30"],["33"],["34"]]}]},{"say":"Contract the edge between 3 and 29. 29 joins the supernode that holds 3, which now has 20 vertices. The edge between 29 and 32 joined the same two supernodes, so it now lies inside the new one and is dropped. 15 supernodes are left.","ops":[{"v":"3","state":"done"},{"v":"28","state":"done"},{"v":"3","state":"current"},{"v":"29","state":"current"},{"e":["3","29"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","18","20","22","28","29","31","32"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["30"],["33"],["34"]]}]},{"say":"Contract the edge between 3 and 33. 33 joins the supernode that holds 3, which now has 21 vertices. The 3 other edges between the two supernodes now lie inside the new one and are dropped. 14 supernodes are left.","ops":[{"v":"3","state":"done"},{"v":"29","state":"done"},{"v":"3","state":"current"},{"v":"33","state":"current"},{"e":["3","33"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","18","20","22","28","29","31","32","33"],["12"],["15"],["16"],["17"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["30"],["34"]]}]},{"say":"Contract the edge between 6 and 17. 17 joins the supernode that holds 6, which now has 22 vertices. The edge between 7 and 17 joined the same two supernodes, so it now lies inside the new one and is dropped. 13 supernodes are left.","ops":[{"v":"3","state":"done"},{"v":"33","state":"done"},{"v":"6","state":"current"},{"v":"17","state":"current"},{"e":["6","17"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","17","18","20","22","28","29","31","32","33"],["12"],["15"],["16"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["30"],["34"]]}]},{"say":"Contract the edge between 9 and 34. 34 joins the supernode that holds 9, which now has 23 vertices. The 8 other edges between the two supernodes now lie inside the new one and are dropped. 12 supernodes are left.","ops":[{"v":"6","state":"done"},{"v":"17","state":"done"},{"v":"9","state":"current"},{"v":"34","state":"current"},{"e":["9","34"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","17","18","20","22","28","29","31","32","33","34"],["12"],["15"],["16"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["30"]]}]},{"say":"Contract the edge between 15 and 33. 15 joins the supernode that holds 33, which now has 24 vertices. The edge between 15 and 34 joined the same two supernodes, so it now lies inside the new one and is dropped. 11 supernodes are left.","ops":[{"v":"9","state":"done"},{"v":"34","state":"done"},{"v":"15","state":"current"},{"v":"33","state":"current"},{"e":["15","33"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","17","18","20","22","28","29","31","32","33","34"],["12"],["16"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["30"]]}]},{"say":"Contract the edge between 16 and 33. 16 joins the supernode that holds 33, which now has 25 vertices. The edge between 16 and 34 joined the same two supernodes, so it now lies inside the new one and is dropped. 10 supernodes are left.","ops":[{"v":"15","state":"done"},{"v":"33","state":"done"},{"v":"16","state":"current"},{"v":"33","state":"current"},{"e":["16","33"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","20","22","28","29","31","32","33","34"],["12"],["19"],["21"],["23"],["24"],["25"],["26"],["27"],["30"]]}]},{"say":"Contract the edge between 19 and 33. 19 joins the supernode that holds 33, which now has 26 vertices. The edge between 19 and 34 joined the same two supernodes, so it now lies inside the new one and is dropped. 9 supernodes are left.","ops":[{"v":"16","state":"done"},{"v":"33","state":"done"},{"v":"19","state":"current"},{"v":"33","state":"current"},{"e":["19","33"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","22","28","29","31","32","33","34"],["12"],["21"],["23"],["24"],["25"],["26"],["27"],["30"]]}]},{"say":"Contract the edge between 21 and 33. 21 joins the supernode that holds 33, which now has 27 vertices. The edge between 21 and 34 joined the same two supernodes, so it now lies inside the new one and is dropped. 8 supernodes are left.","ops":[{"v":"19","state":"done"},{"v":"33","state":"done"},{"v":"21","state":"current"},{"v":"33","state":"current"},{"e":["21","33"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","28","29","31","32","33","34"],["12"],["23"],["24"],["25"],["26"],["27"],["30"]]}]},{"say":"Contract the edge between 23 and 33. 23 joins the supernode that holds 33, which now has 28 vertices. The edge between 23 and 34 joined the same two supernodes, so it now lies inside the new one and is dropped. 7 supernodes are left.","ops":[{"v":"21","state":"done"},{"v":"33","state":"done"},{"v":"23","state":"current"},{"v":"33","state":"current"},{"e":["23","33"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","28","29","31","32","33","34"],["12"],["24"],["25"],["26"],["27"],["30"]]}]},{"say":"Contract the edge between 24 and 26. 24 and 26 form a supernode of 2 vertices. 6 supernodes are left.","ops":[{"v":"23","state":"done"},{"v":"33","state":"done"},{"v":"24","state":"current"},{"v":"26","state":"current"},{"e":["24","26"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","28","29","31","32","33","34"],["12"],["24","26"],["25"],["27"],["30"]]}]},{"say":"Contract the edge between 24 and 28. The supernodes of 24 and 28, with 2 and 28 vertices, merge into one of 30. The 3 other edges between the two supernodes now lie inside the new one and are dropped. 5 supernodes are left.","ops":[{"v":"24","state":"done"},{"v":"26","state":"done"},{"v":"24","state":"current"},{"v":"28","state":"current"},{"e":["24","28"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","24","26","28","29","31","32","33","34"],["12"],["25"],["27"],["30"]]}]},{"say":"Contract the edge between 24 and 30. 30 joins the supernode that holds 24, which now has 31 vertices. The 2 other edges between the two supernodes now lie inside the new one and are dropped. 4 supernodes are left.","ops":[{"v":"24","state":"done"},{"v":"28","state":"done"},{"v":"24","state":"current"},{"v":"30","state":"current"},{"e":["24","30"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","24","26","28","29","30","31","32","33","34"],["12"],["25"],["27"]]}]},{"say":"Contract the edge between 25 and 26. 25 joins the supernode that holds 26, which now has 32 vertices. The 2 other edges between the two supernodes now lie inside the new one and are dropped. 3 supernodes are left.","ops":[{"v":"24","state":"done"},{"v":"30","state":"done"},{"v":"25","state":"current"},{"v":"26","state":"current"},{"e":["25","26"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","24","25","26","28","29","30","31","32","33","34"],["12"],["27"]]}]},{"say":"Contract the edge between 27 and 30. 27 joins the supernode that holds 30, which now has 33 vertices. The edge between 27 and 34 joined the same two supernodes, so it now lies inside the new one and is dropped. That leaves k = 2 supernodes.","ops":[{"v":"25","state":"done"},{"v":"26","state":"done"},{"v":"27","state":"current"},{"v":"30","state":"current"},{"e":["27","30"],"state":"tree"},{"panel":"supernodes","groups":[["1","2","3","4","5","6","7","8","9","10","11","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34"],["12"]]}]},{"say":"Done. After 32 contractions, k = 2 supernodes are left, so the contraction stops. The edge between 1 and 12 is the only one between two supernodes, so it is the whole cut. Every vertex now shows its supernode.","ops":[{"v":"1","state":"component-1"},{"v":"2","state":"component-1"},{"v":"3","state":"component-1"},{"v":"4","state":"component-1"},{"v":"5","state":"component-1"},{"v":"6","state":"component-1"},{"v":"7","state":"component-1"},{"v":"8","state":"component-1"},{"v":"9","state":"component-1"},{"v":"10","state":"component-1"},{"v":"11","state":"component-1"},{"v":"13","state":"component-1"},{"v":"14","state":"component-1"},{"v":"15","state":"component-1"},{"v":"16","state":"component-1"},{"v":"17","state":"component-1"},{"v":"18","state":"component-1"},{"v":"19","state":"component-1"},{"v":"20","state":"component-1"},{"v":"21","state":"component-1"},{"v":"22","state":"component-1"},{"v":"23","state":"component-1"},{"v":"24","state":"component-1"},{"v":"25","state":"component-1"},{"v":"26","state":"component-1"},{"v":"27","state":"component-1"},{"v":"28","state":"component-1"},{"v":"29","state":"component-1"},{"v":"30","state":"component-1"},{"v":"31","state":"component-1"},{"v":"32","state":"component-1"},{"v":"33","state":"component-1"},{"v":"34","state":"component-1"},{"v":"12","state":"single"},{"e":["1","12"],"state":"cut"}]}],"traceNote":"","verification":"The steps replay one contraction order that leads to the cut gograph returned when the server started, not gograph's own random order.","snippet":"cut, err := partition.RandomizedKCut(g, 2)\nif err != nil {\n\treturn err\n}\nfor _, group := range cut.Supernodes {\n\tvar members []string\n\tfor _, v := range group {\n\t\tmembers = append(members, v.Label())\n\t}\n\tfmt.Println(members)\n}\nfor _, e := range cut.CutEdges {\n\tfmt.Println(e.Source().Label(), e.Destination().Label())\n}"}
