Versiones soportadas: latest (3.8) main dev

pgr_contractionDeadEnd - Propuesto

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

Proposed

Advertencia

Funciones propuestas para la próxima versión mayor.

• No están oficialmente en la versión actual.

• Es probable que oficialmente formen parte del próximo lanzamiento:

  • Las funciones hacen uso de ENTEROS y FLOTANTES

  • Probablemente el nombre no cambie. (Pero todavía puede)

  • Es posible que la firma no cambie. (Pero todavía puede)

  • Probablemente la funcionalidad no cambie. (Pero todavía puede)

  • Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.

  • Es posible que la documentación necesite un refinamiento.

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.

Un nodo se considera sin salida cuando:

• En grafos no dirigidos:

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

• En grafos dirigidos:

  • Cuando hay solo un vértice adyacente o

  • When all edges are incoming regardless of the number of adjacent vertices.

Adentro: Boost Graph

Firmas

pgr_contractionDeadEnd(SQL de aristas, [opciones])

opciones: [directed, forbidden]

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

Ejemplo:

Contracción de vértice sin salida en un grafo no dirigido.

SELECT * FROM pgr_contractionDeadEnd(
  'SELECT id, source, target, cost, reverse_cost FROM edges',
  directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  4 | {2}                 |     -1 |     -1 |   -1
 v    |  6 | {5}                 |     -1 |     -1 |   -1
 v    |  7 | {1,3}               |     -1 |     -1 |   -1
 v    |  8 | {9}                 |     -1 |     -1 |   -1
 v    | 14 | {13}                |     -1 |     -1 |   -1
(5 rows)

• Los nodos verdes son nodos sin salida.

  • El nodo $3$ es sin salida después de haberse contraído el nodo $1$.

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
forbidden_vertices	ARRAY[ ANY-INTEGER ]	vacío	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	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

Vértice sin salida en un grafo sin dirigir

Los nodos verdes son nodos sin salida.

• They have only one adjacent node.

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

Vértice sin salida en un grafo dirigido

• Los nodos verdes son nodos sin salida

• Los nodos azules tienen un número ilimitado de aristas entrantes y/o salientes.

Nodo	Nodos adyacentes	Sin salida	Reason
$6$	$\{1\}$	Si	Solo tiene un nodo adyacente.
$7$	$\{2\}$	Si	Solo tiene un nodo adyacente.
$8$	$\{2,3\}$	Si	Has more than one adjacent node and all edges are incoming.
$9$	$\{4\}$	Si	Solo tiene un nodo adyacente.
$10$	$\{4,5\}$	No	Has more than one adjacent node and all edges are outgoing.
$1,2,3,4,5$	Muchos nodos adyacentes.	No	Has more than one adjacent node and some edges are incoming and some are outgoing.

De arriba, nodes $\{6,7,9\}$ son sin salida por que el número de vértices adyacentes es 1.

When there are more than one adjacent vertex, all edges need to be all incoming edges otherwise it is not a dead end.

SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
  (1, 1, 6, 1, 1),
  (2, 2, 7, 1, -1),
  (3, 2, 8, 1, -1),
  (4, 3, 8, 1, -1),
  (5, 9, 4, 1, -1),
  (6, 10, 4, 1, 1),
  (7, 10, 5, 1, 1),
  /* Rest of the graph */
  (8, 1, 25, 1, 1), (9, 1, 26, 1, 1),
  (10, 2, 25, 1, 1), (11, 2, 26, 1, 1),
  (12, 3, 25, 1, 1), (13, 3, 26, 1, 1),
  (14, 4, 25, 1, 1), (15, 4, 26, 1, 1),
  (16, 5, 25, 1, 1), (17, 5, 26, 1, 1)) AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  1 | {6}                 |     -1 |     -1 |   -1
 v    |  2 | {7,8}               |     -1 |     -1 |   -1
 v    |  3 | {8}                 |     -1 |     -1 |   -1
 v    |  4 | {9}                 |     -1 |     -1 |   -1
(4 rows)

Paso a paso contracción sin salida

La contracción sin salida se detendrá hasta que no haya más nodos sin salida. Por ejemplo, del siguiente grafo donde $3$ es el nodo sin salida:

Después de contraer $3$, el nodo ` $2$ es ahora un nodo sin salida y es contraído:

Después de contraer $2$, detener. El nodo $1$ tiene la información de los nodos que se contraen.

SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
  (1, 1, 2, 1, -1),
  (2, 2, 3, 1, -1),
  /* Rest of the graph */
  (3, 1, 25, 1, 1), (4, 1, 26, 1, 1),
  (5, 25, 25, 1, 1), (6, 25, 26, 1, 1)) AS edges(id,source,target,cost,reverse_cost)$$,
  directed => true);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  1 | {2,3}               |     -1 |     -1 |   -1
(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 vertices ADD contracted_vertices BIGINT[];
ALTER TABLE

Almacenar los resultados en una tabla.

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

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 6

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 5

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
----+---------------
  1 | t
  2 | t
  3 | t
  5 | t
  9 | t
 13 | t
(6 rows)

El grafo contraído

DROP VIEW IF EXISTS contracted_graph;
NOTICE:  view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
WITH
vertices_in_graph AS (
  SELECT id FROM vertices WHERE is_contracted = false
)
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

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

SELECT *
FROM pgr_dijkstra('SELECT * FROM contracted_graph', 6, 17);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      17 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      17 |    7 |    8 |    1 |        1
   3 |        3 |         6 |      17 |   11 |   11 |    1 |        2
   4 |        4 |         6 |      17 |   12 |   13 |    1 |        3
   5 |        5 |         6 |      17 |   17 |   -1 |    0 |        4
(5 rows)

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

SELECT * FROM pgr_dijkstra(
  'WITH cul_de_sac AS (
    SELECT contracted_vertices || id as v
    FROM vertices WHERE 1 = ANY(contracted_vertices))
  SELECT id, source, target, cost, reverse_cost FROM edges, cul_de_sac
  WHERE source = ANY(v) AND target = ANY(v)

  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 |    6 |    1 |        0
   2 |        2 |         1 |      17 |    3 |    7 |    1 |        1
   3 |        3 |         1 |      17 |    7 |    8 |    1 |        2
   4 |        4 |         1 |      17 |   11 |    9 |    1 |        3
   5 |        5 |         1 |      17 |   16 |   15 |    1 |        4
   6 |        6 |         1 |      17 |   17 |   -1 |    0 |        5
(6 rows)

Usando cuando la salida y el destino no están en el grafo contraído

SELECT * FROM pgr_dijkstra(
  'WITH cul_de_sac AS (
    SELECT contracted_vertices || id as v
    FROM vertices WHERE 1 = ANY(contracted_vertices) OR 9 = ANY(contracted_vertices))
  SELECT id, source, target, cost, reverse_cost FROM edges, cul_de_sac WHERE source = ANY(v) AND target = ANY(v)

  UNION

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

Ver también

• Contraction - Familia de funciones

Índices y tablas

• Índice

• Página de Búsqueda