All Pairs - Family of Functions

The following functions work on all vertices pair combinations

Introduction

The main characteristics are:

  • It does not return a path.
  • Returns the sum of the costs of the shortest path for each pair of nodes in the graph.
  • Process is done only on edges with positive costs.
  • Boost returns a \(V \times V\) matrix, where the infinity values. Represent the distance between vertices for which there is no path.
    • We return only the non infinity values in form of a set of (start_vid, end_vid, agg_cost).
  • Let be the case the values returned are stored in a table, so the unique index would be the pair: (start_vid, end_vid).
  • For the undirected graph, the results are symmetric.
    • The agg_cost of (u, v) is the same as for (v, u).
  • When start_vid = end_vid, the agg_cost = 0.
  • Recommended, use a bounding box of no more than 3500 edges.

Parameters

Parameter Type Default Description
Edges SQL TEXT   Edges SQL as described below.

Optional parameters

Column Type Default Description
directed BOOLEAN true
  • When true the graph is considered Directed
  • When false the graph is considered as Undirected.

Inner Queries

Edges SQL

Column Type Default Description
source ANY-INTEGER   Identifier of the first end point vertex of the edge.
target ANY-INTEGER   Identifier of the second end point vertex of the edge.
cost ANY-NUMERICAL   Weight of the edge (source, target)
reverse_cost ANY-NUMERICAL -1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

Where:

ANY-INTEGER:SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Result Columns

Set of (start_vid, end_vid, agg_cost)

Column Type Description
start_vid BIGINT Identifier of the starting vertex.
end_vid BIGINT Identifier of the ending vertex.
agg_cost FLOAT Aggregate cost from start_vid to end_vid.

Performance

The following tests:
  • non server computer
  • with AMD 64 CPU
  • 4G memory
  • trusty
  • posgreSQL version 9.3

Data

The following data was used

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

Data processing was done with osm2pgrouting-alpha

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

Results

Test:One

This test is not with a bounding box The density of the passed graph is extremely low. For each <SIZE> 30 tests were executed to get the average The tested query is:

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>');

The results of this tests are presented as:

SIZE:is the number of edges given as input.
EDGES:is the total number of records in the query.
DENSITY:is the density of the data \(\dfrac{E}{V \times (V-1)}\).
OUT ROWS:is the number of records returned by the queries.
Floyd-Warshall:is the average execution time in seconds of pgr_floydWarshall.
Johnson:is the average execution time in seconds of pgr_johnson.
SIZE EDGES DENSITY OUT ROWS 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
Test:Two

This test is with a bounding box The density of the passed graph higher than of the Test One. For each <SIZE> 30 tests were executed to get the average The tested edge query is:

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

The tested queries

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

The results of this tests are presented as:

SIZE:is the size of the bounding box.
EDGES:is the total number of records in the query.
DENSITY:is the density of the data \(\dfrac{E}{V \times (V-1)}\).
OUT ROWS:is the number of records returned by the queries.
Floyd-Warshall:is the average execution time in seconds of pgr_floydWarshall.
Johnson:is the average execution time in seconds of pgr_johnson.
SIZE EDGES DENSITY OUT ROWS 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

See Also

Indices and tables