奖品收集施泰纳树

有向

无向

异构节点

异构关系

加权关系

词汇表

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

简介

生成树是一种图，其中集合中任意两个节点之间都只有一条路径。图可以有许多可能的生成树子集，具体取决于所选节点/关系的集合。

给定一个每个节点都有奖品的加权图，奖品收集施泰纳树问题要求找到满足以下条件的生成树

图中节点的奖品总和最大化。
树中不存在的关系的权重和节点的奖品总和最小化。

这两个约束可以通过简单地用第一个约束减去第二个约束来组合成一个单一的最大化问题。

奖品收集施泰纳树是 NP-完全问题，目前尚无已知的有效精确算法。Neo4j GDS 库实现了一种实用的 2-近似算法。这意味着返回的答案至少是最佳答案的一半。

考量

默认情况下，奖品收集施泰纳树问题只考虑节点的奖品。但在某些情况下，考虑关系上的奖品也可能有用。GDS 实现可以通过以下转换来处理关系的奖品：给定一个权重为 w、奖品为 p 的关系，我们建议将 w 替换为 w' = w - p。这应在投影内存图之前作为预处理步骤完成。

语法

各模式下的奖品收集施泰纳树语法

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

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

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

表 2. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
prizeProperty	字符串	`不适用`	否	表示节点奖品的节点属性名称。
1. 在 GDS 会话中，默认值为可用处理器数量

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

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

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

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

表 5. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
prizeProperty	字符串	`不适用`	否	表示节点奖品的节点属性名称。
2. 在 GDS 会话中，默认值为可用处理器数量

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

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

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

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

表 8. 配置
名称	类型	默认值	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系类型。
mutateProperty	字符串	`不适用`	否	权重被写入的 GDS 图中的关系属性。
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
prizeProperty	字符串	`不适用`	否	表示节点奖品的节点属性名称。

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

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

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

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

表 11. 配置
名称	类型	默认值	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定节点标签过滤命名图。将包含具有任何给定标签的节点。
relationshipTypes	字符串列表	`['*']`	是	使用给定关系类型过滤命名图。将包含具有任何给定类型的关系。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可用于更轻松地跟踪算法进度的 ID。
logProgress	布尔值	`true`	是	如果禁用，则不会记录进度百分比。
writeConcurrency	整数	`“concurrency”的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于在 Neo4j 数据库中持久化计算关系的类型。
writeProperty	字符串	`不适用`	否	权重被写入的 Neo4j 数据库中的关系属性。
relationshipWeightProperty	字符串	`null`	是	用作权重的关系属性名称。如果未指定，算法将以无权重模式运行。
prizeProperty	字符串	`不适用`	否	表示节点奖品的节点属性名称。
3. 在 GDS 会话中，默认值为可用处理器数量

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

示例

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

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

在本节中，我们将展示在具体图上运行奖品收集施泰纳树算法的示例。目的是说明结果是什么样子，并提供在实际设置中如何使用该算法的指南。我们将在一个包含少量节点并以特定模式连接的小型道路网络图上进行此操作。示例图如下所示

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

CREATE (a:Place {id: 'A', prize: 5.0}),
       (b:Place {id: 'B', prize: 20.0}),
       (c:Place {id: 'C',prize: 11.0}),
       (d:Place {id: 'D',prize: 10.0}),
       (e:Place {id: 'E',prize: 8.0}),
       (f:Place {id: 'F',prize: 1.0}),
       (a)-[:LINK {cost:10}]->(f),
       (a)-[:LINK {cost:3}]->(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,
{
    sourceNodeProperties: source { .prize },
    targetNodeProperties: target { .prize },
    relationshipProperties: r { .cost }
  },
  { undirectedRelationshipTypes: ['*'] }
)

内存估算

首先，我们将使用 estimate 过程估算运行算法的成本。这可以通过任何执行模式完成。在此示例中，我们将使用 stream 模式。估算算法有助于了解在您的图上运行算法将产生的内存影响。当您随后实际以某种执行模式运行算法时，系统将执行估算。如果估算显示执行超出其内存限制的可能性非常高，则将禁止执行。要了解更多信息，请参阅自动估算和执行阻止。

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

以下将估算在流模式下运行算法的内存要求

CALL gds.prizeSteinerTree.stream.estimate('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
节点计数	关系计数	最小字节数	最大字节数	所需内存
6	14	3897	561616	"[3897 字节 ... 548 KiB]"

流模式

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

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

以下将以流模式运行奖品收集施泰纳树算法，并返回每个有效节点的结果。

CALL gds.prizeSteinerTree.stream('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize'
})
YIELD nodeId,parentId, weight
RETURN gds.util.asNode(nodeId).id AS node, gds.util.asNode(parentId).id AS parent,weight
ORDER BY node

表 14. 结果
节点	父节点	权重
"A"	"B"	3.0
"B"	"C"	1.0
"D"	"C"	4.0
"E"	"C"	6.0

该算法找到一棵包含 A、B、C、D 和 E 的树。节点 F 被跳过，因为它奖品非常低，并且将其与其他节点连接会产生次优解。

统计模式

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

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

以下将以统计模式运行奖品收集施泰纳树算法，并返回其统计信息。

CALL gds.prizeSteinerTree.stats('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize'
})
YIELD effectiveNodeCount, totalWeight, sumOfPrizes
RETURN effectiveNodeCount, totalWeight, sumOfPrizes

表 15. 结果
effectiveNodeCount	totalWeight	sumOfPrizes
5	14.0	54.0

统计模式为我们提供了有关连接树中关系总权重的信息，即 14.0，以及节点 A、B、C、D 和 E 的奖品总和，即 54.0。

修改模式

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

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

以下将以修改模式运行奖品收集施泰纳树算法，并返回其统计信息。

CALL gds.prizeSteinerTree.mutate('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize',
  mutateProperty: 'weight',
  mutateRelationshipType: 'STEINER'
})
YIELD effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten
RETURN effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten

表 16. 结果
effectiveNodeCount	totalWeight	sumOfPrizes	relationshipsWritten
5	14.0	54.0	4

mutate 模式将内存图 graph 更新为新的关系类型 STEINER，并带有一个 weight 属性。从 relationshipsWritten 列中，我们可以看到恰好添加了四个这样的关系。它们连接施泰纳树中的节点，并且它们的属性是每个连接的成本。

添加回图中的关系始终是有向的，即使输入图是无向的。它们以固定的树顺序从父节点指向子节点。

写入模式

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

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

以下将以写入模式运行奖品收集施泰纳树算法，并返回其统计信息。

CALL gds.prizeSteinerTree.write('graph', {
  relationshipWeightProperty: 'cost',
  prizeProperty: 'prize',
  writeProperty: 'weight',
  writeRelationshipType: 'STEINER'
})
YIELD effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten
RETURN effectiveNodeCount, totalWeight, sumOfPrizes, relationshipsWritten

表 17. 结果
effectiveNodeCount	totalWeight	sumOfPrizes	relationshipsWritten
5	14.0	54.0	4

此查询将四条新的 STEINER 类型关系写入数据库，每条关系都带有一个 weight 属性。

添加回的关系始终是有向的，即使输入图是无向的。它们以固定的树顺序从父节点指向子节点。