{"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":"maze","name":"Maze","description":"A maze of 30 cells in five rows, A to E, and six columns, 1 to 6, so C4 is row C, column 4. Each edge is an open passage between two cells. The way from A1 to E6 winds through most of the maze, and two short loops give a few cells a second route.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"A1","x":100,"y":180},{"id":"A2","x":260,"y":180},{"id":"A3","x":420,"y":180},{"id":"A4","x":580,"y":180},{"id":"A5","x":740,"y":180},{"id":"A6","x":900,"y":180},{"id":"B1","x":100,"y":340},{"id":"B2","x":260,"y":340},{"id":"B3","x":420,"y":340},{"id":"B4","x":580,"y":340},{"id":"B5","x":740,"y":340},{"id":"B6","x":900,"y":340},{"id":"C1","x":100,"y":500},{"id":"C2","x":260,"y":500},{"id":"C3","x":420,"y":500},{"id":"C4","x":580,"y":500},{"id":"C5","x":740,"y":500},{"id":"C6","x":900,"y":500},{"id":"D1","x":100,"y":660},{"id":"D2","x":260,"y":660},{"id":"D3","x":420,"y":660},{"id":"D4","x":580,"y":660},{"id":"D5","x":740,"y":660},{"id":"D6","x":900,"y":660},{"id":"E1","x":100,"y":820},{"id":"E2","x":260,"y":820},{"id":"E3","x":420,"y":820},{"id":"E4","x":580,"y":820},{"id":"E5","x":740,"y":820},{"id":"E6","x":900,"y":820}],"edges":[{"from":"A1","to":"A2"},{"from":"A2","to":"A3"},{"from":"A3","to":"B3"},{"from":"A4","to":"A5"},{"from":"A4","to":"B4"},{"from":"A5","to":"A6"},{"from":"A6","to":"B6"},{"from":"B1","to":"B2"},{"from":"B1","to":"C1"},{"from":"B2","to":"B3"},{"from":"B4","to":"C4"},{"from":"B5","to":"B6"},{"from":"B5","to":"C5"},{"from":"B6","to":"C6"},{"from":"C1","to":"C2"},{"from":"C2","to":"D2"},{"from":"C3","to":"C4"},{"from":"C3","to":"D3"},{"from":"C4","to":"D4"},{"from":"C5","to":"C6"},{"from":"C5","to":"D5"},{"from":"D1","to":"E1"},{"from":"D2","to":"E2"},{"from":"D3","to":"E3"},{"from":"D4","to":"E4"},{"from":"D5","to":"D6"},{"from":"D6","to":"E6"},{"from":"E1","to":"E2"},{"from":"E2","to":"E3"},{"from":"E3","to":"E4"},{"from":"E5","to":"E6"}],"details":{"vertices":30,"edges":31,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.07126436781609195,"degree":{"min":1,"avg":2.066666666666667,"max":3},"selfLoops":0,"components":1}},"problem":"Split the maze into 4 regions and try to close as few passages as possible.","params":{"k":4},"result":{"kind":"cut","groups":[["A1","A2","A3","A4","A5","A6","B1","B2","B3","B4","B5","B6","C1","C2","C3","C4","C5","C6","D1","D2","D3","D4","E1","E2","E3","E4"],["D5","D6"],["E5"],["E6"]],"edges":[["C5","D5"],["D6","E6"],["E5","E6"]]},"answer":"On this run, the cut splits the vertices into 4 groups, of 26, 2, 1 and 1 vertices, and cuts 3 edges: C5 and D5; D6 and E6; E5 and E6.","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, 26 vertices","color":"#56B4E9","shape":"filled"},{"id":"component-2","label":"Supernode 2, 2 vertices","color":"#CC79A7","shape":"dashed-square"},{"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 30 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 = 4 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":[["A1"],["A2"],["A3"],["A4"],["A5"],["A6"],["B1"],["B2"],["B3"],["B4"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A1 and A2. A1 and A2 form a supernode of 2 vertices. 29 supernodes are left.","ops":[{"v":"A1","state":"current"},{"v":"A2","state":"current"},{"e":["A1","A2"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2"],["A3"],["A4"],["A5"],["A6"],["B1"],["B2"],["B3"],["B4"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A2 and A3. A3 joins the supernode of A1 and A2, which now has 3 vertices. 28 supernodes are left.","ops":[{"v":"A1","state":"done"},{"v":"A2","state":"done"},{"v":"A2","state":"current"},{"v":"A3","state":"current"},{"e":["A2","A3"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3"],["A4"],["A5"],["A6"],["B1"],["B2"],["B3"],["B4"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A3 and B3. B3 joins the supernode of A1, A2 and A3, which now has 4 vertices. 27 supernodes are left.","ops":[{"v":"A2","state":"done"},{"v":"A3","state":"done"},{"v":"A3","state":"current"},{"v":"B3","state":"current"},{"e":["A3","B3"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4"],["A5"],["A6"],["B1"],["B2"],["B4"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A4 and A5. A4 and A5 form a supernode of 2 vertices. 26 supernodes are left.","ops":[{"v":"A3","state":"done"},{"v":"B3","state":"done"},{"v":"A4","state":"current"},{"v":"A5","state":"current"},{"e":["A4","A5"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4","A5"],["A6"],["B1"],["B2"],["B4"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A4 and B4. B4 joins the supernode of A4 and A5, which now has 3 vertices. 25 supernodes are left.","ops":[{"v":"A4","state":"done"},{"v":"A5","state":"done"},{"v":"A4","state":"current"},{"v":"B4","state":"current"},{"e":["A4","B4"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4","A5","B4"],["A6"],["B1"],["B2"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A5 and A6. A6 joins the supernode of A4, A5 and B4, which now has 4 vertices. 24 supernodes are left.","ops":[{"v":"A4","state":"done"},{"v":"B4","state":"done"},{"v":"A5","state":"current"},{"v":"A6","state":"current"},{"e":["A5","A6"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4","A5","A6","B4"],["B1"],["B2"],["B5"],["B6"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between A6 and B6. B6 joins the supernode that holds A6, which now has 5 vertices. 23 supernodes are left.","ops":[{"v":"A5","state":"done"},{"v":"A6","state":"done"},{"v":"A6","state":"current"},{"v":"B6","state":"current"},{"e":["A6","B6"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4","A5","A6","B4","B6"],["B1"],["B2"],["B5"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B1 and B2. B1 and B2 form a supernode of 2 vertices. 22 supernodes are left.","ops":[{"v":"A6","state":"done"},{"v":"B6","state":"done"},{"v":"B1","state":"current"},{"v":"B2","state":"current"},{"e":["B1","B2"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4","A5","A6","B4","B6"],["B1","B2"],["B5"],["C1"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B1 and C1. C1 joins the supernode of B1 and B2, which now has 3 vertices. 21 supernodes are left.","ops":[{"v":"B1","state":"done"},{"v":"B2","state":"done"},{"v":"B1","state":"current"},{"v":"C1","state":"current"},{"e":["B1","C1"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B3"],["A4","A5","A6","B4","B6"],["B1","B2","C1"],["B5"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B2 and B3. The supernodes of B2 and B3, with 3 and 4 vertices, merge into one of 7. 20 supernodes are left.","ops":[{"v":"B1","state":"done"},{"v":"C1","state":"done"},{"v":"B2","state":"current"},{"v":"B3","state":"current"},{"e":["B2","B3"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1"],["A4","A5","A6","B4","B6"],["B5"],["C2"],["C3"],["C4"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B4 and C4. C4 joins the supernode that holds B4, which now has 6 vertices. 19 supernodes are left.","ops":[{"v":"B2","state":"done"},{"v":"B3","state":"done"},{"v":"B4","state":"current"},{"v":"C4","state":"current"},{"e":["B4","C4"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1"],["A4","A5","A6","B4","B6","C4"],["B5"],["C2"],["C3"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B5 and B6. B5 joins the supernode that holds B6, which now has 7 vertices. 18 supernodes are left.","ops":[{"v":"B4","state":"done"},{"v":"C4","state":"done"},{"v":"B5","state":"current"},{"v":"B6","state":"current"},{"e":["B5","B6"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1"],["A4","A5","A6","B4","B5","B6","C4"],["C2"],["C3"],["C5"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B5 and C5. C5 joins the supernode that holds B5, which now has 8 vertices. 17 supernodes are left.","ops":[{"v":"B5","state":"done"},{"v":"B6","state":"done"},{"v":"B5","state":"current"},{"v":"C5","state":"current"},{"e":["B5","C5"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1"],["A4","A5","A6","B4","B5","B6","C4","C5"],["C2"],["C3"],["C6"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between B6 and C6. C6 joins the supernode that holds B6, which now has 9 vertices. The edge between C5 and C6 joined the same two supernodes, so it now lies inside the new one and is dropped. 16 supernodes are left.","ops":[{"v":"B5","state":"done"},{"v":"C5","state":"done"},{"v":"B6","state":"current"},{"v":"C6","state":"current"},{"e":["B6","C6"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1"],["A4","A5","A6","B4","B5","B6","C4","C5","C6"],["C2"],["C3"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between C1 and C2. C2 joins the supernode that holds C1, which now has 8 vertices. 15 supernodes are left.","ops":[{"v":"B6","state":"done"},{"v":"C6","state":"done"},{"v":"C1","state":"current"},{"v":"C2","state":"current"},{"e":["C1","C2"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2"],["A4","A5","A6","B4","B5","B6","C4","C5","C6"],["C3"],["D1"],["D2"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between C2 and D2. D2 joins the supernode that holds C2, which now has 9 vertices. 14 supernodes are left.","ops":[{"v":"C1","state":"done"},{"v":"C2","state":"done"},{"v":"C2","state":"current"},{"v":"D2","state":"current"},{"e":["C2","D2"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2"],["A4","A5","A6","B4","B5","B6","C4","C5","C6"],["C3"],["D1"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between C3 and C4. C3 joins the supernode that holds C4, which now has 10 vertices. 13 supernodes are left.","ops":[{"v":"C2","state":"done"},{"v":"D2","state":"done"},{"v":"C3","state":"current"},{"v":"C4","state":"current"},{"e":["C3","C4"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6"],["D1"],["D3"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between C3 and D3. D3 joins the supernode that holds C3, which now has 11 vertices. 12 supernodes are left.","ops":[{"v":"C3","state":"done"},{"v":"C4","state":"done"},{"v":"C3","state":"current"},{"v":"D3","state":"current"},{"e":["C3","D3"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3"],["D1"],["D4"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between C4 and D4. D4 joins the supernode that holds C4, which now has 12 vertices. 11 supernodes are left.","ops":[{"v":"C3","state":"done"},{"v":"D3","state":"done"},{"v":"C4","state":"current"},{"v":"D4","state":"current"},{"e":["C4","D4"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4"],["D1"],["D5"],["D6"],["E1"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between D1 and E1. D1 and E1 form a supernode of 2 vertices. 10 supernodes are left.","ops":[{"v":"C4","state":"done"},{"v":"D4","state":"done"},{"v":"D1","state":"current"},{"v":"E1","state":"current"},{"e":["D1","E1"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4"],["D1","E1"],["D5"],["D6"],["E2"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between D2 and E2. E2 joins the supernode that holds D2, which now has 10 vertices. 9 supernodes are left.","ops":[{"v":"D1","state":"done"},{"v":"E1","state":"done"},{"v":"D2","state":"current"},{"v":"E2","state":"current"},{"e":["D2","E2"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2","E2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4"],["D1","E1"],["D5"],["D6"],["E3"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between D3 and E3. E3 joins the supernode that holds D3, which now has 13 vertices. 8 supernodes are left.","ops":[{"v":"D2","state":"done"},{"v":"E2","state":"done"},{"v":"D3","state":"current"},{"v":"E3","state":"current"},{"e":["D3","E3"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2","E2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4","E3"],["D1","E1"],["D5"],["D6"],["E4"],["E5"],["E6"]]}]},{"say":"Contract the edge between D4 and E4. E4 joins the supernode that holds D4, which now has 14 vertices. The edge between E3 and E4 joined the same two supernodes, so it now lies inside the new one and is dropped. 7 supernodes are left.","ops":[{"v":"D3","state":"done"},{"v":"E3","state":"done"},{"v":"D4","state":"current"},{"v":"E4","state":"current"},{"e":["D4","E4"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2","E2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4","E3","E4"],["D1","E1"],["D5"],["D6"],["E5"],["E6"]]}]},{"say":"Contract the edge between D5 and D6. D5 and D6 form a supernode of 2 vertices. 6 supernodes are left.","ops":[{"v":"D4","state":"done"},{"v":"E4","state":"done"},{"v":"D5","state":"current"},{"v":"D6","state":"current"},{"e":["D5","D6"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D2","E2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4","E3","E4"],["D1","E1"],["D5","D6"],["E5"],["E6"]]}]},{"say":"Contract the edge between E1 and E2. The supernodes of E1 and E2, with 2 and 10 vertices, merge into one of 12. 5 supernodes are left.","ops":[{"v":"D5","state":"done"},{"v":"D6","state":"done"},{"v":"E1","state":"current"},{"v":"E2","state":"current"},{"e":["E1","E2"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","B1","B2","B3","C1","C2","D1","D2","E1","E2"],["A4","A5","A6","B4","B5","B6","C3","C4","C5","C6","D3","D4","E3","E4"],["D5","D6"],["E5"],["E6"]]}]},{"say":"Contract the edge between E2 and E3. The supernodes of E2 and E3, with 12 and 14 vertices, merge into one of 26. That leaves k = 4 supernodes.","ops":[{"v":"E1","state":"done"},{"v":"E2","state":"done"},{"v":"E2","state":"current"},{"v":"E3","state":"current"},{"e":["E2","E3"],"state":"tree"},{"panel":"supernodes","groups":[["A1","A2","A3","A4","A5","A6","B1","B2","B3","B4","B5","B6","C1","C2","C3","C4","C5","C6","D1","D2","D3","D4","E1","E2","E3","E4"],["D5","D6"],["E5"],["E6"]]}]},{"say":"Done. After 26 contractions, k = 4 supernodes are left, so the contraction stops. The 3 edges between different supernodes form the cut. Every vertex now shows its supernode.","ops":[{"v":"A1","state":"component-1"},{"v":"A2","state":"component-1"},{"v":"A3","state":"component-1"},{"v":"A4","state":"component-1"},{"v":"A5","state":"component-1"},{"v":"A6","state":"component-1"},{"v":"B1","state":"component-1"},{"v":"B2","state":"component-1"},{"v":"B3","state":"component-1"},{"v":"B4","state":"component-1"},{"v":"B5","state":"component-1"},{"v":"B6","state":"component-1"},{"v":"C1","state":"component-1"},{"v":"C2","state":"component-1"},{"v":"C3","state":"component-1"},{"v":"C4","state":"component-1"},{"v":"C5","state":"component-1"},{"v":"C6","state":"component-1"},{"v":"D1","state":"component-1"},{"v":"D2","state":"component-1"},{"v":"D3","state":"component-1"},{"v":"D4","state":"component-1"},{"v":"E1","state":"component-1"},{"v":"E2","state":"component-1"},{"v":"E3","state":"component-1"},{"v":"E4","state":"component-1"},{"v":"D5","state":"component-2"},{"v":"D6","state":"component-2"},{"v":"E5","state":"single"},{"v":"E6","state":"single"},{"e":["C5","D5"],"state":"cut"},{"e":["D6","E6"],"state":"cut"},{"e":["E5","E6"],"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, 4)\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}"}
