#!/usr/bin/env setl
--
-- clique in SETL
--
-- Inspired by the {log} (setlog) program
-- http://www.math.unipr.it/~gianfr/SETLOG/SamplePrograms/Clique.slog
-- """
-- Find all possible cliques in a graph.
-- A clique is a sub-graph that is
-- complete, i.e., any two vertices are connected.
--
-- An undirected graph is represented by the set V of its
-- vertices and the set E of its edges. Each edge is
-- represented by the set of the two connected vertices.
-- """
--
-- This SETL program was created by Hakan Kjellerstrand (hakank@bonetmail.com)
-- Also see my SETL page: http://www.hakank.org/setl/
--
if command_line(1) /= om then
file := command_line(1);
print("Reading from file", file);
g := read_file(file);
else
-- this is the graph from the {log} example:
g := {{"a","b"},{"a","c"},{"b","c"},{"b","d"},{"c","d"}};
end if;
print("graph:", g);
c := clique(g);
print("cliques:", c);
print("size:", #c);
--
-- cliques of undirected graph G
--
proc clique(G);
V := { vv : p in G, vv in p}; -- the vertices
cliques := {};
for C in pow(V) loop
-- note the {{I}} construct (i.e. not {I})
if forall I in C | forall J in C | {I,J} in {{I}} + G then
cliques with:= C;
end if;
end loop;
return cliques;
end proc;
--
-- Read a graph from a file with the following format:
-- v1 v2
-- v1 v3
-- v2 v3
--
proc read_file(file);
h := open(file,"r");
g := {};
while not eof(file) loop
reada(file, f,t);
g with:= {f,t};
end loop;
return g;
end proc;