Versiones soportadas: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Versiones no soportadas:2.6 2.5

pgr_connectedComponents

pgr_connectedComponents — Componentes conectados de un grafo no dirigido mediante un enfoque basado en DFS.

Disponibilidad

• Versión 3.0.0

  • Las columnas de resultados cambian:

    • n_seq se elimina

    • seq cambió el tipo a BIGINT”

  • Función promovida a oficial.

• Versión 2.5.0

  • Nueva función experimental.

Descripción

Un componente conectado de un gráfico no direccionado es un conjunto de vértices que son todos accesibles entre sí.

Las principales características son:

• Funciona para grafos no dirigidos.

• Los componentes se describen mediante vértices

• Los valores regresados se ordenan:

  • component ascendente

  • node ascendente

• Tiempo de ejecución: $O(V+E)$

Adentro: Boost Graph

Firmas

pgr_connectedComponents(SQL de aristas)

Regresa conjunto de (seq, component, node)

O CONJUNTO VACÍO

Ejemplo:

Los componentes conectados del grafo

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)

Parámetros

Parámetro	Tipo	Descripción
SQL de aristas	TEXT	SQL de aristas descritas más adelante.

Consultas Internas

SQL aristas

Columna	Tipo	x Defecto	Descripción
id	ENTEROS		Identificador de la arista.
source	ENTEROS		Identificador del primer vértice de la arista.
target	ENTEROS		Identificador del segundo vértice de la arista.
cost	FLOTANTES		Peso de la arista (source, target)
reverse_cost	FLOTANTES	-1	Peso de la arista (target, source) Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de resultados

Regresa conjunto de (seq, component, node)

Columna	Tipo	Descripción
seq	BIGINT	Valor secuencial a partir de 1.
component	BIGINT	Identificador de componente. Continene le valor mínimo de identificador de nodo en el componente.
node	BIGINT	Identificador del vértice que pertenece al component.

Ejemplos Adicionales

Conectando componentes desconectados

Para obtener la conectividad del grafo:

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:

• Del vértice al punto inicial de la arista

• Desde el vértice hasta el punto final de la arista

• Del vértice al vértice más cercano de la arista

  • Esta solución requiere dividir el borde.

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

Crear la tabla de vértices

Using pgr_extractVertices create the table.

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

Actualizar la topología

/* -- 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)

Ver también

• Componentes - Familia de funciones

• Datos Muestra

• Boost: Componentes conectados

• wikipedia: Componente conectado

Índices y tablas

• Índice

• Página de Búsqueda