Comptage de 3 cliques dans un graphique

Question

Je travaille sur un graphe (pas si) grand ayant environ 380K arêtes. J'ai écrit un programme pour compter le nombre de 3-cliques dans le graphique. Un exemple rapide:

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

List of cliques: 
A - B - C 

MySQL Structure de la table:

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

A 3-clique est rien, mais un triangle dans un graphique. Actuellement, je le fais en utilisant PHP + MySQL. Comme prévu, ce n'est pas assez rapide. Y a-t-il un moyen de le faire en pur MySQL? (peut-être un moyen d'insérer tous les 3-cliques dans un tableau?)

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 

Devrait faire l'affaire. Ce que j'ai fait ici, c'est de s'assurer que v1 est inférieur à v2 pour tous les bords considérés, simplement pour supprimer les doublons. Ensuite, il suffit de joindre les bords par leurs points de départ/d'arrivée. Renvoyer le premier point dans chacune des paires.

Si vous avez des tronçons allant d'un nœud vers le même nœud, vous devrez peut-être ajouter des contrôles supplémentaires, le cas échéant.

EDIT: Fait un changement, grâce à Legend.Reminded moi que nous devions nous assurer que le bord trouvé dans T3 correspond au bord dans T1, de sorte que nous devons relier le premier dans chaque ensemble! A l'origine j'avais T3.v1> T3.v2 dans la première ligne de la clause where mais je l'ai changé pour réduire la confusion, j'ai oublié de changer la deuxième partie!