pgr_contraction

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

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

• Contraction - Familia de funciones

Índices y tablas

• Índice

• Página de Búsqueda