遍历框架 Java API

`TraversalDescription`

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

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

`Traverser` 对象

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

以下是使用默认值的 Traverser 示例，即：唯一性：NODE_GLOBAL，扩展器：BOTH，以及分支排序：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…)`	如果给定的节点之一处于给定的深度，则返回该路径。

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。

遍历框架基于深度优先 (depth-first) 和广度优先 (breadth-first) 算法提供了几种基本的排序实现。它们是：

BranchOrderingPolicies.PREORDER_DEPTH_FIRST — 深度优先遍历，在访问子节点之前访问每个节点。
BranchOrderingPolicies.POSTORDER_DEPTH_FIRST — 深度优先遍历，在访问子节点之后访问每个节点。
BranchOrderingPolicies.PREORDER_BREADTH_FIRST — 广度优先遍历，在访问子节点之前访问每个节点。
BranchOrderingPolicies.POSTORDER_BREADTH_FIRST — 广度优先遍历，在访问子节点之后访问每个节点。

请记住，广度优先遍历的内存开销高于深度优先遍历。

以下示例显示了没有任何额外过滤器的 BranchOrderingPolicy 的结果：

排序策略遍历中节点的顺序

排序策略	遍历中节点的顺序
`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

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 ResourceIterable.of(filtered);
    }

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

ResourceIterable.of 从 Neo4j 2026.03 开始提供。

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

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

遍历框架 Java API

TraversalDescription

Traverser 对象

使用 relationships()

使用 Evaluator

内置 Evaluator

Evaluator 的自定义实现

Uniqueness（唯一性）选项

BranchOrderingPolicy 和 BranchSelector

使用 PathExpander

内置 PathExpander

PathExpanderBuilder