最小有向斯坦纳树

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

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

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

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

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

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

注意事项

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

最小有向斯坦纳树问题是更一般化的无向图最小斯坦纳树问题的一个变种。最小斯坦纳树问题仅接受一组目标节点作为输入。目标是找到一个连接这些目标节点的最小权重生成树。

可以通过任意选择其中一个目标节点来充当源节点，从而使用 GDS 实现来找到最小斯坦纳树问题的解决方案。

语法

每种模式下的生成树语法

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

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

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

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

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

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

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

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[2]`	是	运行算法时使用的并发线程数。
jobId	字符串	`内部生成`	是	一个 ID，可以提供此 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	整数	运行算法的毫秒数。
configuration	映射	用于运行算法的配置。

在命名图上以 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	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定配置和/或图过滤配置。

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

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

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

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	字符串	`不适用`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定配置和/或图过滤配置。

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[3]`	是	运行算法时使用的并发线程数。
jobId	字符串	`内部生成`	是	一个 ID，可以提供此 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	整数	写回结果数据的毫秒数。
configuration	映射	用于运行算法的配置。

示例

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

示例通常使用 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 的更多详细信息，请参阅内存估算。

以下将估算以 stats 模式运行算法所需的内存

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 字节 ... 864 字节]"

流模式

在 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. 结果
node	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 执行模式下，算法返回包含算法结果摘要的单行。此执行模式没有任何副作用。通过检查 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 执行模式扩展了 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. 结果
源	目标	weight
"A"	"B"	1.0
"A"	"F"	10.0
"B"	"C"	1.0
"C"	"D"	4.0
"C"	"E"	6.0

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

变异模式

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

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

重路由示例

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

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

简单重路由

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

请注意，不能保证启用重路由总是能带来质量上的改进。

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

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. 结果
node	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. 结果
node	parent	weight
"A"	"A"	0.0
"D"	"F"	3.0
"E"	"A"	7.0
"F"	"A"	10.0

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

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