Thomas G. Kristensen wrote a nice little post about finding cliques in a graph with core.logic. I recommended reading it first before continuing. It's a very short informative post and the code is clear if you have at least some familiarity with core.logic. At the end of his post he points out a couple of problems - it's about 1000X slower and worse, it doesn't terminate if you specify some number of desired results above 22.

There were a couple of very minor things about his approach that bugged me but figuring out the termination issue really got me thinking. I realized that the issue with his program is that all-connected-to-allo would continue to search for answers even though there weren't anymore to find! That is all-connected-to-allo continues searching for cliques of size n even if n is greater than the number of vertices in the graph.

Prior to cKanren expressing a bounded list relation would have been quite difficult. It's now possible to do this in a relational manner.

This relation guarantees that the size of a list can never exceed n. We can now use this relation to ensure that the clique list never exceeds 6, the number of vertices in the graph we are querying.

Here is the full program:

And it's fast - on my machine this finds all cliques (20) in ~3.5-4ms. Even better if you don't specify how many answers you want it will always terminate.

bounded-listo is so useful I've added it to core.logic.