三角形计数

本文介绍三角形计数算法，并演示如何用 GQL 实现该算法。

算法介绍

三角形计数用于统计图中的闭合三元组数量。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见三角形计数。

数据模型

为了在 GQL 中实现三角形计数算法，使用以下数据模型创建图类型：

• 实体由类型为Node的点表示，点属性包括id和rating。
• 实体间关系由类型为Link的边表示，边属性包括weight。

该图类型的完整定义，请参见准备图数据。

过程实现

为了计算三角形计数结果，创建一个过程。

关于该过程的更多信息，请参见过程实现。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

• 该过程不需要输入参数。

此外，在过程内部定义了以下变量：

变量名	变量类型	描述
total	全局 SumAgg 聚合值变量	全局三角形数量累加器。
fwd	点绑定 SumAgg 聚合值变量	每点 ID 更大的邻居 ID 集合（用于三角形计数交集）。

以下步骤概述了该过程的逻辑：

1. 对每条满足 s.id < t.id 的边，将 t.id 添加到 s 的fwd邻居集合中。
2. 再次遍历每条满足 s.id < t.id 的边，检查 t 的fwd集合中每个点 u；若 u 也在 s 的fwd中，则将total加 1。
3. 每个公共元素对应一个闭合三角形；由于 ID 排序已去重，无需额外除以系数。
4. 返回三角形总数。

操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。

1. 准备图数据

1. 创建一个与数据模型匹配的图类型。

   '''
   CREATE GRAPH TYPE IF NOT EXISTS triangle_count_graph_type AS {
       NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
       EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
   }
   '''
   

2. 下载以下 CSV 文件，保留文件名，保存到部署目录下的examples/algorithms/triangle_count/：

   • triangle_count_node.csv：点数据。
   • triangle_count_edge.csv：边数据。
   查看 CSV 内容

   triangle_count_node.csv

   id,rating
   1,0
   2,2
   3,1
   4,0
   5,0
   6,2
   7,1
   8,2
   9,0
   10,1
   11,0
   12,2
   13,1
   14,1
   15,0
   16,2
   17,0
   18,1
   19,2
   20,0
   21,2
   22,1
   23,0
   24,1
   

   triangle_count_edge.csv

   src_id,dst_id,weight
   1,2,4
   1,3,2
   1,4,7
   1,5,9
   2,3,1
   2,4,6
   2,5,5
   2,6,2
   3,4,3
   3,5,4
   3,6,8
   4,6,2
   4,7,6
   4,8,5
   5,6,4
   5,8,7
   5,9,6
   6,8,1
   6,9,5
   6,10,6
   7,9,2
   7,10,9
   8,9,3
   8,11,6
   8,12,4
   9,10,4
   9,12,7
   9,13,2
   10,12,1
   10,13,8
   10,14,4
   11,12,2
   11,14,5
   11,15,7
   12,14,3
   12,15,6
   12,16,5
   13,15,2
   13,16,7
   14,15,4
   14,17,8
   14,18,2
   15,16,1
   15,18,5
   15,19,3
   16,18,3
   16,19,6
   17,18,2
   17,20,7
   17,21,5
   18,19,4
   18,21,9
   18,22,6
   19,21,1
   19,22,5
   20,21,3
   20,23,6
   20,24,8
   21,22,2
   21,23,4
   21,24,7
   22,24,4
   23,24,1
   

3. 基于图类型创建临时图，并将数据文件加载到临时图中。

   CREATE TEMPORARY GRAPH IF NOT EXISTS #triangle_count_graph TYPED triangle_count_graph_type
   

   '''
   USE #triangle_count_graph IMPORT INTO GRAPH {
         NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
             PATH: "file:///examples/algorithms/triangle_count/triangle_count_node.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         },
         EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
             PATH: "file:///examples/algorithms/triangle_count/triangle_count_edge.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         }
     }
   '''
   

   导入成功后，在控制台执行以下查询核对点数：

   '''
   USE #triangle_count_graph
   MATCH (n)
   RETURN count(n) AS node_count
   '''
   

   node_count应为24。点数不符时，先按文件问题排查检查文件和导入结果。

2. 创建过程

创建实现三角形计数算法的过程。关于该过程的更多信息，请参见过程实现。

'''
CREATE OR REPLACE PROCEDURE triangle_count()
RETURNS (triangle_count INT64)
COMMENT "Count the number of undirected triangles in a graph whose vertex primary key is id."
AS {
  VALUE total SumAgg<INT64> = 0

  NODE VALUE fwd SetAgg<INT64>

  MATCH (s)-[e]-(t)
  WHERE s.id < t.id
  PER PATH {
    SET s.@fwd += t.id
  }

  MATCH (s)-[e]-(t)
  WHERE s.id < t.id
  PER PATH {
    VALUE idx INT64 = 0
    VALUE candidate_id INT64 = 0

    WHILE idx < t.@fwd.size() THEN {
      SET candidate_id = t.@fwd[idx]
      IF s.@fwd.contains_key(candidate_id) THEN {
        SET @total += 1
      }
      SET idx = idx + 1
    }
  }

  RETURN @total AS triangle_count
}
'''

3. 调用过程

计算示例图中的三角形总数。

USE #triangle_count_graph CALL triangle_count() RETURN triangle_count

返回：

+----------------+
| triangle_count |
+----------------+
| 47             |
+----------------+

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 EXPORT。导出字段应与返回列及目标属性对应。