pgr_stoerWagner - 实验

pgr_stoerWagner — 使用 stoerWagner 算法对图进行最小分割。

Boost 图内部

Warning

可能服务器崩溃

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

Warning

实验功能

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

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

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

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

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

  • 可能缺乏文档。

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

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

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

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

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

可用性

• 版本3.0

  • 新的 实验 函数

描述

在图论中，Stoer-Wagner 算法是一种递归算法，用于解决具有非负权重的无向带权图中的最小割问题。 该算法的基本思想是通过合并最密集的顶点来收缩图，直到图仅包含两个组合的顶点集。 在每个阶段，算法都会找到任意选择的两个顶点 s 和 t 的最小 s-t 割。 然后算法缩小 s 和 t 之间的缘以搜索非 s-t 切割。 在所有阶段中找到的最小割将是图的最小加权割。

割是将图的顶点划分为两个不相交的子集。 最小切割是指切割的尺寸或重量不大于任何其他切割的尺寸的切割。 对于未加权的图，最小割只是具有最少边的割。 对于加权图，割线上所有边的权重之和决定了它是否是最小割。

主要特点是：

• 仅在具有正成本的边进行处理。

• 它的实现仅在 无向 图上。

• 两组之间所有边的权重之和是最小割。

  • 最小切割 是重量最小的切割。

• 连接图形时返回值。

  • 当图中没有边时，则返回 EMPTY SET。

  • 当图形未连接时，则返回 EMPTY SET。

• 有时一个图有多个最小割，但都具有相同的权重。 该函数准确地确定最小切割之一及其权重。

• 运行时间： \(O(V*E + V^2*log V)\)。

签名

pgr_stoerWagner(Edges SQL)

返回 (seq, edge, cost, mincut) 的集合

OR EMPTY SET

示例:

主子图的最小割

SELECT * FROM pgr_stoerWagner(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id < 17');
 seq | edge | cost | mincut
-----+------+------+--------
   1 |    6 |    1 |      1
(1 row)

参数

参数	类型	描述
Edges SQL	TEXT	Edges SQL 如下所述。

内部查询

Edges SQL

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

结果列

返回集合 (seq, edge, cost, mincut)

列	类型	描述
seq	INT	从 1 开始的顺序值。
edge	BIGINT	将顶点集一分为二的边。
cost	FLOAT	遍历边的成本。
mincut	FLOAT	无向图的最小割权。

附加示例：

示例:

边的最小割

SELECT * FROM pgr_stoerWagner(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges WHERE id = 18');
 seq | edge | cost | mincut
-----+------+------+--------
   1 |   18 |    1 |      1
(1 row)

示例:

使用 pgr_connectedComponents

SELECT * FROM pgr_stoerWagner(
  $$
  SELECT id, source, target, cost, reverse_cost FROM edges
  WHERE source IN (
      SELECT node FROM pgr_connectedComponents(
      'SELECT id, source, target, cost, reverse_cost FROM edges ')
      WHERE component = 2)
  $$
);
 seq | edge | cost | mincut
-----+------+------+--------
   1 |   17 |    1 |      1
(1 row)

另请参阅

• 示例数据

• https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm

索引和表格

• Index

• Search Page