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 las 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(Edges SQL, Contraction order [, max_cycles] [, forbidden_vertices] [, directed])
RETURNS SETOF (type, id, contracted_vertices, source, target, cost)
Ejemplo

Hacer una contracción sin salida y una contracción lineal con el vértice 2 cuya contracción está prohibida

SELECT * FROM pgr_contraction(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[1, 2], forbidden_vertices:=ARRAY[2]);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  2 | {1}                 |     -1 |     -1 |   -1
 v    |  5 | {7,8}               |     -1 |     -1 |   -1
 v    | 10 | {13}                |     -1 |     -1 |   -1
 v    | 15 | {14}                |     -1 |     -1 |   -1
 v    | 17 | {16}                |     -1 |     -1 |   -1
(5 rows)

Parámetros

Columna

Tipo

Descripción

Edges SQL

TEXT

Consulta SQL como se describe en Inner query

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

Valores predeterminados

Descripción

forbidden_vertices

ARRAY[ANY-INTEGER]

Vacío

Identificadores de vértices prohibidos de contracción.

max_cycles

INTEGER

\(1\)

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

dirigido

BOOLEAN

true

  • En caso de “”true”” el grafo se considera como Dirigido.

  • Cuando false el gráfo se considera No Dirigido

Consulta interna

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.

costo

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

DEVOLUCION DE CONJUNTOS (type, id, contracted_vertices, source, target, cost)

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

Columna

Tipo

Descripción

tipo

TEXT
Tipo del id.

  • “v” cuando la fila es un vértice.

  • “e” cuando la fila es una arista.

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.

origen

BIGINT

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

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

objetivo

BIGINT

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

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

costo

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 * FROM pgr_contraction(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
ARRAY[1]);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  2 | {1}                 |     -1 |     -1 |   -1
 v    |  5 | {7,8}               |     -1 |     -1 |   -1
 v    | 10 | {13}                |     -1 |     -1 |   -1
 v    | 15 | {14}                |     -1 |     -1 |   -1
 v    | 17 | {16}                |     -1 |     -1 |   -1
(5 rows)
Ejemplo

Sólo contracción lineal

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

Ver también

Índices y tablas