使用 Neo4j Traversal API 进行航班搜索

在 Cypher 出现之前，如果您想在 Neo4j 中描述图形遍历，您将使用 Traversal Framework Java API 。 Traversal API 是 Neo4j 众多隐藏的瑰宝之一，今天我们将仔细研究它。遍历图就是去旅行。所有旅程都有一个（或多个）起点，因此这是我们要做的第一件事，找出我们在图中开始的位置。它可以是单个节点，也可以是多个节点，但它们将遵循相同的规则继续旅程，因此如果它只是一个节点或相同“类型”的节点，则更容易。

然后我们必须建立一组节点将遵循的规则或描述。第一个决定是 Order 。一个节点应该沿着一条路径一直走到尽头（深度优先），还是应该一次探索每条路径（广度优先）。想一想，你有一个岔路口，你是一直走到一条路的尽头，还是在一条路上走一步，往回走，然后在另一条路上走一步，再走两步在第一条路径上走几步，然后返回，在第二条路径上走两步，等等？您可以看出，沿着一条路径走到尽头会更容易（内存占用更少），并且在大多数情况下，这是首选顺序。

您必须做出的下一个决定是 Uniqueness 。你希望能够多次访问节点，多次访问关系，你一点都不关心吗？使用 Cypher 时，您无法匹配多次遍历同一关系的模式，它强制关系唯一性。除非您正在进行图形分析，否则这就是您大部分时间想要做的事情。

您应该遍历哪些关系类型才能到达目的地？这就是 Path Expanders 的作用。回到我们的旅程类比，你可能想穿过黄砖路，而不是红砖路。也许您想在第一步中尝试一种关系类型，而在第二步中尝试一种不同的关系类型。

所有的旅程都有终点，但并非所有的旅程都会成功。评估器决定我们是否到达了遍历的有效终点，或者我们是否需要继续前进，或者我们是否已经走上了一条糟糕的道路并且应该停下来。它还可以告诉我们什么时候已经走得足够远，不应该采取任何进一步的步骤。

这在代码中看起来像什么？让我们来看看：


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

Cypher 中的等效项类似于：


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

但是，如果您像文档示例那样允许从任一方向遍历 KNOWS 关系会怎样？


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

尝试用 Cypher 编写会更加混乱。注意到我们是如何在深度 5 处停止的吗？这是框架内置的通用评估器。有十几个可供选择，您可以混合搭配它们。请注意“.relationships”是如何被调用两次的？您可以使用此辅助方法来构建 PathExpander 。或者，您可以使用 PathExpanderBuilder 来制作一些有趣的内容，例如：


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

这将限制 PathExpander 仅遵循 RelationshipTypes.LIKES 的 Direction.INCOMING 关系，同时沿任一方向遵循任何其他关系类型。在 Cypher 中试试看。您还可以通过自己编写来完全自定义评估器和扩展器。让我们看看我们如何应用我们所看到的在 Neo4j 中构建航班调度引擎。

我们的服务将采用一系列起始机场，而不仅仅是一个机场，因为一些大都市地区为乘客提供多个机场选择。在芝加哥，我们有 O'Hare 和 Midway。它将需要一个结束机场列表（出于同样的原因）。这将需要一个航班日期。高优先级航空公司列表（针对飞行常客和回程用例）。可选地，它会限制它可以返回的记录数或收集这些结果所需的最长时间。

我们有上一篇博文中的模型，如果您还没有看到它，请回过头来参考一下。因此，我们要做的第一件事是创建一个自定义评估器，用于收集有效的飞行路线（在我们的遍历中表示为路径）。

它通过获取潜在目的地列表和最大长度来工作。它评估路径上的每一步，如果它不是我们需要的长度，它就会排除该路径太短并继续。如果我们最终到达一个不是 AirportDay 的节点，那么我们将其排除并继续。如果我们最终到达了 AirportDay 节点，那么我们会检查它是否是我们想要的目的地之一。如果是，那么我们包括该路径并尝试另一条路径。如果不是，我们排除这条路径并去尝试另一条路径。


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

我们将在查询中使用一些扩展器。我们通过实现 PathExpander 创建 NonStopExpander。构造函数采用我们想要到达的目的地、我们将要尝试的航空公司和一个 stopTime 以在我们用完时间时停止遍历。描述如何遍历图的方法是“展开”。我们想要返回一组关系。一种方法是使用路径的长度，并用它来指导返回哪些关系。如果我们遇到了死胡同，我们将返回一个空列表，如下所示：


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

我会把模型的图片放在下面，这样更容易理解。在 path.length “0” 处，我们处于起点，因此我们将遍历 HAS_DESTINATION 关系。一旦到达那里，我们的路径现在长度为 1，因此我们检查目的地代码以查看它是否与我们的目的地匹配。如果没有，我们放弃，否则，我们继续我们的 AirlineFlight 关系的两跳，直到我们到达 AirportDay 节点并且 Evaluator 从这里接管。

那么我们如何获得这些 AirlineFlight 关系呢？我们将创建一个标记为“Metadata”的节点，其名称属性为“Airlines”。我们将创建一堆航空公司并将它们连接到这个“元节点”。然后我们可以查询图形以获取我们应该遍历的 AirlineFlight 关系的名称。

代码如下。我们会在第一次进行查询时以及在我们的系统中添加/删除或更新航空公司时调用它。


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

为了在每个查询的基础上获得订单，我们创建了一个 ListOrderedSet 并首先添加查询高优先级航空公司，然后是所有其他航空公司。重复的条目不会改变顺序。


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

我们现在可以创建我们的扩展器：


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

…以及我们的 TraversalDescription：


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

最后，我们可以调用 TraversalDescription 的“traverse”方法，并将航班属性添加到我们将其转换为 JSON 并在最后发回的结果数组中。


 TraversalDescription myTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( RelationshipTypes.KNOWS, Direction.INCOMING )
        .relationships( RelationshipTypes.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) );

对于直飞、一站和两站航班，我们会多做几次。出于理智考虑，我将它们分开，出于性能原因（请记住它首先进入深度）并允许查询限制行程中允许的停靠点数量。完整的源代码一如既往地在 github 上可用。因此，请确保您的手提行李妥善存放，座椅放正，小桌放好，手机处于飞行模式，系好安全带，祝您旅途愉快。

使用 Neo4j Traversal API 进行航班搜索

相关文章