pgRouting 基本概念

这是一个简单的指南，介绍了 pgRouting 入门的一些步骤。 本指南涵盖：

图

图定义

图是一个有序对 \(G = (V ,E)\) ，其中：

  • \(V\) 是一组顶点，也称为节点。

  • \(E \subseteq \{( u, v ) \mid u , v \in V \}\)

有不同类型的图：

  • 无向图

    • \(E \subseteq \{( u, v ) \mid u , v \in V\}\)

  • 无向简单图

    • \(E \subseteq \{( u, v ) \mid u , v \in V, u \neq v\}\)

  • 有向图

    • \(E \subseteq \{( u, v ) \mid (u , v) \in (V X V) \}\)

  • 有向简单图

    • \(E \subseteq \{( u, v ) \mid (u , v) \in (V X V), u \neq v\}\)

图：

  • 没有几何图形。

  • 一些图论问题需要图具有权重，在 pgRouting 中称为 成本 。

在 pgRouting 中，有多种方法来表示数据库上的图：

  • 使用 cost

    • (id, source, target, cost)

  • 使用 cost 和 reverse_cost

    • (id, source, target, cost, reverse_cost)

其中：

列

描述

id

边的标识符。要求在数据库中以一致的方式使用。

source

顶点的标识符。

target

顶点的标识符。

cost

边 (source, target)的权重：

  • 当为负时，图上不存在边(source, target)。

  • 查询中必须存在 cost。

reverse_cost

边(target, source)的权重

  • 当为负时，图上不存在边(target, source)。

图是 有向 图还是 无向 图的决定是在执行 pgRouting 算法时完成的。

成本 图

加权有向图， \(G_d(V,E)\):

  • 通过查询获取图数据

    SELECT id, source, target, cost FROM edges

  • 边集 \(E\)

    • \(E = \{(source_{id}, target_{id}, cost_{id}) \text{ when } cost_{id} \ge 0 \}\)

    • 成本非负的边是图的一部分。

  • 顶点集 \(V\)

    • \(V = \{source_{id} \cup target_{id}\}\)

    • source 和``target`` 中的所有顶点都是图的一部分。

有向图

在有向图中，边 \((source_{id}, target_{id}, cost_{id})\) 具有方向性：\(source_{id} \rightarrow target_{id}\)

对于以下数据：

SELECT *
FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3))
     AS t(id, source, target, cost);
 id | source | target | cost
----+--------+--------+------
  1 |      1 |      2 |    5
  2 |      1 |      3 |   -3
(2 rows)

边 \(2\) (\(1 \rightarrow 3\)) 不是图的一部分。

数据代表下图：

digraph G { 1 -> 2 [label="1(5)"]; 3; }

无向图

在无向图中，边 \((source_{id}, target_{id}, cost_{id})\) 没有方向性：\(source_{id} \frac{\;\;\;\;\;}{} target_{id}\)

  • 在有向图的术语中，这相当于有两条边： \(source_{id} \leftrightarrow target_{id}\)

对于以下数据：

SELECT *
FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3))
     AS t(id, source, target, cost);
 id | source | target | cost
----+--------+--------+------
  1 |      1 |      2 |    5
  2 |      1 |      3 |   -3
(2 rows)

边 \(2\) (\(1 \frac{\;\;\;\;\;}{} 3\)) 不是图的一部分。

数据代表下图：

graph G { 1 -- 2 [label="1(5)"]; 3; }

带有 cost 和``reverse_cost`` 的图

加权有向图， \(G_d(V,E)\)， 定义如下：

  • 通过查询获取图数据

    SELECT id, source, target, cost, reverse_cost FROM edges

  • 边的集合 \(E\)：

    • \(E = \begin{split} \begin{align} & {\{(source_{id}, target_{id}, cost_{id}) \text{ when } cost_{id} >=0 \}} \\ & \cup \\ & {\{(target_{id}, source_{id}, reverse\_cost_{id}) \text{ when } reverse\_cost_{id} >=0 \}} \end{align} \end{split}\)

    • 边 \((source \rightarrow target)\) 中的 cost 是非负数的都属于图的一部分。

    • 边 \((target \rightarrow source)\) 中的 reverse_cost 是非负数的都属于图的一部分。

  • 顶点集 \(V\)：

    • \(V = \{source_{id} \cup target_{id}\}\)

    • source 和``target`` 中的所有顶点都是图的一部分。

有向图

在有向图中，两条边都有方向性

  • 边 \((source_{id}, target_{id}, cost_{id})\) 具有方向性： \(source_{id} \rightarrow target_{id}\)

  • 边 \((target_{id}, source_{id}, reverse\_cost_{id})\) 具有方向性： \(target_{id} \rightarrow source_{id}\)

对于以下数据：

SELECT *
FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1))
     AS t(id, source, target, cost, reverse_cost);
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
  1 |      1 |      2 |    5 |            2
  2 |      1 |      3 |   -3 |            4
  3 |      2 |      3 |    7 |           -1
(3 rows)

边不是图的一部分：

  • \(2\) (\(1\rightarrow 3\))

  • \(3\) (\(3\rightarrow 2\))

数据代表下图：

digraph G { 1 -> 2 [label="1(5)"]; 2 -> 1 [label="1(2)"]; 3 -> 1 [label="2(4)"]; 2 -> 3 [label="3(7)"]; }

无向图

