pgr_connectedComponents

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

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0
    • Las columnas de devolución cambian:
      • n_seq se elimina
      • seq cambió el tipo a BIGINT”
    • Función oficial
  • Versión 2.5.0
    • Nueva función experimental

Soporte

Descripción

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

Las características principales son:

  • La firma es para un grafo no dirigido.
  • Los componentes se describen mediante vértices
  • Los valores regresados se ordenan:
    • component ascendente.
    • node ascendente.
  • Tiempo de ejecución: \(O(V + E)\)

Firmas

pgr_connectedComponents(edges_sql)

RETURNS SET OF (seq, component, node)
OR EMPTY SET
Ejemplo:Los componentes conectados del grafo 
SELECT * FROM pgr_connectedComponents(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table'
);
 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 |        14 |   14
  15 |        14 |   15
  16 |        16 |   16
  17 |        16 |   17
(17 rows)

Parámetros

Parámetro Tipo Valores predeterminados Descripción
Edges SQL TEXT   Consulta interna como se describe a continuación.

Consulta interna

bordes SQL:Una consulta SQL de un grafo no dirigido, que debería devolver un conjunto de filas con las siguientes columnas:
Columna Tipo Valores predeterminados Descripción
id ANY-INTEGER   Identificador de la arista.
origen ANY-INTEGER   Identificador del primer punto final en el vértice de la arista.
objetivo ANY-INTEGER   Identificador del segundo punto final en el vértice de la arista.
cost ANY-NUMERICAL  

Peso de la arista (source, target)

  • Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost ANY-NUMERICAL -1

Peso de la arista (target, source),

  • En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve el conjunto de``(seq, component, node)``

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

Ver también

Índices y tablas