最小有向斯坦纳树 (Minimum Directed Steiner Tree)

术语表

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

简介

给定一个源节点和一组目标节点，如果存在从源节点到每个目标节点的路径，则称该有向生成树为有向斯坦纳树。

最小有向斯坦纳树问题旨在寻找一棵使树中所有关系权重之和最小化的斯坦纳树。

已知最小有向斯坦纳树问题是 NP-完全问题，文献中尚未提出高效的精确算法。Neo4j GDS 库为斯坦纳树相关问题提供了一种高效的启发式实现。

所实现的算法分多个步骤进行。在每一步中，找到从源节点到某个未发现目标节点的最短路径，并将其添加到结果中。随后，将该路径中关系的权重减少为零，算法继续以类似方式寻找下一个最近的未访问目标节点。

通过精心的实现，上述启发式算法即使在大型图上也能高效运行。此外，使用了Delta-Stepping 的并行最短路径算法来进一步加快计算速度。

注意事项

由于最小有向斯坦纳树算法依赖于最短路径，它不适用于包含负权关系的图。

最小有向斯坦纳树问题是无向图上更通用的最小斯坦纳树问题的一个变体。最小斯坦纳树问题仅以一组目标节点作为输入，其目标是寻找连接这些目标节点的最小权重生成树。

可以通过任意选择其中一个目标节点作为源节点，使用 GDS 实现来求解最小斯坦纳树问题。

语法

各模式下的生成树语法

在命名图上以流模式运行算法。

CALL gds.steinerTree.stream(
  graphName: String,
  configuration: Map
)
YIELD
  nodeId: Integer,
  parentId: Integer,
  weight: Float

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`null`	不适用	起始源节点 ID。
targetNodes	整数列表	`null`	不适用	目标节点列表。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
delta	浮点数	`2.0`	是	用于对到源节点具有相同暂定距离的节点进行分组的桶宽度。有关更多信息，请参阅 Delta-Stepping 文档。
applyRerouting	布尔值	`false`	是	如果指定，算法将尝试通过额外的后处理启发式方法来改善结果。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
nodeId	整数	发现的生成树中的一个节点。
parentId	整数	节点在生成树中的父节点 ID；如果节点等于源节点，则为节点自身 ID。
weight	浮点数	从 parentId 到 nodeId 的关系权重。

在命名图上以统计模式运行算法。

CALL gds.steinerTree.stats(
  graphName: String,
  configuration: Map
)
YIELD
  effectiveNodeCount: Integer,
  effectiveTargetNodesCount: Integer,
  totalWeight: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  configuration: Map

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
sourceNode	整数	`null`	不适用	起始源节点 ID。
targetNodes	整数列表	`null`	不适用	目标节点列表。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
delta	浮点数	`2.0`	是	用于对到源节点具有相同暂定距离的节点进行分组的桶宽度。有关更多信息，请参阅 Delta-Stepping 文档。
applyRerouting	布尔值	`false`	是	如果指定，算法将尝试通过额外的后处理启发式方法来改善结果。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
effectiveNodeCount	整数	生成树中的节点数。
effectiveTargetNodesCount	整数	生成树中的目标节点数。
totalWeight	浮点数	生成树中所有关系权重的总和。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以修改模式（mutate）运行生成树算法。

CALL gds.steinerTree.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  effectiveNodeCount: Integer,
  effectiveTargetNodesCount: Integer,
  totalWeight: Float,
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系的关系类型。
mutateProperty	字符串	`不适用`	否	写入权重的 GDS 图中的关系属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
sourceNode	整数	`null`	不适用	起始源节点 ID。
targetNodes	整数列表	`null`	不适用	目标节点列表。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
delta	浮点数	`2.0`	是	用于对到源节点具有相同暂定距离的节点进行分组的桶宽度。有关更多信息，请参阅 Delta-Stepping 文档。
applyRerouting	布尔值	`false`	是	如果指定，算法将尝试通过额外的后处理启发式方法来改善结果。

表 9. 结果
名称	类型	描述
effectiveNodeCount	整数	生成树中的节点数。
effectiveTargetNodesCount	整数	生成树中的目标节点数。
totalWeight	浮点数	生成树中所有关系权重的总和。
relationshipsWritten	整数	添加到内存图中关系的数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	将结果数据写回的毫秒数。
配置	Map	用于运行算法的配置。

在命名图上以写入模式（write）运行生成树算法。

