Contraction - Familia de funciones

Introducción

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:

  1. Contracción sin salida

  2. Contracción lineal

Permitiendo que el usuario:

  • Prohíba la contracción en un conjunto de nodos.

  • Decida el orden de los algoritmos de contracción y establezca el número máximo de veces que se van a ejecutar.

Contracción sin salida

Contracción de los nodos de hoja del grafo.

Sin salida

Un nodo se considera sin salida cuando

  • En grafos no dirigidos:

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

  • En grafos dirigidos:

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

    • No hay aristas salientes y tiene al menos una arista entrante.

    • No hay aristas entrantes y tiene al menos una arista saliente.

Cuando las condiciones son verdaderas, se puede hacer la Operación: Contracción de callejón sin salida.

Vértice sin salida en un grafo sin dirigir

  • Los nodos verdes son nodos dead end

  • Los nodos azules tienen un número ilimitado de aristas.

graph G {
    u, v [shape=circle;style=filled;width=.4;color=deepskyblue];
    a, b [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 -- a [color=black];
    u -- a [color=darkgray];
    v -- b;
}

Nodo

Nodos adyacentes

Número de vértices adyacentes

\(a\)

\(\{u\}\)

1

\(b\)

\(\{v\}\)

1

Vértice sin salida en un grafo dirigido

  • Los nodos verdes son nodos dead end

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

digraph G {
    u, v, w, x, y [shape=circle;style=filled;width=.4;color=deepskyblue];
    a, b, c, d, e [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;
       color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    G -> {u, v, w} [dir=none, weight=1, penwidth=3];
    {x, y} -> G  [dir=none, weight=1, penwidth=3];
    u -> a -> u;
    v -> b;
    {w, v} -> c;
    d -> x;
    e -> {x, y};
}

Nodo

Nodos adyacentes

Número de vértices adyacentes

Número de aristas entrantes

Número de aristas salientes

\(a\)

\(\{u\}\)

1

\(b\)

\(\{v\}\)

1

\(c\)

\(\{v, w\}\)

2

2

0

\(d\)

\(\{x\}\)

1

\(e\)

\(\{x, y\}\)

2

0

2

De arriba, nodes \(\{a, b, d\}\) son callejones sin salida por que el número de vértices adyacentes es 1. No son necesarios los checks para esos nodos.

En al siguiente tabla, nodos \(\{c, e\}\) por que el par del numero de vértices adyacentes no es 1 para

  • \(c\)

    • No hay aristas salientes y tiene al menos una arista entrante.

  • \(e\)

    • No hay aristas entrantes y tiene al menos una arista saliente.

Operación: 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 \(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;
}

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

Después de contraer math:v, detenerse El nodo math: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];
}

El nodo \(u\) tiene la información de los nodos que se contrajeron.

Contracción lineal

En el algoritmo, la contracción lineal es representada con un 2.

Lineal

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

  • 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

Vértice lineal en grafo no dirigido

  • Los nodos verdes son lineales

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

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

Nodo

Nodos adyacentes

Número de vértices adyacentes

\(v\)

\(\{u, w\}\)

2

Vértice lineal en grafo dirigido

  • Los nodos verdes son lineales

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

  • El nodo blanco no es linero por que la linealidad no es simétrica.

    • Es posible ir a \(y \rightarrow c \rightarrow z\)

    • No es posible ir a \(z \rightarrow c \rightarrow y\)

digraph G {
    u, v, w, x, y, z [shape=circle;style=filled;width=.4;color=deepskyblue];
    a, b [style=filled; color=green];
    G [shape=tripleoctagon;width=1.5;style=filled;
      color=deepskyblue;label = "Rest of the Graph"];

    rankdir=LR;
    {u, v} -> G -> {x, w, y, z} [dir=none, weight=1, penwidth=3];
    u -> a -> v;
    w -> b -> x;
    x -> b -> w [color=darkgray];
    y -> c -> z -> c;
}

Nodo

Nodos adyacentes

Número de vértices adyacentes

Es simétrico?

\(a\)

\(\{u, v\}\)

2

\(b\)

\(\{w, x\}\)

2

\(c\)

\(\{y, z\}\)

2

no

Operación: Contracción Lineal

La contracción lineal se detendrá hasta que no hayan 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;
}

Contrayendo \(w\),

  • El vértice \(w\) se elimina del grafo

  • Los aristas \(v \rightarrow w\) y \(w \rightarrow z\) fueron eliminados del grafo.

  • Se inserta un nuevo arista \(v \rightarrow z\) y se representa con color rojo.

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