在有向图中，两条边都没有方向性

  • 边 \((source_{id}, target_{id}, cost_{id})\) 是 \(source_{id} \frac{\;\;\;\;\;}{} target_{id}\)

  • 边 \((target_{id}, source_{id}, reverse\_cost_{id})`是 :math:`target_{id} \frac{\;\;\;\;\;}{} source_{id}\)

  • 就有向图而言，就像有四个边：

    • \(source_i \leftrightarrow target_i\)

    • \(target_i \leftrightarrow source_i\)

对于以下数据：

SELECT *
FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1))
     AS t(id, source, target, cost, reverse_cost);
 id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
  1 |      1 |      2 |    5 |            2
  2 |      1 |      3 |   -3 |            4
  3 |      2 |      3 |    7 |           -1
(3 rows)

边不是图的一部分：

  • \(2\) (\(1 \frac{\;\;\;\;\;}{} 3\))

  • \(3\) (\(3 \frac{\;\;\;\;\;}{} 2\))

数据代表下图：

graph G { 1 -- 2 [label="1(5)"]; 2 -- 1 [label="1(2)"]; 3 -- 1 [label="2(4)"]; 2 -- 3 [label="3(7)"]; }

没有几何信息的图

使用 pgRouting 可以解决个人关系、家谱和文件依赖性问题。这些问题通常不会与图形相关的几何图形一起出现。

维基示例

解决来自 维基百科 ）的示例问题 ：

_images/Dijkstra_Animation.gif

其中：

  • 问题是找到从 \(1\) 到 \(5\) 的最短路径。

  • 是一个无向图。

  • 虽然视觉上看起来有几何形状，但该图并不是按比例绘制的。

    • 没有与顶点或边关联的几何图形

  • 有6个顶点 \(\{1,2,3,4,5,6\}\)

  • 有九个边：

    \(\begin{split} \begin{align} E = & \{(1,2,7), (1,3,9), (1,6,14), \\ & (2,3,10), (2,4,13), \\ & (3,4,11), (3,6,2), \\ & (4,5,6), \\ & (5,6,9) \} \end{align} \end{split}\)

  • 该图可以用多种方式表示，例如：

graph G { rankdir="LR"; 1 [color="red"]; 5 [color="green"]; 1 -- 2 [label="(7)"]; 5 -- 6 [label="(9)"]; 1 -- 3 [label="(9)"]; 1 -- 6 [label="(14)"]; 2 -- 3 [label="(10)"]; 2 -- 4 [label="(13)"]; 3 -- 4 [label="(11)"]; 3 -- 6 [label="(2)"]; 4 -- 5 [label="(6)"]; }

准备数据库

为示例创建一个数据库，访问数据库并安装 pgRouting：:

$ createdb wiki
$ psql wiki
wiki =# CREATE EXTENSION pgRouting CASCADE;

创建表

在无向图上执行基本路由所需的基本元素是：

列

类型

描述

id

ANY-INTEGER

边的标识符。

source

ANY-INTEGER

边的第一个端点顶点的标识符。

target

ANY-INTEGER

边的第二个端点顶点的标识符。

cost

ANY-NUMERICAL

边(source, target)的权重

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

本示例使用此表设计：

CREATE TABLE wiki (
  id SERIAL,
  source INTEGER,
  target INTEGER,
  cost INTEGER);
CREATE TABLE

插入数据

INSERT INTO wiki (source, target, cost) VALUES
(1, 2, 7),  (1, 3, 9), (1, 6, 14),
(2, 3, 10), (2, 4, 15),
(3, 6, 2),  (3, 4, 11),
(4, 5, 6),
(5, 6, 9);
INSERT 0 9

寻找最短路径

为了解决这个例子，使用了 pgr_dijkstra`：

SELECT * FROM pgr_dijkstra(
  'SELECT id, source, target, cost FROM wiki',
  1, 5, false);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         1 |       5 |    1 |    2 |    9 |        0
   2 |        2 |         1 |       5 |    3 |    6 |    2 |        9
   3 |        3 |         1 |       5 |    6 |    9 |    9 |       11
   4 |        4 |         1 |       5 |    5 |   -1 |    0 |       20
(4 rows)

从 \(1\) 到 \(5\) 的路径要经过以下顶点： \(1 \rightarrow 3 \rightarrow 6 \rightarrow 5\)

graph G { rankdir="LR"; 1 [color="red"]; 5 [color="green"]; 1 -- 2 [label="(7)"]; 5 -- 6 [label="(9)", color="blue"]; 1 -- 3 [label="(9)", color="blue"]; 1 -- 6 [label="(14)"]; 2 -- 3 [label="(10)"]; 2 -- 4 [label="(13)"]; 3 -- 4 [label="(11)"]; 3 -- 6 [label="(2)", color="blue"]; 4 -- 5 [label="(6)"]; }

顶点信息

要获取顶点信息，请使用 pgr_extractVertices -- 拟议

SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, source, target FROM wiki');
 id | in_edges | out_edges
----+----------+-----------
  3 | {2,4}    | {6,7}
  5 | {8}      | {9}
  4 | {5,7}    | {8}
  2 | {1}      | {4,5}
  1 |          | {1,2,3}
  6 | {3,6,9}  |
(6 rows)

具有几何图形的图

创建路由数据库

第一步是创建数据库并在数据库中加载 pgRouting。

通常为每个项目创建一个数据库。

一旦数据库可以工作，加载数据并在该数据库中构建路由应用程序。

createdb sampledata
psql sampledata -c "CREATE EXTENSION pgrouting CASCADE"

加载数据

有多种方法可以将数据加载到 pgRouting 中。

有多种开源工具可以提供帮助，例如：

shp2pgsql:

  • postgresql shapefile 加载器

ogr2ogr:

  • 矢量数据转换实用程序

osm2pgsql:

  • 将OSM数据加载到postgresql中

请注意，这些工具 不会 导入与 pgRouting 兼容的结构中的数据，当发生这种情况时，需要调整拓扑。

  • 在每个线段-线段交叉点上分解线段

  • 如果缺少，请添加列并为 source, target, cost, reverse_cost 分配值。

  • 连接断开的图。

  • 创建完整的图拓扑

  • 根据要开发的应用程序创建一个或多个图。

    • 为高速道路创建收缩图

    • 创建每个州/国家的图

简而言之：

准备图

准备什么以及如何准备图将取决于应用程序和/或数据质量和/或信息与 pgRouting 可用的拓扑的接近程度和/或未提及的一些其他因素。

准备图的步骤涉及使用`PostGIS <https://postgis.net/>`__ 进行几何操作，其他一些步骤涉及诸如 pgr_contraction 之类的图操作来收缩图。

