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

  • La firma es para un grafo no dirigido.

  • 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 edge_table'
);
 edge
------
    1
    6
    7
   14
   17
   18
(6 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 (edge)

Columna

Tipo

Descripción

edge

BIGINT

Identificador del borde que es un puente.

Ver también

Índices y tablas