pgr_cuthillMckeeOrdering`` - 试验性的

pgr_cuthillMckeeOrdering — 返回无向图的反向 Cuthill-Mckee 排序

Boost 图内部

Warning

可能服务器崩溃

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

Warning

实验功能

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

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

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

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

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

  • 可能缺乏文档。

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

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

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

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

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

可用性

• 版本 3.4.0

  • 新 实验 函数

描述

在数值线性代数中，Cuthill-McKee 算法（CM）以 Elizabeth Cuthill 和 James McKee 的名字命名，是一种将具有对称稀疏性模式的稀疏矩阵置换为带宽较小的带状矩阵形式的算法。

顶点的搜索顺序基本上是广度优先，只不过在每一步中，相邻的顶点会按照度数递增的顺序排列在队列中。

主要特点是：

• 该实现适用于 无向 图。

• 带宽最小化问题被认为是NP完全问题。

• 运行时间复杂度为： \(O(m log(m)|V|)\)

  • 其中 \(|V|\) 是顶点数，

  • \(m\) 是图中顶点的最大度数。

签名

pgr_cuthillMckeeOrdering(Edges SQL)

Returns set of (seq, node)

OR EMPTY SET

示例:

pgRouting 示例数据 的图形排序

SELECT * FROM pgr_cuthillMckeeOrdering(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
  );
 seq | node
-----+------
   1 |   13
   2 |   14
   3 |    2
   4 |    4
   5 |    1
   6 |    9
   7 |    3
   8 |    8
   9 |    5
  10 |    7
  11 |   12
  12 |    6
  13 |   11
  14 |   17
  15 |   10
  16 |   16
  17 |   15
(17 rows)

参数

参数	类型	描述
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, node) 的集合

列	类型	描述
seq	BIGINT	从1开始的顺序序列。
node	BIGINT	新的逆序排列。

另请参阅

• 查询使用 示例数据 网络。

• Boost: Cuthill-McKee 排序

• Wikipedia: Cuthill-McKee 排序

索引和表格

• Index

• Search Page