我在一个(不是很)大的图上操作,它有大约380k条边。我写了一个程序来计算图中三个团的数目。一个简单的例子:
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 | |
+-------+------------+------+-----+---------+-------+
三集团不过是图中的三角形。目前,我正在使用php+mysql进行这项工作。不出所料,速度不够快。在纯mysql中有这样做的方法吗?(也许是一种将所有三个派系都插入一张桌子的方法?)
最佳答案
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的所有边,只是为了删除重复项。然后,通过边的起点/终点连接边是一件简单的事情。返回每对中的第一个点。
如果有从一个节点返回到同一个节点的边,则可能需要根据需要添加额外的检查。
编辑:多亏了传说,我们做了一个改动。提醒我,我们需要确保t3中找到的边与t1中的边匹配,所以我们必须将每个边中的第一个连接在一起!最初我在where子句的第一行有t3.v1>t3.v2,但是为了减少混淆,我把它改了,但是忘了改第二部分!