`pgr_edmondsKarp`¶

pgr_edmondsKarp —使用 Edmonds Karp 算法计算图边上的流量，以最大化从源到目标的流量。

可用性

版本3.2.0
- 新的拟议签名
  - pgr_edmondsKarp (组合)
版本3.0.0
- 官方函数
版本2.5.0
- 从 pgr_maxFlowEdmondsKarp 更名而来
- 拟议函数
版本2.3.0
- 新的实验函数

描述¶

主要特点是：

该图是有向的。
仅在具有正容量的边缘上进行处理。
当最大流量为0时则没有流量并返回 EMPTY SET 。
- There is no flow when source has the same vaule as target.
Any duplicated values in source or target are ignored.
计算每条边的流量/剩余容量。在输出中
- 流量为零的边被忽略。
Creates
- a super source and edges from it to all the sources,
- a super target and edges from it to all the targetss.
当使用相同参数执行时，通过图表的最大流量保证是 pgr_maxFlow 返回的值，并且可以计算：
- 通过聚合来自源的传出流量
- 通过聚合到达目标的传入流量

运行时间： \(O( V * E ^ 2)\)

签名¶

总结

pgr_edmondsKarp(Edges SQL, start vid, end vid)
pgr_edmondsKarp(Edges SQL, start vid, end vids)
pgr_edmondsKarp(Edges SQL, start vids, end vid)
pgr_edmondsKarp(Edges SQL, start vids, end vids)
pgr_edmondsKarp(Edges SQL, Combinations SQL)

Returns set of (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

一对一¶

pgr_edmondsKarp(Edges SQL, start vid, end vid)

Returns set of (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

示例:: 从顶点 \(11\) 到顶点 \(12\)

SELECT * FROM pgr_edmondsKarp(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, 12);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |   10 |         7 |       8 |  100 |                30
   2 |   12 |         8 |      12 |  100 |                 0
   3 |    8 |        11 |       7 |  100 |                30
   4 |   11 |        11 |      12 |  130 |                 0
(4 rows)

一对多¶

pgr_edmondsKarp(Edges SQL, start vid, end vids)

Returns set of (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

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

SELECT * FROM pgr_edmondsKarp(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  11, ARRAY[5, 10, 12]);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    1 |         6 |       5 |   50 |                80
   2 |    4 |         7 |       6 |   50 |                 0
   3 |   10 |         7 |       8 |   80 |                50
   4 |   12 |         8 |      12 |   80 |                20
   5 |    8 |        11 |       7 |  130 |                 0
   6 |   11 |        11 |      12 |  130 |                 0
   7 |    9 |        11 |      16 |   80 |                50
   8 |    3 |        15 |      10 |   80 |                50
   9 |   16 |        16 |      15 |   80 |                 0
(9 rows)

多对一¶

pgr_edmondsKarp(Edges SQL, start vids, end vid)

Returns set of (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

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

SELECT * FROM pgr_edmondsKarp(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], 12);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    7 |         3 |       7 |   50 |                 0
   2 |   10 |         7 |       8 |  100 |                30
   3 |   12 |         8 |      12 |  100 |                 0
   4 |    8 |        11 |       7 |   50 |                80
   5 |   11 |        11 |      12 |  130 |                 0
(5 rows)

多对多¶

pgr_edmondsKarp(Edges SQL, start vids, end vids)

Returns set of (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

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

SELECT * FROM pgr_edmondsKarp(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    7 |         3 |       7 |   50 |                 0
   2 |    1 |         6 |       5 |   50 |                80
   3 |    4 |         7 |       6 |   50 |                 0
   4 |   10 |         7 |       8 |  100 |                30
   5 |   12 |         8 |      12 |  100 |                 0
   6 |    8 |        11 |       7 |  100 |                30
   7 |   11 |        11 |      12 |  130 |                 0
   8 |    9 |        11 |      16 |   80 |                50
   9 |    3 |        15 |      10 |   80 |                50
  10 |   16 |        16 |      15 |   80 |                 0
(10 rows)

组合¶

pgr_edmondsKarp(Edges SQL, Combinations SQL)

Returns set of (seq, edge, start_vid, end_vid, flow, residual_capacity)

OR EMPTY SET

示例:: 使用组合表，相当于计算从顶点 \(\{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_edmondsKarp(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    4 |         6 |       7 |   80 |                20
   2 |    8 |         7 |      11 |   80 |                20
   3 |    9 |        11 |      16 |   80 |                50
   4 |   16 |        16 |      15 |   80 |                 0
(4 rows)

参数¶

列	类型	描述
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

结果列¶

列	类型	描述
seq	`INT`	从 1 开始的顺序值。
edge	`BIGINT`	原始查询中边的标识符 (edges_sql)。
start_vid	`BIGINT`	边的第一个端点顶点的标识符。
end_vid	`BIGINT`	边的第二个端点顶点的标识符。
flow	`BIGINT`	沿 (`start_vid`, `end_vid`)方向流经边缘。
residual_capacity	`BIGINT`	(`start_vid`, `end_vid`)方向上边缘的剩余容量。

其他示例¶

示例:: 手动指定的顶点组合。

SELECT * FROM pgr_edmondsKarp(
  'SELECT id, source, target, capacity, reverse_capacity
  FROM edges',
  'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)');
 seq | edge | start_vid | end_vid | flow | residual_capacity
-----+------+-----------+---------+------+-------------------
   1 |    4 |         6 |       7 |   80 |                20
   2 |    8 |         7 |      11 |   80 |                20
   3 |    9 |        11 |      16 |   80 |                50
   4 |   16 |        16 |      15 |   80 |                 0
(4 rows)

另请参阅¶

索引和表格

pgr_edmondsKarp¶

描述¶

签名¶

一对一¶

一对多¶

多对一¶

多对多¶

组合¶

参数¶

内部查询¶

Edges SQL¶

分量 SQL¶

结果列¶

其他示例¶

另请参阅¶

`pgr_edmondsKarp`¶