pgr_strongComponents

pgr_strongComponents — Componentes fuertemente conectados de un grafo dirigido utilizando el algoritmo de Tarjan basado en DFS.

Disponibilidad

• Versión 3.0.0

  • Las columnas de resultados cambian:

    • n_seq se elimina

    • seq cambió el tipo a BIGINT”

  • Function promoted to official.

• Versión 2.5.0

  • New experimental function.

Descripción

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

Las principales características son:

• Funciona paragrafos dirigidos.

• Los componentes se describen mediante identificadores de vértices.

• Los valores regresados se ordenan:

  • component ascendente

  • node ascendente

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

Boost Graph Inside

Firmas

pgr_strongComponents(SQL de aristas)

Regresa conjunto de (seq, component, node)

O CONJUNTO VACÍO

Ejemplo:

Los componentes fuertes del grafo

SELECT * FROM pgr_strongComponents(
    '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.

Ver también

• Componentes - Familia de funciones

• Datos Muestra

• Boost: Strong components

• Wikipedia: Componentes fuertemente conectados

Índices y tablas

• Índice

• Página de Búsqueda