pgr_maxCardinalityMatch

pgr_maxCardinalityMatch — 计算图中的最大基数匹配。.

Boost 图内部

可用性

• 版本 3.4.0

  • 在内部查询上使用 cost 和 reverse_cost

  • 结果已排序

  • 适用于无向图。

  • 新签名

    • pgr_maxCardinalityMatch(text) 仅仅返回``边`` 列.

  • 已弃用的签名

    • pgr_maxCardinalityMatch(text,boolean)

      • 使用时 directed => false。

• 版本3.0.0

  • 官方 函数

• 版本2.5.0

  • 从 pgr_maximumCardinalityMatching 重命名

  • 拟议 函数

• 版本2.3.0

  • 新的 实验 函数

描述

主要特点是：

• 适用于 无向 图。

• 图中的匹配或独立边集是一组没有公共顶点的边。

• 最大匹配是包含尽可能多的边的匹配。

  • 可能有很多最大匹配。

  • 计算图中一种可能的最大基数匹配。

• 运行时间： \(O( E*V * \alpha(E,V))\)

  • \(\alpha(E,V)\) 与 Ackermann function 相反。

签名

pgr_maxCardinalityMatch(Edges SQL)

返回集合 (edge)

OR EMPTY SET

示例:

使用所有边。

SELECT * FROM pgr_maxCardinalityMatch(
  'SELECT id, source, target, cost, reverse_cost FROM edges');
 edge
------
    1
    5
    6
   13
   14
   16
   17
   18
(8 rows)

参数

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

内部查询

Edges SQL

SQL 查询，应返回一组包含以下列的行：

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		正值表示存在边(source, target)。
reverse_cost	ANY-NUMERICAL	-1	正值表示存在边(target, source)

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

列	类型	描述
edge	BIGINT	原始查询中边的标识符。

另请参阅

• Flow - 函数族

• 迁移指南

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

• https://en.wikipedia.org/wiki/Matching_%28graph_theory%29

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

索引和表格

• Index

• Search Page