pgr_articulationPoints

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

_images/boost-inside.jpeg

Boost Graph Inside

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

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

x Defecto

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

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

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.

Ver también

Índices y tablas