pgr_sequentialVertexColoring - 拟议¶

pgr_sequentialVertexColoring — 使用贪婪方法返回无向图的顶点着色。

Warning

下一版本的拟议功能。

它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分：
- 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名字可能不会改变。（但仍然有可能改变）
- 签名可能不会改变。（但仍然有可能改变）
- 功能可能不会改变。（但仍然有可能改变）
- pgTap 测试已经完成。但可能需要更多。
- 文档可能需要完善。

可用性

版本 3.3.0
- 晋升为拟议签名
版本3.2.0
- 新的实验签名

描述¶

顺序顶点着色算法是一种图着色算法，其中颜色标识符以顺序方式分配给图的顶点，使得没有边连接两个相同颜色的顶点。

主要特点是：

该实现仅适用于无向图。
提供要分配给图中存在的所有顶点的颜色。
颜色标识符值在范围 \([1, |V|]\) 内
该算法尝试为每个顶点分配尽可能少的颜色。
高效的图着色是一个 NP 困难问题，因此，该算法并不总是产生最佳着色。它遵循贪婪策略，依次迭代所有顶点，并将其邻居未使用的最小可能颜色分配给每个顶点。
返回的行按顶点值的升序排列。
顺序顶点着色运行时间： \(O(|V|*(d + k))\)
- 其中 \(|V|\) 是顶点数，
- \(d\) 是图中顶点的最大度数，
- \(k\) 是使用的颜色数量。

签名¶

pgr_sequentialVertexColoring(Edges SQL)

Returns set of (vertex_id, color_id)

OR EMPTY SET

示例:: pgRouting 示例数据的图形着色

SELECT * FROM pgr_sequentialVertexColoring(
    'SELECT id, source, target, cost, reverse_cost FROM edges
    ORDER BY id'
);
 vertex_id | color_id
-----------+----------
         1 |        1
         2 |        1
         3 |        2
         4 |        2
         5 |        1
         6 |        2
         7 |        1
         8 |        2
         9 |        1
        10 |        1
        11 |        2
        12 |        1
        13 |        1
        14 |        2
        15 |        2
        16 |        1
        17 |        2
(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

结果列¶

返回集合 (vertex_id, color_id)

列	类型	描述
`vertex_id`	`BIGINT`	顶点的标识符。
`color_id`	`BIGINT`	顶点颜色的标识符。颜色的最小值为 1。

列

类型

描述

vertex_id

BIGINT

顶点的标识符。

color_id

BIGINT

顶点颜色的标识符。

颜色的最小值为 1。

另请参阅¶

查询使用示例数据网络。

索引和表格