{"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":"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":"Which groups of switches and rooms are all wired to each other, where nothing else is wired to all of them?","params":{},"result":{"kind":"sets","sets":[["Core","Dev"],["Core","Ops"],["Core","Sales"],["Core","Support"],["Dev","Dev 1","Lab"],["Dev","Dev 2"],["Lab","Sales"],["Ops","Ops 1"],["Ops","Shared"],["Sales","Sales 1"],["Sales","Uplink"],["Shared","Support"],["Support","Support 1"],["Support","Uplink"]]},"answer":"The graph has 14 maximal cliques. The largest has 3 vertices: Dev, Dev 1 and Lab.","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":"Sales 1"},{"key":"Dev 2"},{"key":"Support 1"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Ops"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]}]},{"say":"Start from Sales 1, the first vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Sales to R. P and X are both empty, so no other vertex is adjacent to both Sales 1 and Sales. Record them as maximal clique 1.","ops":[{"v":"Sales","state":"current"},{"v":"Sales 1","state":"current"},{"e":["Sales 1","Sales"],"state":"tree"},{"panel":"r","list":[{"key":"Sales 1"},{"key":"Sales"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Dev 2"},{"key":"Support 1"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Ops"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"]]}]},{"say":"Start from Dev 2, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Dev to R. P and X are both empty, so no other vertex is adjacent to both Dev 2 and Dev. Record them as maximal clique 2.","ops":[{"v":"Sales","state":"idle"},{"v":"Dev","state":"current"},{"v":"Sales 1","state":"idle"},{"v":"Dev 2","state":"current"},{"e":["Sales 1","Sales"],"state":"idle"},{"e":["Dev 2","Dev"],"state":"tree"},{"panel":"r","list":[{"key":"Dev 2"},{"key":"Dev"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Support 1"},{"key":"Ops 1"},{"key":"Shared"},{"key":"Ops"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"]]}]},{"say":"Start from Support 1, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Support to R. P and X are both empty, so no other vertex is adjacent to both Support 1 and Support. Record them as maximal clique 3.","ops":[{"v":"Support","state":"current"},{"v":"Dev","state":"idle"},{"v":"Dev 2","state":"idle"},{"v":"Support 1","state":"current"},{"e":["Dev 2","Dev"],"state":"idle"},{"e":["Support 1","Support"],"state":"tree"},{"panel":"r","list":[{"key":"Support 1"},{"key":"Support"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Ops 1"},{"key":"Shared"},{"key":"Ops"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"]]}]},{"say":"Start from Ops 1, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Ops to R. P and X are both empty, so no other vertex is adjacent to both Ops 1 and Ops. Record them as maximal clique 4.","ops":[{"v":"Support","state":"idle"},{"v":"Ops","state":"current"},{"v":"Support 1","state":"idle"},{"v":"Ops 1","state":"current"},{"e":["Support 1","Support"],"state":"idle"},{"e":["Ops 1","Ops"],"state":"tree"},{"panel":"r","list":[{"key":"Ops 1"},{"key":"Ops"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Shared"},{"key":"Ops"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"]]}]},{"say":"Start from Shared, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Support to R. P and X are both empty, so no other vertex is adjacent to both Shared and Support. Record them as maximal clique 5.","ops":[{"v":"Support","state":"current"},{"v":"Ops","state":"idle"},{"v":"Shared","state":"current"},{"v":"Ops 1","state":"idle"},{"e":["Ops 1","Ops"],"state":"idle"},{"e":["Shared","Support"],"state":"tree"},{"panel":"r","list":[{"key":"Shared"},{"key":"Support"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Ops"},{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"]]}]},{"say":"Back up until R holds only Shared, then add Ops. P and X are both empty, so no other vertex is adjacent to both Shared and Ops. Record them as maximal clique 6.","ops":[{"v":"Support","state":"idle"},{"v":"Ops","state":"current"},{"e":["Shared","Support"],"state":"idle"},{"e":["Shared","Ops"],"state":"tree"},{"panel":"r","list":[{"key":"Shared"},{"key":"Ops"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"]]}]},{"say":"Start from Ops, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Core to R. P and X are both empty, so no other vertex is adjacent to both Ops and Core. Record them as maximal clique 7.","ops":[{"v":"Core","state":"current"},{"v":"Shared","state":"idle"},{"e":["Shared","Ops"],"state":"idle"},{"e":["Ops","Core"],"state":"tree"},{"panel":"r","list":[{"key":"Ops"},{"key":"Core"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Dev 1"},{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"]]}]},{"say":"Start from Dev 1, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Dev and Lab to R. P and X are both empty, so no other vertex is adjacent to all of Dev 1, Dev and Lab. Record them as maximal clique 8.","ops":[{"v":"Core","state":"idle"},{"v":"Ops","state":"idle"},{"v":"Dev","state":"current"},{"v":"Lab","state":"current"},{"v":"Dev 1","state":"current"},{"e":["Ops","Core"],"state":"idle"},{"e":["Dev 1","Dev"],"state":"tree"},{"e":["Dev 1","Lab"],"state":"tree"},{"e":["Dev","Lab"],"state":"tree"},{"panel":"r","list":[{"key":"Dev 1"},{"key":"Dev"},{"key":"Lab"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Lab"},{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"]]}]},{"say":"Start from Lab, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Sales to R. P and X are both empty, so no other vertex is adjacent to both Lab and Sales. Record them as maximal clique 9.","ops":[{"v":"Sales","state":"current"},{"v":"Dev","state":"idle"},{"v":"Dev 1","state":"idle"},{"e":["Dev 1","Dev"],"state":"idle"},{"e":["Dev 1","Lab"],"state":"idle"},{"e":["Dev","Lab"],"state":"idle"},{"e":["Lab","Sales"],"state":"tree"},{"panel":"r","list":[{"key":"Lab"},{"key":"Sales"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Dev"},{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"],["Lab","Sales"]]}]},{"say":"Start from Dev, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Core to R. P and X are both empty, so no other vertex is adjacent to both Dev and Core. Record them as maximal clique 10.","ops":[{"v":"Core","state":"current"},{"v":"Sales","state":"idle"},{"v":"Dev","state":"current"},{"v":"Lab","state":"idle"},{"e":["Lab","Sales"],"state":"idle"},{"e":["Dev","Core"],"state":"tree"},{"panel":"r","list":[{"key":"Dev"},{"key":"Core"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Uplink"},{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"],["Lab","Sales"],["Dev","Core"]]}]},{"say":"Start from Uplink, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Sales to R. P and X are both empty, so no other vertex is adjacent to both Uplink and Sales. Record them as maximal clique 11.","ops":[{"v":"Core","state":"idle"},{"v":"Sales","state":"current"},{"v":"Dev","state":"idle"},{"v":"Uplink","state":"current"},{"e":["Dev","Core"],"state":"idle"},{"e":["Uplink","Sales"],"state":"tree"},{"panel":"r","list":[{"key":"Uplink"},{"key":"Sales"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Sales"},{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"],["Lab","Sales"],["Dev","Core"],["Uplink","Sales"]]}]},{"say":"Back up until R holds only Uplink, then add Support. P and X are both empty, so no other vertex is adjacent to both Uplink and Support. Record them as maximal clique 12.","ops":[{"v":"Sales","state":"idle"},{"v":"Support","state":"current"},{"e":["Uplink","Sales"],"state":"idle"},{"e":["Uplink","Support"],"state":"tree"},{"panel":"r","list":[{"key":"Uplink"},{"key":"Support"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"],["Lab","Sales"],["Dev","Core"],["Uplink","Sales"],["Uplink","Support"]]}]},{"say":"Start from Sales, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Core to R. P and X are both empty, so no other vertex is adjacent to both Sales and Core. Record them as maximal clique 13.","ops":[{"v":"Core","state":"current"},{"v":"Sales","state":"current"},{"v":"Support","state":"idle"},{"v":"Uplink","state":"idle"},{"e":["Uplink","Support"],"state":"idle"},{"e":["Sales","Core"],"state":"tree"},{"panel":"r","list":[{"key":"Sales"},{"key":"Core"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Support"},{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"],["Lab","Sales"],["Dev","Core"],["Uplink","Sales"],["Uplink","Support"],["Sales","Core"]]}]},{"say":"Start from Support, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. Add Core to R. P and X are both empty, so no other vertex is adjacent to both Support and Core. Record them as maximal clique 14.","ops":[{"v":"Sales","state":"idle"},{"v":"Support","state":"current"},{"e":["Sales","Core"],"state":"idle"},{"e":["Support","Core"],"state":"tree"},{"panel":"r","list":[{"key":"Support"},{"key":"Core"}]},{"panel":"p","list":[]},{"panel":"x","list":[]},{"panel":"starts","list":[{"key":"Core"}]},{"panel":"cliques","groups":[["Sales 1","Sales"],["Dev 2","Dev"],["Support 1","Support"],["Ops 1","Ops"],["Shared","Support"],["Shared","Ops"],["Ops","Core"],["Dev 1","Dev","Lab"],["Lab","Sales"],["Dev","Core"],["Uplink","Sales"],["Uplink","Support"],["Sales","Core"],["Support","Core"]]}]},{"say":"Start from Core, the next vertex in degeneracy order, with its later neighbors in P and its earlier ones in X. P is empty, but all 4 vertices in X are adjacent to Core, so R is not a maximal clique. The cliques that extend it were listed already. Back up.","ops":[{"v":"Sales","state":"done"},{"v":"Support","state":"done"},{"v":"Ops","state":"done"},{"v":"Dev","state":"done"},{"e":["Support","Core"],"state":"idle"},{"panel":"r","list":[{"key":"Core"}]},{"panel":"p","list":[]},{"panel":"x","list":[{"key":"Sales"},{"key":"Support"},{"key":"Ops"},{"key":"Dev"}]},{"panel":"starts","list":[]}]},{"say":"Done. Every vertex has been a start, and the search found 14 maximal cliques. The biggest has 3 vertices.","ops":[{"v":"Core","state":"idle"},{"v":"Sales","state":"idle"},{"v":"Support","state":"idle"},{"v":"Ops","state":"idle"},{"v":"Dev","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}"}
