DAG 最长路径

术语表

有向: 有向图特性。该算法在有向图上定义良好。
有向: 有向图特性。该算法忽略图的方向。
有向: 有向图特性。该算法不适用于有向图。
无向: 无向图特性。该算法在无向图上定义良好。
无向: 无向图特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法具有区分不同类型节点的能力。
异构节点: 异构节点允许使用。无论标签如何，该算法对所有选定节点的处理方式相同。
异构关系: 异构关系完全支持。该算法具有区分不同类型关系的能力。
异构关系: 异构关系允许使用。无论类型如何，该算法对所有选定关系的处理方式相同。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特性。该算法将每种关系视为同等重要，丢弃任何关系权重值。
节点属性: 节点属性特性。该算法利用节点属性。

简介

对于 DAG（即不包含循环的图）这一特殊情况，可以在线性时间内找到指向图中某个节点的最长路径。

GDS 对该问题的实现基于拓扑排序，并在线性时间内运行。当图不是 DAG 时，任何属于包含至少一个循环的组件的节点都将从结果中排除。也就是说，该实现仅针对构成 DAG 的图组件提供结果。

你可以使用拓扑排序来确保该图是一个 DAG。

该算法支持加权图和无权图。目前不支持负权重。

使用

该算法的一个使用示例是在供应链图的背景下。如果边表示供应时间，则指向目标节点的最长路径距离就是从决策到完成制造该节点所需的时间。

语法

本节介绍了在每种执行模式下执行 DAG 最长路径算法所使用的语法。我们正在描述该语法的命名图变体。要了解有关通用语法变体的更多信息，请参阅语法概述。

示例 1. 每种模式下的最长路径语法

在命名图上以流模式运行 DAG 最长路径。

CALL gds.dag.longestPath.stream(
  graphName: String,
  configuration: Map
) YIELD
  index: Integer,
  sourceNode: Integer,
  targetNode: Integer,
  totalCost: Float,
  nodeIds: List of Integer,
  costs: List of Float,
  path: Path

表 1. 参数
名称	类型	默认	可选	描述
graphName	字符串	`不适用`	否	存储在目录中的图的名称。
配置	Map	`{}`	是	算法特定配置和/或图过滤配置。

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
1. 在 GDS 会话中，默认值为可用处理器数量。

表 3. 结果
名称	类型	描述
index	整数	已发现路径的从 0 开始的索引。
sourceNode	整数	路径的源节点。
targetNode	整数	路径的目标节点。
totalCost	浮点数	从源到目标的总成本。
nodeIds	整数列表	遍历顺序中路径上的节点 ID。
costs	浮点数列表	路径上每个节点的累计成本。
path	路径	以 Cypher 实体表示的路径。

示例

在本节中，我们将展示在具体图上运行 DAG 最长路径算法的示例。其目的是说明结果的样子，并为如何在实际环境中使用该算法提供指导。我们将使用一个小型的供应链图进行演示，该图由少量按特定模式连接的节点组成。示例图如下所示：

以下 Cypher 语句将在 Neo4j 数据库中创建示例图：

CREATE
       (n0:Goods {name: 'Timber'}),
       (n1:Goods {name: 'Lumber'}),
       (n2:Goods {name: 'Screws'}),
       (n3:Workshop {name: 'Table Maker'}),
       (n4:Product {name: 'Table'}),

       (n0)-[:Processing {time: 1}]->(n1),
       (n1)-[:Shipment {time: 0}]->(n3),
       (n2)-[:Shipment {time: 3}]->(n3),
       (n3)-[:Processing {time: 1}]->(n4)

该图描述了一个简单的供应链，即在“桌子制造坊”（Table Maker workshop）制造桌子的过程。为了获得桌子所需的木材，工作坊需要加工木料，这需要 1 天时间。一旦木材准备好，它就已经在工作坊中了，因此运输它不需要时间。然而，螺丝需要 3 天才能运送到工作坊。只有在工作坊满足所有要求后，才能制造桌子，这个过程需要 1 天。

通往桌子节点的最长路径从螺丝开始，然后是工作坊，最后是桌子，总共需要：4 天。这就是瓶颈路径，也是制造桌子所需的总时间。

以下 Cypher 语句将把图投影到 GDS：

MATCH (n)
OPTIONAL MATCH (n)-[r:Processing|Shipment]->(target)
RETURN gds.graph.project("g", n, target, {relationshipProperties: r {.time}})

流模式

流过程（stream procedure）会流式输出图中的每个节点以及指向该节点的最长路径距离。

有关流模式的更多一般性详细信息，请参阅流 (Stream)。

以下内容将在带有权重的 stream 模式下运行最长路径算法：

CALL gds.dag.longestPath.stream("g", {relationshipWeightProperty: "time"})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).name AS sourceNode,
    gds.util.asNode(targetNode).name AS targetNode,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
    costs,
    nodes(path) as path
ORDER BY index

我们使用实用函数 asNode 来返回节点名称而不是 ID，以使结果更具可读性。

表 4. 结果
index	sourceNode	targetNode	totalCost	nodeNames	costs	path
0	"Timber"（木料）	"Timber"（木料）	0.0	["Timber"]	[0.0]	[Node[0]]
1	"Timber"（木料）	"Lumber"（木材）	1.0	["Timber", "Lumber"]	[0.0, 1.0]	[Node[0], Node[1]]
2	"Screws"（螺丝）	"Table Maker"（桌子制造坊）	3.0	["Screws", "Table Maker"]	[0.0, 3.0]	[Node[2], Node[3]]
3	"Screws"（螺丝）	"Screws"（螺丝）	0.0	["Screws"]	[0.0]	[Node[2]]
4	"Screws"（螺丝）	"Table"（桌子）	4.0	["Screws", "Table Maker", "Table"]	[0.0, 3.0, 4.0]	[Node[2], Node[3], Node[4]]