`pgr_maxFlowMinCost` - 实验¶

pgr_maxFlowMinCost — 计算图上最大流的总成本最小化的边

Warning

可能服务器崩溃

这些功能可能会导致服务器崩溃

Warning

实验功能

它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分：
- 这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名称可能会改变。
- 签名可能会改变。
- 功能可能会改变。
- pgTap 测试可能丢失。
- 可能需要 c/c++编码。
- 可能缺乏文档。
- 文档（如果有）可能需要重写。
- 可能需要自动生成文档示例。
- 可能需要社区的大量反馈。
- 可能取决于 pgRouting 的拟议功能
- 可能依赖于 pgRouting 的已弃用函数

可用性

版本3.2.0
- 新的实验函数：
  - pgr_maxFlowMinCost (组合)
版本3.0.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 返回的值，并且可以计算：
- 通过聚合来自源的传出流量
- 通过聚合到达目标的传入流量

TODO 检查哪个陈述是正确的：
- 所有输入边的成本值必须是非负的。
- 当所有输入边的成本值为非负时，处理完成。
- 过程是在具有非负成本的边上完成的。
运行时间： \(O(U * (E + V * logV))\)
- 其中 \(U\) 是最大流量的值。
- \(U`是迭代次数的上限。在许多现实世界的情况下，迭代次数远小于 :math:`U\) 。

签名¶

总结

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

返回 (seq, edge, source, target, flow, residual_capacity, cost, agg_cost) 的集合

OR EMPTY SET

一对一¶

pgr_maxFlowMinCost(Edges SQL, start vid, end vid)

返回 (seq, edge, source, target, flow, residual_capacity, cost, agg_cost) 的集合

OR EMPTY SET

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

SELECT * FROM pgr_maxFlowMinCost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  11, 12);
 seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
   1 |   10 |      7 |      8 |  100 |                30 |  100 |      100
   2 |   12 |      8 |     12 |  100 |                 0 |  100 |      200
   3 |    8 |     11 |      7 |  100 |                30 |  100 |      300
   4 |   11 |     11 |     12 |  130 |                 0 |  130 |      430
(4 rows)

一对多¶

pgr_maxFlowMinCost(Edges SQL, start vid, end vids)

返回 (seq, edge, source, target, flow, residual_capacity, cost, agg_cost) 的集合

OR EMPTY SET

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

SELECT * FROM pgr_maxFlowMinCost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  11, ARRAY[5, 10, 12]);
 seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
   1 |    1 |      6 |      5 |   30 |               100 |   30 |       30
   2 |    4 |      7 |      6 |   30 |                20 |   30 |       60
   3 |   10 |      7 |      8 |  100 |                30 |  100 |      160
   4 |   12 |      8 |     12 |  100 |                 0 |  100 |      260
   5 |    8 |     11 |      7 |  130 |                 0 |  130 |      390
   6 |   11 |     11 |     12 |  130 |                 0 |  130 |      520
   7 |    9 |     11 |     16 |   80 |                50 |   80 |      600
   8 |    3 |     15 |     10 |   80 |                50 |   80 |      680
   9 |   16 |     16 |     15 |   80 |                 0 |   80 |      760
(9 rows)

多对一¶

pgr_maxFlowMinCost(Edges SQL, start vids, end vid)

返回 (seq, edge, source, target, flow, residual_capacity, cost, agg_cost) 的集合

OR EMPTY SET

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

SELECT * FROM pgr_maxFlowMinCost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], 12);
 seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
   1 |    7 |      3 |      7 |   50 |                 0 |   50 |       50
   2 |   10 |      7 |      8 |  100 |                30 |  100 |      150
   3 |   12 |      8 |     12 |  100 |                 0 |  100 |      250
   4 |    8 |     11 |      7 |   50 |                80 |   50 |      300
   5 |   11 |     11 |     12 |  130 |                 0 |  130 |      430
(5 rows)

多对多¶

pgr_maxFlowMinCost(Edges SQL, start vids, end vids)

返回 (seq, edge, source, target, flow, residual_capacity, cost, agg_cost) 的集合

OR EMPTY SET

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

SELECT * FROM pgr_maxFlowMinCost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
   1 |    7 |      3 |      7 |   50 |                 0 |   50 |       50
   2 |    1 |      6 |      5 |   50 |                80 |   50 |      100
   3 |    4 |      7 |      6 |   50 |                 0 |   50 |      150
   4 |   10 |      7 |      8 |  100 |                30 |  100 |      250
   5 |   12 |      8 |     12 |  100 |                 0 |  100 |      350
   6 |    8 |     11 |      7 |  100 |                30 |  100 |      450
   7 |   11 |     11 |     12 |  130 |                 0 |  130 |      580
   8 |    9 |     11 |     16 |   30 |               100 |   30 |      610
   9 |    3 |     15 |     10 |   80 |                50 |   80 |      690
  10 |   16 |     16 |     15 |   80 |                 0 |   80 |      770
  11 |   15 |     17 |     16 |   50 |                 0 |   50 |      820
(11 rows)

组合¶

pgr_maxFlowMinCost(Edges SQL, Combinations SQL)

返回 (seq, edge, source, target, flow, residual_capacity, cost, agg_cost) 的集合

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_maxFlowMinCost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 seq | edge | source | target | flow | residual_capacity | cost | agg_cost
-----+------+--------+--------+------+-------------------+------+----------
   1 |    4 |      6 |      7 |   80 |                20 |   80 |       80
   2 |    8 |      7 |     11 |   80 |                20 |   80 |      160
   3 |    9 |     11 |     16 |   80 |                50 |   80 |      240
   4 |   16 |     16 |     15 |   80 |                 0 |   80 |      320
(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`)的容量当为负时：边（ `target`, `source` ）不存在，因此它不是图的一部分。
`reverse_capacity`	ANY-INTEGER	-1	边 (`target`, `source`)的容量当为负时：边（ `target`, `source` ）不存在，因此它不是图的一部分。
`cost`	ANY-NUMERICAL		边 (`source`, `target`)的权重（如果存在）
`reverse_cost`	ANY-NUMERICAL	\(-1\)	边(`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)。
source	`BIGINT`	边的第一个端点顶点的标识符。
target	`BIGINT`	边的第二个端点顶点的标识符。
flow	`BIGINT`	沿方向 (source, target)流经边缘。
residual_capacity	`BIGINT`	方向 (source, target)上边缘的剩余容量。
cost	`FLOAT`	在方向 (source, target)上通过边缘发送此流的成本。
agg_cost	`FLOAT`	总成本。

其他示例¶

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

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

另请参阅¶

索引和表格

pgr_maxFlowMinCost - 实验¶

描述¶

签名¶

一对一¶

一对多¶

多对一¶

多对多¶

组合¶

参数¶

内部查询¶

Edges SQL¶

分量 SQL¶

结果列¶

其他示例¶

另请参阅¶

`pgr_maxFlowMinCost` - 实验¶