{"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":"office-network","name":"Office network","description":"Switches and rooms in a four-team office, wired through a core switch.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"Core","x":512,"y":320},{"id":"Sales","x":320,"y":192},{"id":"Support","x":704,"y":192},{"id":"Ops","x":704,"y":448},{"id":"Dev","x":320,"y":448},{"id":"Uplink","x":512,"y":64},{"id":"Sales 1","x":128,"y":128},{"id":"Lab","x":160,"y":320},{"id":"Dev 1","x":128,"y":528},{"id":"Dev 2","x":512,"y":576},{"id":"Support 1","x":896,"y":112},{"id":"Shared","x":912,"y":304},{"id":"Ops 1","x":896,"y":544}],"edges":[{"from":"Core","to":"Sales"},{"from":"Core","to":"Support"},{"from":"Core","to":"Ops"},{"from":"Core","to":"Dev"},{"from":"Sales","to":"Uplink"},{"from":"Sales","to":"Sales 1"},{"from":"Sales","to":"Lab"},{"from":"Support","to":"Uplink"},{"from":"Support","to":"Support 1"},{"from":"Support","to":"Shared"},{"from":"Ops","to":"Shared"},{"from":"Ops","to":"Ops 1"},{"from":"Dev","to":"Lab"},{"from":"Dev","to":"Dev 1"},{"from":"Dev","to":"Dev 2"},{"from":"Lab","to":"Dev 1"}],"details":{"vertices":13,"edges":16,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.20512820512820512,"degree":{"min":1,"avg":2.4615384615384617,"max":4},"selfLoops":0,"components":1}},"problem":"Split the office network into 3 parts and try to cut as few cables as possible.","params":{"k":3},"result":{"kind":"cut","groups":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab","Dev 1","Dev 2","Shared"],["Support 1"],["Ops 1"]],"edges":[["Ops","Ops 1"],["Support","Support 1"]]},"answer":"On this run, the cut splits the vertices into 3 groups, of 11, 1 and 1 vertices, and cuts 2 edges: Ops and Ops 1; Support and Support 1.","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, 11 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 13 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 = 3 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":[["Core"],["Sales"],["Support"],["Ops"],["Dev"],["Uplink"],["Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Core and Sales. Core and Sales form a supernode of 2 vertices. 12 supernodes are left.","ops":[{"v":"Core","state":"current"},{"v":"Sales","state":"current"},{"e":["Core","Sales"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales"],["Support"],["Ops"],["Dev"],["Uplink"],["Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Core and Support. Support joins the supernode of Core and Sales, which now has 3 vertices. 11 supernodes are left.","ops":[{"v":"Core","state":"done"},{"v":"Sales","state":"done"},{"v":"Core","state":"current"},{"v":"Support","state":"current"},{"e":["Core","Support"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support"],["Ops"],["Dev"],["Uplink"],["Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Core and Ops. Ops joins the supernode of Core, Sales and Support, which now has 4 vertices. 10 supernodes are left.","ops":[{"v":"Core","state":"done"},{"v":"Support","state":"done"},{"v":"Core","state":"current"},{"v":"Ops","state":"current"},{"e":["Core","Ops"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops"],["Dev"],["Uplink"],["Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Core and Dev. Dev joins the supernode that holds Core, which now has 5 vertices. 9 supernodes are left.","ops":[{"v":"Core","state":"done"},{"v":"Ops","state":"done"},{"v":"Core","state":"current"},{"v":"Dev","state":"current"},{"e":["Core","Dev"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev"],["Uplink"],["Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Sales and Uplink. Uplink joins the supernode that holds Sales, which now has 6 vertices. The edge between Support and Uplink joined the same two supernodes, so it now lies inside the new one and is dropped. 8 supernodes are left.","ops":[{"v":"Core","state":"done"},{"v":"Dev","state":"done"},{"v":"Sales","state":"current"},{"v":"Uplink","state":"current"},{"e":["Sales","Uplink"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev","Uplink"],["Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Sales and Sales 1. Sales 1 joins the supernode that holds Sales, which now has 7 vertices. 7 supernodes are left.","ops":[{"v":"Sales","state":"done"},{"v":"Uplink","state":"done"},{"v":"Sales","state":"current"},{"v":"Sales 1","state":"current"},{"e":["Sales","Sales 1"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1"],["Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Sales and Lab. Lab joins the supernode that holds Sales, which now has 8 vertices. The edge between Dev and Lab joined the same two supernodes, so it now lies inside the new one and is dropped. 6 supernodes are left.","ops":[{"v":"Sales","state":"done"},{"v":"Sales 1","state":"done"},{"v":"Sales","state":"current"},{"v":"Lab","state":"current"},{"e":["Sales","Lab"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab"],["Dev 1"],["Dev 2"],["Support 1"],["Shared"],["Ops 1"]]}]},{"say":"Contract the edge between Support and Shared. Shared joins the supernode that holds Support, which now has 9 vertices. The edge between Ops and Shared joined the same two supernodes, so it now lies inside the new one and is dropped. 5 supernodes are left.","ops":[{"v":"Sales","state":"done"},{"v":"Lab","state":"done"},{"v":"Support","state":"current"},{"v":"Shared","state":"current"},{"e":["Support","Shared"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab","Shared"],["Dev 1"],["Dev 2"],["Support 1"],["Ops 1"]]}]},{"say":"Contract the edge between Dev and Dev 1. Dev 1 joins the supernode that holds Dev, which now has 10 vertices. The edge between Lab and Dev 1 joined the same two supernodes, so it now lies inside the new one and is dropped. 4 supernodes are left.","ops":[{"v":"Support","state":"done"},{"v":"Shared","state":"done"},{"v":"Dev","state":"current"},{"v":"Dev 1","state":"current"},{"e":["Dev","Dev 1"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab","Dev 1","Shared"],["Dev 2"],["Support 1"],["Ops 1"]]}]},{"say":"Contract the edge between Dev and Dev 2. Dev 2 joins the supernode that holds Dev, which now has 11 vertices. That leaves k = 3 supernodes.","ops":[{"v":"Dev","state":"done"},{"v":"Dev 1","state":"done"},{"v":"Dev","state":"current"},{"v":"Dev 2","state":"current"},{"e":["Dev","Dev 2"],"state":"tree"},{"panel":"supernodes","groups":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab","Dev 1","Dev 2","Shared"],["Support 1"],["Ops 1"]]}]},{"say":"Done. After 10 contractions, k = 3 supernodes are left, so the contraction stops. The 2 edges between different supernodes form the cut. Every vertex now shows its supernode.","ops":[{"v":"Core","state":"component-1"},{"v":"Sales","state":"component-1"},{"v":"Support","state":"component-1"},{"v":"Ops","state":"component-1"},{"v":"Dev","state":"component-1"},{"v":"Uplink","state":"component-1"},{"v":"Sales 1","state":"component-1"},{"v":"Lab","state":"component-1"},{"v":"Dev 1","state":"component-1"},{"v":"Dev 2","state":"component-1"},{"v":"Shared","state":"component-1"},{"v":"Support 1","state":"single"},{"v":"Ops 1","state":"single"},{"e":["Support","Support 1"],"state":"cut"},{"e":["Ops","Ops 1"],"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, 3)\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}"}
