pgr_biconnectedComponents

pgr_biconnectedComponents — Componentes biconectados de un grafo no dirigido.

_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

Los componentes biconectados de un grafo no dirigido son los subconjuntos máximos de vértices de modo que la eliminación de un vértice de un componente determinado no desconectará el mismo. A diferencia de los componentes conectados, los vértices pueden pertenecer a varios componentes biconectados. Los vértices pueden estar presentes en varios componentes biconectados, pero cada arista solo puede estar contenida en un único componente biconectado.

Las principales características son:

  • Funciona para grafos no dirigidos.

  • Los componentes se describen mediante aristas.

  • Los valores regresados se ordenan:

    • componente ascendente.

    • edge ascendente.

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

Firmas

pgr_biconnectedComponents(Edges SQL)
RETURNS SET OF (seq, component, edge)
OR EMPTY SET
Ejemplo:

Los componentes biconectados del grafo

SELECT * FROM pgr_biconnectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | edge
-----+-----------+------
   1 |         1 |    1
   2 |         2 |    2
   3 |         2 |    3
   4 |         2 |    4
   5 |         2 |    5
   6 |         2 |    8
   7 |         2 |    9
   8 |         2 |   10
   9 |         2 |   11
  10 |         2 |   12
  11 |         2 |   13
  12 |         2 |   15
  13 |         2 |   16
  14 |         6 |    6
  15 |         7 |    7
  16 |        14 |   14
  17 |        17 |   17
  18 |        18 |   18
(18 rows)

_images/bcc_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

Returns set of (seq, component, edge)

Columna

Tipo

Descripción

seq

BIGINT

Valor secuencial a partir de 1.

component

BIGINT

Identificador de componente.

  • Contiene el identificador mínimo de arista en el componente.

edge

BIGINT

Identificador de arista que pertenece a component.

Ver también

Índices y tablas