1-cliques: Vertices. You already have this.

2-cliques: Edges. You already have this.

3-cliques: Triangles. For every edge, compute the intersecion of the neighborhoods of both vertices. Both are sorted arrays, so this is fast (you need a specialized function for this!).

4-cliques: Let `link(p,q)`

be the intersection computed for the 3-cliques. Now, for each z in `link(p,q)`

you intersect the neigborhood of z with the link (again, intersection of two sorted lists of integers)

5-cliques: You store all the 4-cliques from the last step into a bitmap. In other words, you compute the induced subgraph on `link(p,q)`

. Now you are interested in triangles in this small graph; and the graph is already stored as a bitmap. Iterate over edges, take the intersection of neighborhoods (which is probably a single bitwise AND, if your links have <= 64 vertices; depending on your SIMD width it is almost surely a single vector bitwise AND instruction).

6-cliques: Repeat obvious recursive algorithm.

7-cliques: Repeat obvious recursive algorithm.

You can take code from https://github.com/chethega/BitmapGraphs for bitmapped graphs. This has most of the required pieces (you may need to adapt some things). It already contains the code for constructing a bitmap representation of the link of an edge in a lightgraph, so you get 3-cliques and 4-cliques without writing anything yourself.

I strongly recommend to use the `SBMGraph{N}`

variant. This induces a single dynamic dispatch for each edge, but then the 5-7 cliques are allocation free, all loops unrolled, etc. I should probably make this a real package at some time, and make the types explicit `VecElement`

to help the compiler figure out that it should SIMD, but you can start with this.

PS. Feel free to join the #graphs channel on slack, open issues on my non-package, or just take code and run with it.

PPS. Bitmap means in this context a datastructure for a graph where every edge is a single bit (1 if edge is present, 0 if not present), and you have aligned rows, i.e. `neighbors(g, i)`

always starts at a 64-bit boundary (i.e. an UInt64). This basically means that you round up the number of vertices to a multiple of 64, and then use a `BitMatrix`

. It is very helpful to store the number of `UInt64`

that represent `neighbors(g, i)`

in the type, which is what `SBMGraph{N}`

does. That way, all loops over the chunks are fully unrolled and typically a single instruction (for small `N`

, which is what you care about). Relevant not-super-trivial parts are only a bit of pointer arithmetic (in order to quickly manipulate the underlying tuple types) and the fast iteration over bits in a tuple (same code as Base logical indexing by bitarray, i.e. tzcnt and blsr instructions), as well as API design (my API kinda sucks).