Randomized k-cut

Splits an undirected graph into k groups by merging the ends of random edges until k groups are left, and cuts the edges between them.

Time complexity O(V·E), gograph function partition.RandomizedKCut.

gograph picks the edges to contract at random, so the cut can change each time the server restarts.

Maze

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.

An undirected graph with 30 vertices and 31 edges.

Split the maze into 4 regions and try to close as few passages as possible.

Use it in Go

cut, err := partition.RandomizedKCut(g, 4)
if err != nil {
	return err
}
for _, group := range cut.Supernodes {
	var members []string
	for _, v := range group {
		members = append(members, v.Label())
	}
	fmt.Println(members)
}
for _, e := range cut.CutEdges {
	fmt.Println(e.Source().Label(), e.Destination().Label())
}

Example graphs

• Friend groups, 12 vertices and 21 edges
• Office network, 13 vertices and 16 edges
• Maze, 30 vertices and 31 edges
• Karate club, 34 vertices and 78 edges

More in Partitioning

• Maximal cliques: Finds every group of vertices that are all adjacent to each other and can't take one more vertex.
• Girvan-Newman: Splits an undirected graph into k communities by removing, one at a time, the edge that the most shortest paths cross.

All algorithms