CALL gds.steinerTree.write(
  graphName: String,
  configuration: Map
)
YIELD
  effectiveNodeCount: Integer,
  effectiveTargetNodesCount: Integer,
  totalWeight: Float,
  relationshipsWritten: Integer,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  configuration: Map

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于将计算出的关系持久化到 Neo4j 数据库的关系类型。
writeProperty	字符串	`不适用`	否	写入权重的 Neo4j 数据库中的关系属性。
sourceNode	整数	`null`	不适用	起始源节点 ID。
targetNodes	整数列表	`null`	不适用	目标节点列表。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将作为无权重运行。
delta	浮点数	`2.0`	是	用于对到源节点具有相同暂定距离的节点进行分组的桶宽度。有关更多信息，请参阅 Delta-Stepping 文档。
applyRerouting	布尔值	`false`	是	如果指定，算法将尝试通过额外的后处理启发式方法来改善结果。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
effectiveNodeCount	整数	生成树中的节点数。
effectiveTargetNodesCount	整数	生成树中的目标节点数。
totalWeight	浮点数	生成树中所有关系权重的总和。
relationshipsWritten	整数	写入图中的关系数量。
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
配置	Map	用于运行算法的配置。

示例

以下所有示例应在空数据库中运行。

这些示例将 Cypher 投影作为规范。原生投影将在未来版本中弃用。

在本节中，我们将展示在具体图上运行斯坦纳树启发式算法的示例。旨在说明结果的样子，并提供如何在实际场景中使用该算法的指南。我们将使用一个小型的道路网络图进行操作。示例图如下所示：

以下代码将创建图中描绘的示例图

CREATE (a:Place {id: 'A'}),
       (b:Place {id: 'B'}),
       (c:Place {id: 'C'}),
       (d:Place {id: 'D'}),
       (e:Place {id: 'E'}),
       (f:Place {id: 'F'}),
       (a)-[:LINK {cost:10}]->(f),
       (a)-[:LINK {cost:1}]->(b),
       (a)-[:LINK {cost:7}]->(e),
       (b)-[:LINK {cost:1}]->(c),
       (c)-[:LINK {cost:4}]->(d),
       (c)-[:LINK {cost:6}]->(e),
       (f)-[:LINK {cost:3}]->(d);

以下代码将投影并存储一个命名图

MATCH (source:Place)-[r:LINK]->(target:Place)
RETURN gds.graph.project(
  'graph',
  source,
  target,
  { relationshipProperties: r { .cost } }
)

内存估算

首先，我们将使用 estimate 过程估算运行该算法的成本。这可以在任何执行模式下完成。在此示例中，我们将使用 stats 模式。估算算法对于理解在图上运行算法对内存的影响非常有用。当您随后在某种执行模式下实际运行算法时，系统将执行一次估算。如果估算结果显示执行超出其内存限制的概率极高，则会禁止执行。要阅读更多关于此的内容，请参见自动估算和执行阻塞。

有关 estimate 的更多详细信息，请参阅内存估算。

以下代码将估算以统计模式运行算法所需的内存

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.stats.estimate('graph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost'
})
YIELD nodeCount, relationshipCount, requiredMemory
RETURN nodeCount, relationshipCount, requiredMemory

表 13. 结果
nodeCount	relationshipCount	requiredMemory
6	7	"[672 Bytes ... 864 Bytes]"

流 (Stream)

在 stream 执行模式下，算法返回每个关系的权重。这允许我们直接检查结果或在 Cypher 中进行后处理，而不会产生任何副作用。

有关 stream 模式的更多详细信息，请参阅流式读取。

以下代码将以流模式运行最小有向斯坦纳树算法，并返回每个有效节点的结果。

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.stream('graph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost'
})
YIELD nodeId,parentId, weight
RETURN gds.util.asNode(nodeId).id AS node, gds.util.asNode(parentId).id AS parent,weight
ORDER BY node

表 14. 结果
节点	parent	weight
"A"	"A"	0.0
"B"	"A"	1.0
"C"	"B"	1.0
"D"	"C"	4.0
"E"	"C"	6.0
"F"	"A"	10.0

算法首先找到从 A 到 D 的最短路径。然后，尽管从 A 到 E 的关系权重小于加权路径 A,B,C,E 之和，但算法发现 A 到 B 以及 B 到 C 的关系已经包含在解决方案中，因此通过 C 到达 E 是一个更好的选择。最后，算法将 A 到 F 的关系添加到解决方案中并终止。

统计 (Stats)

在 stats 执行模式下，算法返回一行包含算法结果摘要的数据。此执行模式没有任何副作用。它对于通过检查 computeMillis 返回项来评估算法性能非常有用。在下面的示例中，我们将省略返回时间。过程的完整签名可以在语法部分找到。

有关 stats 模式的更多详细信息，请参阅统计。

以下代码将运行最小权重生成树算法并返回其统计信息。

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.stats('graph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost'
})
YIELD effectiveNodeCount, totalWeight
RETURN effectiveNodeCount, totalWeight

表 15. 结果
effectiveNodeCount	totalWeight
6	22.0

写入 (Write)

