在 GAP 中查找图的所有最大派系的有效方法

Question

我希望找到称为紊乱图的特殊类型 Cayley 图的所有最大团。我在 GAP 工作，我目前使用 GRAPE 包来建立以下内容：

#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));

我已经多次阅读 GRAPE 文档，但我找不到生成所有最大团的命令。在 Sage 中，可以调用 cliquer 命令 (https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/cliquer.html)，它可以相当快速有效地找到所有最大团（根据我的经验，对于 < 3000 的订单组）。 GAP里面有这个选项吗？

注意：我也尝试使用 YAGS 包来使用 "CompletesOfGivenOrder(Cay,n)" 命令，但我发现它非常慢。

Answer 1

几点说明：

要“找到所有 maximum cliques”（即具有最大可能大小的 cliques），您可以要求 Grape 计算所有的（G 轨道代表）最大派系，然后从那些拥有最大规模
的派系中挑选
你的测试程序对我来说只需要几毫秒，所以我能提供的任何优化都是假设的；最好知道您有哪些输入没有在短短几毫秒内完成？
为了测试，我尝试了PrimitiveGroup(15,2)；第一个瓶颈是找到最大的派系（在那个例子中花了 10 秒）。这可以通过使用 digraphs 包（只用了 200 毫秒）来克服。但是这是否适合您的情况取决于您感兴趣的实际输入。
默认情况下只有葡萄 returns 代表集团的 G 轨道；对于凯莱图中的许多问题，使用这些就足够了。由于你没有说你想对这些派系做什么，我不能说你的情况是否有这种方法，但我建议你考虑一下这种可能性，因为到目前为止（如果可能的话）最有效的方法
您认为效率低下的位基本上是在执行轨道枚举，但实际上效率非常低。要克服这个问题，只需使用 GAP 丰富的轨道功能来解决这个问题。

这是您的程序的修改版本，它计算所有最大派系。它在我的电脑上运行几毫秒，但当然对于更大的输入会慢得多。

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);

你也可以试试有向图；如上所述计算 Cay，然后像这样继续：

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}));

在 GAP 中查找图的所有最大派系的有效方法

Efficient method of finding all maximum cliques of a graph in GAP

performance

graph-theory

clique

clique-problem

gap-system