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 resultados: seq se elimina

    • Función oficial

  • Versión 2.5.0

    • Nueva función experimental

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

  • Funciona para grafos no dirigidos.

  • Los valores regresados se ordenan:

    • node ascendente

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

Firmas

pgr_articulationPoints(SQL de aristas)
Regresa conjunto de (node)
O CONJUNTO VACÍO
Ejemplo:

Los puntos de articulación del grafo

SELECT * FROM pgr_articulationPoints(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 node
------
    3
    6
    7
    8
(4 rows)

Nodos en rojo son los puntos de articulación.

_images/ap_sampledata.png

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

Columna

Tipo

Descripción

node

BIGINT

Identificador del vértice.

Ver también

Índices y tablas