pgr_maxFlowMinCost_Cost - 实验

pgr_maxFlowMinCost_Cost — 计算图上最大流量的最小总成本

Boost 图内部

Warning

可能服务器崩溃

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

Warning

实验功能

• 它们不是当前版本的正式版本。

• 它们可能不会正式成为下一个版本的一部分：

  • 这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

  • 可能需要 c/c++编码。

  • 可能缺乏文档。

  • 文档（如果有）可能需要重写。

  • 可能需要自动生成文档示例。

  • 可能需要社区的大量反馈。

  • 可能取决于 pgRouting 的拟议功能

  • 可能依赖于 pgRouting 的已弃用函数

可用性

• 版本3.2.0

  • 新的 实验 函数：

    • pgr_maxFlowMinCost_Cost (组合)

• 版本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 返回的值，并且可以计算：

  • 通过聚合来自源的传出流量

  • 通过聚合到达目标的传入流量

主要特点是：

• 该图是 有向 的。

• 所有输入边的成本值必须是非负的。

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

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

• Any duplicated values in source or target are ignored.

• 使用 pgr_maxFlowMinCost - 实验。

• 运行时间： \(O(U * (E + V * logV))\)

  • 其中 \(U\) 是最大流量的值。

  • \(U`是迭代次数的上限。 在许多现实世界的情况下，迭代次数远小于 :math:`U\) 。

签名

总结

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vid)

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vids)

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vid)

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vids)

pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)

RETURNS FLOAT

一对一

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vid)

RETURNS FLOAT

示例:

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

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  11, 12);
 pgr_maxflowmincost_cost
-------------------------
                     430
(1 row)

一对多

pgr_maxFlowMinCost_Cost(Edges SQL, start vid, end vids)

RETURNS FLOAT

示例:

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

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], 12);
 pgr_maxflowmincost_cost
-------------------------
                     430
(1 row)

多对一

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vid)

RETURNS FLOAT

示例:

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

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  11, ARRAY[5, 10, 12]);
 pgr_maxflowmincost_cost
-------------------------
                     760
(1 row)

多对多

pgr_maxFlowMinCost_Cost(Edges SQL, start vids, end vids)

RETURNS FLOAT

示例:

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

SELECT * FROM pgr_maxFlowMinCost_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 pgr_maxflowmincost_cost
-------------------------
                     820
(1 row)

组合

pgr_maxFlowMinCost_Cost(Edges SQL, Combinations SQL)

RETURNS FLOAT

示例:

使用组合表，相当于计算从顶点 \(\{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_Cost(
  'SELECT id, source, target, capacity, reverse_capacity, cost, reverse_cost
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)');
 pgr_maxflowmincost_cost
-------------------------
                     320
(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)的容量 当为负时：边（ 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

返回列

类型	描述
FLOAT	从source(s) 到target(s)的最小成本最大流量

其他示例

示例:

手动指定的顶点组合。

SELECT * FROM pgr_maxFlowMinCost_Cost(
  '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)');
 pgr_maxflowmincost_cost
-------------------------
                     320
(1 row)

另请参阅

• Flow - 函数族

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

索引和表格

• Index

• Search Page