该 workshop 逐步介绍了如何使用开放街道地图数据为小型应用程序准备图。

数据库设计上索引的使用一般：

  • 对几何图形进行索引。

  • 对标识符列建立索引。

请查阅`PostgreSQL <https://www.postgresql.org/docs/>`__ 文档和 PostGIS 文档。

构建路由拓扑

使用大多数 pgRouting 函数的基本信息``id, source, target, cost, [reverse_cost]`` 在 pgRouting 中被称为路由拓扑。

reverse_cost 是可选的，但强烈建议使用，以便由于几何列的大小而减小数据库的大小。 话虽如此，在本文档中使用了 reverse_cost。

当数据带有几何图形并且没有路由拓扑时，则需要此步骤。

几何图的所有开始和结束顶点都需要一个标识符，该标识符将存储在数据表的``source``列和``target``列中。 同样，cost 和 reverse_cost 需要具有在两个方向上遍历边的值。

如果这些列不存在，则需要将它们添加到相关表中。 （参见`ALTER TABLE <https://www.postgresql.org/docs/current/sql-altertable.html>`__ ）

函数 pgr_extractVertices -- 拟议 用于根据边标识符和图边的几何形状创建顶点表。

最后使用存储在顶点表上的数据填充 source 和``target``。

有关构建拓扑的示例，请参阅 示例数据。

来自 OSM 并使用 osm2pgrouting 作为导入工具的数据附带路由拓扑。 请参阅 workshop 上使用 osm2pgrouting 的示例。

调整成本

对于本示例， cost 和 reverse_cost 值将是几何体长度的两倍。

将成本更新为几何形状的长度

假设样本数据中的 cost 和 reverse_cost 列表示：

  • 当边存在于图中时为 \(1\)

  • 当图中不存在边时为 \(-1\)

使用该信息更新几何形状的长度：

UPDATE edges SET
cost = sign(cost) * ST_length(geom) * 2,
reverse_cost = sign(reverse_cost) * ST_length(geom) * 2;
UPDATE 18

给出以下结果：

SELECT id, cost, reverse_cost FROM edges;
 id |        cost        |    reverse_cost
----+--------------------+--------------------
  6 |                  2 |                  2
  7 |                  2 |                  2
  4 |                  2 |                  2
  5 |                  2 |                 -2
  8 |                  2 |                  2
 12 |                  2 |                 -2
 11 |                  2 |                 -2
 10 |                  2 |                  2
 17 |     2.999999999998 |     2.999999999998
 14 |                  2 |                  2
 18 | 3.4000000000000004 | 3.4000000000000004
 13 |                  2 |                 -2
 15 |                  2 |                  2
 16 |                  2 |                  2
  9 |                  2 |                  2
  3 |                 -2 |                  2
  1 |                  2 |                  2
  2 |                 -2 |                  2
(18 rows)

请注意，为了能够遵循文档示例，一切都基于原始图。

回到原始数据：

UPDATE edges SET
cost = sign(cost),
reverse_cost = sign(reverse_cost);
UPDATE 18

根据代码更新成本

其他数据集可以有一列包含如下值

  • FT 几何方向上的车流

  • TF 车流与几何方向相反

  • B 双向车流

为示例准备代码列：

ALTER TABLE edges ADD COLUMN direction TEXT;
ALTER TABLE
UPDATE edges SET
direction = CASE WHEN (cost>0 AND reverse_cost>0) THEN 'B'   /* both ways */
           WHEN (cost>0 AND reverse_cost<0) THEN 'FT'  /* direction of the LINESSTRING */
           WHEN (cost<0 AND reverse_cost>0) THEN 'TF'  /* reverse direction of the LINESTRING */
           ELSE '' END;
UPDATE 18
/* unknown */

根据代码调整成本：

UPDATE edges SET
cost = CASE WHEN (direction = 'B' OR direction = 'FT')
       THEN ST_length(geom) * 2
       ELSE -1 END,
reverse_cost = CASE WHEN (direction = 'B' OR direction = 'TF')
       THEN ST_length(geom) * 2
       ELSE -1 END;
UPDATE 18

给出以下结果：

SELECT id, cost, reverse_cost FROM edges;
 id |        cost        |    reverse_cost
