Supported versions: latest (3.7) 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5 2.4 2.3

Flow - 函数族

• pgr_maxFlow - 仅使用 Push 和 Relabel 算法进行最大流量计算。

• pgr_boykovKolmogorov - Boykov 和 Kolmogorov 的边流动细节。

• pgr_edmondsKarp - 带有边流量详细信息的 Edmonds 和 Karp 算法。

• pgr_pushRelabel - 推送和重新标记算法以及边流量的详细信息。

• 应用

  • pgr_edgeDisjointPaths - 计算两组顶点之间的边不相交路径。

  • pgr_maxCardinalityMatch - 计算图中的最大基数匹配。

实验性的

Warning

可能服务器崩溃

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

Warning

实验功能

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

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

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

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

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

  • 可能缺乏文档。

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

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

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

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

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

• pgr_maxFlowMinCost - 实验 - 边缘上的流量和成本详细信息。

• pgr_maxFlowMinCost_Cost - 实验 -仅最小成本计算。

流函数一般信息

主要特点是：

• 该图是 有向 的。

• 仅在具有正容量的边缘上进行处理。

• 当最大流量为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 返回的值，并且可以计算：

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

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

pgr_maxFlow 是最大流量，并且该最大值保证在函数 pgr_pushRelabel, pgr_edmondsKarp, pgr_boykovKolmogorov, 上相同，但通过每条边的实际流量可能会有所不同。

内部查询

Edges SQL

容量边缘

• pgr_pushRelabel

• pgr_edmondsKarp

• pgr_boykovKolmogorov

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

容量-成本边

• pgr_maxFlowMinCost - 实验

• pgr_maxFlowMinCost_Cost - 实验

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

成本边

• pgr_edgeDisjointPaths

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		边(source, target)的权重
reverse_cost	ANY-NUMERICAL	-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

结果列

用于

• pgr_pushRelabel

• pgr_edmondsKarp

• pgr_boykovKolmogorov

列	类型	描述
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)方向上边缘的剩余容量。

对于 pgr_maxFlowMinCost - 实验

列	类型	描述
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	总成本。

高级文档

流网络是一个有向图，其中每条边都有容量和流量。通过一条边的流量不能超过边的容量。此外，节点的流入流出必须相等，除了源节点只有流出流量，以及目标（汇点）节点只有流入流量。

最大流量算法计算通过图的最大流量以及每条边的流量。

所有实现中通过图表的最大流量保证相同，但通过每条边的实际流量可能会有所不同。

给出以下查询：

pgr_maxFlow $(edges\mathrm{\_}sql,source\mathrm{\_}vertex,sink\mathrm{\_}vertex)$

其中 $edges\mathrm{\_}sql=\{(i{d}_i,sourc{e}_i,targe{t}_i,capacit{y}_i,reverse\mathrm{\_}capacit{y}_i)\}$

图定义

加权有向图， $G(V,E)$ 定义为：

• 顶点集 $V$

  • $source\mathrm{\_}vertex\cup sink\mathrm{\_}vertex\bigcup sourc{e}_i\bigcup targe{t}_i$

• 边集 $E$

  • $E=\{\begin{array}{ll}\{(sourc{e}_i,targe{t}_i,capacit{y}_i)\text{ when }capacity>0\}& \text{ if }reverse\mathrm{\_}capacity=\varnothing \\ & \\ \{(sourc{e}_i,targe{t}_i,capacit{y}_i)\text{ when }capacity>0\}& \\ \cup \{(targe{t}_i,sourc{e}_i,reverse\mathrm{\_}capacit{y}_i)\text{ when }reverse\mathrm{\_}capacit{y}_i>0)\}& \text{ if }reverse\mathrm{\_}capacity\ne \varnothing \end{array}$

最大流量问题

给定：

• $G(V,E)$

• $source\mathrm{\_}vertex\in V$ the source vertex

• $sink\mathrm{\_}vertex\in V$ the sink vertex

然后：

• $pgr\mathrm{\_}maxFlow(edges\mathrm{\_}sql,source,sink)=\mathbf{\Phi }$

• $\mathbf{\Phi }=(i{d}_i,edge\mathrm{\_}i{d}_i,sourc{e}_i,targe{t}_i,flo{w}_i,residual\mathrm{\_}capacit{y}_i)$

其中：

$\mathbf{\Phi }$ 是原始边及其剩余容量和流量的子集。 通过图的最大流量可以通过在源或汇上聚合并对来自/到它的流量求和来获得。 尤其：

• $i{d}_i=i$

• $edge\mathrm{\_}id=i{d}_i$ 在edges_sql中

• $residual\mathrm{\_}capacit{y}_i=capacit{y}_i-flo{w}_i$

另请参阅

• https://en.wikipedia.org/wiki/Maximum_flow_problem

索引和表格

• Index

• Search Page