Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5

pgr_connectedComponents

pgr_connectedComponents — 使用基于深度优先搜索（DFS）的方法计算无向图的连通分量。

可用性

• 版本3.0.0

  • 结果列发生变化：

    • n_seq 被删除

    • seq 将类型更改为``BIGINT``

  • 函数正式发布。

• 版本2.5.0

  • 新实验功能。

描述

无向图的连通部分是指相互之间均可到达的顶点集合。

主要特点是：

• 适用于 无向 图。

• 连通分量由顶点描述

• 返回值是有序的：

  • component 升序

  • node 升序

• 运行时间： $O(V+E)$

Boost 图内部

签名

pgr_connectedComponents(Edges SQL)

返回集合 (seq, component, node)

OR EMPTY SET

示例:

图的连通分量

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

列	类型	描述
seq	BIGINT	从 1 开始的顺序值。
component	BIGINT	分量标识符。 具有组件中最小节点标识符的值。
node	BIGINT	属于该 组件 的顶点的标识符。

其他示例

连接不连通的组件

要获取图的连通性：

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

There are three basic ways to connect components:

• 从顶点到边的起点

• 从顶点到边的终点

• 从边上的顶点到最近的顶点

  • 该解决方案需要将边缘分割。

In this example pgr_separateCrossing and pgr_separateTouching will be used.

Get the connectivity

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

Prepare tables

In this example: the edges table will need an additional column and the vertex table will be rebuilt completely.

ALTER TABLE edges ADD old_id BIGINT;
ALTER TABLE
DROP TABLE vertices;
DROP TABLE

Insert new edges

Using pgr_separateCrossing and pgr_separateTouching insert the results into the edges table.

INSERT INTO edges (old_id, geom)
SELECT id, geom FROM pgr_separateCrossing('SELECT * FROM edges')
UNION
SELECT id, geom FROM pgr_separateTouching('SELECT * FROM edges');
INSERT 0 6

创建顶点表

Using pgr_extractVertices create the table.

CREATE TABLE vertices AS
SELECT * FROM pgr_extractVertices('SELECT id, geom FROM edges');
SELECT 18

Update the topology

/* -- set the source information */
UPDATE edges AS e
SET source = v.id, x1 = x, y1 = y
FROM vertices AS v
WHERE ST_StartPoint(e.geom) = v.geom;
UPDATE 24
/* -- set the target information */
UPDATE edges AS e
SET target = v.id, x2 = x, y2 = y
FROM vertices AS v
WHERE ST_EndPoint(e.geom) = v.geom;
UPDATE 24

Update other values

In this example only cost and reverse_cost are updated, where they are based on the length of the geometry and the directionality is kept using the sign function.

UPDATE edges e
  SET cost          = ST_length(e.geom)*sign(e1.cost),
      reverse_cost  = ST_length(e.geom)*sign(e1.reverse_cost)
FROM edges e1
WHERE e.cost IS NULL AND e1.id = e.old_id;
UPDATE 6

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

另请参阅

• 分量 - 函数族

• 示例数据

• Boost: Connected components

• 维基百科: 连通分量

索引和表格

• Index

• Search Page