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

Soporte

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)