Chapter III Clique

Bron–Kerbosch in C++

The classical algorithm for enumerating maximal cliques. With pivoting, it is roughly the best you can do.

01

Represent the graph as adjacency bitsets — for n ≤ 64 vertices, a single uint64_t per vertex. Set intersection becomes a bitwise AND, which is the inner loop of clique enumeration.
```
#include <cstdint>
#include <vector>
using Bits = uint64_t;
std::vector<Bits> adj;  // adj[v] = neighbors of v as bitmask
```

Bron–Kerbosch with Tomita's pivot. R is the clique being built, P the candidates, X the already-explored. The pivot u minimizes branching by skipping anyone adjacent to it.

void bk(Bits R, Bits P, Bits X, std::vector<Bits>& out) {
  if (P == 0 && X == 0) { out.push_back(R); return; }
  Bits PX = P | X;
  int pivot = __builtin_ctzll(PX);
  Bits cand = P & ~adj[pivot];
  while (cand) {
    int v = __builtin_ctzll(cand);
    Bits vbit = 1ULL << v;
    bk(R | vbit, P & adj[v], X & adj[v], out);
    P &= ~vbit; X |= vbit; cand &= ~vbit;
  }
}

Drive it from main, then keep the largest result. The bitset trick (__builtin_ctzll picks the lowest set bit; popcount counts set bits) is the reason this kernel screams on modern CPUs.

Bits all = (1ULL << n) - 1;
std::vector<Bits> cliques;
bk(0, all, 0, cliques);
auto best = *std::max_element(cliques.begin(), cliques.end(),
  [](Bits a, Bits b){ return __builtin_popcountll(a) < __builtin_popcountll(b); });

04

For n > 64, swap uint64_t for std::vector<uint64_t> and the same idea generalizes. Industrial implementations (like cliquer) add degeneracy ordering on top — a 2× to 10× speedup on real-world graphs.
```
// std::bitset<N> works too if N is known at compile time.
// For variable n, std::vector<uint64_t> with manual word ops
// stays cache-friendly enough.
```

Grammar — C++

C++ gives you the bare metal: explicit types, manual memory, and intrinsics that map almost 1:1 onto CPU instructions. Bitset graph algorithms are exactly where that pays off.

#include <h>: pull in a header. Standard library headers go in angle brackets; project headers in quotes.
using T = ...;: a type alias — Bits becomes a synonym for uint64_t.
std::vector<T>: a heap-allocated growable array. Pass by const& to avoid copies.
1ULL << v: unsigned-long-long literal 1, shifted left by v bits — that is, a bitmask with only bit v set.
__builtin_ctzll(x): GCC/Clang intrinsic: count trailing zeros, i.e. the position of the lowest set bit. One CPU instruction.
__builtin_popcountll(x): count the number of 1 bits. Another single instruction on modern x86.
[](Bits a){ ... }: a lambda — anonymous function. The square brackets are the capture list.
auto x = expr;: type inference. The compiler picks the type from the right-hand side.
std::max_element(b, e, cmp): returns an iterator to the maximum element under cmp. Dereference with * to get the value.

Represent which vertices are adjacent to v as a single 64-bit integer: bit i is 1 if there is an edge v–i, 0 otherwise. Then common neighbors of u and v is just one bitwise AND.

Bits adj_u = 0b00110100;  // u's neighbors: bits 2, 4, 5
Bits adj_v = 0b01100100;  // v's neighbors: bits 2, 5, 6
Bits common = adj_u & adj_v;          // 0b00100100 — bits 2 and 5
int first  = __builtin_ctzll(common); // -> 2
int count  = __builtin_popcountll(common); // -> 2

Compiler Explorer — try C++ and see the assembly →