拓扑排序

有向

无向

异构节点

异构关系

加权关系

词汇表

有向: 有向特征。该算法在有向图上定义良好。
有向: 有向特征。该算法忽略图的方向。
有向: 有向特征。该算法不在有向图上运行。
无向: 无向特征。该算法在无向图上定义良好。
无向: 无向特征。该算法忽略图的无向性。
异构节点: 异构节点完全支持。该算法能够区分不同类型的节点。
异构节点: 异构节点允许。该算法对所有选定的节点进行类似的处理，而不管其标签如何。
异构关系: 异构关系完全支持。该算法能够区分不同类型的关系。
异构关系: 异构关系允许。该算法对所有选定的关系进行类似的处理，而不管其类型如何。
加权关系: 加权特征。该算法支持将关系属性用作权重，通过 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（它是循环的一部分）到达，因此它也将被排除。

用法

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

循环检测

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

从源节点到目标节点的最大距离

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

在节点模拟具有依赖关系的任务的情况下，了解最大距离可以帮助更有效地安排任务：如果两个节点与源节点具有相同的最大距离，则它们之间没有依赖关系，并且可以并行安排。

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

语法

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

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

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

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

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

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

表 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模式下运行拓扑排序算法，并启用从源节点到目标节点的最大距离功能。

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