Versiones soportadas: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Versiones no soportadas:2.6 2.5 2.4 2.3

pgr_contraction

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

Disponibilidad

Versión 3.8.0

• Nueva firma:

  • El parámetro Orden de contracción, antes obligatorio, es ahora opcional con el nombre methods.

  • Nuevo nombre y orden de parámetros opcionales.

• Firma obsoleta pgr_contraction(text,bigint[],integer,bigint[],boolean)

Versión 3.0.0

• Cambio de columnas de resultados: seq se elimina

• Cambio de nombre de pgr_contractGraph

• Correcciones

• Función promovida a 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 contraído completo.

  • Solo se devuelven los cambios en el grafo.

• Los valores devueltos incluyen:

  • Las nuevas aristas generadas por la 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 es un vértice modificado.

  • columna id con números negativos descendentes cuando es una nueva arista.

• Actualmente hay dos tipos de métodos de contracción incluidos en esta función:

  • Contracción sin salida. Véase pgr_contractionDeadEnd - Propuesto.

  • Linear Contraction. See pgr_contractionLinear - Propuesto.

Adentro: Boost Graph

Firmas

pgr_contraction(SQL de aristas, [opciones])

opciones: [directed, methods, cycles, forbidden]

Regresa conjunto de (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', 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.

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
methods	INTEGER[]	ARRAY[1,2]	Operaciones de contracción ordenadas. 1 = Contracción sin salida 2 - Contracción lineal
cycles	INTEGER	$1$	Número de veces que se realizarán las operaciones de contracción.
forbidden	BIGINT[]	ARRAY[]::BIGINT[]	Identificadores de vértices prohibidos para contracción.

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

Regresa conjunto de (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 de la fila. 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

Sólo contracción sin salida

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

Sólo contracción lineal

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

El ciclo

Contraer un grafo se puede hacer con más de una operación. El orden de las operaciones afecta al grafo contraído resultante, después de aplicar una operación, el conjunto de vértices que se pueden contraer con otra operación cambia.

Esta implementación cicla `` cycles`` veces a través de los methods.

<input>
do max_cycles times {
    for (operation in operations_order)
     { do operation }
}
<output>

Contracción de los datos de muestra

En esta sección, la creación y el uso de un grafo contraído se mostrarán en el ejemplo.

• Se usa Datos Muestra para un grafo no dirigido

• una operación sin salida primero seguida de una operación lineal.

Construcción del grafo en la base de datos

El grafo original:

Los resultados no representan al grafo contraído. Representan los cambios que necesitan hacerse en el grafo después de aplicar los métodos de contracción.

Observe que los vértices, por ejemplo, $6$ , no aparecen en los resultados porque no se vieron afectados por el algoritmo de contracción.

SELECT * FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges', 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)

Después de realizar la operación de contracción sin salida:

Después de hacer la operación de contracción lineal al grafo anterior:

El proceso para crear el grafo de contracción en la base de datos:

Añadir columnas adicionales

Adding extra columns to the edges and vertices tables. In this documentation the following will be used:

Columna.	Descripción
contracted_vertices	El conjunto de vértices que pertenecen al vértice/arista
is_contracted	En la tabla de vértices En caso de “”true”” se contrae el vértice, no forma parte del grafo contraído. En caso de “”false”” el vértice no se contrae, su parte del grafo contraído.
is_new	En la tabla de aristas En caso de `` true``, la arista se generó por el algoritmo de contracción. Es parte del grafo contraído. En caso de false , la arista es una arista original, podría ser o no parte del grafo contraído.

ALTER TABLE vertices
  ADD is_contracted BOOLEAN DEFAULT false,
  ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edges
  ADD is_new BOOLEAN DEFAULT false,
  ADD contracted_vertices BIGINT[];
ALTER TABLE

Almacenar información de contracción

Almacenar los resultados de la contracción en una tabla.

SELECT * INTO contraction_results
FROM pgr_contraction(
  'SELECT id, source, target, cost, reverse_cost FROM edges', false);
SELECT 7

Actualizar las tablas de aristas y vértices

Usar la columna is_contracted para indicar los vértices contraídos.

UPDATE vertices
SET is_contracted = true
WHERE id IN (SELECT  unnest(contracted_vertices) FROM  contraction_results);
UPDATE 10

Llenar contracted_vertices con la información de los resultados que pertenecen a los vértices.

UPDATE vertices
SET contracted_vertices = contraction_results.contracted_vertices
FROM contraction_results
WHERE type = 'v' AND vertices.id = contraction_results.id;
UPDATE 3

Inserte las nuevas aristas generadas por pgr_contraction.

INSERT INTO edges(source, target, cost, reverse_cost, contracted_vertices, is_new)
SELECT source, target, cost, -1, contracted_vertices, true
FROM contraction_results
WHERE type = 'e';
INSERT 0 4

El grafo contraído

Vértices que pertenecen al grafo contraído.

SELECT id FROM vertices WHERE is_contracted = false ORDER BY id;
 id
----
  4
  7
 10
 11
 12
 14
 16
(7 rows)

Aristas que pertenecen al grafo contraído.

WITH
vertices_in_graph AS (SELECT id FROM vertices WHERE is_contracted = false)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edges
WHERE
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
  AND
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target)
ORDER BY id;
 id | source | target | cost | reverse_cost | contracted_vertices
----+--------+--------+------+--------------+---------------------
  5 |     10 |     11 |    1 |           -1 |
  8 |      7 |     11 |    1 |            1 |
  9 |     11 |     16 |    1 |            1 |
 11 |     11 |     12 |    1 |           -1 |
 19 |      7 |     10 |    2 |           -1 | {5,6}
 20 |      7 |     12 |    2 |           -1 | {8,9}
 21 |     12 |     16 |    2 |           -1 | {17}
 22 |     10 |     16 |    2 |           -1 | {15}
(8 rows)

Visualmente:

Usando el grafo contraído

Depending on the final application the graph is to be prepared. In this example the final application will be to calculate the cost from two vertices in the original graph by using the contracted graph with pgr_dijkstraCost

Hay tres casos al calcular la ruta más corta entre un origen y un destino determinados en un grafo contraído:

• Caso 1: Tanto el origen como el destino pertenecen al grafo contraído.

• Caso 2: El origen y/o el destino pertenecen a un subgrafo de aristas.

• Caso 3: El origen y/o el destino pertenecen a un vértice.

The final application should consider all of those cases.

Crear una vista (o tabla) del grafo Contraído:

DROP VIEW IF EXISTS contracted_graph;
NOTICE:  view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
SELECT id,source, target, cost, reverse_cost, contracted_vertices FROM edges
WHERE
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
  AND
  EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target);
