All Pairs - Family of Functions¶

The following functions work on all vertices pair combinations

pgr_floydWarshall - Floyd-Warshall’s algorithm.
pgr_johnson - Johnson’s algorithm

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