双向遍历框架

双向遍历由从不同节点开始的两个遍历组成，并返回两个遍历碰撞处的路径。双向遍历框架允许使用 BidirectionalTraversalDescription 描述此类遍历。

以下是从起始节点 1 和结束节点 5 进行双向遍历的可视化表示，其中所有加粗的关系都在结果路径中，并受以下限制：

  • 起始侧遍历器只遍历类型为 A 的关系。

  • 结束侧遍历器只遍历类型为 B 的关系。

bidirectional example

请注意，仅其中一个遍历器到达相反起始/结束节点的路径也包含在内，例如 (1)-[:A]→(5) 和 (1)-[:B]→(5)。在被接受的路径 (1)-[:A]→(2)-[:A]→(3)-[:B]→(4)-[:B]→(5) 中，遍历器在节点 3 处发生碰撞。

Uniqueness 在两个遍历之间共享，这意味着如果 Uniqueness 设置为 Uniqueness.NODE_GLOBAL（这是默认值），则不会有结果，因为两个遍历都需要到达同一个节点才能发生碰撞。因此，在使用 BidirectionalTraversalDescription 时，务必手动设置 Uniqueness。有关可用选项的更多信息，请参阅Uniqueness 选项。

定义双向遍历器

在创建 BidirectionalTraversalDescription 时，可以选择每一侧采用的 TraversalDescription。这可以通过为每一侧（startSide/endSide）单独设置，或为两侧设置一个（mirroredSides）来实现。

起始侧和结束侧遍历

以下是 BidirectionalTraversalDescription 的一个示例，其中 startSide() 和 endSide() 各自使用一个独立的遍历器：

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .startSide(transaction
                .traversalDescription()
                .expand(PathExpanders.forTypeAndDirection(RelationshipType.withName("A"), Direction.OUTGOING))
                .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
        .endSide(transaction
                .traversalDescription()
                .expand(PathExpanders.forTypeAndDirection(RelationshipType.withName("B"), Direction.INCOMING))
                .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL));
td.traverse(startNode, endNode);

一侧从起始节点向前遍历并扩展所有类型为 A 的出站关系。另一侧从结束节点向后遍历并扩展所有类型为 B 的入站关系。

最终路径从起始节点到结束节点，其中所有关系都具有出站方向。可能的路径包括：

  • 所有关系都是类型 A。

  • 所有关系都是类型 B。

  • 从起始节点的关系是类型 A，碰撞后它们都是类型 B。

镜像遍历

mirroredSides(TraversalDescription) 方法设置此双向遍历的起始侧和结束侧。然而，结束侧是起始侧的反向。对于 Relationships 的 Direction，这意味着 OUTGOING 变为 INCOMING，反之亦然。PathExpander 接口还带有一个 reverse() 函数，如果在 mirroredSides 实现中使用，则应覆盖此函数。

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .mirroredSides(transaction
                               .traversalDescription()
                               .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL));
td.traverse(startNode, endNode);

侧选择器

在双向遍历中，遍历器在每一步选择移动哪一侧（起始或结束）。通过实现 SideSelectorPolicy 接口可以改变其工作方式，因为它有一个函数用于确定下一步从哪一侧开始遍历。

  • Direction.OUTGOING — 从起始节点过来的遍历器。

  • Direction.INCOMING — 从结束节点过来的遍历器。

内置策略包括：

  • SideSelectorPolicies.LEVEL — 如果组合深度大于给定最大深度，则停止遍历。

  • SideSelectorPolicies.LEVEL_STOP_DESCENT_ON_RESULT — 一旦找到结果即停止。

  • SideSelectorPolicies.ALTERNATING — 交替选择哪个分支继续遍历。

SideSelectorPolicy 可选地接受 maxDepth，它表示双方必须遵守的组合深度。

以下是如何使用内置 SideSelectorPolicy 的示例，最大组合深度为 5：

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .mirroredSides(transaction
                               .traversalDescription()
                               .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
                               .sideSelector(SideSelectorPolicies.LEVEL, 5);
td.traverse(startNode, endNode);

碰撞策略

BranchCollisionPolicy 定义了在双向遍历中何时检测到并接受碰撞。给定一个评估器和路径谓词，BranchCollisionPolicy 创建 BranchCollisionDetector，它检测两个遍历器之间的碰撞，如果结果路径满足碰撞评估器和唯一性约束给出的条件，则将其添加到结果中。

这些是内置的 BranchCollisionPolicies：

  • STANDARD — 返回所有发生碰撞的路径。

  • SHORTEST_PATH — 返回所有具有最小遍历深度的路径。

以下是如何使用内置 BranchCollisionPolicy 的示例：

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .mirroredSides(transaction
                               .traversalDescription()
                               .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
        .collisionPolicy(BranchCollisionPolicies.SHORTEST_PATH);
td.traverse(startNode, endNode);

碰撞评估器

便利方法 collisionEvaluator() 添加 PathEvaluator，它验证有效碰撞中的路径。多次使用此方法会导致评估器的组合。

BidirectionalTraversalDescription td = transaction
    .bidirectionalTraversalDescription()
    .mirroredSides(transaction
       .traversalDescription()
       .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
    .collisionEvaluator(Evaluators.atDepth(3));
td.traverse(startNode, endNode);
© . All rights reserved.