pgr_edgeColoring - 实验

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

_images/boost-inside.jpeg

Boost 图内部

Warning

可能服务器崩溃

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

Warning

实验功能

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

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

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

    • 名称可能会改变。

    • 签名可能会改变。

    • 功能可能会改变。

    • pgTap 测试可能丢失。

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

    • 可能缺乏文档。

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

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

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

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

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

可用性

  • 版本 3.3.0

    • 新的 实验 签名

描述

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

主要特点是：

  • 针对 无向 和 无环 图实施

    • 无环:

      无自循环，无平行边。

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

  • 最多使用 \(\Delta + 1\) 种颜色，其中 \(\Delta\) 是图的度数。

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

    • 当图形为两方时

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

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

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

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

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

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

      • 其中 \(|E|\) 是图中的边数、

      • \(|V|\) 是图中的顶点数。

签名

pgr_edgeColoring(Edges SQL)
Returns set of (edge_id, color_id)
OR EMPTY SET
示例:

pgRouting 示例数据 的图形着色

SELECT * FROM pgr_edgeColoring(
    'SELECT id, source, target, cost, reverse_cost FROM edges
    ORDER BY id'
);
 edge_id | color_id
---------+----------
       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

边(source, target)的权重

reverse_cost

ANY-NUMERICAL

-1

边(target, source)的权重

  • 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

结果列

返回 (edge_id, color_id) 的集合

列

类型

描述

edge_id

BIGINT

边的标识符。

color_id

BIGINT

边颜色的标识符。

  • 颜色的最小值为 1。

另请参阅

索引和表格