CREATE VIEW

Crear la función que va a utilizar el grafo contraído.

CREATE OR REPLACE FUNCTION path_cost(source BIGINT, target BIGINT)
RETURNS SETOF FLOAT AS
$BODY$

SELECT agg_cost FROM pgr_dijkstraCost(
  /* The inner query */
  'WITH
  cul_de_sac AS (
    SELECT contracted_vertices || id as v
    FROM vertices WHERE ' || $1 ||' = ANY(contracted_vertices)
    OR ' || $2 ||' = ANY(contracted_vertices)),
  linears_to_expand AS (
    SELECT id, contracted_vertices
    FROM edges WHERE is_new AND (' || $1 ||' = ANY(contracted_vertices)
      OR '|| $2 ||'  = ANY(contracted_vertices))
  ),
  additional_vertices AS (
    SELECT * FROM cul_de_sac UNION SELECT contracted_vertices FROM linears_to_expand)
  SELECT id, source, target, cost, reverse_cost
  FROM edges, additional_vertices WHERE source = ANY(v) OR target = ANY(v)

  UNION

  SELECT id, source, target, cost, reverse_cost
  FROM contracted_graph LEFT JOIN linears_to_expand c USING (id) WHERE c.id IS NULL',

  source, target, false);

$BODY$ LANGUAGE SQL;
CREATE FUNCTION

Caso 1: Tanto el origen como el destino pertenecen al grafo contraído.

SELECT * FROM path_cost(10, 12);
 path_cost
-----------
         2
(1 row)

Caso 2: El origen y/o el destino pertenecen a una arista que ha contraído vertices.

SELECT * FROM path_cost(15, 12);
 path_cost
-----------
         3
(1 row)

Caso 3: El origen y/o el destino pertenecen a un vértice que ha sido contraído.

SELECT * FROM path_cost(15, 1);
 path_cost
-----------
         5
(1 row)

Ver también

• Contraction - Familia de funciones

Índices y tablas

• Índice

• Página de Búsqueda