Versiones soportadas: latest (3.8) main dev

pgr_contractionLinear - Propuesto

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

Disponibilidad

• Versión 3.8.0

  • Nueva función propuesta.

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.

Adentro: Boost Graph

Firmas

pgr_contractionLinear(SQL de aristas, [opciones])

opciones: [directed, forbidden]

Regresa conjunto de (type, id, contracted_vertices, source, target, cost)

Ejemplo:

Contracción lineal en un grafo no dirigido.

SELECT * FROM pgr_contractionLinear(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {3}                 |      1 |      7 |    2
 e    | -2 | {17}                |     12 |     16 |    2
 e    | -3 | {15}                |     10 |     16 |    2
(3 rows)

• Los nodos verdes son lineales y no forman parte del grafo contraído.

  • Aristas adyacentes no forman parte del grafo contraído.

• Las lineas verdes son aristas que pertenecen al grafo contraído.

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	ARRAY[ ANY-INTEGER ]	vacío	Identificadores de vértices prohibidos para contracción.
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

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	Valor = e cuando la fila es una arista.
id	BIGINT	Un pseudo identificador de la arista. Todos los números de esta columna son “”DISTINTOS”” Disminución de la secuencia a partir de -1.
contracted_vertices	ARRAY[BIGINT]	Arreglo de identificadores de vértices contraídos.
source	BIGINT	Identificador del vértice de origen de la arista actual.
target	BIGINT	Identificador del vértice destino de la arista actual.
cost	FLOAT	Peso de la arista actual.

Ejemplos Adicionales

Bordes lineales

Grafo no dirigido

A node connects two (or more) linear edges when

• El número de vértices adyacentes es 2.

En el caso de un grafo dirigido, un nodo se considera lineal cuando

• El número de vértices adyacentes es 2.

• La linealidad es simétrica.

La linealidad no es simétrica

Grafo dirigido

Grafo cuando la linealidad no es simétrica.

When the graph is processed as a directed graph, linearity is not symmetrical, therefore the graph can not be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, -1),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
(0 rows)

Grafo no dirigido

When the same graph is processed as an undirected graph, linearity is symmetrical, therefore the graph can be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, -1),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2}                 |      1 |      3 |    4
(1 row)

Las tres aristas pueden ser reemplazadas por una arista no dirigida

• Arista $1-3$.

  • Con costo: $4$.

  • Vértices contraídos en la arista: $\{2\}$.

La linealidad es simétrica

Grafo dirigido

Grafo donde la linealidad es simétrica.

When the graph is processed as a directed graph, linearity is not symmetrical, therefore the graph can not be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, 2),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2}                 |      1 |      3 |    4
 e    | -2 | {2}                 |      3 |      1 |    6
(2 rows)

Las cuatro aristas pueden ser reemplazadas con dos aristas dirigidas.

• Arista $1-3$.

  • Con costo: $4$.

  • Vértices contraídos en la arista: $\{2\}$.

• Arista $3-1$.

  • Con costo: $6$.

  • Vértices contraídos en la arista: $\{2\}$.

Grafo no dirigido

When the same graph is processed as an undirected graph, linearity is symmetrical, therefore the graph can be contracted.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, 2),
  (2, 2, 3, 3, 4))
  AS edges(id,source,target,cost,reverse_cost)$$,
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2}                 |      1 |      3 |    4
(1 row)

Las cuatro aristas pueden ser reemplazadas con una arista no dirigida.

• Arista $1-3$.

  • Con costo: $4$.

  • Vértices contraídos en la arista: $\{2\}$.

Contracción lineal, paso a paso

La contracción lineal se detendrá hasta que no hayan más aristas lineales. Por ejemplo, en el siguiente grafo hay aristas lineales

Contrayendo el vértice $3$,

• El vértice $3$ se elimina del grafo

• Los aristas $2\to 3$ y $w\to z$ fueron eliminados del grafo.

• Se inserta una nuevo arista $2\to 4$ y se representa con color rojo.

Contrayendo el vértice $2$:

• El vértice $2$ se elimina del grafo

• Los aristas $1\to 2$ y $2\to 3$ son eliminados del grafo.

• Se inserta una nuevo arista $1\to 3$ y se representa con color rojo.

El arista $1\to 3$ tiene la información de los costos y nodos que fueron contraídos.

SELECT * FROM pgr_contractionLinear(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1),
  (2, 2, 3, 1),
  (2, 3, 4, 1))
  AS edges(id,source,target,cost)$$);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 e    | -1 | {2,3}               |      1 |      4 |    3
(1 row)

Creando el grafo contraído

Pasos para la creación del grafo contraído

Añadir columnas adicionales.

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

Almacenar los resultados en una tabla.

SELECT * INTO contraction_results
FROM pgr_contractionLinear(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  directed => false);
SELECT 3

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 3

Los vértices contraído no forman parte del grafo contraído.

SELECT id, is_contracted
FROM vertices WHERE is_contracted ORDER BY id;
 id | is_contracted
----+---------------
  3 | t
 15 | t
 17 | t
(3 rows)

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;
INSERT 0 3

Crear el grafo contraído.

CREATE VIEW contracted_graph AS
WITH
vertices_in_graph AS (
  SELECT id FROM vertices WHERE NOT is_contracted
)
SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
ORDER BY id;
CREATE VIEW

El grafo contraído

SELECT * FROM contracted_graph ORDER by id;
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
  1 |      5 |      6 |    1 |            1
  2 |      6 |     10 |   -1 |            1
  4 |      6 |      7 |    1 |            1
  5 |     10 |     11 |    1 |           -1
  8 |      7 |     11 |    1 |            1
  9 |     11 |     16 |    1 |            1
 10 |      7 |      8 |    1 |            1
 11 |     11 |     12 |    1 |           -1
 12 |      8 |     12 |    1 |           -1
 14 |      8 |      9 |    1 |            1
 17 |      2 |      4 |    1 |            1
 18 |     13 |     14 |    1 |            1
 19 |      1 |      7 |    2 |           -1
 20 |     12 |     16 |    2 |           -1
 21 |     10 |     16 |    2 |           -1
(15 rows)

Usando cuando la salida como el destino pertenecen al grafo contraído

SELECT *
FROM pgr_dijkstra('SELECT * FROM contracted_graph', 7, 16);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         7 |      16 |    7 |    8 |    1 |        0
   2 |        2 |         7 |      16 |   11 |    9 |    1 |        1
   3 |        3 |         7 |      16 |   16 |   -1 |    0 |        2
(3 rows)

Usando cuando la salida /destino no pertenecen al grafo contraído

SELECT * FROM pgr_dijkstra(
  'WITH in_line AS (SELECT contracted_vertices FROM edges WHERE 17 = ANY(contracted_vertices))
   SELECT id, source, target, cost, reverse_cost
   FROM edges, in_line
   WHERE source = ANY(in_line.contracted_vertices) OR target = ANY(in_line.contracted_vertices)

  UNION

  SELECT id, source, target, cost, reverse_cost FROM contracted_graph',
  1, 17);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         1 |      17 |    1 |   19 |    2 |        0
   2 |        2 |         1 |      17 |    7 |    8 |    1 |        2
   3 |        3 |         1 |      17 |   11 |    9 |    1 |        3
   4 |        4 |         1 |      17 |   16 |   15 |    1 |        4
   5 |        5 |         1 |      17 |   17 |   -1 |    0 |        5
(5 rows)

Ver también

• Contraction - Familia de funciones

Índices y tablas

• Índice

• Página de Búsqueda