拓扑排序

此功能在 Aura 图分析无服务器中不可用。

有向

无向

异构节点

异构关系

加权关系

术语表

有向: 有向特性。该算法在有向图上定义良好。
有向: 有向特性。该算法忽略图的方向。
有向: 有向特性。该算法不能在有向图上运行。
无向: 无向特性。该算法在无向图上定义良好。
无向: 无向特性。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点一视同仁，无论其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系一视同仁，无论其类型如何。
加权关系: 加权特性。该算法支持将关系属性用作权重，通过 relationshipWeightProperty 配置参数指定。
加权关系: 加权特性。该算法将每个关系视为同等重要，忽略任何关系权重的价值。

此功能处于 Alpha 阶段。有关功能阶段的更多信息，请参阅 API 阶段。

简介

图中的节点拓扑排序是一种节点排序方式，其中每个节点仅在其所有指向它的节点都出现之后才出现。例如，对于一个有 4 个节点和这些关系的图：`a→b`、`a→c`、`b→d`、`c→d`，有两种可接受的拓扑排序：`a, b, c, d` 和 `a, c, b, d`。

节点的拓扑顺序仅针对有向无环图 (DAG) 定义。有关含环图的预期结果，请参阅下文。

GDS 为该算法提供了高效的并行实现。

循环

在有环图上运行该算法将导致部分节点被排除在排序之外。被排除的节点是：

属于循环一部分的节点（包括自循环）
依赖于循环的节点。这意味着可以从属于循环的另一个节点到达的节点

图中所有其他节点将按有效的拓扑顺序排序。

例如，在以下图中，只有节点 0 会参与排序。节点 1 和 2 是循环的一部分，因此将从排序中排除。节点 3 可以从节点 1 到达，而节点 1 是循环的一部分，因此节点 3 也将被排除。

用法

节点的拓扑排序在您希望确保一个节点仅在其依赖项处理完毕后才被处理时非常有用。这对于依赖相关任务（例如调度或从其依赖项派生值的计算）非常有用。

循环检测

该算法还可以用于确定图是否包含循环。如果图中所有节点都出现在排序中，则图中没有循环。如果排序中缺少某些节点，则存在循环。它不会说明哪些节点构成循环，但会提供线索，如循环部分所述。

距源节点的最大距离

除了排序后的节点 ID，该算法还可以返回节点到任何源节点（即没有任何入站关系的节点）的最大距离。如果您对实际的最长路径感兴趣，您应该查看最长路径算法。

在节点建模具有依赖关系的任务的情况下，了解最大距离有助于更高效地调度任务：如果两个节点到源节点的距离相同，则它们之间没有依赖关系，可以并行调度。

要使用此功能，请将 `computeMaxDistanceFromSource` 设置为 `true`。请注意，这将带来更高的内存使用量和略长的运行时间。

语法

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

示例 1. 每种模式下的拓扑排序语法

在命名图上以流模式运行拓扑排序。

CALL gds.dag.topologicalSort.stream(
  graphName: String,
  configuration: Map
) YIELD
  nodeId: Integer,
  maxDistanceFromSource: Float

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

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

false
名称	类型	描述
是否启用计算距源节点的最大距离	concurrency	1. 在 GDS 会话中，默认值为可用处理器数量
表 3. 结果	concurrency	nodeId

整数

排序中当前节点的 ID

maxDistanceFromSource

CREATE
       (n0:Part {name: 'Cement'}),
       (n1:Part {name: 'Base'}),
       (n2:Part {name: 'Skeleton'}),
       (n3:Part {name: 'Steel'}),
       (n4:Part {name: 'Support'}),
       (n5:Part {name: 'Door'}),
       (n6:Part {name: 'House'}),

       (n0)-[:REQUIRED]->(n1),
       (n1)-[:REQUIRED]->(n2),
       (n3)-[:REQUIRED]->(n4),
       (n4)-[:REQUIRED]->(n2),
       (n2)-[:REQUIRED]->(n5),
       (n5)-[:REQUIRED]->(n6)

整数

节点与源节点之间的最大节点数

MATCH (n)
OPTIONAL MATCH (n)-[r:REQUIRED]->(target)
RETURN gds.graph.project("g", n, target, {})

示例

在本节中，我们将展示在具体图上运行拓扑排序算法的示例。目的是说明结果如何，并提供如何在实际设置中使用该算法的指南。我们将在一个包含少量节点并以特定模式连接的小型供应链图上进行此操作。示例图如下所示：

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

该图描述了建造房屋的简化供应链。房屋的每个部分都必须在其要求得到满足后才能进行施工。例如，在获得钢材之前我们无法建造支撑，骨架在支撑和基础都准备好之前无法完成。

CALL gds.dag.topologicalSort.stream("g", {computeMaxDistanceFromSource: true})
YIELD nodeId, maxDistanceFromSource
RETURN gds.util.asNode(nodeId).name AS name, maxDistanceFromSource
ORDER BY maxDistanceFromSource, name

以下 Cypher 语句将图投影到 GDS

流模式
流式过程按有效的拓扑顺序流式传输图中的节点。然后可以逐个处理节点，确保每个节点仅在其依赖项处理完毕后才被处理。	表 3. 结果
有关流模式的更多详细信息，请参阅流模式。	0.0
以下将在 `stream` 模式下运行拓扑排序算法，并启用距源节点最大距离功能。	0.0
我们使用实用函数 `asNode` 返回节点名称而不是其 ID，以使结果更具可读性。	1.0
表 4. 结果	1.0
名称	2.0
"水泥"	3.0
"钢材"	4.0