Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 main dev

pgr_edgeColoring - 实验性

pgr_edgeColoring - 返回无向图和无环图的边着色

Experimental

Warning

可能服务器崩溃

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

Warning

实验性函数

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

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

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

  • 名称可能会改变。

  • 签名可能会改变。

  • 功能可能会改变。

  • pgTap 测试可能丢失。

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

  • 可能缺乏文档。

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

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

  • 需要从社区获取大量反馈意见。

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

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

可用性

Version 4.0.0

• Output columns standardized to (edge, color)

版本 3.3.0

• 新实验性功能。

描述

边着色是一种用于为图形中顶点的边着色的算法。它为图中的边分配颜色，使相邻的两条边没有相同的颜色。

主要特点是：

• 针对 无向 和 无环 图实施

  • 无环:

    无自循环，无平行边。

• 指定要分配给图中所有边的颜色。

• 最多使用 $\mathrm{\Delta }+1$ 种颜色，其中 $\mathrm{\Delta }$ 是图的度数。

  • 这对于某些图是最优的，根据Vizing定理，对于所有其他图，它使用的颜色最多比最优解多一种。

  • 当图形为两方时

    • 色数（chromatic number） $x^{\prime }(G)‘（\mathrm{用}\mathrm{于}\mathrm{图}\mathrm{的}\mathrm{适}\mathrm{当}\mathrm{边}\mathrm{着}\mathrm{色}\mathrm{所}\mathrm{需}\mathrm{的}\mathrm{最}\mathrm{小}\mathrm{颜}\mathrm{色}\mathrm{数}）\mathrm{等}\mathrm{于}\mathrm{图}\mathrm{的}\mathrm{度}:math:$Delta + 1`（ $x^{\prime }(G)=\mathrm{\Delta }$）

• 该算法尝试为每条边分配尽可能少的颜色。

  • 并不总是产生最佳的着色。

• 返回的行按边标识符升序排列。

• 高效图形着色是一个 NP-Hard问题，因此：

  • 在此实现中，运行时间为： $O(|E|\ast |V||)$

    • 其中 $|E|$ 是图中的边数、

    • $|V|$ 是图中的顶点数。

Boost 图内部

签名

pgr_edgeColoring(Edges SQL)

Returns set of (edge, color)

OR EMPTY SET

示例:

pgRouting 示例数据 的图形着色

SELECT edge, color FROM pgr_edgeColoring(
    'SELECT id, source, target, cost, reverse_cost FROM edges
    ORDER BY id'
);
 edge | color
------+-------
    1 |     3
    2 |     2
    3 |     3
    4 |     4
    5 |     4
    6 |     1
    7 |     2
    8 |     1
    9 |     2
   10 |     5
   11 |     5
   12 |     3
   13 |     2
   14 |     1
   15 |     3
   16 |     1
   17 |     1
   18 |     1
(18 rows)

参数

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

内部查询

Edges SQL

列	类型	默认	描述
id	ANY-INTEGER		边的标识符。
source	ANY-INTEGER		边的第一个端点顶点的标识符。
target	ANY-INTEGER		边的第二个端点顶点的标识符。
cost	ANY-NUMERICAL		edge (source, target)的权重
reverse_cost	ANY-NUMERICAL	-1	边(target, source)的权重 当为负时：edge (target, source) 不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

Returns set of (edge, color)

列	类型	描述
edge	BIGINT	边的标识符。
color	BIGINT	Color of the edge. 颜色的最小值为 1。

另请参阅

• 示例数据

• Boost: 边着色

• 维基百科：图着色

索引和表格

• Index

• Search Page