Contrayendo \(v\):

  • El vértice \(v\) se elimina del grafo

  • Los aristas \(u \rightarrow v\) y \(v \rightarrow z\) son removidos del grafo.

  • Se inserta un nuevo arista \(u \rightarrow z\) y se representa con color rojo.

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

El arista \(u \rightarrow z\) tiene la información de los nodos que fueron contraídos.

El ciclo

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>

Contracción de los datos de muestra

En esta sección, la creación y el uso de un grafo contraído se mostrarán en el ejemplo.

  • Se usa Datos Muestra para un grafo no dirigido

  • una operación sin salida primero seguida de una operación lineal.

Construcción del grafo en la base de datos

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 edges ORDER BY id;
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
  1 |      5 |      6 |    1 |            1
  2 |      6 |     10 |   -1 |            1
  3 |     10 |     15 |   -1 |            1
  4 |      6 |      7 |    1 |            1
  5 |     10 |     11 |    1 |           -1
  6 |      1 |      3 |    1 |            1
  7 |      3 |      7 |    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
 13 |     12 |     17 |    1 |           -1
 14 |      8 |      9 |    1 |            1
 15 |     16 |     17 |    1 |            1
 16 |     15 |     16 |    1 |            1
 17 |      2 |      4 |    1 |            1
 18 |     13 |     14 |    1 |            1
(18 rows)

El grafo original:

_images/Fig6-undirected.png

Resultados de la Contracción

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 edges',
  array[1, 2], directed => false);
 type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
 v    |  4 | {2}                 |     -1 |     -1 |   -1
 v    |  7 | {1,3}               |     -1 |     -1 |   -1
 v    | 14 | {13}                |     -1 |     -1 |   -1
 e    | -1 | {5,6}               |      7 |     10 |    2
 e    | -2 | {8,9}               |      7 |     12 |    2
 e    | -3 | {17}                |     12 |     16 |    2
 e    | -4 | {15}                |     10 |     16 |    2
(7 rows)

Después de realizar la operación de contracción sin salida:

_images/undirected_sampledata_b.png

Después de hacer la operación de contracción lineal al grafo anterior:

_images/undirected_sampledata_c.png

El proceso para crear el grafo de contracción en la base de datos:

Añadir columnas adicionales

Agregar 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 de vértices

  • En caso de “”true”” se contrae el vértice, no forma parte del grafo contraído.

  • En caso de “”false”” el vértice no se contrae, su parte del grafo contraído.

is_new

En la tabla de aristas

  • En caso de `` true``, la arista se generó por el algoritmo de contracción. Es parte del grafo contraído.

  • En caso de false , la arista es una arista original, podría ser o no parte del grafo contraído.

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

Almacenar información de contracción

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 edges',
  array[1, 2], directed => false);
SELECT 7

Actualización de la tabla de vértices

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 10

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

La tabla de vértices modificada:

SELECT id, contracted_vertices, is_contracted
FROM vertices
ORDER BY id;
 id | contracted_vertices | is_contracted
----+---------------------+---------------
  1 |                     | t
  2 |                     | t
  3 |                     | t
  4 | {2}                 | f
  5 |                     | t
  6 |                     | t
  7 | {1,3}               | f
  8 |                     | t
  9 |                     | t
 10 |                     | f
 11 |                     | f
 12 |                     | f
 13 |                     | t
 14 | {13}                | f
 15 |                     | t
 16 |                     | f
 17 |                     | t
(17 rows)

Actialización de la tabla de aristas

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
WHERE type = 'e';
INSERT 0 4

La modificada edge_table.

SELECT id, source, target, cost, reverse_cost, contracted_vertices, is_new
FROM edges
ORDER BY id;
 id | source | target | cost | reverse_cost | contracted_vertices | is_new
