最大流 (Maximum flow)

术语表

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

简介

给定源节点、目标节点以及具有容量限制的关系，最大流算法为每条关系分配一个流量，以实现从源到目标的最大传输。

流量是每条关系的标量属性，且必须满足以下条件：

流入节点的流量等于流出节点的流量（流量守恒）
流量受限于关系的容量

源节点可以作为节点列表提供，也可以作为节点与标量的配对列表提供。后者被解释为每个源节点的最大流出量，而对于前者，流出量仅受关系容量的限制。

对于目标节点，有一个等效的选项，其中的标量决定了每个目标节点接收多少流量。如果不提供，则不受限制。

Neo4j GDS 库的实现基于这篇论文中的并行推送重贴标签 (push-relabel) 算法，并进行了一些修改。

语法

本节介绍了在每种执行模式下执行最大流算法所使用的语法。我们描述的是命名图变体的语法。要了解更多关于通用语法变体的信息，请参阅语法概述。

每种模式的最大流语法

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

CALL gds.maxFlow.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	字符串	`不适用`	否	用作容量的关系属性名称。
sourceNodes	节点列表或整数或整数	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数或整数	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此属性，则具有给定属性的节点处理的总流量将受其属性值限制。对于没有限制的节点，请保留为未定义。
1. 在 GDS 会话中，默认值为可用处理器的数量。

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

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

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

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

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

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

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

CALL gds.maxFlow.mutate(
  graphName: String,
  configuration: Map
)
YIELD
  totalFlow: 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	字符串	`不适用`	否	用作容量的关系属性名称。
sourceNodes	节点列表或整数或整数	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数或整数	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此属性，则具有给定属性的节点处理的总流量将受其属性值限制。对于没有限制的节点，请保留为未定义。

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

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

CALL gds.maxFlow.write(
  graphName: String,
  configuration: Map
)
YIELD
  totalFlow: 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	字符串	`不适用`	否	用作容量的关系属性名称。
sourceNodes	节点列表或整数或整数	`不适用`	否	作为节点或节点 ID 提供的源节点，流量从这些节点流入网络。
targetNodes	节点列表或整数或整数	`不适用`	否	作为节点或节点 ID 提供的目标节点，流量存入这些节点。
nodeCapacityProperty	字符串	`不适用`	是	如果定义了此属性，则具有给定属性的节点处理的总流量将受其属性值限制。对于没有限制的节点，请保留为未定义。
3. 在 GDS 会话中，默认值为可用处理器的数量。

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

示例

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

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

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

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

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

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

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

内存估算

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

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

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

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

表 13. 结果
nodeCount	relationshipCount	bytesMin	bytesMax	requiredMemory
6	7	3072	3072	"3072 Bytes"

流式传输 (Stream)

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

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

以下代码将在 stream 模式下运行最大流算法，并返回每个有效节点的结果。

MATCH (a:Place {id: 'A'}), (d:Place {id: 'D'})
CALL gds.maxFlow.stream('graph', {
  sourceNodes: [a],
  targetNodes: [d],
  capacityProperty: 'capacity'
})
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"	1.0
"A"	"F"	3.0
"B"	"C"	1.0
"C"	"D"	1.0
"F"	"D"	3.0

该算法将流量分别从源 (A) 引导至目标 (D)，路径经过 B-C 和 F。沿这两条路径的最低容量（瓶颈）分别为 1 和 3。这使得从节点 A 到节点 D 的总流量为 4。

统计信息 (Stats)

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

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

以下代码将在 stats 模式下运行最大流算法并返回其统计信息。

MATCH (a:Place {id: 'A'}), (d:Place {id: 'D'})
CALL gds.maxFlow.stats('graph', {
  sourceNodes: [a],
  targetNodes: [d],
  capacityProperty: 'capacity'
})
YIELD totalFlow
RETURN totalFlow

表 15. 结果
totalFlow
4.0

stats 模式为我们提供了关于目标节点 (D) 的总净流量的信息，即 4.0。

Mutate

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

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

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

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

表 16. 结果
totalFlow	relationshipsWritten
4.0	5

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

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

Write

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

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

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

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

表 17. 结果
totalFlow	relationshipsWritten
4.0	5

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

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

节点容量要求

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

以下代码将在 stream 模式下运行带有供给和需求限制的最大流算法。

MATCH (a:Place {id: 'A'}), (b:Place {id: 'B'}), (d:Place {id: 'D'}), (e:Place {id: 'E'})
CALL gds.maxFlow.stream('graph', {
  sourceNodes: [a,b],
  targetNodes: [d,e],
  capacityProperty: 'capacity',
  nodeCapacityProperty: 'constraint'
})
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"	"E"	7.0
"A"	"F"	2.0
"B"	"C"	1.0
"C"	"D"	1.0
"F"	"D"	2.0