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\_sql, source\_vertex, sink\_vertex)\)

其中 \(edges\_sql = \{(id_i, source_i, target_i, capacity_i, reverse\_capacity_i)\}\)

图定义

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

• 顶点集 \(V\)

  • \(source\_vertex \cup sink\_vertex \bigcup source_i \bigcup target_i\)

• 边集 \(E\)

  • \(E = \begin{cases} \text{ } \{(source_i, target_i, capacity_i) \text{ when } capacity > 0 \} & \quad \text{ if } reverse\_capacity = \varnothing \\ \text{ } & \quad \text{ } \\ \{(source_i, target_i, capacity_i) \text{ when } capacity > 0 \} & \text{ } \\ \cup \{(target_i, source_i, reverse\_capacity_i) \text{ when } reverse\_capacity_i > 0)\} & \quad \text{ if } reverse\_capacity \neq \varnothing \\ \end{cases}\)

最大流量问题

给定：

• \(G(V,E)\)

• \(source\_vertex \in V\) the source vertex

• \(sink\_vertex \in V\) the sink vertex

然后：

• \(pgr\_maxFlow(edges\_sql, source, sink) = \boldsymbol{\Phi}\)

• \(\boldsymbol{\Phi} = {(id_i, edge\_id_i, source_i, target_i, flow_i, residual\_capacity_i)}\)

其中：

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

• \(id_i = i\)

• \(edge\_id = id_i\) 在edges_sql中

• \(residual\_capacity_i = capacity_i - flow_i\)

另请参阅

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

索引和表格

• Index

• Search Page