php - 图中的 3 团计数

Question

我正在处理一个(不是那么)大的图，它有大约 38 万条边。我写了一个程序来计算图中 3-cliques 的数量。一个简单的例子:

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 团只不过是图中的一个三角形。目前，我正在使用 PHP+MySQL 执行此操作。正如预期的那样，它不够快。有没有办法在纯 MySQL 中做到这一点？ (也许是一种将所有 3 组插入到表中的方法？)

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 但为了减少混淆而更改了它，但是忘记更改第二部分了!