%% max_clique.cr -- CR-Prolog solution to additional exercise for
%% Chapter 6, finding a maximum clique in a graph.
%% Last Modified: 4/11/14
%% You can run it with CR-Models:
%% crmodels max_clique.cr
%% A clique is a subset of a graph such that each of its vertices
%% is connected by an edge to all the other vertices in the clique.
%% Note that each node of a graph is a clique of size 1 and that the empty
%% set is also a clique.
%% A maximum clique is a clique of the largest possible size in a given graph.
%% Write a CR-Prolog program which finds a maximum clique in a given undirected
%% graph.
#domain node(N). %% required for cr-rules of CRModels
in_clique(N) :- node(N),
not -in_clique(N).
r1(N): -in_clique(N) +-.
:- in_clique(N1),
in_clique(N2),
node(N1), node(N2),
N1 != N2,
not edge(N1,N2).
%% ----------------------------------------------
%% Description of a patricular, undirected graph:
%% (Change at will.)
node(1..5).
edge(1,2).
edge(2,3).
edge(3,4).
edge(3,5).
edge(4,5).
edge(2,5).
edge(2,4).
edge(N1,N2) :- node(N1), node(N2),
edge(N2,N1).
% crmodels output formatting:
#hide.
#show in_clique(A).