pgr_biconnectedComponents

pgr_biconnectedComponents — Componentes biconectados de un grafo no dirigido.

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(SQL de aristas)

REGRESA CONJUNTO DE (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)

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

• Componentes - Familia de funciones

• Las consultas utilizan la red Datos Muestra .

• Boost: Componentes Biconectados

• wikipedia: Componentes biconnectados

Índices y tablas

• Índice

• Página de Búsqueda