----+--------+--------+------+--------------+---------------------+--------
  1 |      5 |      6 |    1 |            1 |                     | f
  2 |      6 |     10 |   -1 |            1 |                     | f
  3 |     10 |     15 |   -1 |            1 |                     | f
  4 |      6 |      7 |    1 |            1 |                     | f
  5 |     10 |     11 |    1 |           -1 |                     | f
  6 |      1 |      3 |    1 |            1 |                     | f
  7 |      3 |      7 |    1 |            1 |                     | f
  8 |      7 |     11 |    1 |            1 |                     | f
  9 |     11 |     16 |    1 |            1 |                     | f
 10 |      7 |      8 |    1 |            1 |                     | f
 11 |     11 |     12 |    1 |           -1 |                     | f
 12 |      8 |     12 |    1 |           -1 |                     | f
 13 |     12 |     17 |    1 |           -1 |                     | f
 14 |      8 |      9 |    1 |            1 |                     | f
 15 |     16 |     17 |    1 |            1 |                     | f
 16 |     15 |     16 |    1 |            1 |                     | f
 17 |      2 |      4 |    1 |            1 |                     | f
 18 |     13 |     14 |    1 |            1 |                     | f
 19 |      7 |     10 |    2 |           -1 | {5,6}               | t
 20 |      7 |     12 |    2 |           -1 | {8,9}               | t
 21 |     12 |     16 |    2 |           -1 | {17}                | t
 22 |     10 |     16 |    2 |           -1 | {15}                | t
(22 rows)

El grafo contraído

Vértices que pertenecen al grafo contraído.

SELECT id
FROM vertices
WHERE is_contracted = false
ORDER BY id;
 id
----
  4
  7
 10
 11
 12
 14
 16
(7 rows)

Aristas que pertenecen al grafo contraído.

WITH
vertices_in_graph AS (
  SELECT id
  FROM vertices
  WHERE is_contracted = false
)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edges
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 |     10 |     11 |    1 |           -1 |
  8 |      7 |     11 |    1 |            1 |
  9 |     11 |     16 |    1 |            1 |
 11 |     11 |     12 |    1 |           -1 |
 19 |      7 |     10 |    2 |           -1 | {5,6}
 20 |      7 |     12 |    2 |           -1 | {8,9}
 21 |     12 |     16 |    2 |           -1 | {17}
 22 |     10 |     16 |    2 |           -1 | {15}
(8 rows)

El grafo contraído

_images/newgraph.png

Usando el grafo contraído

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:

  • Caso 1: Tanto el origen como el destino pertenecen al grafo contraído.

  • Caso 2: El origen y/o el destino pertenecen a un subgrafo de aristas.

  • Caso 3: El origen y/o el destino pertenecen a un vértice.

Caso 1: Tanto el origen como el destino pertenecen al grafo contraído.

Usando las Aristas que pertenecen al grafo contraído. en las líneas 11 a 20.

 1CREATE OR REPLACE FUNCTION my_dijkstra(
 2  departure BIGINT, destination BIGINT,
 3  OUT seq INTEGER, OUT path_seq INTEGER,
 4  OUT start_vid BIGINT, OUT end_vid BIGINT,
 5  OUT node BIGINT, OUT edge BIGINT,
 6  OUT cost FLOAT, OUT agg_cost FLOAT)
 7RETURNS SETOF RECORD AS
 8$BODY$
 9SELECT * FROM pgr_dijkstra(
10  $$
11  WITH
12  vertices_in_graph AS (
13    SELECT id
14    FROM vertices
15    WHERE is_contracted = false
16  )
17  SELECT id, source, target, cost, reverse_cost
18  FROM edges
19  WHERE source IN (SELECT * FROM vertices_in_graph)
20  AND target IN (SELECT * FROM vertices_in_graph)
21  $$,
22  departure, destination, false);
23$BODY$
24LANGUAGE SQL VOLATILE;
25CREATE FUNCTION

Caso 1

Cuando el origen y el destino pertenecen al grafo contraído, se encuentra ruta.

SELECT * FROM my_dijkstra(10, 12);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        10 |      12 |   10 |    5 |    1 |        0
   2 |        2 |        10 |      12 |   11 |   11 |    1 |        1
   3 |        3 |        10 |      12 |   12 |   -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(15, 12);
 seq | path_seq | start_vid | end_vid | 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(15, 1);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)

Caso 2: El origen y/o el destino pertenecen a un subgrafo de aristas.

