最小成本最大流

术语表

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

简介

最小费用最大流 (MCMF) 算法用于解决在源节点和目标节点之间寻找最大流量且费用最低的问题。

如果仅需计算最大流而不考虑费用，请参阅最大流 (maximum flow)

流量是每条关系的一个非负标量，受限于该关系的容量值。对于图中的某个节点，流入流量的总和等于流出流量的总和，但有两个例外情况

源节点的净流出量是无界的，或者在给定 supply（供应）参数的情况下，受该参数限制。
目标节点（汇点）的净流入量是无界的，或者在给定 demand（需求）参数的情况下，受该参数限制。

常规的最大流问题仅是为关系分配流量以使从源到目标的总传输量最大化，而 MCMF 处理第二个问题：在不降低总流量的前提下，找到该分配方式中最便宜的方案。

在 MCMF 中，每条关系都带有一个费用值 (cost value)。这代表单位流量的费用，因此每条关系的费用等于其流量乘以该费用。将图中所有关系的费用相加即可得出整个流量分配的成本。通过重定向流量，目标是在保持总流量最大的同时，使总成本最小化。

为了运行该算法，用户需要提供源节点和目标节点（可选供应和需求值），并指定分别对应容量和费用的关系属性。

Neo4j GDS 库的实现是基于这篇论文的费用缩放推送重贴标签算法 (cost-scaling push-relabel)。对于整数费用和容量，该算法保证在固定次数的迭代内产生最优解。我们同样允许在双精度浮点数上运行该算法，并使用相同的边界。

语法

本节涵盖了在每种执行模式下执行最小费用最大流算法的语法。我们描述的是命名图 (named graph) 变体的语法。要了解更多关于通用语法变体的信息，请参阅语法概述 (Syntax overview)。

各模式下的最大流语法

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

CALL gds.maxFlow.minCost.stream(
  graphName: String,
  configuration: Map
)
YIELD
  source: Integer,
  target: Integer,
  flow: Float

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

表 2. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[1]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
capacityProperty	字符串	`不适用`	否	用作容量的关系属性名称。
costProperty	字符串	`不适用`	否	用作费用的关系属性名称。
sourceNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此项，则具有给定属性的节点处理的总流量将受到其属性的限制
alpha	整数	`6`	是	算法细化阶段的费用缩放率。调整此参数可以提高速度。
1. 在 GDS 会话中，默认值为可用处理器的数量。

表 3. 结果
名称	类型	描述
source	整数	返回关系中的第一个节点。
target（目标）	整数	返回关系中的第二个节点。
flow	浮点数	返回关系上的流量。

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

CALL gds.maxFlow.minCost.stats(
  graphName: String,
  configuration: Map
)
YIELD
  totalFlow: Float,
  totalCost: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  configuration: Map

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

表 5. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[2]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
capacityProperty	字符串	`不适用`	否	用作容量的关系属性名称。
costProperty	字符串	`不适用`	否	用作费用的关系属性名称。
sourceNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此项，则具有给定属性的节点处理的总流量将受到其属性的限制
alpha	整数	`6`	是	算法细化阶段的费用缩放率。调整此参数可以提高速度。
2. 在 GDS 会话中，默认值为可用处理器的数量。

表 6. 结果
名称	类型	描述
totalFlow	浮点数	到所有目标节点的净流量。
totalCost	浮点数	与返回的流量相关联的费用
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
配置	Map	用于运行算法的配置。

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

CALL gds.maxFlow.minCost.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  totalFlow: Float,
  totalCost: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  mutateMillis: Integer,
  relationshipsWritten: Integer,
  configuration: Map

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

表 8. 配置
名称	类型	默认	可选	描述
mutateRelationshipType	字符串	`不适用`	否	用于写入投影图的新关系的关系类型。
mutateProperty	字符串	`不适用`	否	GDS 图中写入流量的关系属性。
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。
concurrency	整数	`4`	是	用于运行算法的并发线程数。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
capacityProperty	字符串	`不适用`	否	用作容量的关系属性名称。
costProperty	字符串	`不适用`	否	用作费用的关系属性名称。
sourceNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此项，则具有给定属性的节点处理的总流量将受到其属性的限制
alpha	整数	`6`	是	算法细化阶段的费用缩放率。调整此参数可以提高速度。

