pgr_edgeDisjointPaths

pgr_edgeDisjointPaths — Calcula las rutas de aristas desarticuladas entre dos grupos de vértices.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.2.0

    • Nueva función propuesta:

      • pgr_edgeDisjointPaths(Combinaciones)

  • Versión 3.0.0

    • Función oficial

  • Versión 2.5.0

    • Función propuesta

  • Versión 2.3.0

    • Nueva función Experimental

Descripción

Calcula las rutas de aristas desarticuladas entre dos grupos de vértices. Utiliza algoritmos de flujo máximo subyacentes para calcular las rutas.

Los principales características son:
  • Calcula las rutas de aristas desarticuladas entre dos grupos de vértices cualquiera.

  • Devuelve un conjunto vacío EMPTY SET cuando el origen y el destino son los mismos o no se puede llegar.

  • El gráfico puede dirigido o no.

  • Utiliza pgr_boykovKolmogorov para calcular las rutas.

Firmas

Resumen

pgr_edgeDisjointPaths(Edges SQL, start vid, end vid, [directed])
pgr_edgeDisjointPaths(Edges SQL, start vid, end vids, [directed])
pgr_edgeDisjointPaths(Edges SQL, start vids, end vid, [directed])
pgr_edgeDisjointPaths(Edges SQL, start vids, end vids, [directed])
pgr_edgeDisjointPaths(SQL de aristas, SQL de combinaciones, [directed])
RETURNS SET OF (seq, path_id, path_seq, [start_vid,] [end_vid,] node, edge, cost, agg_cost)
OR EMPTY SET

Uno a Uno

