拓扑排序 (Topological Sort)

在 Aura 图分析中，此功能仅可通过 Python 客户端使用。它目前无法作为 Cypher 过程或函数使用。

术语表

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

简介

图节点的拓扑排序是指对图中所有节点进行的一种排序，使得每个节点都在指向它的所有节点之后出现。例如，对于一个包含 4 个节点和以下关系的图：a→b、a→c、b→d、c→d，有两种可行的拓扑排序：a, b, c, d 和 a, c, b, d。

节点的拓扑顺序仅针对有向无环图 (DAG) 定义。关于图中存在环时的预期结果，请参见下文。

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

环 (Cycles)

在包含环的图上运行该算法会导致部分节点被排除在排序之外。被排除的节点包括：

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

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

例如，在下图中，只有节点 0 会参与排序。节点 1 和 2 属于一个环，因此将被排除在排序之外。节点 3 可以从节点 1 到达（节点 1 是环的一部分），因此它也将被排除。

使用

当您希望确保节点仅在其依赖项处理完毕后才被处理时，拓扑排序非常有用。这对于诸如调度或根据依赖项派生计算值等依赖相关任务非常有效。

环检测

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

距源节点的最大距离

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

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

要使用此功能，请将 computeMaxDistanceFromSource 设置为 true。请注意，这会增加内存使用量并略微增加运行时间。

语法

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

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

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

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

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

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

表 3. 结果
名称	类型	描述
nodeId	整数	排序中当前节点的 ID
maxDistanceFromSource	整数	该节点与源节点之间的最大节点数

示例

在本节中，我们将展示在具体图上运行拓扑排序算法的示例。旨在演示结果的样子，并提供如何在实际环境中使用该算法的指南。我们将使用一个小型供应链图，其中的节点以特定模式连接。示例图如下所示：

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

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)

该图描述了一个建造房屋的简化供应链。房屋的每个部分在满足其先决条件之前都无法开工。例如，在获得钢材之前无法建造支撑结构，在支撑结构和基础都准备好之前，骨架还没准备好。

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

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

流模式

流过程以有效的拓扑顺序输出图中的节点。然后可以逐个处理这些节点，保证每个节点仅在其依赖项处理完成后才被处理。

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

以下代码将在 stream 模式下运行拓扑排序算法，并启用距源节点的最大距离功能。

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

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

表 4. 结果
名称 (name)	maxDistanceFromSource
"水泥"	0.0
"钢材"	0.0
"基础"	1.0
"支撑"	1.0
"骨架"	2.0
"门"	3.0
"房屋"	4.0