Refinar la función anterior para incluir nodos que pertenezcan a una arista.

  • Los vértices que deben ampliarse se calculan en las líneas 11 a 17.

  • Añadiendo al grafo contraído esa sección adicional en las líneas 26 a 28.

 1CREATE OR REPLACE FUNCTION my_dijkstra(
 2  departure BIGINT, destination BIGINT,
 3  OUT seq INTEGER, OUT path_seq INTEGER,
 4  OUT start_vid BIGINT, OUT end_vid BIGINT,
 5  OUT node BIGINT, OUT edge BIGINT,
 6  OUT cost FLOAT, OUT agg_cost FLOAT)
 7RETURNS SETOF RECORD AS
 8$BODY$
 9SELECT * FROM pgr_dijkstra(
10  $$
11  WITH
12  edges_to_expand AS (
13    SELECT id
14    FROM edges
15    WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
16    OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
17  ),
18
19  vertices_in_graph AS (
20    SELECT id
21    FROM vertices
22    WHERE is_contracted = false
23
24    UNION
25
26    SELECT unnest(contracted_vertices)
27    FROM edges
28    WHERE id IN (SELECT id FROM edges_to_expand)
29  )
30
31  SELECT id, source, target, cost, reverse_cost
32  FROM edges
33  WHERE source IN (SELECT * FROM vertices_in_graph)
34  AND target IN (SELECT * FROM vertices_in_graph)
35  $$,
36  departure, destination, false);
37$BODY$
38LANGUAGE SQL VOLATILE;
39CREATE FUNCTION

Caso 1

Cuando el origen y el destino pertenecen al grafo contraído, se encuentra ruta.

SELECT * FROM my_dijkstra(10, 12);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        10 |      12 |   10 |    5 |    1 |        0
   2 |        2 |        10 |      12 |   11 |   11 |    1 |        1
   3 |        3 |        10 |      12 |   12 |   -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(15, 12);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        15 |      12 |   15 |   16 |    1 |        0
   2 |        2 |        15 |      12 |   16 |   21 |    2 |        1
   3 |        3 |        15 |      12 |   12 |   -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(15, 1);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)

Caso 3: El origen y/o el destino pertenecen a un vértice.

Refinar la función anterior para incluir nodos que pertenezcan a una arista.

  • Los vértices que deben ampliarse se calculan en las líneas 19 a 24.

  • Añadiendo al grafo contraído esa sección adicional en las líneas 38 a 40.

 1CREATE OR REPLACE FUNCTION my_dijkstra(
 2  departure BIGINT, destination BIGINT,
 3  OUT seq INTEGER, OUT path_seq INTEGER,
 4  OUT start_vid BIGINT, OUT end_vid BIGINT,
 5  OUT node BIGINT, OUT edge BIGINT,
 6  OUT cost FLOAT, OUT agg_cost FLOAT)
 7RETURNS SETOF RECORD AS
 8$BODY$
 9SELECT * FROM pgr_dijkstra(
10  $$
11  WITH
12  edges_to_expand AS (
13    SELECT id
14    FROM edges
15    WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
16    OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
17  ),
18
19  vertices_to_expand AS (
20    SELECT id
21    FROM vertices
22    WHERE ARRAY[$$ || departure || $$]::BIGINT[] <@ contracted_vertices
23    OR ARRAY[$$ || destination || $$]::BIGINT[] <@ contracted_vertices
24  ),
25
26  vertices_in_graph AS (
27    SELECT id
28    FROM vertices
29    WHERE is_contracted = false
30
31    UNION
32
33    SELECT unnest(contracted_vertices)
34    FROM edges
35    WHERE id IN (SELECT id FROM edges_to_expand)
36
37    UNION
38
39    SELECT unnest(contracted_vertices)
40    FROM vertices
41    WHERE id IN (SELECT id FROM vertices_to_expand)
42  )
43
44  SELECT id, source, target, cost, reverse_cost
45  FROM edges
46  WHERE source IN (SELECT * FROM vertices_in_graph)
47  AND target IN (SELECT * FROM vertices_in_graph)
48  $$,
49  departure, destination, false);
50$BODY$
51LANGUAGE SQL VOLATILE;
52CREATE FUNCTION

Caso 1

Cuando el origen y el destino pertenecen al grafo contraído, se encuentra ruta.

SELECT * FROM my_dijkstra(10, 12);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        10 |      12 |   10 |    5 |    1 |        0
   2 |        2 |        10 |      12 |   11 |   11 |    1 |        1
   3 |        3 |        10 |      12 |   12 |   -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(15, 12);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        15 |      12 |   15 |   16 |    1 |        0
   2 |        2 |        15 |      12 |   16 |   21 |    2 |        1
   3 |        3 |        15 |      12 |   12 |   -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(15, 1);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |        15 |       1 |   15 |    3 |    1 |        0
   2 |        2 |        15 |       1 |   10 |   19 |    2 |        1
   3 |        3 |        15 |       1 |    7 |    7 |    1 |        3
   4 |        4 |        15 |       1 |    3 |    6 |    1 |        4
   5 |        5 |        15 |       1 |    1 |   -1 |    0 |        5
(5 rows)

Ver también

Índices y tablas