Supported versions: latest (3.8) 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

pgr_maxCardinalityMatch

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

可用性

• 版本 3.4.0

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

  • 结果已排序

  • 适用于无向图。

  • 新签名

    • pgr_maxCardinalityMatch(text) returns only edge column.

  • 已弃用的签名

    • pgr_maxCardinalityMatch(text,boolean)

      • directed => false when used.

• 版本3.0.0

  • Function promoted to official.

• 版本2.5.0

  • 从 pgr_maximumCardinalityMatching 重命名

  • Function promoted to proposed.

• 版本2.3.0

  • New experimental function.

描述

主要特点是：

• 适用于 无向 图。

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

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

  • 可能有很多最大匹配。

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

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

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

Boost Graph Inside

签名

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 - 函数族

• 迁移指南

• Boost: maximum_matching

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

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

索引和表格

• Index

• Search Page