ArangoDB AQL 中的不相交子图

Question

给定一个图形数据库，我有一个演员顶点集合，该集合具有将其连接到场景顶点集合的边。

我在创建可以 select 所有不相交子图的查询时遇到问题，即：给定数据库中的子图 A 和 B，没有边（OUTBOUND 或 INBOUND）连接子图A到子图B。

来自这个 AQL：

FOR actor IN actors
FOR v, e, p IN 1..1 ANY actor._id acts_in_scenes
    RETURN e

我可以在上传的图像中得到以下图形结果，我想要的结果是一个列表列表，其中包含不相交子图（演员和场景）内的所有顶点。示例以红色圈出。

我已经多次尝试使用子查询和收集，我认为到目前为止最好的结果是下面的查询，但它仍然只是返回场景：

FOR actor IN actors
    LET sub_result = (FOR v, e, p IN 1..1 ANY actor._id acts_in_scenes RETURN DISTINCT v._id) // this just returns me scenes
    FILTER LENGTH(sub_result) > 0
    RETURN DISTINCT sub_result

有谁知道这是否可以通过 AQL 查询来解决？

编辑： 因此，我在图形遍历子查询中将深度增加到 5 (1..5)，现在我可以获得参与者顶点。现在的问题是在检查结果 json 时，我可以在组上看到重复的场景键，如果这个结果代表不相交的子图，这应该是不可能的：

FOR actor IN actors
    LET sub_result = (
        FOR v, e, p IN 1..5 ANY actor._id acts_in_scenes 
        SORT v._id
        RETURN DISTINCT v._id
    )
    FILTER LENGTH(sub_result) > 0
    SORT COUNT(sub_result) DESC
    RETURN DISTINCT { 'count': COUNT(sub_result), result: sub_result }

编辑 2：

我不得不通过在应用程序端使用 networkx library and using the nx.connected_components() 函数创建图表来解决这个问题。但我真的希望我可以通过仅使用数据库的图形功能来解决这个问题，因为它增加了应用程序的复杂性并要求我在应用程序端的内存中创建一个图形。

Answer 1

在 ArangoDB v3.7 中，添加了一种新的 Pregel 算法 wcc 用于查找弱连通分量：

https://www.arangodb.com/docs/stable/release-notes-new-features37.html#pregel

它允许您预先计算子图。在阿兰戈什：

var pregel = require("@arangodb/pregel");

var params = {
  "maxGSS": db.actors.count(), /* the number of vertices */
  "resultField": "subgraph"
};

var id = pregel.start("wcc", {
  vertexCollections:["actors"],
  edgeCollections:["acts_in_scenes"]
}, params);

完成后（pregel.status(id).state 等于 "done"），每个角色文档将具有一个数字属性 "subgraph"，该属性对于同一子图的所有顶点都是相同的。

ArangoDB AQL 中的不相交子图

Disjoint subgraphs in ArangoDB AQL

graph-theory

graph-databases

disjoint-sets

arangodb

aql