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 retorno 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:

  • 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)\)

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

_images/scc_sampledata.png

Parámetros

Parámetro

Tipo

Descripción

SQL Aristas

TEXT

SQL 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

Devuelve el 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

Índices y tablas