遍历框架 Java API

TraversalDescription

TraversalDescription 是用于定义和初始化遍历的主要接口。它不应由遍历框架的用户实现，但它可作为用户描述遍历的手段。

TraversalDescription 实例是不可变的。它们的方法返回一个新的 TraversalDescription，该对象根据调用方法的对象及其参数进行修改。traverse() 方法返回在 TraversalDescription 中定义的遍历结果。

Traverser 对象

Traverser 对象是对 TraversalDescription 调用 traverse() 的结果。它表示在图上定位的遍历以及结果格式的规范。实际的遍历在每次调用 Traverser 迭代器的 next() 方法时惰性执行。

以下是 Traverser 使用默认值的示例，即唯一性 (Uniqueness): NODE_GLOBAL、扩展器 (Expander): BOTH 和分支排序 (Branch Ordering): PREORDER_DEPTH_FIRST

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription();
}

Traverser traverser = td.traverse( startNode );

for ( Path path : traverser ) {
    // Extend as needed
}

此外，Traverser 提供了一些方法，用于读取返回的每个 Paths 的最新 relationships() 和 nodes() 以及 metadata()。它还提供了便捷方法，用于查找返回路径的总数 getNumberOfPathsReturned()，以及遍历关系的数目 getNumberOfRelationshipsTraversed()。

使用 relationships()

relationships() 方法定义了要遍历的关系类型，以及可选的关系方向。默认情况下，所有关系都会被遍历，无论其类型如何。但是，如果添加了一个或多个关系，则只遍历添加的类型。

TraversalDescription td = transaction.traversalDescription()
    .relationships(RelationshipType.withName("A"))
    .relationships(RelationshipType.withName("B"), Direction.OUTGOING);
return td.traverse(startNode);

使用 Evaluator

一个 Evaluator 接收从起始节点到当前节点的 Path，并决定该 Path 是否应该

  • 包含在结果中。

  • 展开以供进一步评估。

给定 Path，评估器可以执行以下四种操作之一

  • Evaluation.INCLUDE_AND_CONTINUE — 将当前节点包含在结果中并继续遍历。

  • Evaluation.INCLUDE_AND_PRUNE — 将当前节点包含在结果中，但不再继续遍历。

  • Evaluation.EXCLUDE_AND_CONTINUE — 将当前节点从结果中排除，但继续遍历。

  • Evaluation.EXCLUDE_AND_PRUNE — 将当前节点从结果中排除，并且不再继续遍历。

由于可以添加多个评估器，不同的组合可能会导致意外结果。因此，请记住

  • 如果所有评估器都包含某个路径，则该路径才会被包含。

  • 只有当所有评估器都没有剪枝某个路径时，该路径才能被扩展。

  • 遍历器遇到的所有路径都会调用评估器，甚至包括仅由起始节点组成的路径。

内置 Evaluator

遍历框架提供了几个内置评估器

评估器 描述

Evaluators.all()

包含并继续遍历所有节点。

Evaluators.atDepth(int)

仅包含给定深度的路径，剪枝其他所有路径。

Evaluators.toDepth(int)

包含达到给定深度的路径，剪枝更深的所有路径。

Evaluators.fromDepth(int)

包含从给定深度开始的路径，忽略之前的路径，并且永不剪枝。

Evaluators.includingDepths(int, int)

仅包含深度等于并介于给定两个深度之间的路径。

Evaluators.lastRelationshipTypeIs(Evaluation, Evaluation, RelationshipType…​)

根据最后一个关系是否与给定关系之一匹配，选择要执行的评估。

Evaluators.includeWhereLastRelationshipTypeIs(RelationshipType…​)

仅返回最终关系与给定关系匹配的路径。

Evaluators.endNodeIs(Evaluation, Evaluation, Node…​)

根据最后一个节点是否与给定节点之一匹配，选择要执行的评估。

Evaluators.includeIfContainsAll(Node…​)

如果所有给定节点都包含在路径中，则返回该路径。

Evaluators.includeIfAcceptedByAny(PathEvaluator)

如果任何给定评估器包含当前路径，则返回该路径。

Evaluators.endNodeIsAtDepth(int, Node…​)

如果给定节点之一位于给定深度，则返回该路径。

以下是使用内置评估器的示例

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription()
            .evaluator(Evaluators.atDepth(2));
}

td.traverse( startNode );

Evaluator 的自定义实现

现在，您可以看到一个自定义实现的示例，它只包含以特定标签节点结尾的路径

class LabelEvaluator implements Evaluator {

    private final Label label;

