Maximal cliques

Finds every group of vertices that are all adjacent to each other and can't take one more vertex.

Time complexity O(3^(V/3)), gograph function partition.MaximalCliques.

Office network

Switches and rooms in a four-team office, wired through a core switch.

An undirected graph with 13 vertices and 16 edges.

Which groups of switches and rooms are all wired to each other, where nothing else is wired to all of them?

Use it in Go

for _, clique := range partition.MaximalCliques(g) {
	var names []string
	for _, v := range clique {
		names = append(names, v.Label())
	}
	fmt.Println(strings.Join(names, ", "))
}

Example graphs

• Friend groups, 12 vertices and 21 edges
• Office network, 13 vertices and 16 edges
• Karate club, 34 vertices and 78 edges
• Campus network, 100 vertices and 114 edges

More in Partitioning

• Girvan-Newman: Splits an undirected graph into k communities by removing, one at a time, the edge that the most shortest paths cross.
• 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.

All algorithms