I wish to find all maximum cliques of special types of Cayley graphs called derangement graphs. I work in GAP and I currently use the GRAPE package to establish the following:
#This is a nice example to work with.
grp := PrimitiveGroup(8,2);
n := LargestMovedPoint(grp);
#The derangement graph of grp
derang := [];
for x in grp do
if NrMovedPoints(x) = n then
AddSet(derang, x);
fi;
od;
#This uses the GRAPE package.
Cay:=CayleyGraph(grp, derang);
#The following function returns a set of complete subgraphs of Cay (of size n) which are maximal.
#The cliques are returned as vertices of Cay.
max_clique_indices := CompleteSubgraphs(Cay,n,1);
#We convert the vertices of Cay into permutations of grp.
max_clique_perms := [];
for x in max_clique_indices do
Add(max_clique_perms, Cay.names{x});
od;
#To find all maximum cliques, we perform the following "right translation" action.
#This is where the inefficiency is (I think). We get so many duplicates that must be removed.
maximum_cliques := [];
for x in grp do
for cl in max_clique_perms do
Add(maximum_cliques, x*cl);
od;
od;
maximum_cliques := AsSet(List(maximum_cliques, AsSet));
I've read the the GRAPE documentation many times, but I can't find a command that generates all maximum cliques. In Sage, one can invoke the cliquer command (https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/cliquer.html), which finds all maximum cliques fairly quickly and efficiently (for groups of order < 3000 in my experience). Is there such an option in GAP?
Note: I tried using the YAGS package as well to make use of the "CompletesOfGivenOrder(Cay,n)" command, but I found it to be incredibly slow.
Several remarks:
To "find all maximum cliques" (i.e. cliques with the largest possible size) you can ask Grape to compute (G-orbit representatives of) all maximal cliques, then pick among those the one which have maximum size
Your test program runs in a few milliseconds for me, so any optimizations I can provide are hypothetical; it would be good to know which inputs you have that don't complete in just a few milliseconds?
For the sake of testing, I tried PrimitiveGroup(15,2); there the first bottleneck was to find the maximal cliques (which took 10 seconds in that example). This can be overcome by using the digraphs package (which only took 200 milliseconds). But whether this is suitable for your case or not depends on the actual inputs you are interested in.
Grape by default only returns representatives for the G-orbits of cliques; and for many problems in Cayley graphs, it is sufficient to work with these. As you don't say what you want to do with these cliques, I can't say whether there is such an approach in your case, but I'd suggest that you ponder the possibility, as that will (if possible) by far the most efficient way to go about it
The bit you identified as inefficient is basically performing an orbit enumeration, but indeed in a very inefficient way. To overcome this, just use GAP's rich orbit functionality to resolve this.
Here is a modified version of your program which computes all maximum cliques. It runs in a few milliseconds on my computer, but of course for larger inputs gets much slower.
LoadPackage("grape");
grp := PrimitiveGroup(8,2);
n := LargestMovedPoint(grp);
# the derangement graph of grp; this uses the GRAPE package
Cay := CayleyGraph(grp, Filtered(grp, x -> NrMovedPoints(x) = n));
# compute a set of maximal cliques in Cay which is guaranteed to contain
# at least one representative from each orbit of maximal cliques;
# returned as lists of indices into Cay
max_clique_indices := CompleteSubgraphs(Cay,-1,1);
# compute the size of maximum clique
msize := Maximum(List(max_clique_indices, Length));
# discard all cliques which are not maximum
max_clique_indices:=Filtered(max_clique_indices, c -> Length(c) = msize);
# convert the vertices of Cay into permutations of grp.
max_clique_perms := List(max_clique_indices, i->AsSet(Cay.names{i}));
# we want all maximum cliques, so compute the orbits of the orbit representatives;
# we act on sets by right multiplication
maximum_clique_orbs := Orbits(grp, max_clique_perms, {set,perm} -> AsSet(set*perm));
# finally merge all the orbits into one
maximum_cliques := Concatenation(maximum_clique_orbs);
You could also try Digraphs; compute Cay as above, but then proceed like this:
LoadPackage("digraph");
dig:=Digraph(Cay);
max_clique_indices := DigraphMaximalCliquesReps(dig);
msize := Maximum(List(max_clique_indices, Length));
max_clique_indices:=Filtered(max_clique_indices, c -> Length(c) = msize);
maximum_clique_orbs := Orbits(AutomorphismGroup(dig), max_clique_indices, OnSets);
maximum_cliques := List(Union(maximum_clique_orbs), i->AsSet(Cay.names{i}));