----+--------------------+--------------------
  6 |                  2 |                  2
  7 |                  2 |                  2
  4 |                  2 |                  2
  5 |                  2 |                 -1
  8 |                  2 |                  2
 12 |                  2 |                 -1
 11 |                  2 |                 -1
 10 |                  2 |                  2
 17 |     2.999999999998 |     2.999999999998
 14 |                  2 |                  2
 18 | 3.4000000000000004 | 3.4000000000000004
 13 |                  2 |                 -1
 15 |                  2 |                  2
 16 |                  2 |                  2
  9 |                  2 |                  2
  3 |                 -1 |                  2
  1 |                  2 |                  2
  2 |                 -1 |                  2
(18 rows)

回到原始数据：

UPDATE edges SET
cost = sign(cost),
reverse_cost = sign(reverse_cost);
UPDATE 18
ALTER TABLE edges DROP COLUMN direction;
ALTER TABLE

检查路由拓扑

图中可能存在很多问题。

  • 使用的数据在设计时可能没有考虑路由。

  • 图有一些非常具体的要求。

  • 该图已断开连接。

  • 存在不需要的交叉点。

  • 图太大，需要收缩。

  • 该应用程序需要一个子图。

  • 以及 pgRouting 用户（即应用程序开发人员）可能遇到的许多其他问题。

交叉边

要获取交叉边：

SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
 id | id
----+----
 13 | 18
(1 row)
_images/crossing_edges.png

这些信息是正确的，例如，就车辆而言，是隧道还是横跨另一条道路的桥梁。

它可能是不正确的，例如：

  1. 当它实际上是道路交叉口时，车辆可以转弯。

  2. 在电力线路方面，电力线能够在隧道或桥梁上甚至切换道路。

当不正确时，需要修复：

  1. 对于车辆和行人

    • 如果数据来自 OSM 并使用 osm2pgrouting 导入到数据库，则需要在 OSM portal 中完成修复并再次导入数据。

    • 一般来说，当数据来自为车辆路线准备数据的供应商时，并且出现问题时，需要从供应商处修复数据

  2. 对于非常具体的应用

    • 从路线车辆或行人的角度来看，数据是正确的。

    • 数据需要针对特定应用程序进行本地修复。

对交叉点进行一一分析后，对于需要局部修复的交叉点，需要 分割 边。

