Versiones soportadas: latest (3.8) main dev

pgr_contractionDeadEnd - Proposed

pgr_contractionDeadEnd — Performs graph contraction and returns the contracted vertices and edges.

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

• Version 3.8.0

  • New proposed function.

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.

• Does not return the full contracted graph.

  • Only changes on the graph are returned.

• The returned values include:

  • The new edges generated by linear contraction.

  • The modified vertices generated by dead end contraction.

• Los valores devueltos se ordenan de la siguiente manera:

  • column id ascending when its a modified vertex.

  • column id with negative numbers descending when its a new edge.

A node is considered a dead end node when:

• En grafos no dirigidos:

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

• En grafos dirigidos:

  • When there is only one adjacent vertex or

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

Boost Graph Inside

Firmas

pgr_contractionDeadEnd(Edges SQL, [options])

options: [directed, forbidden]

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

Ejemplo:

Dead end contraction on an undirected graph.

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)

• The green nodes are dead end nodes.

  • Node $3$ is a dead end node after node $1$ is contracted.

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	Value = e indicating the row is an edge.
id	BIGINT	A pseudo id of the edge. 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	Weight of the current edge.

Ejemplos Adicionales

Vértice sin salida en un grafo sin dirigir

The green nodes are dead end nodes.

• 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

• The green nodes are dead end nodes

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

Nodo	Adjacent nodes	Sin salida	Reason
$6$	$\{1\}$	Yes	Has only one adjacent node.
$7$	$\{2\}$	Yes	Has only one adjacent node.
$8$	$\{2,3\}$	Yes	Has more than one adjacent node and all edges are incoming.
$9$	$\{4\}$	Yes	Has only one adjacent node.
$10$	$\{4,5\}$	No	Has more than one adjacent node and all edges are outgoing.
$1,2,3,4,5$	Many adjacent nodes.	No	Has more than one adjacent node and some edges are incoming and some are outgoing.

From above, nodes $\{6,7,9\}$ are dead ends because the total number of adjacent vertices is one.

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)

Step by step dead end contraction

The dead end contraction will stop until there are no more dead end nodes. For example, from the following graph where $3$ is the dead end node:

After contracting $3$, node $2$ is now a dead end node and is contracted:

After contracting $2$, stop. Node $1$ has the information of nodes that were contracted.

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)

Creating the contracted graph

Steps for the creation of the contracted graph

Add additional columns.

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

Save results into a table.

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

Fill contracted_vertices with the information from the results that belong to the vertices.

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

The contracted vertices are not part of the contracted graph.

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

Using when departure and destination are in the contracted graph

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)

Using when departure/destination is not in the contracted graph

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)

Using when departure and destination are not in the contracted graph

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