最小有向斯坦纳树

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

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

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

众所周知，最小有向斯坦纳树问题是 NP 完全问题，文献中还没有提出有效的精确算法。Neo4j GDS 库提供了一种针对斯坦纳树相关问题的著名启发式算法的高效实现。

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

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

注意事项

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

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

可以使用 GDS 实现来找到最小斯坦纳树问题的解决方案，方法是任意选择一个目标节点来充当源节点的角色。

语法

每个模式下的生成树语法

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

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

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

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

表 3. 结果
名称	类型	描述
nodeId	整数	发现的生成树中的一个节点。
parentId	整数	生成树中 nodeId 的父节点，如果它等于源节点，则为 nodeId 本身。
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	字符串	`n/a`	否	存储在目录中的图的名称。
configuration	映射	`{}`	是	算法特定和/或图过滤的配置。

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

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

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

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

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

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

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

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

示例

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

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

在本节中，我们将展示在具体图上运行 Steiner Tree 启发式算法的示例。目的是说明结果是什么样子，并提供有关如何在实际环境中使用该算法的指南。我们将在少量节点以特定模式连接的小型道路网络图上进行此操作。示例图如下所示

以下将创建图中所示的示例图

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

流

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

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

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

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 模式的更多详细信息，请参阅写入。

以下将运行最小有向 Steiner 树算法并将结果写回图。

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 模式的更多详细信息，请参阅变异。

以下将运行最小有向 Steiner 树算法并变异内存图。

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 来启用此选项。

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

简单重新路由

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

请注意，启用重新路由不能保证始终能提高质量。

以下将以流模式运行具有重新路由功能的最小有向 Steiner 树算法，并返回每个有效节点的结果。

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，Steiner 树的总权重减少了 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 的最优 Steiner 树。

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