计算两个节点之间的跳数并识别层次图中最低节点的方法

Question

我对 arangodb 相对较新，因此下面的问题可能非常容易回答，但我还无法从文档中找出解决方案。

我有：

1。问题： 我已经建模了由边（isChildOf）链接的项目（节点）的父子层次结构。各个分支的深度不平衡，可以达到从 1 到 1.1 到 1.1.1 和 1.1.1.1。每个层次结构都有一个根节点。现在我想找出一个给定的孩子，例如1.1.1.1 距离根节点 1 有多少条边。因此，我不想将边数设置为查询过滤器参数，而是想做相反的事情，计算来自例如 1.1.1.1 的“跳数”。 1至1.1.1.1或从1.1.1.1至1.1.1.1.5.2。我如何在 AQL 中实现这一目标？

2。问题：我仍在寻找一种方法来检索先前定义的层次结构的最低节点（不是子节点的父节点）。例如。如果层次结构以 1.1.1.1 和 1.1.1.2.1 结尾，我如何在 AQL 单个查询中检索所有这些最低节点？

Answer 1

有几种方法可以实现此目的，具体取决于您想要返回的内容（或查询的嵌套方式），但无论哪种方式，

SHORTEST_PATH

或

K_SHORTEST_PATHS

都将是您的朋友。这是一个例子：

FOR v,e IN INBOUND SHORTEST_PATH start_node to root_node
    GRAPH 'named_graph'
    RETURN e

参考SHORTEST_PATH文档，我们可以开始分解它。

1. 我们正在寻找从“起始”节点到“结束”节点的路径（按跳数或“权重”计算的最短路径）。
2. 使用

   INBOUND

   或

   OUTBOUND

   将取决于您的图形/数据模型的构建方式。

3. v,e

   变量代表沿路径找到的“顶点”和“边”（分别为

   v

   和

   e

   ）。

此查询模式可用于计算顶点或边的数量，如下所示：

FOR start_node in child_collection
    FOR root_node IN root_collection
        LET edges = (
            FOR v,e IN INBOUND SHORTEST_PATH start_node to root_node
                GRAPH 'named_graph'
                RETURN e._id
        )
        RETURN {
            root: root_node._id,
            child: start_node._id,
            pathLen: LENGTH(paths)
        }

这可能有点基础（可能有一些方法可以优化它），但它展示了如何使用变量来保存子查询，使用这些结果来计算路径长度。

或者，您可以使用 K_SHORTEST_PATHS 为您进行此计算。例如，前面的查询可以简化为：

FOR p IN INBOUND K_SHORTEST_PATHS start_node to root_node
    GRAPH 'named_graph'
    OPTIONS { weightAttribute: 'weight' }
    LIMIT 1
    RETURN p

找到两点之间的第一条最短路径。在这里，我们使用

LIMIT 1

来确保我们只返回一条路径。结果会是这样的：

[
  {
    edges: [ ... ],
    vertices: [ ... ],
    weight: <number>
  }
]

或者您可以自定义退货以更好地满足您的需求。不要返回您不需要或不会使用的数据。

Answer 2

FOR start_node in child_collection
    FOR root_node IN root_collection
        LET edges = (
            FOR v,e IN INBOUND SHORTEST_PATH start_node to root_node
                GRAPH 'named_graph'
                RETURN e._id
        )
        RETURN {
            root: root_node._id,
            child: start_node._id,
            pathLen: LENGTH(paths)
    }

上面的代码是错误的。如果没有使用for语句，如何返回LENGTH(paths)。放置前请检查一次您的代码