Looking for Prolog code for Clique

[Ulrich Scholz]

Hi, I'm looking for some Prolog code for Clique. Of course, there are
1000 ways to program it; some are better, some are not. And the best
way is not to program yourself :-) (It's not a homework assignment!).
I wouild be grateful if you could point me to some good code (in the
public domain).

The graph is undirected and is built incrementally. Once in a while,
I want to know for a subset of nodes N all largest cliques of the
graph that are covered by N.

I use ECLiPSe but probably could easily re-write code of other Prolog
dialects.

Thanks,

Ulrich

[Chip Eastham]

On Dec 30, 3:47 am, Ulrich Scholz <d...@thispla.net> wrote:
> Hi, I'm looking for some Prolog code for Clique.
> Of course, there are 1000 ways to program it;
> some are better, some are not. And the best
> way is not to program yourself :-) (It's not a
> homework assignment!).

Hi, Ulrich:

I'll assume you have in mind to find one or all
of maximal cliques in an undirected graph.

> I wouild be grateful if you could point me to
> some good code (in the public domain).

I don't know of any such code in the public
domain. SICStus Prolog implements a clique
predicate for undirected graphs, but their
licensing retains a copyright on the code.

Colin Barker has some code links here:

[LPA Win-Prolog Goodies]
http://pagesperso-orange.fr/colin.barker/lpa/lpa.htm

including one two-thirds of the way down
the list for "Maximum Clique of Graph."

If you wanted to write it yourself, I can
give some references to the algorithm
literature. As I'm sure you are aware, it's
an NP-hard problem to find the maximum size
of a clique. The choice of implementation
would thus reflect to some degree what
application you have in mind.

regards, chip