Подсчет 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-клика - это не что иное, как треугольник на графе. В настоящее время я делаю это, используя 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, поэтому мы должны связать первое в каждом вместе! Первоначально я имел T3.v1> T3.v2 в первой строке предложения where, но изменил его, чтобы уменьшить путаницу, однако забыл изменить вторую часть!