%% s_max_clique.sp -- SPARC solution (using cr-rules) to additional exercise for 
%% Chapter 6, finding a maximum clique in a graph.
%% Last Modified: 4/11/14
%% 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 SPARC program which finds a maximum clique in a given undirected 
%% graph.
%% Suggested invocation:
%%   java -jar sparc.jar s_max_clique.sp -A -solveropts "-pfilter=in_clique"

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
#const n = 5.
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
sorts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

#node = 1..n.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
predicates
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

edge(#node,#node).
in_clique(#node).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
rules
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

in_clique(N) :-
         not -in_clique(N).

-in_clique(N) :+.

:- in_clique(N1),
   in_clique(N2),
   N1 != N2,
   not edge(N1,N2).


%% ----------------------------------------------
%% Description of a patricular, undirected graph:
%% (Change at will.)

edge(N1,N2) :-
     edge(N2,N1).

edge(1,2).
edge(2,3).
edge(3,4).
edge(3,5).
edge(4,5).
edge(2,5).
edge(2,4).