Todos los Pares - Familia de Funciones

Las siguientes funciones funcionan en todas las combinaciones de pares de vértices

Introducción

Las principales características son:

  • No devuelve una ruta.

  • Regresa la suma de los costos de la ruta más corta para cada par de nodos del grafo.

  • El proceso se realiza sólo en aristas con costos positivos.

  • Boost devuelve una matriz \(V \times V\) donde los valores infinitos representan la distancia entre vértices para los que no hay ruta.

    • Solo regresa los valores no infinitos en forma de un conjunto de (start_vid, end_vid, agg_cost).

  • Sea el caso donde los valores devueltos se almacenan en una tabla, por lo que el índice único sería el par: (start_vid, end_vid).

  • Para el grafo no dirigido, los resultados son simétricos.

    • El agg_cost de (u, v) es el mismo que para (v, u).

  • Cuando start_vid = end_vid, el agg_cost = 0.

  • Recomendación: utilice un cuadro delimitador de no más de 3500 aristas.

Parámetros

Parámetro

Tipo

x Defecto

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.

Consultas Internas

SQL aristas

Columna

Tipo

x Defecto

Descripción

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

Conjunto de (start_vid, end_vid, agg_cost)

Columna

Tipo

Descripción

start_vid

BIGINT

Identificador del vértice de salida.

end_vid

BIGINT

Identificador del vértice final.

agg_cost

FLOAT

Costo afregado desde start_vid hasta end_vid.

Rendimiento

Las siguientes pruebas:

  • computadora que no sea servidor

  • con unidad de procesamiento central AMD 64

  • memoria 4G

  • confiable

  • postgreSQL versión 9.3

Datos

Se usaron los siguientes datos

BBOX="-122.8,45.4,-122.5,45.6"
wget --progress=dot:mega -O "sampledata.osm"      "https://www.overpass-api.de/api/xapi?*[bbox=][@meta]"

El procesamiento de datos se llevó a cabo con osm2pgrouting-alpha

createdb portland
psql -c "create extension postgis" portland
psql -c "create extension pgrouting" portland
osm2pgrouting -f sampledata.osm -d portland -s 0

Resultados

Prueba:

Uno

Esta prueba no se hace con cuadro delimitador. La densidad del gráfico que se pasa es extremadamente baja. Para cada <SIZE> se ejecutaron 30 pruebas para obtener el medio. La consulta probada es:

SELECT count(*) FROM pgr_floydWarshall(
   'SELECT gid as id, source, target, cost, reverse_cost
    FROM ways where id <= <SIZE>');

SELECT count(*) FROM pgr_johnson(
   'SELECT gid as id, source, target, cost, reverse_cost
    FROM ways where id <= <SIZE>');

Los resultados de la prueba son:

TAMAÑO:

es la cantidad de aristas dadas como entradas.

ARISTAS:

es el número de registros en la consulta.

DENSIDAD:

es la densidad de los datos \(\dfrac{E}{V \times (V-1)}\).

REGISTROS DEVUELTOS:

es el número de registros devueltos por las consultas.

Floyd-Warshall:

es el tiempo promedio de ejecución en segundos de pgr_floydWarshall.

Johnson:

es el tiempo promedio de ejecución en segundos de pgr_johnson.

TAMAÑO

ARISTAS

DENSIDAD

REGISTROS DEVUELTOS

Floyd-Warshall

Johnson

500

500

0.18E-7

1346

0.14

0.13

1000

1000

0.36E-7

2655

0.23

0.18

1500

1500

0.55E-7

4110

0.37

0.34

2000

2000

0.73E-7

5676

0.56

0.37

2500

2500

0.89E-7

7177

0.84

0.51

3000

3000

1.07E-7

8778

1.28

0.68

3500

3500

1.24E-7

10526

2.08

0.95

4000

4000

1.41E-7

12484

3.16

1.24

4500

4500

1.58E-7

14354

4.49

1.47

5000

5000

1.76E-7

16503

6.05

1.78

5500

5500

1.93E-7

18623

7.53

2.03

6000

6000

2.11E-7

20710

8.47

2.37

6500

6500

2.28E-7

22752

9.99

2.68

7000

7000

2.46E-7

24687

11.82

3.12

7500

7500

2.64E-7

26861

13.94

3.60

8000

8000

2.83E-7

29050

15.61

4.09

8500

8500

3.01E-7

31693

17.43

4.63

9000

9000

3.17E-7

33879

19.19

5.34

9500

9500

3.35E-7

36287

20.77

6.24

10000

10000

3.52E-7

38491

23.26

6.51
Prueba:

Dos

Esta prueba se hace con cuadro delimitador. La densidad del gráfico que se pasa es superior a la de la prueba 1. Para cada <SIZE> se ejecutaron 30 pruebas para obtener el medio. La consulta de arista que se prueba es:

WITH
buffer AS (
  SELECT ST_Buffer(ST_Centroid(ST_Extent(the_geom)), SIZE) AS geom
  FROM ways),
bbox AS (
  SELECT ST_Envelope(ST_Extent(geom)) as box FROM buffer)
SELECT gid as id, source, target, cost, reverse_cost
FROM ways where the_geom && (SELECT box from bbox);

Las consultas probadas

SELECT count(*) FROM pgr_floydWarshall(<edge query>)
SELECT count(*) FROM pgr_johnson(<edge query>)

Los resultados de la prueba son:

TAMAÑO:

es el tamaño del cuadro delimitador.

ARISTAS:

es el número de registros en la consulta.

DENSIDAD:

es la densidad de los datos \(\dfrac{E}{V \times (V-1)}\).

REGISTROS DEVUELTOS:

es el número de registros devueltos por las consultas.

Floyd-Warshall:

es el tiempo promedio de ejecución en segundos de pgr_floydWarshall.

Johnson:

es el tiempo promedio de ejecución en segundos de pgr_johnson.

TAMAÑO

ARISTAS

DENSIDAD

REGISTROS DEVUELTOS

Floyd-Warshall

Johnson

0.001

44

0.0608

1197

0.10

0.10

0.002

99

0.0251

4330

0.10

0.10

0.003

223

0.0122

18849

0.12

0.12

0.004

358

0.0085

71834

0.16

0.16

0.005

470

0.0070

116290

0.22

0.19

0.006

639

0.0055

207030

0.37

0.27

0.007

843

0.0043

346930

0.64

0.38

0.008

996

0.0037

469936

0.90

0.49

0.009

1146

0.0032

613135

1.26

0.62

0.010

1360

0.0027

849304

1.87

0.82

0.011

1573

0.0024

1147101

2.65

1.04

0.012

1789

0.0021

1483629

3.72

1.35

0.013

1975

0.0019

1846897

4.86

1.68

0.014

2281

0.0017

2438298

7.08

2.28

0.015

2588

0.0015

3156007

10.28

2.80

0.016

2958

0.0013

4090618

14.67

3.76

0.017

3247

0.0012

4868919

18.12

4.48

Ver también

Índices y tablas