All Pairs - 函数族¶

以下函数适用于所有顶点对组合

pgr_floydWarshall - Floyd-Warshall 算法。
pgr_johnson - Johnson算法

介绍¶

主要特点是：

它不返回路径。
返回图中每对节点的最短路径成本之和。
仅在具有正成本的边进行处理。
Boost 返回一个 \(V \times V\) 矩阵，其中无穷大值。表示没有路径的顶点之间的距离。
- 我们仅以一组 (start_vid, end_vid, agg_cost) 的形式返回非无穷大值。
假设返回的值存储在表中，因此唯一索引将是一对：(start_vid, end_vid)。
对于无向图，结果是对称的。
- (u, v) 的 agg_cost 与 (v, u) 相同。
当 start_vid = end_vid 时，agg_cost = 0。
建议使用不超过 3500 条边的边界框。

参数¶

参数	类型	默认	描述
Edges SQL	`TEXT`		Edges SQL 如下所述。

可选参数¶

列	类型	默认	描述
`directed`	`BOOLEAN`	`true`	当 `true` 时，该图被视为有有向如果为 `false` ，则该图被视为无向。

内部查询¶

Edges SQL¶

列	类型	默认	描述
`source`	ANY-INTEGER		边的第一个端点顶点的标识符。
`target`	ANY-INTEGER		边的第二个端点顶点的标识符。
`cost`	ANY-NUMERICAL		边(`source`, `target`)的权重
`reverse_cost`	ANY-NUMERICAL	-1	边(`target`, `source`)的权重当为负时：边（ `target`, `source` ）不存在，因此它不是图的一部分。

其中：

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

结果列¶

(start_vid, end_vid, agg_cost) 的集合

列	类型	描述
`start_vid`	`BIGINT`	起始顶点的标识符。
`end_vid`	`BIGINT`	结束顶点的标识符。
`agg_cost`	`FLOAT`	从 `start_vid` 到 `end_vid` 的总成本。

表现¶

以下测试：

非服务式计算机
配备 AMD 64 CPU
4G内存
可靠
postgreSQL 版本 9.3

数据¶

使用了以下数据

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

数据处理是使用 osm2pgrouting-alpha 完成的

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

结果¶

测试:: 一

该测试没有使用边界框，通过的图形密度极低。对于每个 <SIZE> 执行 30 次测试以获得平均值，测试的查询是：

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

该测试的结果如下：

SIZE:: 是作为输入给出的边数。
EDGES:: 是查询中的记录总数。
DENSITY:: 是数据 \(\dfrac{E}{V \times (V-1)}\) 的密度。
OUT ROWS:: 是查询返回的记录数。
Floyd-Warshall:: 是 pgr_floydWarshall 的平均执行时间（以秒为单位）。
Johnson:: 是 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

测试:: 二

该测试带有边界框。通过的图形的密度高于测试一的密度。对于每个 <SIZE> 执行 30 次测试以获得平均值，测试的边缘查询为：

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

测试的查询

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

该测试的结果如下：

SIZE:: 是边界框的大小。
EDGES:: 是查询中的记录总数。
DENSITY:: 是数据 \(\dfrac{E}{V \times (V-1)}\) 的密度。
OUT ROWS:: 是查询返回的记录数。
Floyd-Warshall:: 是 pgr_floydWarshall 的平均执行时间（以秒为单位）。
Johnson:: 是 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

另请参阅¶

索引和表格