pgr_edgeDisjointPaths(Edges SQL, start vid, end vid, [directed])
RETURNS SET OF (seq, path_id, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Del vértice \(11\) al vértice \(12\)

SELECT * FROM pgr_edgeDisjointPaths(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges',
  11, 12);
 seq | path_id | path_seq | node | edge | cost | agg_cost
-----+---------+----------+------+------+------+----------
   1 |       1 |        1 |   11 |    8 |    1 |        0
   2 |       1 |        2 |    7 |   10 |    1 |        1
   3 |       1 |        3 |    8 |   12 |    1 |        2
   4 |       1 |        4 |   12 |   -1 |    0 |        3
   5 |       2 |        1 |   11 |   11 |    1 |        0
   6 |       2 |        2 |   12 |   -1 |    0 |        1
(6 rows)

Uno a Muchos

pgr_edgeDisjointPaths(Edges SQL, start vid, end vids, [directed])
RETURNS SET OF (seq, path_id, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Desde el vértice \(11\) a los vértices \(\{5, 10, 12\}\)

SELECT * FROM pgr_edgeDisjointPaths(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges',
  11, ARRAY[5, 10, 12]);
 seq | path_id | path_seq | end_vid | node | edge | cost | agg_cost
-----+---------+----------+---------+------+------+------+----------
   1 |       1 |        1 |       5 |   11 |    8 |    1 |        0
   2 |       1 |        2 |       5 |    7 |    4 |    1 |        1
   3 |       1 |        3 |       5 |    6 |    1 |    1 |        2
   4 |       1 |        4 |       5 |    5 |   -1 |    0 |        3
   5 |       2 |        1 |      10 |   11 |    9 |    1 |        0
   6 |       2 |        2 |      10 |   16 |   16 |    1 |        1
   7 |       2 |        3 |      10 |   15 |    3 |    1 |        2
   8 |       2 |        4 |      10 |   10 |   -1 |    0 |        3
   9 |       3 |        1 |      12 |   11 |    8 |    1 |        0
  10 |       3 |        2 |      12 |    7 |   10 |    1 |        1
  11 |       3 |        3 |      12 |    8 |   12 |    1 |        2
  12 |       3 |        4 |      12 |   12 |   -1 |    0 |        3
  13 |       4 |        1 |      12 |   11 |   11 |    1 |        0
  14 |       4 |        2 |      12 |   12 |   -1 |    0 |        1
(14 rows)

Muchos a Uno

pgr_edgeDisjointPaths(Edges SQL, start vids, end vid, [directed])
RETURNS SET OF (seq, path_id, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

De los vértices vertices \(\{11, 3, 17\}\) al vértice \(12\)

SELECT * FROM pgr_edgeDisjointPaths(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], 12);
 seq | path_id | path_seq | start_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+------+------+------+----------
   1 |       1 |        1 |         3 |    3 |    7 |    1 |        0
   2 |       1 |        2 |         3 |    7 |    8 |    1 |        1
   3 |       1 |        3 |         3 |   11 |   11 |    1 |        2
   4 |       1 |        4 |         3 |   12 |   -1 |    0 |        3
   5 |       2 |        1 |        11 |   11 |    8 |    1 |        0
   6 |       2 |        2 |        11 |    7 |   10 |    1 |        1
   7 |       2 |        3 |        11 |    8 |   12 |    1 |        2
   8 |       2 |        4 |        11 |   12 |   -1 |    0 |        3
   9 |       3 |        1 |        11 |   11 |   11 |    1 |        0
  10 |       3 |        2 |        11 |   12 |   -1 |    0 |        1
  11 |       4 |        1 |        17 |   17 |   15 |    1 |        0
  12 |       4 |        2 |        17 |   16 |    9 |    1 |        1
  13 |       4 |        3 |        17 |   11 |   11 |    1 |        2
  14 |       4 |        4 |        17 |   12 |   -1 |    0 |        3
(14 rows)

Muchos a Muchos

pgr_edgeDisjointPaths(Edges SQL, start vids, end vids, [directed])
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

De los vértices \(\{11, 3, 17\}\) a los vértices \(\{5, 10, 12\}\)

SELECT * FROM pgr_edgeDisjointPaths(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges',
  ARRAY[11, 3, 17], ARRAY[5, 10, 12]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
   1 |       1 |        1 |         3 |       5 |    3 |    7 |    1 |        0
   2 |       1 |        2 |         3 |       5 |    7 |    4 |    1 |        1
   3 |       1 |        3 |         3 |       5 |    6 |    1 |    1 |        2
   4 |       1 |        4 |         3 |       5 |    5 |   -1 |    0 |        3
   5 |       2 |        1 |         3 |      10 |    3 |    7 |    1 |        0
   6 |       2 |        2 |         3 |      10 |    7 |    8 |    1 |        1
   7 |       2 |        3 |         3 |      10 |   11 |    9 |    1 |        2
   8 |       2 |        4 |         3 |      10 |   16 |   16 |    1 |        3
   9 |       2 |        5 |         3 |      10 |   15 |    3 |    1 |        4
  10 |       2 |        6 |         3 |      10 |   10 |   -1 |    0 |        5
  11 |       3 |        1 |         3 |      12 |    3 |    7 |    1 |        0
  12 |       3 |        2 |         3 |      12 |    7 |    8 |    1 |        1
  13 |       3 |        3 |         3 |      12 |   11 |   11 |    1 |        2
  14 |       3 |        4 |         3 |      12 |   12 |   -1 |    0 |        3
  15 |       4 |        1 |        11 |       5 |   11 |    8 |    1 |        0
  16 |       4 |        2 |        11 |       5 |    7 |    4 |    1 |        1
  17 |       4 |        3 |        11 |       5 |    6 |    1 |    1 |        2
  18 |       4 |        4 |        11 |       5 |    5 |   -1 |    0 |        3
  19 |       5 |        1 |        11 |      10 |   11 |    9 |    1 |        0
  20 |       5 |        2 |        11 |      10 |   16 |   16 |    1 |        1
  21 |       5 |        3 |        11 |      10 |   15 |    3 |    1 |        2
  22 |       5 |        4 |        11 |      10 |   10 |   -1 |    0 |        3
  23 |       6 |        1 |        11 |      12 |   11 |    8 |    1 |        0
  24 |       6 |        2 |        11 |      12 |    7 |   10 |    1 |        1
  25 |       6 |        3 |        11 |      12 |    8 |   12 |    1 |        2
  26 |       6 |        4 |        11 |      12 |   12 |   -1 |    0 |        3
  27 |       7 |        1 |        11 |      12 |   11 |   11 |    1 |        0
  28 |       7 |        2 |        11 |      12 |   12 |   -1 |    0 |        1
  29 |       8 |        1 |        17 |       5 |   17 |   15 |    1 |        0
  30 |       8 |        2 |        17 |       5 |   16 |   16 |    1 |        1
  31 |       8 |        3 |        17 |       5 |   15 |    3 |    1 |        2
  32 |       8 |        4 |        17 |       5 |   10 |    2 |    1 |        3
  33 |       8 |        5 |        17 |       5 |    6 |    1 |    1 |        4
  34 |       8 |        6 |        17 |       5 |    5 |   -1 |    0 |        5
  35 |       9 |        1 |        17 |      10 |   17 |   15 |    1 |        0
  36 |       9 |        2 |        17 |      10 |   16 |   16 |    1 |        1
  37 |       9 |        3 |        17 |      10 |   15 |    3 |    1 |        2
  38 |       9 |        4 |        17 |      10 |   10 |   -1 |    0 |        3
  39 |      10 |        1 |        17 |      12 |   17 |   15 |    1 |        0
  40 |      10 |        2 |        17 |      12 |   16 |    9 |    1 |        1
  41 |      10 |        3 |        17 |      12 |   11 |   11 |    1 |        2
  42 |      10 |        4 |        17 |      12 |   12 |   -1 |    0 |        3
(42 rows)

Combinaciones

pgr_edgeDisjointPaths(SQL de aristas, SQL de combinaciones, [directed])
RETURNS SET OF (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo:

Usando una tabla de combinaciones, equivalente a calcular el resultado de los vértices \(\{5, 6\}\) a los vértices \(\{10, 15, 14\}\) en un grafo no dirigido.

La tabla de combinaciones:

SELECT source, target FROM combinations
WHERE target NOT IN (5, 6);
 source | target
--------+--------
      5 |     10
      6 |     15
      6 |     14
(3 rows)

La consulta:

SELECT * FROM pgr_edgeDisjointPaths(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges',
  'SELECT * FROM combinations WHERE target NOT IN (5, 6)',
  directed => false);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
   1 |       1 |        1 |         5 |      10 |    5 |    1 |    1 |        0
   2 |       1 |        2 |         5 |      10 |    6 |    2 |   -1 |        1
   3 |       1 |        3 |         5 |      10 |   10 |   -1 |    0 |        0
   4 |       2 |        1 |         6 |      15 |    6 |    4 |    1 |        0
   5 |       2 |        2 |         6 |      15 |    7 |    8 |    1 |        1
   6 |       2 |        3 |         6 |      15 |   11 |    9 |    1 |        2
   7 |       2 |        4 |         6 |      15 |   16 |   16 |    1 |        3
   8 |       2 |        5 |         6 |      15 |   15 |   -1 |    0 |        4
   9 |       3 |        1 |         6 |      15 |    6 |    2 |   -1 |        0
  10 |       3 |        2 |         6 |      15 |   10 |    3 |   -1 |       -1
  11 |       3 |        3 |         6 |      15 |   15 |   -1 |    0 |       -2
(11 rows)

Parámetros

Columna

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describe a continuación

SQL de combinaciones

TEXT

SQL de combinaciones como se describe a abajo

salida

BIGINT

Identificador del vértice inicial de la ruta.

salidas

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

destino

BIGINT

Identificador del vértice final de la ruta.

destinos

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

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.

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

SQL Combinaciones

Parámetro

Tipo

Descripción

source

ENTEROS

Identificador del vértice de salida.

target

ENTEROS

Identificador del vértice de llegada.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

Conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_id

INTEGER

Identificador del camino.

  • Tiene valor 1 para el primero de la ruta de start_vid a end_vid.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.

start_vid

BIGINT

Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta.

end_vid

BIGINT

Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identificador de la arista utilizado para ir del node al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.

cost

FLOAT

Costo para atravesar desde node usando edge hasta el siguiente nodo en la secuencia de la ruta.

agg_cost

FLOAT

Costo agregado desde start_vid hasta node.

Ejemplos Adicionales

Ejemplo:

Asignando manualmente las combinaciones de vértices en un grafo no dirigido.

SELECT * FROM pgr_edgeDisjointPaths(
  'SELECT id, source, target, cost, reverse_cost
  FROM edges',
  'SELECT * FROM (VALUES (5, 10), (6, 15), (6, 14)) AS t(source, target)',
  directed => false);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------
   1 |       1 |        1 |         5 |      10 |    5 |    1 |    1 |        0
   2 |       1 |        2 |         5 |      10 |    6 |    2 |   -1 |        1
   3 |       1 |        3 |         5 |      10 |   10 |   -1 |    0 |        0
   4 |       2 |        1 |         6 |      15 |    6 |    4 |    1 |        0
   5 |       2 |        2 |         6 |      15 |    7 |    8 |    1 |        1
   6 |       2 |        3 |         6 |      15 |   11 |    9 |    1 |        2
   7 |       2 |        4 |         6 |      15 |   16 |   16 |    1 |        3
   8 |       2 |        5 |         6 |      15 |   15 |   -1 |    0 |        4
   9 |       3 |        1 |         6 |      15 |    6 |    2 |   -1 |        0
  10 |       3 |        2 |         6 |      15 |   10 |    3 |   -1 |       -1
  11 |       3 |        3 |         6 |      15 |   15 |   -1 |    0 |       -2
(11 rows)

Ver también

Índices y tablas