pgr_contraction

pgr_contraction — Realiza la contracción del grafo y devuelve los vértices y aristas contraídos..

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0

    • Cambio de columnas de retorno: seq se elimina

    • Cambio de nombre de pgr_contractGraph

    • Correcciones

    • Función oficial

  • Versión 2.3.0

    • Nueva función experimental

Descripción

La contracción reduce el tamaño del grafo eliminando algunos de los vértices y aristas, también por ejemplo, podría agregar aristas que representan una secuencia de aristas originales disminuyendo el tiempo total y el espacio utilizados en los algoritmos de grafo.

Las características principales son:

  • El proceso se realiza sólo en aristas con costos positivos.

  • No devuelve el grafo completo contraído

    • Solo se devuelven los cambios en el gráfico

  • Actualmente hay dos tipos de métodos de contracción

    • Contracción Sin Salida

    • Contracción Lineal

  • Los valores devueltos incluyen

    • las aristas añadidas por contracción lineal.

    • los vértices modificados por contracción sin salida.

  • Los valores devueltos se ordenan de la siguiente manera:

    • columna id ascendente cuando el tipo = v

    • columna id descendente cuando el tipo = e

Firmas

Resumen

La función pgr_contraction tiene la siguiente firma:

pgr_contraction(SQL de aristas, orden de contracción, [opciones])
options: [ max_cycles, forbidden_vertices, directed]
RETURNS SET OF (type, id, contracted_vertices, source, target, cost)
Ejemplo:

Hacer una contracción de callejón sin salida y una contracción lineal en ese orden en un grafo no dirigido.

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[1, 2], directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  4 | {2}                 |     -1 |     -1 |   -1
 v    |  7 | {1,3}               |     -1 |     -1 |   -1
 v    | 14 | {13}                |     -1 |     -1 |   -1
 e    | -1 | {5,6}               |      7 |     10 |    2
 e    | -2 | {8,9}               |      7 |     12 |    2
 e    | -3 | {17}                |     12 |     16 |    2
 e    | -4 | {15}                |     10 |     16 |    2
(7 rows)

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas descritas más adelante.

Orden de contracciones

ARRAY[ ANY-INTEGER ]

Operaciones de contracción ordenadas.

  • 1 = Contracción sin salida

  • 2 - Contracción lineal

Parámetros opcionales

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido.

Parámetros opcionales de Contracción

Columna

Tipo

x Defecto

Descripción

forbidden_vertices

ARRAY[ ANY-INTEGER ]

vacío

Identificadores de vértices prohibidos para contracción.

max_cycles

INTEGER

\(1\)

Número de veces que se realizarán las operaciones de contracción en el orden contraction_order.

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 (type, id, contracted_vertices, source, target, cost)

La función devuelve una sola fila. Las columnas de la fila son:

Columna

Tipo

Descripción

type

TEXT

Tipo del id.

  • v cuando la fila es un vértice.

    • Columna id tiene valor positivo

  • e cuando la fila es una arista.

    • Columna id tiene valor negativo

id

BIGINT

Todos los números de esta columna son “”DISTINTOS””

  • En caso de type = “v”.

    • Identificador del vértice modificado.

  • En caso de type = “e”.

    • Disminución de la secuencia a partir de -1.

    • Representando un pseudo id como no incorporado en el conjunto de aristas originales.

contracted_vertices

ARRAY[BIGINT]

Arreglo de identificadores de vértices contraídos.

source

BIGINT

  • En caso de type = “v”: \(-1\)

  • En caso de type = “e”: Identificador del vétice de la arista actual (source, target).

target

BIGINT

  • En caso de type = “v”: \(-1\)

  • En caso de type = “e”: Identificador del vértice objetivo de la arista actual (source, target).

cost

FLOAT

  • En caso de type = “v”: \(-1\)

  • En caso de type = “e”: Peso de la arista actual (source, target).

Ejemplos Adicionales

Ejemplo:

Sólo contracción sin salida

SELECT type, id, contracted_vertices FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[1]);
 type | id | contracted_vertices
------+----+---------------------
 v    |  4 | {2}
 v    |  6 | {5}
 v    |  7 | {1,3}
 v    |  8 | {9}
 v    | 14 | {13}
(5 rows)

Ejemplo:

Sólo contracción lineal

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  ARRAY[2]);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {3}                 |      1 |      7 |    2
 e    | -2 | {3}                 |      7 |      1 |    2
(2 rows)

Ver también

Índices y tablas