Versiones anteriores de esta página
En grafos grandes, como los grafos de carretera o de redes eléctricas, la contracción de grafos se puede utilizar para acelerar algunos algoritmos. La contracción reduce el tamaño del grafo eliminando algunos de los vértices y aristas, por ejemplo, podría agregar aristas que representen una secuencia de las aristas originales disminuyendo el tiempo total y el espacio utilizados en los algoritmos de grafos.
Esta implementación proporciona un marco flexible para agregar algoritmos de contracción en el futuro, actualmente, admite dos algoritmos:
Permitiendo que el usuario:
En el algoritmo, la contracción sin salida se representa mediante 1.
En el caso de un grafo no dirigido, un nodo se considera dead end (sin salida)
En el caso de un grafo dirigido, un nodo se considera “sin salida” cuando
Cuando las condiciones son verdaderas, se puede hacer la Operation: Dead End Contraction
Grafo dirigido
![digraph G {
u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
w, z [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, v} [dir=none, weight=1, penwidth=3];
u -> w -> u;
v -> z;
}](_images/graphviz-719bacabd05e51044745f0e4f81d88759332c4ac.png)
Grafo no dirigido
![graph G {
u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
w, z [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -- {u, v} [dir=none, weight=1, penwidth=3];
u -- w [color=black];
u -- w [color=darkgray];
v -- z;
}](_images/graphviz-5cc9f6e395e7daf9c40782667b2aa08e14e2023c.png)
La contracción sin salida se detendrá hasta que no haya más nodos sin salida. Por ejemplo, del siguiente grafo donde w es el nodo dead end:
![digraph G {
u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
w [style=filled; color=green];
"G" [shape=tripleoctagon;style=filled;color=deepskyblue; label = "Rest of the Graph"];
rankdir=LR;
G -> u [dir=none, weight=1, penwidth=3];
u -> v -> w;
}](_images/graphviz-5e35f42543a9c600b7fe7e468fc428e28f807680.png)
Después de contraer w, el nodo v es ahora un nodo dead end y es contraído:
![digraph G {
u [shape=circle;style=filled;width=.4;color=deepskyblue];
v [style=filled; color=green, label="v{w}"];
"G" [shape=tripleoctagon;style=filled;color=deepskyblue; label = "Rest of the Graph"];
rankdir=LR;
G -> u [dir=none, weight=1, penwidth=3];
u -> v;
}](_images/graphviz-3f9e880839fe6efd5dc5b18040e053875842ac83.png)
Después de contraer v, deténgase. El nodo u tiene la información de los nodos que se contraen.
![digraph G {
u [style=filled; color=green, label="u{v,w}"];
"G" [shape=tripleoctagon;style=filled;color=deepskyblue; label = "Rest of the Graph"];
rankdir=LR;
G -> u [dir=none, weight=1, penwidth=3];
}](_images/graphviz-2edc9968b9c36f48f03f71989951c8e2e7c962d3.png)
El nodo u tiene la información de los nodos que se contrajeron.
En el algoritmo, la contracción lineal es representada con un 2.
En el caso de un grafo no dirigido, un nodo se considera un nodo lineal cuando
En el caso de un grafo dirigido, un nodo se considera lineal cuando
Dirigido
![digraph G {
u, c, a, w [shape=circle;style=filled;width=.4;color=deepskyblue];
v, b [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
{w, c} -> G -> {u, a} [dir=none, weight=1, penwidth=3];
u -> v -> w;
a -> b -> c;
c -> b -> a[color=darkgray];
}](_images/graphviz-93fba87277a8ad89ceebbcdd692e3bc067d7d28b.png)
No dirigido
![graph G {
u, w [shape=circle;style=filled;width=.4;color=deepskyblue];
v [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
w -- G -- u [dir=none, weight=1, penwidth=3];
u -- v -- w;
}](_images/graphviz-14a237d334776e6005cd949cf4a0eed1207c1c05.png)
Usando un contra ejemplo, el vértice v no es lineal porque no es posible pasar de w a u a través de v.
![digraph G {
u, w, v [shape=circle;style=filled;width=.4;color=deepskyblue];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
{w} -> G -> {u} [dir=none, weight=1, penwidth=3];
u -> v -> w -> v;
}](_images/graphviz-bc77587ebc527e97cf3403da611daafab99363d2.png)
La contracción lineal se detendrá hasta que no haya más nodos lineales. Por ejemplo, en el siguiente grafo donde v y w son nodos lineales :
![digraph G {
u, z [shape=circle;style=filled;color=deepskyblue];
v, w [style=filled; color=green];
"G" [shape=tripleoctagon; style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, z} [dir=none, weight=1, penwidth=3];
u -> v -> w -> z;
}](_images/graphviz-bde47d0456a0ce341e8e9c57a3df5cf0ddc93edc.png)
Después de contraer w,
![digraph G {
u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
w, z [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, v} [dir=none, weight=1, penwidth=3];
u -> w;
v -> w;
v -> z;
}](_images/graphviz-5f3bfe4d32984fc40bd619e2f6314f0a36eb7d33.png)
![digraph G {
u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
w, z [style=filled; color=green];
G [shape=tripleoctagon;width=1.5;style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
{u, v} -> G [dir=none, weight=1, penwidth=3];
w -> u;
w -> v;
z -> v;
}](_images/graphviz-492ba6c358cd5f61817c7f57808ad644768f36f9.png)
w se elimina del grafo![digraph G {
u, z [shape=circle;style=filled;color=deepskyblue];
v [style=filled; color=green];
"G" [shape=tripleoctagon; style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, z} [dir=none, weight=1, penwidth=3];
u -> v;
v -> z [label="{w}";color=red]
}](_images/graphviz-63b882f3d7f9ec7a229e9396ea668378bad82744.png)
Contracción v:
v se elimina del grafo![digraph G {
u, z [shape=circle;style=filled;color=deepskyblue];
"G" [shape=tripleoctagon; style=filled;color=deepskyblue;label = "Rest of the Graph"];
rankdir=LR;
G -> {u, z} [dir=none, weight=1, penwidth=3];
u -> z [label="{v, w}";color=red]
}](_images/graphviz-0e10939fbc318e2b97bfa91ba11a684750f4e1b8.png)
El arista \(u \rightarrow z\) tiene la información de los nodos que fueron contraídos.
Contraer un grafo se puede hacer con más de una operación. El orden de las operaciones afecta al gráfico 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 alterna los tiempos `` max_cycles`` a través de `` operations_order``.
<input>
do max_cycles times {
for (operation in operations_order)
{ do operation }
}
<output>
En esta sección, la creación y el uso de un grafo contraído se mostrarán en el ejemplo.
Datos Originales
La siguiente consulta muestra los datos originales implicados en la operación de contracción.
SELECT id, source, target, cost, reverse_cost FROM edge_table;
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 | 1 | 2 | 1 | 1
2 | 2 | 3 | -1 | 1
3 | 3 | 4 | -1 | 1
4 | 2 | 5 | 1 | 1
5 | 3 | 6 | 1 | -1
6 | 7 | 8 | 1 | 1
7 | 8 | 5 | 1 | 1
8 | 5 | 6 | 1 | 1
9 | 6 | 9 | 1 | 1
10 | 5 | 10 | 1 | 1
11 | 6 | 11 | 1 | -1
12 | 10 | 11 | 1 | -1
13 | 11 | 12 | 1 | -1
14 | 10 | 13 | 1 | 1
15 | 9 | 12 | 1 | 1
16 | 4 | 9 | 1 | 1
17 | 14 | 15 | 1 | 1
18 | 16 | 17 | 1 | 1
(18 rows)
El grafo original:
Los resultados no representan al grafo contraído. Representan los cambios realizados en el grafo después de aplicar el algoritmo 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 edge_table',
array[1,2], directed:=false);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 5 | {7,8} | -1 | -1 | -1
v | 15 | {14} | -1 | -1 | -1
v | 17 | {16} | -1 | -1 | -1
e | -1 | {1,2} | 3 | 5 | 2
e | -2 | {4} | 3 | 9 | 2
e | -3 | {10,13} | 5 | 11 | 2
e | -4 | {12} | 9 | 11 | 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:
Adición de columnas adicionales a las tablas edge_table y edge_table_vertices_pgr donde:
| Columna | Descripción |
|---|---|
| contracted_vertices | El conjunto de vértices que pertenecen al vértice/arista |
| is_contracted | En la tabla vértice
|
| is_new | En la tabla edge:
|
ALTER TABLE edge_table_vertices_pgr ADD is_contracted BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edge_table_vertices_pgr ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edge_table ADD is_new BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE edge_table ADD contracted_vertices BIGINT[];
ALTER TABLE
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 edge_table',
array[1,2], directed:=false);
SELECT 7
Actualice la tabla vértice utilizando la información de contracción
Use edge_table_vertices_pgr.is_contracted para indicar los vértices que son contraídos.
UPDATE edge_table_vertices_pgr
SET is_contracted = true
WHERE id IN (SELECT unnest(contracted_vertices) FROM contraction_results);
UPDATE 10
Agregar a edge_table_vertices_pgr.contracted_vertices los vértices contraídos que pertenecen a los vértices.
UPDATE edge_table_vertices_pgr
SET contracted_vertices = contraction_results.contracted_vertices
FROM contraction_results
WHERE type = 'v' AND edge_table_vertices_pgr.id = contraction_results.id;
UPDATE 3
El modificado edge_table_vertices_pgr.
SELECT id, contracted_vertices, is_contracted
FROM edge_table_vertices_pgr
ORDER BY id;
id | contracted_vertices | is_contracted
----+---------------------+---------------
1 | | t
2 | | t
3 | | f
4 | | t
5 | {7,8} | f
6 | | f
7 | | t
8 | | t
9 | | f
10 | | t
11 | | f
12 | | t
13 | | t
14 | | t
15 | {14} | f
16 | | t
17 | {16} | f
(17 rows)
Actualice la tabla edge utilizando la información de la contracción
Inserte las nuevas aristas generadas por pgr_contraction.
INSERT INTO edge_table(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
La modificada edge_table.
SELECT id, source, target, cost, reverse_cost, contracted_vertices, is_new
FROM edge_table
ORDER BY id;
id | source | target | cost | reverse_cost | contracted_vertices | is_new
----+--------+--------+------+--------------+---------------------+--------
1 | 1 | 2 | 1 | 1 | | f
2 | 2 | 3 | -1 | 1 | | f
3 | 3 | 4 | -1 | 1 | | f
4 | 2 | 5 | 1 | 1 | | f
5 | 3 | 6 | 1 | -1 | | f
6 | 7 | 8 | 1 | 1 | | f
7 | 8 | 5 | 1 | 1 | | f
8 | 5 | 6 | 1 | 1 | | f
9 | 6 | 9 | 1 | 1 | | f
10 | 5 | 10 | 1 | 1 | | f
11 | 6 | 11 | 1 | -1 | | f
12 | 10 | 11 | 1 | -1 | | f
13 | 11 | 12 | 1 | -1 | | f
14 | 10 | 13 | 1 | 1 | | f
15 | 9 | 12 | 1 | 1 | | f
16 | 4 | 9 | 1 | 1 | | f
17 | 14 | 15 | 1 | 1 | | f
18 | 16 | 17 | 1 | 1 | | f
19 | 3 | 5 | 2 | -1 | {1,2} | t
20 | 3 | 9 | 2 | -1 | {4} | t
21 | 5 | 11 | 2 | -1 | {10,13} | t
22 | 9 | 11 | 2 | -1 | {12} | t
(22 rows)
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
ORDER BY id;
id
----
3
5
6
9
11
15
17
(7 rows)
WITH
vertices_in_graph AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edge_table
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
ORDER BY id;
id | source | target | cost | reverse_cost | contracted_vertices
----+--------+--------+------+--------------+---------------------
5 | 3 | 6 | 1 | -1 |
8 | 5 | 6 | 1 | 1 |
9 | 6 | 9 | 1 | 1 |
11 | 6 | 11 | 1 | -1 |
19 | 3 | 5 | 2 | -1 | {1,2}
20 | 3 | 9 | 2 | -1 | {4}
21 | 5 | 11 | 2 | -1 | {10,13}
22 | 9 | 11 | 2 | -1 | {12}
(8 rows)
Uso del grafo contraído con pgr_dijkstra
Hay tres casos al calcular la ruta más corta entre un origen y un destino determinados en un grafo contraído:
Usando las Aristas que pertenecen al grafo contraído. en las líneas 10 a 19.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | CREATE OR REPLACE FUNCTION my_dijkstra(
departure BIGINT, destination BIGINT,
OUT seq INTEGER, OUT path_seq INTEGER,
OUT node BIGINT, OUT edge BIGINT,
OUT cost FLOAT, OUT agg_cost FLOAT)
RETURNS SETOF RECORD AS
$BODY$
SELECT * FROM pgr_dijkstra(
$$
WITH
vertices_in_graph AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
)
SELECT id, source, target, cost, reverse_cost
FROM edge_table
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
$$,
departure, destination, false);
$BODY$
LANGUAGE SQL VOLATILE;
CREATE FUNCTION
|
Caso 1
Cuando el origen y el destino pertenecen al grafo contraído, se encuentra ruta.
SELECT * FROM my_dijkstra(3, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 3 | 5 | 1 | 0
2 | 2 | 6 | 11 | 1 | 1
3 | 3 | 11 | -1 | 0 | 2
(3 rows)
Caso 2
Cuando el origen y/o el destino pertenecen a un subgrafo de aristas, no se encuentra una ruta.
En este caso, el grafo contraído no tiene una arista que se conecte con el nodo \(4\).
SELECT * FROM my_dijkstra(4, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)
Caso 3
Cuando el origen y/o el destino pertenecen a un vértice, no se encuentra ruta.
En este caso, el grafo contraído no tiene algún arista que conecte con el nodo \(7\) ni con el nodo \(4\) del segundo caso.
SELECT * FROM my_dijkstra(4, 7);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)
Refinar la función anterior para incluir nodos que pertenezcan a una arista.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | CREATE OR REPLACE FUNCTION my_dijkstra(
departure BIGINT, destination BIGINT,
OUT seq INTEGER, OUT path_seq INTEGER,
OUT node BIGINT, OUT edge BIGINT,
OUT cost FLOAT, OUT agg_cost FLOAT)
RETURNS SETOF RECORD AS
$BODY$
SELECT * FROM pgr_dijkstra(
$$
WITH
edges_to_expand AS (
SELECT id
FROM edge_table
WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
),
vertices_in_graph AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
UNION
SELECT unnest(contracted_vertices)
FROM edge_table
WHERE id IN (SELECT id FROM edges_to_expand)
)
SELECT id, source, target, cost, reverse_cost
FROM edge_table
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
$$,
departure, destination, false);
$BODY$
LANGUAGE SQL VOLATILE;
CREATE FUNCTION
|
Caso 1
Cuando el origen y el destino pertenecen al grafo contraído, se encuentra ruta.
SELECT * FROM my_dijkstra(3, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 3 | 5 | 1 | 0
2 | 2 | 6 | 11 | 1 | 1
3 | 3 | 11 | -1 | 0 | 2
(3 rows)
Caso 2
Cuando el origen y/o el destino pertenecen a un subgrafo de arista, entonces se encuentra una ruta.
El grafo de ruteo ahora tiene un arista que se conecta con el nodo \(4\).
SELECT * FROM my_dijkstra(4, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 4 | 16 | 1 | 0
2 | 2 | 9 | 22 | 2 | 1
3 | 3 | 11 | -1 | 0 | 3
(3 rows)
Caso 3
Cuando el origen y/o el destino pertenecen a un vértice, no se encuentra ruta.
En este caso, el grafo contraído no tiene una arista que se conecte con el nodo \(7\).
SELECT * FROM my_dijkstra(4, 7);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
(0 rows)
Refinar la función anterior para incluir nodos que pertenezcan a una arista.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | CREATE OR REPLACE FUNCTION my_dijkstra(
departure BIGINT, destination BIGINT,
OUT seq INTEGER, OUT path_seq INTEGER,
OUT node BIGINT, OUT edge BIGINT,
OUT cost FLOAT, OUT agg_cost FLOAT)
RETURNS SETOF RECORD AS
$BODY$
SELECT * FROM pgr_dijkstra(
$$
WITH
edges_to_expand AS (
SELECT id
FROM edge_table
WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
),
vertices_to_expand AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
),
vertices_in_graph AS (
SELECT id
FROM edge_table_vertices_pgr
WHERE is_contracted = false
UNION
SELECT unnest(contracted_vertices)
FROM edge_table
WHERE id IN (SELECT id FROM edges_to_expand)
UNION
SELECT unnest(contracted_vertices)
FROM edge_table_vertices_pgr
WHERE id IN (SELECT id FROM vertices_to_expand)
)
SELECT id, source, target, cost, reverse_cost
FROM edge_table
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
$$,
departure, destination, false);
$BODY$
LANGUAGE SQL VOLATILE;
CREATE FUNCTION
|
Caso 1
Cuando el origen y el destino pertenecen al grafo contraído, se encuentra ruta.
SELECT * FROM my_dijkstra(3, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 3 | 5 | 1 | 0
2 | 2 | 6 | 11 | 1 | 1
3 | 3 | 11 | -1 | 0 | 2
(3 rows)
Caso 2
El cambio de código no afecta a este caso, por lo que cuando el origen o el destino pertenecen a un subgrafo de aristas, aún se puede encontrar ruta.
SELECT * FROM my_dijkstra(4, 11);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 4 | 16 | 1 | 0
2 | 2 | 9 | 22 | 2 | 1
3 | 3 | 11 | -1 | 0 | 3
(3 rows)
Caso 3
Cuando el origen y/o el destino pertenecen a un vértice, entonces se encuentra ruta.
Ahora, el grafo de ruteo tiene un arista que se conecta con el nodo \(7\).
SELECT * FROM my_dijkstra(4, 7);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 4 | 3 | 1 | 0
2 | 2 | 3 | 19 | 2 | 1
3 | 3 | 5 | 7 | 1 | 3
4 | 4 | 8 | 6 | 1 | 4
5 | 5 | 7 | -1 | 0 | 5
(5 rows)
Índices y tablas