In this recent post I described a Clojure implementation of the Bron Kerbosch algorithm for finding maximum cliques. In my finishing statement, I mentioned that the Bron Kerbosch algorithm is somewhat similar to the algorithm employed by miniKanren and core.logic when looking for solutions to relational systems. I’ve since implemented a version of the algorithm in core.logic. I guess it’s slightly misleading to say I’ve implemented an algorithm – rather, I have defined, in core.logic, what it means to be a clique and asked core.logic to do the rest of the work!

In my original post, I investigated the graph presented below:

In my Bron Kerbosch implementation, this graph could be represented as the following map:

In core.logic, we can define a relation indicating that two numbers are connected, and in that manner describe the graph:

To declare that a set of numbers are a clique, every number in the set has to be `connected`

to every other number in the set. A prerequisit to this is, that one number should be connected to every other number in a set. The method `connected-to-allo`

checks that, given an element `u`

and a set of elements `l`

, `u`

is connected to every other element in a recursive manner

Now, given `connected-to-allo`

, declaring the relation that *all* elements should be connected is done in a similar manner, here in the function `all-connected-to-allo`

Now, given `second function name`

and the `connection`

relation on numbers, we can find *all* the cliques in the graph

The problem is that if we ask for more cliques than there actually is in the system, core.logic is going to continue forever:

That’s a major drawback that I haven’t worked out how to avoid yet. Also, we are given *all* cliques, not only the maximum. We could probably define a criteria that restricts the size of `q`

so that only big cliques are found and then search for a maximum `q`

instead in the manner of linear program. This doesn’t seem like the right way of doing this, so input as to how to solve optimisation problems with logic programming is more than welcome.

An upside to just having to define the relations is that we can now ask other questions, without having to implement any algorithms. For example, say we wanted to find three cliques containing the number 5

Amazing! That’s is certainly one of the most mind-bending things about logic programming: how easy it is to reuse relations and build bigger programs of simple compontents.

Now for the nasty details: how slow is it? Running the core.logic version on the problem a couple of times yields the following results:

Whereas the original algorithm is a fair bit faster, about a factor of a hundred

Bear in mind that the core.logic version solves a much more general problem, and that it is much easier to combine with other criteria to answer much more interesting problems. For example, you could easily define that all nodes in a clique should be of the same colour, have the same number of outgoing edges, etc…

I would be very interested in getting input on how to solve optimisation problems such as this in core.logic. So far, I’ve only declared what being a clique is, not what being a biggest clique is. Also, I wonder if it is possible to declare that the `connected`

relation is symmetrical.

If you haven’t already, go and check out core.logic. It’s great fun! Here’s an excellent introductory talk, another one, and a great one about miniKanren.

David Nolen, being a gentleman and a scholar, has been so kind as to look into my problem! In this post he adds indexes and, more interestingly, defines an upper bound on the size of an answer. In my problem, any clique’s size is bounded by the total number of nodes, forming a termination criteria. See his blog post for the definition of `bounded-listo`

, and a rewrite of my `connected-to-allo`

and `all-connected-to-allo`

relations.

comments powered by Disqus