write 执行模式扩展了 stats 模式，具有一个重要的副作用：将每个关系的权重作为属性写入 Neo4j 数据库。新属性的名称通过强制配置参数 writeProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。write 模式允许直接将结果持久化到数据库中。

有关 write 模式的更多详细信息，请参阅写入。

以下代码将运行最小有向斯坦纳树算法并将结果写回图数据库。

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.write('graph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost',
  writeProperty: 'steinerWeight',
  writeRelationshipType: 'STEINER'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount;

要查找最小生成树中包含的关系，我们可以运行以下查询

MATCH path = (a:Place {id: 'A'})-[:STEINER*]-()
WITH relationships(path) AS rels
UNWIND rels AS rel
WITH DISTINCT rel AS rel
RETURN startNode(rel).id AS Source, endNode(rel).id AS Destination, rel.steinerWeight AS weight
ORDER BY Source, Destination

表 16. 结果
源 (Source)	目标 (Destination)	weight
"A"	"B"	1.0
"A"	"F"	10.0
"B"	"C"	1.0
"C"	"D"	4.0
"C"	"E"	6.0

即使输入图是无向的，写回图中的关系也始终是有向的。

修改 (Mutate)

mutate 执行模式扩展了 stats 模式，具有一个重要的副作用：使用包含该关系权重的新关系属性更新命名图。新属性的名称通过强制配置参数 mutateProperty 指定。结果是单行摘要，类似于 stats，但包含一些额外的指标。当多个算法结合使用时，mutate 模式特别有用。

有关 mutate 模式的更多详细信息，请参阅变更。

以下代码将运行最小有向斯坦纳树算法并修改内存中的图。

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.mutate('graph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost',
  mutateProperty: 'steinerWeight',
  mutateRelationshipType: 'STEINER'
})
YIELD relationshipsWritten
RETURN relationshipsWritten

表 17. 结果
relationshipsWritten
5

即使输入图是无向的，添加回图中的关系也始终是有向的。

重路由示例 (Rerouting)

还可以尝试通过后处理重路由阶段来增强启发式算法发现的解决方案。可以通过在配置中设置 applyRerouting: true 来启用此选项。

该算法支持两种形式的重路由：简单 (simple) 和 扩展 (extended)。扩展重路由比简单重路由更复杂，可以获得更好的质量提升，但需要邻接表的反向索引。

简单重路由

重路由阶段重新检查已发现的斯坦纳树中的关系，并尝试重新路由节点（即将其父节点更改为树中的另一个节点）以降低成本。重路由阶段后，某些节点可能最终没有子节点，即不属于源节点和目标节点之间的任何路径。这些节点随后会从返回的解决方案中删除。

请注意，不能保证启用重路由总是能提高质量。

以下代码将以流模式运行带重路由的最小有向斯坦纳树算法，并返回每个有效节点的结果。

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.stream('graph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost',
  applyRerouting: true
})
YIELD nodeId,parentId, weight
RETURN gds.util.asNode(nodeId).id AS node, gds.util.asNode(parentId).id AS parent, weight
ORDER BY node

表 18. 结果
节点	parent	weight
"A"	"A"	0.0
"B"	"A"	1.0
"C"	"B"	1.0
"D"	"F"	3.0
"E"	"C"	6.0
"F"	"A"	10.0

可以看出，由于重路由步骤，D 的父节点已替换为 F，斯坦纳树的总权重减少了 2。

扩展重路由

我们现在演示扩展重路由的使用。为此，首先需要再次投影图，这次要创建一个反向索引。

MATCH (source:Place)-[r:LINK]->(target:Place)
RETURN gds.graph.project(
  'inverseGraph',
  source,
  target,
  {
    relationshipType: 'LINK',
    relationshipProperties: r { .cost }
  },
  { inverseIndexedRelationshipTypes: ['LINK'] }
)

现在我们再次运行该算法；这次使用扩展重路由启发式方法。

MATCH (a:Place{id: 'A'}), (d:Place{id: 'D'}),(e:Place{id: 'E'}),(f:Place{id: 'F'})
CALL gds.steinerTree.stream('inverseGraph', {
  sourceNode: a,
  targetNodes: [d, e, f],
  relationshipWeightProperty: 'cost',
  applyRerouting: true
})
YIELD nodeId,parentId, weight
RETURN gds.util.asNode(nodeId).id AS node, gds.util.asNode(parentId).id AS parent, weight
ORDER BY node

表 19. 结果
节点	parent	weight
"A"	"A"	0.0
"D"	"F"	3.0
"E"	"A"	7.0
"F"	"A"	10.0

如您所见，多亏了扩展重路由，我们可以进一步降低成本，并返回权重为 20 的最优斯坦纳树。

与主算法不同，重路由阶段是顺序运行的，不受并发参数的影响。