表 9. 结果
名称	类型	描述
totalFlow	浮点数	到所有目标节点的净流量。
totalCost	浮点数	与返回的流量相关联的费用
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
mutateMillis	整数	将结果数据写回的毫秒数。
relationshipsWritten	整数	添加到内存图中关系的数量。
配置	Map	用于运行算法的配置。

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

CALL gds.maxFlow.minCost.write(
  graphName: String,
  configuration: Map
)
YIELD
  totalFlow: Float,
  totalCost: Float,
  preProcessingMillis: Integer,
  computeMillis: Integer,
  writeMillis: Integer,
  relationshipsWritten: Integer,
  configuration: Map

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

表 11. 配置
名称	类型	默认	可选	描述
nodeLabels	字符串列表	`['*']`	是	使用给定的节点标签过滤命名图。具有任何给定标签的节点都将被包含。
relationshipTypes	字符串列表	`['*']`	是	使用给定的关系类型过滤命名图。具有任何给定类型的关系都将被包含。
concurrency	整数	`4 ^[3]`	是	用于运行算法的并发线程数。
jobId	字符串	`内部生成`	是	可以提供一个 ID 以更轻松地跟踪算法的进度。
logProgress	布尔值	`true`	是	如果禁用，进度百分比将不会被记录。
writeConcurrency	整数	`'concurrency' 的值`	是	用于将结果写入 Neo4j 的并发线程数。
writeRelationshipType	字符串	`不适用`	否	用于将计算出的关系持久化到 Neo4j 数据库的关系类型。
writeProperty	字符串	`不适用`	否	Neo4j 数据库中写入流量的关系属性。
capacityProperty	字符串	`不适用`	否	用作容量的关系属性名称。
costProperty	字符串	`不适用`	否	用作费用的关系属性名称。
sourceNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数 (List of Nodes or Integers) 或整数 (Integer)	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此项，则具有给定属性的节点处理的总流量将受到其属性的限制
alpha	整数	`6`	是	算法细化阶段的费用缩放率。调整此参数可以提高速度。
3. 在 GDS 会话中，默认值为可用处理器的数量。

表 12. 结果
名称	类型	描述
totalFlow	浮点数	到所有目标节点的净流量。
totalCost	浮点数	与返回的流量相关联的费用
preProcessingMillis	整数	预处理数据的毫秒数。
computeMillis	整数	运行算法的毫秒数。
writeMillis	整数	将结果数据写回的毫秒数。
relationshipsWritten	整数	写入图中的关系数量。
配置	Map	用于运行算法的配置。

示例

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

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

在本节中，我们将展示在一个具体图上运行最小费用最大流算法的示例。目的是说明结果的样子，并为如何在实际环境中使用该算法提供指南。我们将在一个由少数节点以特定模式连接的小型图上进行演示。示例图如下所示

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

CREATE (a:Place {id: 'A', constraint: 10.0}),
       (b:Place {id: 'B', constraint: 4.0}),
       (c:Place {id: 'C'}),
       (d:Place {id: 'D'}),
       (e:Place {id: 'E', constriant: 20.0}),
       (a)-[:LINK {capacity: 7, cost: 100}]->(b),
       (b)-[:LINK {capacity: 10, cost: 250}]->(c),
       (b)-[:LINK {capacity: 5, cost: 150}]->(d),
       (c)-[:LINK {capacity: 15, cost: 200}]->(e),
       (d)-[:LINK {capacity: 15, cost: 200}]->(e);

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

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

内存估算

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

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

以下代码将估算以 stream 模式运行该算法所需的内存：

MATCH (a:Place {id: 'A'}), (e:Place {id: 'E'})
CALL gds.maxFlow.minCost.stream.estimate('graph', {
  sourceNodes: [a],
  targetNodes: [e],
  capacityProperty: 'capacity',
  costProperty: 'cost'
})
YIELD nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory
RETURN nodeCount, relationshipCount, bytesMin, bytesMax, requiredMemory

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
5	5	3620	3620	"3620 字节"

流 (Stream)

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

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

以下代码将以流模式运行 MCMF 算法，并为每个有效节点返回结果。

MATCH (a:Place {id: 'A'}), (e:Place {id: 'E'})
CALL gds.maxFlow.minCost.stream('graph', {
  sourceNodes: [a],
  targetNodes: [e],
  capacityProperty: 'capacity',
  costProperty: 'cost'
})
YIELD source, target, flow
RETURN gds.util.asNode(source).id AS src, gds.util.asNode(target).id AS tgt, flow
ORDER BY src, tgt

