pgr_bridges

pgr_bridges - Calcula los puentes 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

Descripción

Un puente es un borde de un grafo no dirigido cuya eliminación aumenta su número de componentes conectados. 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:

    • edge ascendente

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

Firmas

pgr_bridges(Edges SQL)
RETURNS SET OF (edge)
OR EMPTY SET
Ejemplo:

Los puentes del grafo

SELECT * FROM pgr_bridges(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 edge
------
    1
    6
    7
   14
   17
   18
(6 rows)

_images/bridge_sampledata.png

Parámetros

Parámetro

Tipo

Descripción

SQL Aristas

TEXT

SQL 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

Returns set of (edge)

Columna

Tipo

Descripción

edge

BIGINT

Identificador del borde que es un puente.

Ver también

Índices y tablas