%% s_clique.sp -- SPARC solution to additional exercise for Chapter 6, finding %% cliques in a graph. %% Last Modified: 3/26/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. %% Write a SPARC program which finds all cliques in a given undirected graph; %% i.e., each answer set will correspond to one clique in the graph. %% Bonus: Look up the #count aggregate in the manual for your %% solver of choice and use it to modify your program to only find %% cliques of size >= 3. %% Suggested invocation: %% java -jar sparc.jar s_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) | -in_clique(N). :- in_clique(N1), in_clique(N2), N1 != N2, not edge(N1,N2). %% Bonus: % :- #count{N : in_clique(N)} < 3. %% Graph description (change at will): edge(1,2). edge(2,3). edge(3,4). edge(3,5). edge(4,5). %% The graph is undirected: edge(N1,N2) :- edge(N2,N1).