{"algorithm":"maximal-cliques","about":["A clique is a set of vertices where every two are joined by an edge. It is maximal when no other vertex is joined to all of them, so it can't grow. partition.MaximalCliques lists every maximal clique with the Bron-Kerbosch algorithm. It grows a clique one vertex at a time from a set of candidates, and keeps the vertices it has already tried so that no clique is listed twice.","gograph adds three things that make it faster. It starts from the vertices in degeneracy order, which keeps the candidate sets small in sparse graphs. At each step it picks a pivot and only branches on candidates that aren't the pivot's neighbors, since every maximal clique holds the pivot or one of those. And it stores the sets as bitsets, so comparing them is quick.","A graph can have up to 3^(V/3) maximal cliques, so no method is fast on every graph, but real networks are usually sparse enough. Edge directions are ignored, and so are self-loops. Use it to find tight groups of friends or devices that are all linked, where one vertex can belong to several groups."],"template":{"id":"friend-groups","name":"Friend groups","description":"Twelve friends in three circles: a climbing group, a book club and a band. Each edge joins two friends. Eli climbs and reads, and Hana reads and plays in the band, so each of them links two circles.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"Ana","x":120,"y":160},{"id":"Ben","x":380,"y":120},{"id":"Cara","x":400,"y":380},{"id":"Dev","x":140,"y":420},{"id":"Eli","x":320,"y":620},{"id":"Fay","x":520,"y":560},{"id":"Gus","x":500,"y":840},{"id":"Hana","x":700,"y":700},{"id":"Ivo","x":640,"y":440},{"id":"Jun","x":860,"y":520},{"id":"Kai","x":640,"y":200},{"id":"Lea","x":880,"y":260}],"edges":[{"from":"Ana","to":"Ben"},{"from":"Ana","to":"Cara"},{"from":"Ana","to":"Dev"},{"from":"Ben","to":"Cara"},{"from":"Ben","to":"Dev"},{"from":"Cara","to":"Dev"},{"from":"Cara","to":"Eli"},{"from":"Dev","to":"Eli"},{"from":"Eli","to":"Fay"},{"from":"Eli","to":"Gus"},{"from":"Fay","to":"Gus"},{"from":"Fay","to":"Hana"},{"from":"Gus","to":"Hana"},{"from":"Hana","to":"Ivo"},{"from":"Hana","to":"Jun"},{"from":"Ivo","to":"Jun"},{"from":"Ivo","to":"Kai"},{"from":"Ivo","to":"Lea"},{"from":"Jun","to":"Kai"},{"from":"Jun","to":"Lea"},{"from":"Kai","to":"Lea"}],"details":{"vertices":12,"edges":21,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.3181818181818182,"degree":{"min":3,"avg":3.5,"max":4},"selfLoops":0,"components":1}},"problem":"Which groups of friends all know each other, where no one else knows everyone in the group?","params":{},"result":{"kind":"sets","sets":[["Ana","Ben","Cara","Dev"],["Cara","Dev","Eli"],["Eli","Fay","Gus"],["Fay","Gus","Hana"],["Hana","Ivo","Jun"],["Ivo","Jun","Kai","Lea"]]},"answer":"The graph has 6 maximal cliques. The 2 largest have 4 vertices each: Ana, Ben, Cara and Dev; Ivo, Jun, Kai and Lea.","legend":{"vertex":[{"id":"idle","label":"Not in R, P or X","color":"#64748B","shape":"hollow"},{"id":"waiting","label":"In P, can join R","color":"#E69F00","shape":"dashed-square"},{"id":"current","label":"In R, the clique so far","color":"#56B4E9","shape":"ring"},{"id":"done","label":"In X, already covered","color":"#009E73","shape":"filled"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"tree","label":"Joins two vertices of R","color":"#009E73","shape":"thick"}],"panels":[{"id":"r","title":"R, the clique so far","kind":"list"},{"id":"p","title":"P, can join R","kind":"list"},{"id":"x","title":"X, already covered","kind":"list"},{"id":"starts","title":"Starts left, in degeneracy order","kind":"list"},{"id":"cliques","title":"Maximal cliques found","kind":"groups"}]},"steps":[{"say":"Bron-Kerbosch grows a clique R. P holds the vertices that can still join R, and X holds the ones that could join but whose cliques were listed already. The search starts once from each vertex, in degeneracy order: repeatedly remove the vertex with the fewest neighbors left. That keeps P small. Each call picks a pivot in P or X with the most neighbors in P and tries only the vertices of P that are not its neighbors.","ops":[{"panel":"starts","list":[{"key":"Ana"},{"key":"Ben"},{"key":"Cara"},{"key":"Dev"},{"key":"Eli"},{"key":"Fay"},{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]}]},{"say":"Start from Ana, the first vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Ben, Cara and Dev to R. P and X are both empty, so no other vertex is adjacent to all of Ana, Ben, Cara and Dev. Record them as maximal clique 1.","ops":[{"v":"Ana","state":"current"},{"v":"Ben","state":"current"},{"v":"Cara","state":"current"},{"v":"Dev","state":"current"},{"e":["Ana","Ben"],"state":"tree"},{"e":["Ana","Cara"],"state":"tree"},{"e":["Ana","Dev"],"state":"tree"},{"e":["Ben","Cara"],"state":"tree"},{"e":["Ben","Dev"],"state":"tree"},{"e":["Cara","Dev"],"state":"tree"},{"panel":"r","list":[{"key":"Ana"},{"key":"Ben"},{"key":"Cara"},{"key":"Dev"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Ben"},{"key":"Cara"},{"key":"Dev"},{"key":"Eli"},{"key":"Fay"},{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"cliques","groups":[["Ana","Ben","Cara","Dev"]]}]},{"say":"Start from Ben, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. The pivot, Ana, is in X and adjacent to every vertex in R and P, so every clique grown from here could also take Ana. Those cliques were listed already. Back up.","ops":[{"v":"Ana","state":"done"},{"v":"Cara","state":"waiting"},{"v":"Dev","state":"waiting"},{"e":["Ana","Ben"],"state":"idle"},{"e":["Ana","Cara"],"state":"idle"},{"e":["Ana","Dev"],"state":"idle"},{"e":["Ben","Cara"],"state":"idle"},{"e":["Ben","Dev"],"state":"idle"},{"e":["Cara","Dev"],"state":"idle"},{"panel":"r","list":[{"key":"Ben"}]},{"panel":"p","list":[{"key":"Cara"},{"key":"Dev"}]},{"panel":"x","list":[{"key":"Ana"}]},{"panel":"starts","list":[{"key":"Cara"},{"key":"Dev"},{"key":"Eli"},{"key":"Fay"},{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]}]},{"say":"Start from Cara, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Eli and Dev to R. P and X are both empty, so no other vertex is adjacent to all of Cara, Eli and Dev. Record them as maximal clique 2.","ops":[{"v":"Ana","state":"idle"},{"v":"Ben","state":"idle"},{"v":"Cara","state":"current"},{"v":"Dev","state":"current"},{"v":"Eli","state":"current"},{"e":["Cara","Eli"],"state":"tree"},{"e":["Cara","Dev"],"state":"tree"},{"e":["Eli","Dev"],"state":"tree"},{"panel":"r","list":[{"key":"Cara"},{"key":"Eli"},{"key":"Dev"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Dev"},{"key":"Eli"},{"key":"Fay"},{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"cliques","groups":[["Ana","Ben","Cara","Dev"],["Cara","Eli","Dev"]]}]},{"say":"Start from Dev, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. The pivot, Cara, is in X and adjacent to every vertex in R and P, so every clique grown from here could also take Cara. Those cliques were listed already. Back up.","ops":[{"v":"Ana","state":"done"},{"v":"Ben","state":"done"},{"v":"Cara","state":"done"},{"v":"Eli","state":"waiting"},{"e":["Cara","Eli"],"state":"idle"},{"e":["Cara","Dev"],"state":"idle"},{"e":["Eli","Dev"],"state":"idle"},{"panel":"r","list":[{"key":"Dev"}]},{"panel":"p","list":[{"key":"Eli"}]},{"panel":"x","list":[{"key":"Ana"},{"key":"Ben"},{"key":"Cara"}]},{"panel":"starts","list":[{"key":"Eli"},{"key":"Fay"},{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]}]},{"say":"Start from Eli, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Fay and Gus to R. P and X are both empty, so no other vertex is adjacent to all of Eli, Fay and Gus. Record them as maximal clique 3.","ops":[{"v":"Ana","state":"idle"},{"v":"Ben","state":"idle"},{"v":"Cara","state":"idle"},{"v":"Dev","state":"idle"},{"v":"Eli","state":"current"},{"v":"Fay","state":"current"},{"v":"Gus","state":"current"},{"e":["Eli","Fay"],"state":"tree"},{"e":["Eli","Gus"],"state":"tree"},{"e":["Fay","Gus"],"state":"tree"},{"panel":"r","list":[{"key":"Eli"},{"key":"Fay"},{"key":"Gus"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Fay"},{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"cliques","groups":[["Ana","Ben","Cara","Dev"],["Cara","Eli","Dev"],["Eli","Fay","Gus"]]}]},{"say":"Start from Fay, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Hana and Gus to R. P and X are both empty, so no other vertex is adjacent to all of Fay, Hana and Gus. Record them as maximal clique 4.","ops":[{"v":"Eli","state":"idle"},{"v":"Hana","state":"current"},{"e":["Eli","Fay"],"state":"idle"},{"e":["Eli","Gus"],"state":"idle"},{"e":["Fay","Hana"],"state":"tree"},{"e":["Hana","Gus"],"state":"tree"},{"panel":"r","list":[{"key":"Fay"},{"key":"Hana"},{"key":"Gus"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Gus"},{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"cliques","groups":[["Ana","Ben","Cara","Dev"],["Cara","Eli","Dev"],["Eli","Fay","Gus"],["Fay","Hana","Gus"]]}]},{"say":"Start from Gus, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. The pivot, Fay, is in X and adjacent to every vertex in R and P, so every clique grown from here could also take Fay. Those cliques were listed already. Back up.","ops":[{"v":"Eli","state":"done"},{"v":"Fay","state":"done"},{"v":"Hana","state":"waiting"},{"e":["Fay","Hana"],"state":"idle"},{"e":["Fay","Gus"],"state":"idle"},{"e":["Hana","Gus"],"state":"idle"},{"panel":"r","list":[{"key":"Gus"}]},{"panel":"p","list":[{"key":"Hana"}]},{"panel":"x","list":[{"key":"Eli"},{"key":"Fay"}]},{"panel":"starts","list":[{"key":"Hana"},{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]}]},{"say":"Start from Hana, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Ivo and Jun to R. P and X are both empty, so no other vertex is adjacent to all of Hana, Ivo and Jun. Record them as maximal clique 5.","ops":[{"v":"Eli","state":"idle"},{"v":"Fay","state":"idle"},{"v":"Gus","state":"idle"},{"v":"Hana","state":"current"},{"v":"Ivo","state":"current"},{"v":"Jun","state":"current"},{"e":["Hana","Ivo"],"state":"tree"},{"e":["Hana","Jun"],"state":"tree"},{"e":["Ivo","Jun"],"state":"tree"},{"panel":"r","list":[{"key":"Hana"},{"key":"Ivo"},{"key":"Jun"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"cliques","groups":[["Ana","Ben","Cara","Dev"],["Cara","Eli","Dev"],["Eli","Fay","Gus"],["Fay","Hana","Gus"],["Hana","Ivo","Jun"]]}]},{"say":"Start from Jun, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Ivo, Kai and Lea to R. P and X are both empty, so no other vertex is adjacent to all of Jun, Ivo, Kai and Lea. Record them as maximal clique 6.","ops":[{"v":"Hana","state":"idle"},{"v":"Kai","state":"current"},{"v":"Lea","state":"current"},{"e":["Hana","Ivo"],"state":"idle"},{"e":["Hana","Jun"],"state":"idle"},{"e":["Ivo","Jun"],"state":"idle"},{"e":["Jun","Ivo"],"state":"tree"},{"e":["Jun","Kai"],"state":"tree"},{"e":["Jun","Lea"],"state":"tree"},{"e":["Ivo","Kai"],"state":"tree"},{"e":["Ivo","Lea"],"state":"tree"},{"e":["Kai","Lea"],"state":"tree"},{"panel":"r","list":[{"key":"Jun"},{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Ivo"},{"key":"Kai"},{"key":"Lea"}]},{"panel":"cliques","groups":[["Ana","Ben","Cara","Dev"],["Cara","Eli","Dev"],["Eli","Fay","Gus"],["Fay","Hana","Gus"],["Hana","Ivo","Jun"],["Jun","Ivo","Kai","Lea"]]}]},{"say":"Start from Ivo, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. The pivot, Jun, is in X and adjacent to every vertex in R and P, so every clique grown from here could also take Jun. Those cliques were listed already. Back up.","ops":[{"v":"Hana","state":"done"},{"v":"Jun","state":"done"},{"v":"Kai","state":"waiting"},{"v":"Lea","state":"waiting"},{"e":["Jun","Ivo"],"state":"idle"},{"e":["Jun","Kai"],"state":"idle"},{"e":["Jun","Lea"],"state":"idle"},{"e":["Ivo","Kai"],"state":"idle"},{"e":["Ivo","Lea"],"state":"idle"},{"e":["Kai","Lea"],"state":"idle"},{"panel":"r","list":[{"key":"Ivo"}]},{"panel":"p","list":[{"key":"Kai"},{"key":"Lea"}]},{"panel":"x","list":[{"key":"Hana"},{"key":"Jun"}]},{"panel":"starts","list":[{"key":"Kai"},{"key":"Lea"}]}]},{"say":"Start from Kai, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. The pivot, Ivo, is in X and adjacent to every vertex in R and P, so every clique grown from here could also take Ivo. Those cliques were listed already. Back up.","ops":[{"v":"Hana","state":"idle"},{"v":"Ivo","state":"done"},{"v":"Kai","state":"current"},{"panel":"r","list":[{"key":"Kai"}]},{"panel":"p","list":[{"key":"Lea"}]},{"panel":"x","list":[{"key":"Ivo"},{"key":"Jun"}]},{"panel":"starts","list":[{"key":"Lea"}]}]},{"say":"Start from Lea, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. P is empty, but Ivo, Jun and Kai in X are adjacent to Lea, so R is not a maximal clique. The cliques that extend it were listed already. Back up.","ops":[{"v":"Kai","state":"done"},{"v":"Lea","state":"current"},{"panel":"r","list":[{"key":"Lea"}]},{"panel":"p","list":[]},{"panel":"x","list":[{"key":"Ivo"},{"key":"Jun"},{"key":"Kai"}]},{"panel":"starts","list":[]}]},{"say":"Done. Every vertex has been a start, and the search found 6 maximal cliques. The biggest has 4 vertices.","ops":[{"v":"Ivo","state":"idle"},{"v":"Jun","state":"idle"},{"v":"Kai","state":"idle"},{"v":"Lea","state":"idle"},{"panel":"r","list":[]},{"panel":"p","list":[]},{"panel":"x","list":[]}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"for _, clique := range partition.MaximalCliques(g) {\n\tvar names []string\n\tfor _, v := range clique {\n\t\tnames = append(names, v.Label())\n\t}\n\tfmt.Println(strings.Join(names, \", \"))\n}"}