SELECT ST_AsText((ST_Dump(ST_Split(a.geom, b.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18
UNION
SELECT ST_AsText((ST_Dump(ST_Split(b.geom, a.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18;
         st_astext
---------------------------
 LINESTRING(3.5 2.3,3.5 3)
 LINESTRING(3 3,3.5 3)
 LINESTRING(3.5 3,4 3)
 LINESTRING(3.5 3,3.5 4)
(4 rows)

需要将新边添加到边表中，需要更新新边中的其余属性，需要删除旧边并需要更新路由拓扑。

添加分割边

对于每一对交叉边，必须执行与此类似的过程。

插入的列和计算方式取决于应用程序。 例如，如果边具有特征 名称 ，则将复制该列。

用于 pgRouting 计算

  • 基于边相交位置的 因子 可用于调整 cost 和 reverse_cost 列。

  • 分割边时，在 Flow - 函数族 函数中使用的容量信息不需要改变。

WITH
first_edge AS (
  SELECT (ST_Dump(ST_Split(a.geom, b.geom))).path[1],
    (ST_Dump(ST_Split(a.geom, b.geom))).geom,
    ST_LineLocatePoint(a.geom,ST_Intersection(a.geom,b.geom)) AS factor
  FROM edges AS a, edges AS b
  WHERE a.id = 13 AND b.id = 18),
first_segments AS (
  SELECT path, first_edge.geom,
    capacity, reverse_capacity,
    CASE WHEN path=1 THEN factor * cost
         ELSE (1 - factor) * cost END AS cost,
    CASE WHEN path=1 THEN factor * reverse_cost
         ELSE (1 - factor) * reverse_cost END AS reverse_cost
  FROM first_edge , edges WHERE id = 13),
second_edge AS (
  SELECT (ST_Dump(ST_Split(b.geom, a.geom))).path[1],
    (ST_Dump(ST_Split(b.geom, a.geom))).geom,
    ST_LineLocatePoint(b.geom,ST_Intersection(a.geom,b.geom)) AS factor
  FROM edges AS a, edges AS b
  WHERE a.id = 13 AND b.id = 18),
second_segments AS (
  SELECT path, second_edge.geom,
    capacity, reverse_capacity,
    CASE WHEN path=1 THEN factor * cost
         ELSE (1 - factor) * cost END AS cost,
    CASE WHEN path=1 THEN factor * reverse_cost
         ELSE (1 - factor) * reverse_cost END AS reverse_cost
  FROM second_edge , edges WHERE id = 18),
all_segments AS (
  SELECT * FROM first_segments
  UNION
  SELECT * FROM second_segments)
INSERT INTO edges
  (capacity, reverse_capacity,
    cost, reverse_cost,
    x1, y1, x2, y2,
    geom)
(SELECT capacity, reverse_capacity, cost, reverse_cost,
  ST_X(ST_StartPoint(geom)), ST_Y(ST_StartPoint(geom)),
  ST_X(ST_EndPoint(geom)), ST_Y(ST_EndPoint(geom)),
  geom
  FROM all_segments);
INSERT 0 4

添加新的顶点

添加应用程序所需的所有分割边后，需要将新创建的顶点添加到顶点表中。

INSERT INTO vertices (in_edges, out_edges, x, y, geom)
(SELECT nv.in_edges, nv.out_edges, nv.x, nv.y, nv.geom
FROM pgr_extractVertices('SELECT id, geom FROM edges') AS nv
LEFT JOIN vertices AS v USING(geom) WHERE v.geom IS NULL);
INSERT 0 1

更新边拓扑

/* -- set the source information */
UPDATE edges AS e
SET source = v.id
FROM vertices AS v
WHERE source IS NULL AND ST_StartPoint(e.geom) = v.geom;
UPDATE 4
/* -- set the target information */
UPDATE edges AS e
SET target = v.id
FROM vertices AS v
WHERE target IS NULL AND ST_EndPoint(e.geom) = v.geom;
UPDATE 4

去除多余的边

一旦应用程序所需的所有重要信息都已传输到新边，则可以删除交叉边。

DELETE FROM edges WHERE id IN (13, 18);
DELETE 2

还有其他选项可以完成此任务，例如创建视图或物化视图。

更新顶点拓扑

为了保持图的一致性，需要更新顶点拓扑

UPDATE vertices AS v SET
in_edges = nv.in_edges, out_edges = nv.out_edges
FROM (SELECT * FROM pgr_extractVertices('SELECT id, geom FROM edges')) AS nv
WHERE v.geom = nv.geom;
UPDATE 18

检查交叉边

图上没有交叉边。

SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
 id | id
----+----
(0 rows)

断开连接的图

要获取图的连通性：

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | node
-----+-----------+------
   1 |         1 |    1
   2 |         1 |    3
   3 |         1 |    5
   4 |         1 |    6
   5 |         1 |    7
   6 |         1 |    8
   7 |         1 |    9
   8 |         1 |   10
   9 |         1 |   11
  10 |         1 |   12
  11 |         1 |   13
  12 |         1 |   14
  13 |         1 |   15
  14 |         1 |   16
  15 |         1 |   17
  16 |         1 |   18
  17 |         2 |    2
  18 |         2 |    4
(18 rows)

在此示例中，组件 \(2`由顶点 :math:\){2, 4}` 组成，并且两个顶点也是死端结果集的一部分。

这个图需要连接起来。

Note

对于本文档的原始图，将有 3 个组件，因为该图中的交叉边是不同的组件。

为连接信息准备存储

ALTER TABLE vertices ADD COLUMN component BIGINT;
ALTER TABLE
ALTER TABLE edges ADD COLUMN component BIGINT;
ALTER TABLE

保存顶点连接信息

UPDATE vertices SET component = c.component
FROM (SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
)) AS c
WHERE id = node;
UPDATE 18

保存边连接信息

UPDATE edges SET component = v.component
FROM (SELECT id, component FROM vertices) AS v
WHERE source = v.id;
UPDATE 20

获取最近的顶点

使用 pgr_findCloseEdges 距离组件 \(1\) 最近的顶点是顶点 \(4\)。 距离顶点 \(4\) 最近的边是 边 \(14\)。

SELECT edge_id, fraction, ST_AsText(edge) AS edge, id AS closest_vertex
FROM pgr_findCloseEdges(
  $$SELECT id, geom FROM edges WHERE component = 1$$,
  (SELECT array_agg(geom) FROM vertices WHERE component = 2),
  2, partial => false) JOIN vertices USING (geom) ORDER BY distance LIMIT 1;
 edge_id | fraction |                 edge                 | closest_vertex
---------+----------+--------------------------------------+----------------
      14 |      0.5 | LINESTRING(1.999999999999 3.5,2 3.5) |              4
(1 row)

edge``可用于连接组件，利用边 :math:`14` 的``fraction 信息来分割连接边。

连接组件

连接组件有三种基本方法

  • 从顶点到边的起点

  • 从顶点到边的终点

  • 从边上的顶点到最近的顶点

    • 该解决方案需要将边缘分割。

以下查询显示了连接组件的三种方式：

WITH
info AS (
  SELECT
    edge_id, fraction, side, distance, ce.geom, edge, v.id AS closest,
    source, target, capacity, reverse_capacity, e.geom AS e_geom
  FROM pgr_findCloseEdges(
    $$SELECT id, geom FROM edges WHERE component = 1$$,
    (SELECT array_agg(geom) FROM vertices WHERE component = 2),
    2, partial => false) AS ce
  JOIN vertices AS v USING (geom)
  JOIN edges AS e ON (edge_id = e.id)
  ORDER BY distance LIMIT 1),
three_options AS (
  SELECT
    closest AS source, target, 0 AS cost, 0 AS reverse_cost,
    capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_EndPoint(e_geom)) AS x2, ST_Y(ST_EndPoint(e_geom)) AS y2,
    ST_MakeLine(geom, ST_EndPoint(e_geom)) AS geom
  FROM info
  UNION
  SELECT closest, source, 0, 0, capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_StartPoint(e_geom)) AS x2, ST_Y(ST_StartPoint(e_geom)) AS y2,
    ST_MakeLine(info.geom, ST_StartPoint(e_geom))
  FROM info
  /*
  UNION
  -- This option requires splitting the edge
  SELECT closest, NULL, 0, 0, capacity, reverse_capacity,
    ST_X(geom) AS x1, ST_Y(geom) AS y1,
    ST_X(ST_EndPoint(edge)) AS x2, ST_Y(ST_EndPoint(edge)) AS y2,
    edge
  FROM info */
  )
INSERT INTO edges
  (source, target,
    cost, reverse_cost,
    capacity, reverse_capacity,
    x1, y1, x2, y2,
    geom)
(SELECT
    source, target, cost, reverse_cost, capacity, reverse_capacity,
    x1, y1, x2, y2, geom
  FROM three_options);
INSERT 0 2

检查组件

忽略需要进一步工作的边缘。 该图现在已完全连接，因为只有一个组件。

SELECT * FROM pgr_connectedComponents(
  'SELECT id, source, target, cost, reverse_cost FROM edges'
);
 seq | component | node
-----+-----------+------
   1 |         1 |    1
   2 |         1 |    2
   3 |         1 |    3
   4 |         1 |    4
   5 |         1 |    5
   6 |         1 |    6
   7 |         1 |    7
   8 |         1 |    8
   9 |         1 |    9
  10 |         1 |   10
  11 |         1 |   11
  12 |         1 |   12
  13 |         1 |   13
  14 |         1 |   14
  15 |         1 |   15
  16 |         1 |   16
  17 |         1 |   17
  18 |         1 |   18
(18 rows)

图的收缩

可以使用 收缩 - 函数族 来减小图形的大小

何时收缩将取决于图的大小、处理时间、数据的正确性、最终应用程序或任何其他未提及的因素。

确定收缩是否有用的一个相当好的方法是根据死端的数量和/或线性边的数量。

有关如何收缩以及如何使用收缩图的完整方法在 收缩 - 函数族 中进行了描述

死端

获取死端：

SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 1;
 id
----
  1
  5
  9
 13
 14
  2
  4
(7 rows)

例如，当死端位于导入图的极限时，该信息是正确的。

从视觉上看，节点 \(4\) 看起来是 3 条边的开始/结束，但事实并非如此。

那是对的吗？

  • 有这么小的路边吗：

    • 这不允许车辆使用该视觉交叉路口？

    • 是否适用于行人，因此行人可以轻松地在小路边行走？

    • 电力和电线的应用是否可以轻松地延伸到小路边顶部？

  • 是否有一个大悬崖，从鹰的角度看，死胡同靠近该路段？

当有很多死端时，为了加快速度，可以使用 收缩 - 函数族 函数来划分问题。

线性边

要获得线性边：

SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 2;
 id
----
  3
 15
 17
(3 rows)

例如，当应用程序考虑减速带、停止信号时，此信息是正确的。

当线性边较多时，为了加快速度，可以使用 收缩 - 函数族 函数来划分问题。

函数的结构

完成上述图准备工作后，就可以使用

pgRouting 函数调用的一般形式是：

pgr_<name>(Inner queries , parameters, [Optional parameters)

其中：

  • Inner queries ：是强制参数，是包含 SQL 查询的 TEXT 字符串。

  • parameters：函数需要的附加强制参数。

  • Optional parameters ：是非强制命名参数，省略时具有默认值。

强制参数是位置参数，可选参数是命名参数。

例如，对于这个 pgr_dijkstra` 签名：

pgr_dijkstra(Edges SQL, start vids, end vids, [directed])

  • Edges SQL:

    • 是第一个参数。

    • 这是强制性的。

    • 这是一个内部查询。

    • 它没有名称，因此 Edges SQL 给出了需要使用哪种内部查询的想法

  • start vid:

    • 是第二个参数。

    • 这是强制性的。

    • 它没有名称，因此 start vid 给出了第二个参数的值应包含的内容。

  • end vid

    • 是第三个参数。

    • 这是强制性的。

    • 它没有名称，因此 end vid 给出了第三个参数的值应包含的内容

  • directed

    • 是第四个参数。

    • 是可选的。

    • 它有一个名字。

参数的完整描述可以在每个函数的 Parameters 部分找到。

函数的重载

一个函数可能有不同的重载。 最常见的是：

根据过载，参数类型会发生变化。

  • 一: ANY-INTEGER

  • 多: ARRAY [ANY-INTEGER]

根据函数的不同，重载可能会有所不同。 但参数类型改变的概念保持不变。

一对一

当路由来自：

  • 从 一 起始顶点

  • 到 一 结束顶点

一对多

当路由来自：

  • 从 一 起始顶点

  • 到 多 结束顶点

多对一

当路由来自：

  • 从 多 起始顶点

  • 到 一 结束顶点

多对多

当路由来自：

  • 从 多 起始顶点

  • 到 多 结束顶点

组合

当路由来自：

  • 从 多个 不同的起始顶点

  • 到 多个 不同的结束顶点

  • 每个元组指定一对起始顶点和结束顶点

  • 用户可以根据需要定义组合。

  • 需要 Combinations SQL

内部查询

There are several kinds of valid inner queries and also the columns returned are depending of the function. Which kind of inner query will depend on the function's requirements. To simplify the variety of types, ANY-INTEGER and ANY-NUMERICAL is used.

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Edges SQL

常规

边 SQL

列

类型

默认

描述

id

ANY-INTEGER

边的标识符。

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

一般没有 id

边 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

通常带有（X,Y)

边 SQL

参数

类型

默认

描述

id

ANY-INTEGER

边的标识符。

source

ANY-INTEGER

边的第一个端点顶点的标识符。

target

ANY-INTEGER

边的第二个端点顶点的标识符。

cost

ANY-NUMERICAL

边(source, target)的权重

  • 当为负时：边（source, target）不存在，因此它不是图的一部分。

reverse_cost

ANY-NUMERICAL

-1

边 (target, source)的权重，

  • 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

x1

ANY-NUMERICAL

source 顶点的X坐标。

y1

ANY-NUMERICAL

source 顶点的Y坐标。

x2

ANY-NUMERICAL

target 顶点的X坐标。

y2

ANY-NUMERICAL

target 顶点的Y坐标。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

流

用于流数据系列 ( Flow - 函数族) 的Edges SQL

边 SQL

列

类型

默认

描述

id

ANY-INTEGER

边的标识符。

source

ANY-INTEGER

边的第一个端点顶点的标识符。

target

ANY-INTEGER

边的第二个端点顶点的标识符。

capacity

ANY-INTEGER

边(source, target)的权重

reverse_capacity

ANY-INTEGER

-1

边(target, source)的权重

  • 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Edges SQL 适用于 Flow - 函数族 的以下函数

列

类型

默认

描述

id

ANY-INTEGER

边的标识符。

source

ANY-INTEGER

边的第一个端点顶点的标识符。

target

ANY-INTEGER

边的第二个端点顶点的标识符。

capacity

ANY-INTEGER

边 (source, target)的容量

  • 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

reverse_capacity

ANY-INTEGER

-1

边 (target, source)的容量

  • 当为负时：边（ target, source ）不存在，因此它不是图的一部分。

cost

ANY-NUMERICAL

边 (source, target)的权重（如果存在）

reverse_cost

ANY-NUMERICAL

\(-1\)

边(target, source)的权重（如果存在）

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

分量 SQL

结合签名使用

参数

类型

描述

source

ANY-INTEGER

出发顶点的标识符。

target

ANY-INTEGER

到达顶点的标识符。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

Restrictions SQL

列

类型

描述

path

ARRAY [ANY-INTEGER]

形成不允许采用的路径的边缘标识符序列。 - 空数组或 NULL 数组将被忽略。 - 具有 NULL 元素的数组将引发异常。

Cost

ANY-NUMERICAL

走禁路的成本。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Points SQL

用于Points SQL

参数

类型

默认

描述

pid

ANY-INTEGER

value

点的标识符。

  • 使用正值，因为内部将转换为负值

  • 如果列存在，则它不能为 NULL。

  • 如果列不存在，将自动给出连续的负 值 。

edge_id

ANY-INTEGER

距离该点“最近”的边的标识符。

fraction

ANY-NUMERICAL

<0,1> 中的值指示距边缘第一个端点的相对位置。

side

CHAR

b

[b, r, l, NULL] 中的值指示该点是否为：

  • r 在右边，

  • l 在左边，

  • b, NULL 在两边

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

参数

大多数 pgRouting 函数的主要参数是选择图的边的查询。

参数

类型

描述

Edges SQL

TEXT

Edges SQL 如下所述。

根据函数的族或类别，它将具有附加参数，其中一些是强制性的，一些是可选的。

强制参数是无名的，并且必须按要求的顺序给出。 可选参数是命名参数，并且具有默认值。

Via 函数的参数

参数

类型

默认

描述

Edges SQL

TEXT

如所述的 SQL 查询。

via vertices

ARRAY [ANY-INTEGER]

将要访问的有序顶点标识符数组。

directed

BOOLEAN

true

  • 当为 true 时，图被视为`有向`图

  • 当为 false 时，图被视为无向图。

strict

BOOLEAN

false

  • 当为 true 时，如果路径丢失，则停止并返回 EMPTY SET

  • 当 false 忽略丢失的路径时，返回找到的所有路径

U_turn_on_edge

BOOLEAN

true

  • 当 为 true 时，从已访问的顶点出发，不会试图避免使用用于到达它的边。换句话说，允许使用具有相同标识符的边来进行掉头。

  • 当为 false 时，从已访问的顶点出发，尝试避免使用用于到达它的边。换句话说，只有在找不到其他路径时才使用具有相同标识符的边来进行掉头。

对于 TRSP 函数

列

类型

描述

Edges SQL

TEXT

如所述的 SQL 查询。

Restrictions SQL

TEXT

如所述的 SQL 查询。

Combinations SQL

TEXT

Combinations SQL 如下所述

start vid

ANY-INTEGER

出发顶点的标识符。

start vids

ARRAY [ANY-INTEGER]

目标顶点的标识符数组。

end vid

ANY-INTEGER

出发顶点的标识符。

end vids

ARRAY [ANY-INTEGER]

目标顶点的标识符数组。

其中：

ANY-INTEGER:

SMALLINT, INTEGER, BIGINT

结果列

根据函数的不同，返回的列有多种。

路径的结果列

在返回一个路径解的函数中使用

返回 (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) 的集合

列

类型

描述

seq

INTEGER

从 1 开始的顺序值。

path_seq

INTEGER

路径中的相对位置。 路径开头的值为 1。

start_vid

BIGINT

起始顶点的标识符。 当查询中有多个起始向量时返回。

end_vid

BIGINT

结束顶点的标识符。 当查询中有多个结束顶点时返回。

node

BIGINT

从 start_vid 到 end_vid 路径中节点的标识符。

edge

BIGINT

用于从路径序列中的 node 到下一个节点的边的标识符。 -1 表示路径的最后一个节点。

cost

FLOAT

从使用 edge 的 node 遍历到路径序列中的下一个节点的成本。

agg_cost

FLOAT

从 start_vid 到 node 的总成本。

用于以下函数：

返回 (seq, path_seq [, start_pid] [, end_pid], node, edge, cost, agg_cost) 的集合

列

类型

描述

seq

INTEGER

从 1 开始的顺序值。

path_seq

INTEGER

路径中的相对位置。

  • 1 对于路径的第一行。

start_pid

BIGINT

路径起始顶点/点的标识符。

  • 当正数时是起始顶点的标识符。

  • 当负数时是起点的标识符。

  • 多对一 和 多对多 的返回值

end_pid

BIGINT

路径结束顶点/点的标识符。

  • 当正数时是结束顶点的标识符。

  • 当负数时是终点的标识符。

  • 返回 一对多 和 多对多

node

BIGINT

从 start_pid 到 end_pid 路径中节点的标识符。

  • 当正数时是顶点的标识符。

  • 当负数时是a点的标识符。

edge

BIGINT

用于从路径序列中的 node 到下一个节点的边的标识符。

  • -1 表示路径的最后一行。

cost

FLOAT

从使用 edge 的 node 遍历到路径序列中的下一个节点的成本。

  • 0 表示路径的第一行。

agg_cost

FLOAT

从 start_vid 到 node 的总成本。

  • 0 表示路径的第一行。

用于以下函数：

返回 (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

列

类型

描述

seq

INTEGER

从 1 开始的顺序值。

path_seq

INTEGER

路径中的相对位置。 路径开头的值为 1。

start_vid

BIGINT

当前路径起始顶点的标识符。

end_vid

BIGINT

当前路径结束顶点的标识符。

node

BIGINT

从 start_vid 到 end_vid 路径中节点的标识符。

edge

BIGINT

用于从路径序列中的 node 到下一个节点的边的标识符。 -1 表示路径的最后一个节点。

cost

FLOAT

从使用 edge 的 node 遍历到路径序列中的下一个节点的成本。

agg_cost

FLOAT

从 start_vid 到 node 的总成本。

多条路径

多路径选择性。

这些列取决于函数调用。

(seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) 集合

列

类型

描述

seq

INTEGER

从 1 开始的顺序值。

path_id

INTEGER

路径标识符。

  • 从 start_vid 到 end_vid 的第一个路径的值为 1 。

path_seq

INTEGER

路径中的相对位置。 路径开头的值为 1。

start_vid

BIGINT

起始顶点的标识符。 当查询中有多个起始向量时返回。

end_vid

BIGINT

结束顶点的标识符。 当查询中有多个结束顶点时返回。

node

BIGINT

从 start_vid 到 end_vid 路径中节点的标识符。

edge

BIGINT

用于从路径序列中的 node 到下一个节点的边的标识符。 -1 表示路径的最后一个节点。

cost

FLOAT

从使用 edge 的 node 遍历到路径序列中的下一个节点的成本。

agg_cost

FLOAT

从 start_vid 到 node 的总成本。

多路径非选择性

无论调用如何，都会返回所有列。

返回集合``(seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)``

列

类型

描述

seq

INTEGER

从 1 开始的顺序值。

path_id

INTEGER

路径标识符。

  • 从 start_vid 到 end_vid 的第一个路径的值为 1 。

path_seq

INTEGER

路径中的相对位置。 路径开头的值为 1。

start_vid

BIGINT

起始顶点的标识符。

end_vid

BIGINT

结束顶点的标识符。

node

BIGINT

从 start_vid 到 end_vid 路径中节点的标识符。

edge

BIGINT

用于从路径序列中的 node 到下一个节点的边的标识符。 -1 表示路径的最后一个节点。

cost

FLOAT

从使用 edge 的 node 遍历到路径序列中的下一个节点的成本。

agg_cost

FLOAT

从 start_vid 到 node 的总成本。

成本函数结果列

用于以下函数

(start_vid, end_vid, agg_cost) 的集合

列

类型

描述

start_vid

BIGINT

起始顶点的标识符。

end_vid

BIGINT

结束顶点的标识符。

agg_cost

FLOAT

从 start_vid 到 end_vid 的总成本。

Note

当 start_vid 或 end_vid 列具有负值时，标识符用于点。

流量函数的结果列

Edges SQL 适用于以下内容

列

类型

描述

seq

INT

从 1 开始的顺序值。

edge

BIGINT

原始查询中边的标识符 (edges_sql)。

start_vid

BIGINT

边的第一个端点顶点的标识符。

end_vid

BIGINT

边的第二个端点顶点的标识符。

flow

BIGINT

沿 (start_vid, end_vid)方向流经边缘。

residual_capacity

BIGINT

(start_vid, end_vid)方向上边缘的剩余容量。

Edges SQL 适用于 Flow - 函数族 的以下函数

列

类型

描述

seq

INT

从 1 开始的顺序值。

edge

BIGINT

原始查询中边的标识符 (edges_sql)。

source

BIGINT

边的第一个端点顶点的标识符。

target

BIGINT

边的第二个端点顶点的标识符。

flow

BIGINT

沿方向 (source, target)流经边缘。

residual_capacity

BIGINT

方向 (source, target)上边缘的剩余容量。

cost

FLOAT

在方向 (source, target)上通过边缘发送此流的成本。

agg_cost

FLOAT

总成本。

生成树函数的结果列

Edges SQL 适用于以下内容

返回集合 (edge, cost)

列

类型

描述

edge

BIGINT

边的标识符。

cost

FLOAT

穿越边的成本。

性能技巧

对于路由功能

为了获得更快的结果，将查询绑定到路由感兴趣的区域。

在此示例中，使用内部查询 SQL，该 SQL 不包括路由函数中的某些边并且位于结果区域内。

SELECT * FROM pgr_dijkstra($$
  SELECT id, source, target, cost, reverse_cost from edges
  WHERE geom && (SELECT st_buffer(geom, 1) AS myarea
    FROM edges WHERE id = 2)$$,
  1, 2);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)

如何贡献

维基

向 pgRouting 添加功能

查阅`开发者文档 <https://docs.pgrouting.org/doxy/2.4/index.html>`__

索引和表格