• Supported versions:

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

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.

Ver también

Índices y tablas