pgr_bipartite -实验¶

pgr_bipartite - 不相邻的顶点集合，同一集合中没有两个顶点相邻。

Warning

可能服务器崩溃

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

Warning

实验功能

它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分：
- 这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名称可能会改变。
- 签名可能会改变。
- 功能可能会改变。
- pgTap 测试可能丢失。
- 可能需要 c/c++编码。
- 可能缺乏文档。
- 文档（如果有）可能需要重写。
- 可能需要自动生成文档示例。
- 可能需要社区的大量反馈。
- 可能取决于 pgRouting 的拟议功能
- 可能依赖于 pgRouting 的已弃用函数

可用性

版本3.2.0
- 新的实验签名

描述¶

二方图是指有两组顶点的图，这两组顶点相互连接，但内部没有连接。如果可以使用两种颜色对图形着色，从而使一个集合中的顶点着色为相同的颜色，那么就可能是一个二方图。

主要特点是：

该算法只适用于无向图。
返回值没有排序。
该算法检查图是否是二分图。如果它是二分的，那么它返回节点以及代表两个不同集合的两种颜色 0 和`1`。
如果图不是两部分的，那么算法会返回空集。
运行时间： \(O(V + E)\)

签名¶

pgr_bipartite(Edges SQL)

Returns set of (vertex_id, color_id)

OR EMPTY SET

示例:: 当图形为两方时

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

附加示例¶

示例:: 奇长循环图不可能是两部分的。

边 \(5 \rightarrow 1\) 将使顶点为 \(\{1, 3, 7, 6, 5\}\) 的子图成为奇数长度的循环图，因为循环有 5 个顶点。

INSERT INTO edges (source, target, cost, reverse_cost) VALUES
(5, 1, 1, 1);
INSERT 0 1

蓝色边代表奇数长度循环子图。

SELECT * FROM pgr_bipartite(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$
);
 vertex_id | color_id
-----------+----------
(0 rows)

另请参阅¶

示例数据网络。

索引和表格