遍历框架 Java API

`TraversalDescription`

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 — 从结果中排除当前节点，并且不继续遍历。

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

如果所有评估器都包含路径，则包含该路径。
只有在没有评估器修剪路径的情况下，才能扩展路径。
即使对于仅由起始节点组成的路径，也会对遍历器遇到的所有路径调用评估器。

内置 `Evaluators`

遍历框架提供了一些内置评估器

评估器描述

评估器	描述
`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()-method 提供一个数字作为第二个参数以及唯一性级别来指定此集合的大小。
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在没有任何额外过滤器的情况下的结果

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

排序策略	遍历中节点的顺序
`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接口提供给TraversalDescription，该接口是BranchSelector实例的工厂。

即使Traversal Framework的用户很少需要实现自己的BranchSelector / BranchOrderingPolicy，了解这些参数可以让图算法实现者提供自己的遍历顺序也是相关的。

查看Neo4j 图算法包以查看在诸如A*和Dijkstra之类的最佳优先搜索算法中使用的BestFirst顺序BranchSelector / BranchOrderingPolicy。

使用`PathExpander`

Traversal Framework使用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 );

遍历框架 Java API

TraversalDescription

Traverser 对象

使用 relationships()

使用 Evaluator

内置 Evaluators

Evaluator 的自定义实现

Uniqueness 选项

BranchOrderingPolicy 和 BranchSelector

使用PathExpander

内置PathExpander

PathExpanderBuilder