%% 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).