    private LabelEvaluator(Label label) {
        this.label = label;
    }

    @Override
    public Evaluation evaluate(Path path) {
        if (path.endNode().hasLabel(label)) {
            return Evaluation.INCLUDE_AND_CONTINUE;
        } else {
            return Evaluation.EXCLUDE_AND_CONTINUE;
        }
    }
}

以下示例展示了一个组合评估器，它返回所有长度为 2 且末端节点带有标签 A 的路径

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription()
            .evaluator(Evaluators.atDepth( 2 ))
            .evaluator(new LabelEvaluator(Label.label("A")));
}

td.traverse( startNode );

Uniqueness 选项

尽管默认是 NODE_GLOBAL，但可以通过调整 Uniqueness 级别来设置在遍历期间如何重新访问位置的规则。以下是一些可用选项

  • NONE — 图中任何节点都可以被重新访问。

  • NODE_GLOBAL — 整个图中没有节点可以被访问多次。这可能会消耗大量内存，因为它需要维护一个内存数据结构来记住所有已访问的节点。

  • RELATIONSHIP_GLOBAL — 整个图中没有关系可以被访问多次。就像 NODE_GLOBAL 一样，这可能会占用大量内存。然而，由于图通常具有比节点更多的关系，因此此 Uniqueness 级别的内存开销可能会增长得更快。

  • NODE_PATH — 节点在到达该路径之前不得重复出现。

  • RELATIONSHIP_PATH — 关系在到达该路径之前不得重复出现。

  • NODE_RECENT — 与 NODE_GLOBAL 类似，在使用全局访问节点集合进行检查时。但是，此唯一性级别对内存消耗有一个上限，该上限表现为一个仅包含最近访问节点的集合。该集合的大小可以通过将一个数字作为 TraversalDescription.uniqueness() 方法的第二个参数与唯一性级别一起提供来指定。

  • RELATIONSHIP_RECENT — 工作方式与 NODE_RECENT 类似，但使用关系而不是节点。

以下是使用内置 Uniqueness 约束的遍历示例

TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription();
            .uniqueness( Uniqueness.RELATIONSHIP_GLOBAL )
}

td.traverse( startNode );

BranchOrderingPolicy 和 BranchSelector

BranchOrderingPolicy 是一个用于创建 BranchSelector 的工厂，以决定分支返回的顺序——即，分支的位置表示为从起始节点到当前节点的 Path。

遍历框架提供了一些基于 深度优先 和 广度优先 算法的基本排序实现。它们是

  • BranchOrderingPolicies.PREORDER_DEPTH_FIRST — 深度优先遍历，在访问其子节点之前访问每个节点。

  • BranchOrderingPolicies.POSTORDER_DEPTH_FIRST — 深度优先遍历，在访问其子节点之后访问每个节点。

  • BranchOrderingPolicies.PREORDER_BREADTH_FIRST — 广度优先遍历，在访问其子节点之前访问每个节点。

  • BranchOrderingPolicies.POSTORDER_BREADTH_FIRST — 广度优先遍历，在访问其子节点之后访问每个节点。

请记住，广度优先遍历比深度优先遍历具有更高的内存开销。

以下示例展示了不带任何额外过滤器的 BranchOrderingPolicy 结果

traversal order example graph
排序策略 遍历中节点的顺序

BranchOrderingPolicies.PREORDER_DEPTH_FIRST

a, b, d, c, e

BranchOrderingPolicies.POSTORDER_DEPTH_FIRST

d, b, e, c, a

BranchOrderingPolicies.PREORDER_BREADTH_FIRST

a, b, c, d, e

BranchOrderingPolicies.POSTORDER_BREADTH_FIRST

d, e, b, c, a

深度优先和广度优先是常见的策略，可以通过便捷方法 breadthFirst() 和 depthFirst() 访问。这等同于设置 BranchOrderingPolicies.PREORDER_BREADTH_FIRST / BranchOrderingPolicies.PREORDER_DEPTH_FIRST 策略。

使用 depthFirst() 的示例
TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription()
            .depthFirst();
}

td.traverse( startNode );
使用 BranchOrderingPolicies.PREORDER_BREADTH_FIRST 的示例
TraversalDescription td;
try ( Transaction tx = graphDb.beginTx() ) {
     td = tx.traversalDescription()
            .order( BranchOrderingPolicies.PREORDER_BREADTH_FIRST );
}

td.traverse( startNode );

由于 BranchSelector 带有状态，因此需要为每次遍历唯一地实例化，所以应通过 BranchOrderingPolicy 接口（它是 BranchSelector 实例的工厂）将其提供给 TraversalDescription。

