pgr_biconnectedComponents

pgr_biconnectedComponents — Devuelve los componentes biconectados de un grafo no dirigido. En particular, el algoritmo implementado por Boost.Graph.

_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

Soporte

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 características principales son:

  • La firma es para un grafo no dirigido.
  • Los componentes se describen mediante aristas.
  • Los valores regresados se ordenan:
    • componente ascendente.
    • borde 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 edge_table'
);
 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 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 no dirigido, que debería 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, edge)

Columna Tipo Descripción
seq BIGINT Valor secuencial a partir de 1.
component BIGINT Identificador del componente. Es igual al identificador de arista mínima en el componente.
edge BIGINT Identificador de la arista.

Ver también

Índices y tablas