pgr_strongComponents

pgr_strongComponents — Componentes fuertemente conectados de un grafo dirigido utilizando el algoritmo de Tarjan 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

  • Versiones sustentadas: actual(3.0)
  • Versiones no sustentadas: 2.6 2.5

Descripción

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

Las características principales son:

  • La firma es para un grafo 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_strongComponents(Edges SQL)

RETURNS SET OF (seq, component, node)
OR EMPTY SET
Ejemplo:Los componentes fuertes del grafo
SELECT * FROM pgr_strongComponents(
    '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 directed, que debe 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.