尽管遍历框架的用户很少需要实现自己的 BranchSelector / BranchOrderingPolicy，但了解这些参数允许图算法实现者提供自己的遍历顺序是很重要的。

请查看 Neo4j 图算法包，了解在 A* 和 Dijkstra 等 BestFirst 搜索算法中使用的 BestFirst 顺序 BranchSelector / BranchOrderingPolicy。

使用 PathExpander

遍历框架使用 PathExpander 来发现应从特定路径跟随哪些关系以到达遍历中的进一步分支。

有多种指定 PathExpander 的方法，例如

  • 内置的 PathExpander 定义了一些常用的 PathExpander。

  • PathExpanderBuilder 允许组合定义。

  • 可以通过实现 PathExpander 接口来编写自定义的 PathExpander。

内置 PathExpander

以下路径扩展器位于 PathExpander 类中，可用于为遍历设置更具体的 PathExpander

  • allTypesAndDirections() — 扩展所有方向上的所有关系（默认）。

  • forType(relationshipType) — 仅扩展特定类型的关系。

  • forDirection(direction) — 仅扩展特定方向上的关系。

  • forTypeAndDirection(relationshipType, direction) — 仅扩展给定类型和给定方向上的关系。

  • forTypesAndDirections(relationshipType, direction, relationshipType, direction, …​) — 仅扩展给定类型及其特定方向上的关系。

  • forConstantDirectionWithTypes(relationshipType, …​) — 仅扩展给定类型的关系，如果它们继续沿着第一个关系的方向。

以下是设置自定义关系扩展器的示例，该扩展器仅扩展类型为 A 的出站关系

TraversalDescription td = transaction.traversalDescription()
    .expand(PathExpanders.forTypeAndDirection( RelationshipType.withName( "A" ), Direction.OUTGOING ));
td.traverse( startNode );

PathExpanderBuilder

PathExpanderBuilder 允许组合不同的 PathExpander 定义。它提供了更细粒度的自定义级别，而无需从头开始编写 PathExpander。它还包含一组静态方法，允许使用以下方法创建 PathExpander

  • empty() — 不扩展任何关系。

  • emptyOrderedByType() — 不扩展任何关系，并确保在添加任何类型时其扩展顺序。

  • allTypesAndDirections() — 扩展所有方向上的所有关系。

  • allTypes(Direction) — 扩展给定方向上的所有关系。

该 PathExpander 可以通过以下方法进一步定义

  • add(relationshipType) — 扩展给定类型的关系。

  • add(relationshipType, direction) — 扩展给定类型和方向上的关系。

  • remove(relationshipType) — 移除给定类型关系的扩展。

  • addNodeFilter(filter) — 添加基于节点的过滤器。

  • addRelationshipFilter(filter) — 添加基于关系的过滤器。

它可能看起来像这样

TraversalDescription td = transaction.traversalDescription()
    .expand(PathExpanderBuilder.empty()
                               .add(RelationshipType.withName("E1"))
                               .build());
td.traverse( startNode );

以下是一个自定义 PathExpander 的示例，它在其 BranchState 中跟踪路径的权重，并且仅在总权重小于给定最大权重时才包含路径

class MaxWeightPathExpander implements PathExpander<Double>
{

    private final double maxWeight;

    public MaxWeightPathExpander( double maxWeight ) {
        this.maxWeight = maxWeight;
    }

    @Override
    public ResourceIterable<Relationship> expand( Path path, BranchState<Double> branchState )
    {
        if (path.lastRelationship() != null) {
            branchState.setState( branchState.getState() + (double) path.lastRelationship().getProperty( "weight" ) );
        }

        ResourceIterable<Relationship> relationships = path.endNode().getRelationships( Direction.OUTGOING );
        ArrayList<Relationship> filtered = new ArrayList<>();
        for ( Relationship relationship : relationships ) {
            if ( branchState.getState() + (double) relationship.getProperty( "weight" ) <= maxWeight ) {
                filtered.add(relationship);
            }
        }
        return Iterables.asResourceIterable(filtered);
    }

    @Override
    public PathExpander reverse()
    {
        throw new RuntimeException( "Not needed for the MonoDirectional Traversal Framework" );
    }
}

以下是使用自定义 PathExpander 并设置初始状态的示例

TraversalDescription td = transaction.traversalDescription()
        .expand( new MaxWeightPathExpander(5.0), InitialBranchState.DOUBLE_ZERO );
td.traverse( startNode );
© . All rights reserved.