pgr_articulationPoints

pgr_articulationPoints - Devuelve los puntos de articulación de un grafo no dirigido.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0
    • Cambio de columnas de retorno: seq se elimina
    • Función oficial
  • Versión 2.5.0
    • Nueva función experimental

Soporte

Descripción

Los vértices que pertenecen a más de un componente biconectado se denominan puntos de articulación o, equivalentemente, corte de vértices. Los puntos de articulación son vértices cuya eliminación aumentaría el número de componentes conectados en el grafo. Esta implementación solo se puede utilizar con un grafo no dirigido.

Las características principales son:

  • La firma es para un grafo no dirigido.
  • Los valores regresados se ordenan:
    • node ascendente.
  • Tiempo de ejecución: \(O(V + E)\)

Firmas

pgr_articulationPoints(Edges SQL)

RETURNS SET OF (node)
OR EMPTY SET
Ejemplo:Los puntos de articulación del grafo 
SELECT * FROM pgr_articulationPoints(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table'
);
 node
------
    2
    5
    8
   10
(4 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 (node)

Columna Tipo Descripción
node BIGINT Identificador del vértice.