graph-theory - ArangoDB AQL 中的不相交子图

Question

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

我在创建一个可以选择所有不相交子图的查询时遇到问题，即:给定数据库中的子图 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

我可以获得以下图形结果，如上传的图像所示，我想要的结果是包含不相交子图( Actor 和场景)内所有顶点的列表列表。示例以红色圈出。

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

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在应用程序端创建一个图表来解决这个问题。库并使用 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" 对于同一子图的所有顶点都是相同的。