表 14. 结果
src	tgt	flow
"A"	"B"	7.0
"B"	"C"	2.0
"B"	"D"	5.0
"C"	"E"	2.0
"D"	"E"	5.0

该算法分别通过 B-D 和 B-C 将流量从源 (A) 引导至目标 (E)。A-B 处存在瓶颈，阻止了更多流量到达 E，因此显而易见，最大流量为 7。从 B 到目标有两条路径，B→D→E（费用 350）和 B→C→E（费用 450）。由于前者更便宜，因此被优先充分利用，剩下的流量则沿着后者更昂贵的路径发送。

统计信息 (Stats)

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

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

以下代码将以统计模式运行 MCMF 算法并返回其统计信息。

MATCH (a:Place {id: 'A'}), (e:Place {id: 'E'})
CALL gds.maxFlow.minCost.stats('graph', {
  sourceNodes: [a],
  targetNodes: [e],
  capacityProperty: 'capacity',
  costProperty: 'cost'
})
YIELD totalFlow, totalCost
RETURN totalFlow, totalCost

表 15. 结果
totalFlow	totalCost
7.0	3350.0

stats 模式为我们提供了关于目标节点 (E) 总净流量的信息，即 7.0，其费用为 3350。总费用可以与每条关系的单位费用和流量值进行对比，参见上述结果。

Mutate

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

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

以下代码将以 mutate 模式运行 MCMF 算法并返回其统计信息。

MATCH (a:Place {id: 'A'}), (e:Place {id: 'E'})
CALL gds.maxFlow.minCost.mutate('graph', {
  sourceNodes: [a],
  targetNodes: [e],
  capacityProperty: 'capacity',
  costProperty: 'cost',
  mutateProperty: 'flow',
  mutateRelationshipType: 'FLOW_REL'
})
YIELD totalFlow, totalCost, relationshipsWritten
RETURN totalFlow, totalCost, relationshipsWritten

表 16. 结果
totalFlow	totalCost	relationshipsWritten
7.0	3350.0	5

mutate 模式使用名为 FLOW_REL 的新关系类型和名为 flow 的单个属性更新内存图 graph。从 relationshipsWritten 列中，我们可以看到恰好添加了五条此类关系。它们连接了流图的节点，其属性是每条关系上的流量。

即使输入图是无向的，写回图的关系也始终是有向的。它们指向流量的方向。

Write

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

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

以下代码将以 write 模式运行 MCMF 算法并返回其统计信息。

MATCH (a:Place {id: 'A'}), (e:Place {id: 'E'})
CALL gds.maxFlow.minCost.write('graph', {
  sourceNodes: [a],
  targetNodes: [e],
  capacityProperty: 'capacity',
  costProperty: 'cost',
  writeProperty: 'flow',
  writeRelationshipType: 'FLOW_REL'
})
YIELD totalFlow, totalCost, relationshipsWritten
RETURN totalFlow, totalCost, relationshipsWritten

表 17. 结果
totalFlow	totalCost	relationshipsWritten
7.0	3350.0	5

此查询将五条类型为 FLOW_REL 且具有 flow 属性的新关系写回数据库。

写回的关系始终是有向的，即使输入图是无向的。它们指向流量的方向。

节点容量要求

如果对特定节点的输出/接收量有限制，可以使用 nodeCapacity 参数属性进行建模。例如，源设施可能有产品生产量的上限。目标设施也可能有产品存储量的约束。在下例中，我们将 constraint 节点属性作为 nodeCapacity 参数的值传递，以模拟这些额外的要求。

以下代码将运行带有供应和需求的 MCMF 流模式算法。

MATCH (a:Place {id: 'A'}), (b:Place {id: 'B'}), (c:Place {id: 'C'}), (e:Place {id: 'E'})
CALL gds.maxFlow.minCost.stream('graph', {
  sourceNodes: [a, b],
  targetNodes: e,
  capacityProperty: 'capacity',
  nodeCapacityProperty: 'constraint',
  costProperty: 'cost'
})
YIELD source, target, flow
RETURN gds.util.asNode(source).id AS src, gds.util.asNode(target).id AS tgt, flow
ORDER BY src, tgt

表 18. 结果
src	tgt	flow
"A"	"B"	7.0
"B"	"C"	6.0
"B"	"D"	5.0
"C"	"E"	6.0
"D"	"E"	5.0