在图中计算3-团数量

Question

我正在处理一个（不算太大的）图，约有380K条边。我编写了一个程序来计算图中3个点组成的三元组数量。下面是一个快速示例：

List of edges:
A - B
B - C
C - A
C - D

List of cliques:
A - B - C

MySQL表结构：

+-------+------------+------+-----+---------+-------+
| Field | Type       | Null | Key | Default | Extra |
+-------+------------+------+-----+---------+-------+
| v1    | bigint(20) | YES  | MUL | NULL    |       | 
| v2    | bigint(20) | YES  | MUL | NULL    |       | 
+-------+------------+------+-----+---------+-------+

3-clique指的是图中的三角形。目前，我正在使用PHP+MySQL完成此操作。但是，预期的速度不够快。是否有一种纯MySQL的方法来完成这个任务？（也许可以将所有3-clique插入到一个表中？）

- Legend

Answer 1

SELECT T1.v1, T2.v1, T3.v1 FROM TableName T1, TableName T2, TableName T3
WHERE T1.v1 < T1.v2 AND T2.v1 < T2.v2 AND T3.v1 < T3.v2
AND T1.v1 = T3.v1 AND T1.v2 = T2.v1 AND T2.v2 = T3.v2

这应该就可以了。我所做的是确保对于所有考虑的边，v1都小于v2，以消除重复。然后只需按其起始/结束点连接边即可。返回每对中的第一个点。

如果您有从节点返回到相同节点的边，可能需要添加适当的额外检查。

编辑：进行了更改，感谢Legend提醒我们需要确保在T3中找到的边与T1中的边配对，因此我们必须将每个的第一个连接起来！最初，在where从句的第一行中我写的是T3.v1>T3.v2，但为了减少混淆而进行了更改，但忘记更改第二部分了！

- Farthingworth

---

@Farthinworth：谢谢你的时间。出于某种原因，它给了我一个空集。而且我不认为我有你在最后描述的那种情况。你介意再解释一下吗？编辑：我也试过在一个较小的表格上操作。如果有什么我遗漏的地方，我会检查语句。 - Legend

将其作为新评论添加，因为它在测试表上运行成功：SELECT T1.v1、T2.v1、T3.v2 FROM cycletest1 T1、cycletest1 T2、cycletest1 T3 WHERE T1.v1 < T1.v2 AND T2.v1 < T2.v2 AND T3.v1 < T3.v2 AND T1.v1 = T3.v1 AND T1.v2 = T2.v1 AND T2.v2 = T3.v2；不知道运行需要多长时间 :) - Legend

感谢您的修复，更重要的是，非常感谢您的想法。我原本以为我的PHP+MySQL方法需要几天才能完成！ :) - Legend

T1.v1 = T3.v1 AND T1.v2 = T2.v1 AND T2.v2 = T3.v2应该是 T1.v1 = T3.v2 AND T1.v2 = T2.v1 AND T2.v2 = T3.v1 - Fakrudeen