Versiones soportadas: latest (3.8) main dev

pgr_contractionLinear - Proposed

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

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.

Boost Graph Inside

Firmas

pgr_contractionLinear(Edges SQL, [options])

options: [directed, forbidden]

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

Ejemplo:

Linear contraction on an undirected graph.

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)

• The green nodes are linear nodes and will not be part of the contracted graph.

  • All edges adjacent will not be part of the contracted graph.

• The red lines will be new edges of the contracted graph.

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	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

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.

• Linearity is symmetrical.

Linearity is not symmetrical

Grafo dirigido

Graph where linearity is not symmetrical.

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)

The three edges can be replaced by one undirected edge

• Edge $1-3$.

  • With cost: $4$.

  • Contracted vertices in the edge: $\{2\}$.

La linealidad es simétrica

Grafo dirigido

Graph where linearity is symmetrical.

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)

The four edges can be replaced by two directed edges.

• Edge $1-3$.

  • With cost: $4$.

  • Contracted vertices in the edge: $\{2\}$.

• Edge $3-1$.

  • With cost: $6$.

  • Contracted vertices in the edge: $\{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)

The four edges can be replaced by one undirected edge.

• Edge $1-3$.

  • With cost: $4$.

  • Contracted vertices in the edge: $\{2\}$.

Step by step linear contraction

The linear contraction will stop when there are no more linear edges. For example from the following graph there are linear edges

Contracting vertex $3$,

• The vertex $3$ is removed from the graph

• The edges $2\to 3$ and $w\to z$ are removed from the graph.

• A new edge $2\to 4$ is inserted represented with red color.

Contracting vertex $2$:

• The vertex $2$ is removed from the graph

• The edges $1\to 2$ and $2\to 3$ are removed from the graph.

• A new edge $1\to 3$ is inserted represented with red color.

Edge $1\to 3$ has the information of cost and the nodes that were contracted.

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)

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 edges ADD is_new BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edges ADD contracted_vertices BIGINT[];
ALTER TABLE

Save results into a table.

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

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
----+---------------
  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

Create the contracted graph.

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)

Using when departure and destination are in the contracted graph

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)

Using when departure/destination is not in the contracted graph

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