问题标签 [clique-problem]

给定一个无向图，我需要找到最大的集团。我要做的是首先找到它的大小（即有多少顶点/节点）。这样做时，我删除了不属于最大集团的所有节点（即，如果最大大小为 3，我将删除所有只有一个相邻节点的节点，因为它们不能成为这个更大集团的一部分）。

这是我的代码：

我正在通过 Udemy 课程的在线检查器提交，结果如下：

我有一个非常大的表，其中包含产品移动交易（FROM-TO）。

示例表

我需要以 SQL 方式将这些事务连接在一起，以便我可以将这些卷的成本正确地分配给每个站点。

预期结果

1. A->B->C->E
2. A->B->C->F
3. A->B->D

目前，我通过循环将表与表本身连接以连接事务来执行此操作。在这种情况下，它将循环加入原始表本身 3 次。但是，处理需要花费太多时间，尤其是在事务数量增加时。

你能帮我建议任何更聪明的 SQL 方法来解决这个问题吗？

谢谢。

我一直在为我的硕士论文尝试在 Rust 中实现Bron-Kerbosch 算法。到目前为止一切正常，但是当我尝试从 a 更改为 aBTreeSet以HashSet进行性能比较时，行为变得完全随机（至少结果是这样）。

我找不到有关对结果有任何影响的节点顺序的任何信息，但是，更改为无序集合会破坏结果，因为算法似乎在回溯期间错过了一些分支。

操场

运行代码使用BTreeSet给出正确的结果。

更改Nodes类型以HashSet产生完全不同的结果。

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

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

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

我有一个断开的无向网络。我想识别并删除所有属于 cliques 的组件。我不想删除所有的派系，只是那些本身就是网络组成部分的派系。

我应该如何进行？

我实现了 BK 算法 ( https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm ) <- 在 C++ 中没有旋转版本，但没有按预期工作。代码是：

预期产出集团：ABC

AE

CBDF

ED

实际输出派系：ABC

AE

CBDF

CDF <- 这不应该存在

ED

一个相关的问题在这里：Bron Kerbosch algorithm in c++ 解决方案是使用 P 的副本（我正在这样做，虽然我不完全理解为什么需要它）。我测试它的图表是这样的：

注意： users 被定义为 a: map<string, vector<string>>，所以 users[v] 实际上是一个包含 v 所有邻居的向量。

完整的类实现： https ://pastebin.com/dRXrC0Rf

声明类后重现输出的代码： https ://pastebin.com/vV6ppunF

我试图在图中找到最大集团（邻接矩阵），该图最多可以有 50 个节点。目前，当图形大小达到 n = 40 左右时，我已经开始永远花费。谁能找到我可以做的任何优化？

全类内容：https : //pastebin.com/fNPjvgUm 邻接矩阵：https ://pastebin.com/yypN9K4L

对于我作为一名实用程序员的明显数学缺陷，我向这个问题表示歉意。自从我在高中代数上表现出色，然后在任何更高的科目上都失败了，已经有 40 多年了。“NP-complete”和“NP-hard”问题的概念一直很难掌握，但我试过了。我什至购买并研究了似乎是这类问题的原始指南，计算机和难处理性： Michael R. Garey 和 David S. Johnson的 NP 完备性理论指南。

https://goodreads.com/book/show/284369.Computers_and_Intractability/

不管怎样。希望问题本身足够清楚。迄今为止，对于从任何地方提取所有唯一的完整子图（其中所有不同的节点（顶点）相互连接（通过唯一的边））的特定问题，什么是最好的公开可用的蛮力算法（具有有效的分支修剪）随机无向图？也就是说，该算法应该能够首先提取最大的唯一完整子图，无论可能有多少子图，然后按此顺序提取所有较小的唯一完整子图，这些子图（根据定义，我认为）不包含在任何更大的唯一完整子图，从而避免重复产生非唯一（隐含）结果。

哎呀，像这样用清晰的英语拼出来让我有点头疼。希望这个描述仍然足够简单。一个标准的 C/C++/（甚至是 Python）库来为这个功能提供合理的计算资源，比如带有 64GB/128GB DRAM 的 Ryzen 5 3600 盒子会很棒，特别是如果可以在 1,024 个节点的完整分析中完成一两天，但我会尽我所能，非常感谢。

如果网络上某处有一个常见问题解答或文章，用英语涵盖了这个主题，并且可以被非数学家理解，那就更好了！

编辑：以下论文中的语言确实有点超出我的想象，但对于你们那里的计算数学家来说，你能确认它实际上确实解决了核心问题本身吗？如果是这样，我可以开始英勇地努力理解这个“Bron-Kerbosch”算法，并相信它是正确的道路。-_-

“生成所有最大团和计算实验的最坏情况时间复杂度”，作者：Etsuji Tomita、Akira Tanaka 和 Haruhisa Takahashi

（电子通信大学信息与通信工程系，Chofugaoka 1-5-1, Chofu, Tokyo 182-8585, Japan）（Toyota Techno Service Corporation, Imae 1-21, Hanamotocho, Toyota, Aichi 470-0334 ， 日本）

https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf

这是第一次处理weka和ML。我很难阅读（按班级详细准确度）。任何人都可以帮助我吗？如果您有任何链接或资源可以帮助我。

这是我的代码：

if 给了我KeyError: 'Abrev'这个代码的一个关键错误，但我也尝试更改'Abrev'并0删除source='Abrev'所有代码，但每个错误都会略有不同；'KeyError: 0 'KeyError: 'source'

excel文件的示例内容；