pgr_maxFlow

pgr_maxFlow —使用 Push Relabel 算法计算有向图中从源到目标的最大流量。

Boost 图内部

可用性

• 版本3.2.0

  • 新的 拟议 签名

    • pgr_maxFlow (组合)

• 版本3.0.0

  • 官方 函数

• 版本2.4.0

  • 新 拟议 的函数

描述

主要特点是：

• 该图是 有向 的。

• Calculates the maximum flow from the sources to the targets.

  • 当最大流量为 0 时则没有流量，返回 0 。

  • There is no flow when source has the same vaule as target.

• Any duplicated values in source or target are ignored.

• 使用 pgr_pushRelabel 算法。

• 运行时间： \(O( V ^ 3)\)

签名

总结

pgr_maxFlow(Edges SQL, start vid, end vid)

pgr_maxFlow(Edges SQL, start vid, end vids)

pgr_maxFlow(Edges SQL, start vids, end vid)

pgr_maxFlow(Edges SQL, start vids, end vids)

pgr_maxFlow(Edges SQL, Combinations SQL)

RETURNS BIGINT

一对一

pgr_maxFlow(Edges SQL, start vid, end vid)

RETURNS BIGINT

示例:

从顶点 \(11\) 到顶点 \(12\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, 12);
 pgr_maxflow
-------------
         230
(1 row)

一对多

pgr_maxFlow(Edges SQL, start vid, end vids)

RETURNS BIGINT

示例:

从顶点 \(11\) 到顶点 \(\{5, 10, 12\}\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, ARRAY[5, 10, 12]);
 pgr_maxflow
-------------
         340
(1 row)

多对一

pgr_maxFlow(Edges SQL, start vids, end vid)

RETURNS BIGINT

示例:

从顶点 \(\{11, 3, 17\}\) 到顶点 \(12\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], 12);
 pgr_maxflow
-------------
         230
(1 row)

多对多

pgr_maxFlow(Edges SQL, start vids, end vids)

RETURNS BIGINT

示例:

从顶点 \(\{11, 3, 17\}\) 到顶点 \(\{5, 10, 12\}\)

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 pgr_maxflow
-------------
         360
(1 row)

组合

pgr_maxFlow(Edges SQL, Combinations SQL)

RETURNS BIGINT

示例:

使用组合表，相当于计算从顶点 \(\{5, 6\}\) 到顶点 \({\10, 15, 14\}\) 的结果。

组合表：

SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
 source | target
--------+--------
      5 |     10
      6 |     15
      6 |     14
(3 rows)

查询：

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 pgr_maxflow
-------------
          80
(1 row)

参数

列	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述
Combinations SQL	TEXT	Combinations SQL 如下所述
start vid	BIGINT	路径起始顶点的标识符。
start vids	ARRAY[BIGINT]	起始顶点的标识符数组。
end vid	BIGINT	路径结束顶点的标识符。
end vids	ARRAY[BIGINT]	结束顶点的标识符数组。

内部查询

Edges SQL

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
capacity	ANY-INTEGER		边(source, target)的权重
reverse_capacity	ANY-INTEGER	-1	边(target, source)的权重 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

分量 SQL

参数	类型	描述
source	ANY-INTEGER	出发顶点的标识符。
target	ANY-INTEGER	到达顶点的标识符。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

结果列

类型	描述
BIGINT	从 source(s)到 target(s)的可能最大流量

其他示例

示例:

手动指定的顶点组合。

SELECT * FROM pgr_maxFlow(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
 pgr_maxflow
-------------
          80
(1 row)

另请参阅

• Flow - 函数族

  • pgr_pushRelabel

• https://www.boost.org/libs/graph/doc/push_relabel_max_flow.html

• https://en.wikipedia.org/wiki/Push%E2%80%93relabel_maximum_flow_algorithm

索引和表格

• Index

• Search Page