pgRouting 模块实践

简介

pgRouting 扩展了 PostGIS/PostgreSQL 地理空间数据库以提供地理空间路由和其他网络分析功能。

该库包含以下功能:

  • 最短路径算法

  • 双向算法

  • Dijkstra算法的多种应用

  • 距离计算

预备知识

在开始之前,我们会先介绍一下预备的知识,如果你已经对图和图的相关算法有了充足的了解,可以略过此部分。

图的定义

图是由一些点(vertices)边(edges)组成的。可以分为:

  • 无向图

  • 无向简单图

  • 有向图

  • 有向简单图

有些图的理论中还会包含权重这个概念。可以简单的理解为两点之间的距离。

在 pgRouting 中有几种方式可以表示图:

  • 包含权重的:

    (id, source, target, cost)

  • 包含双向权重的

    (id, source, target, cost, reverse_cost)

其中:

标签

含义

id

边的标识符,要求是数据库中的一个数据

source

边起点的标识符

target

边终点的标识符

cost

从起点到终点的权重(当 cost 是负数时,表示这条边并不存在于图中,同时 cost 在一个查询中必须存在)

reverse_cost

从终点到起点的权重(当 reverse_cost 为负数时,表示这条边并不存在于图中)

图示例

  • 有向图(cost)

    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
    

image8

其中 id 为 2 在 cost 为负数,所以在图中没有这个边。

  • 无向图(cost)

    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
    

    image1

与上面的图相比结点 1 和 节点 2 之间的连线时没有指向的。

有向图(cost, reverse_cost)

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

在上面的示例中,id 为 2(1->3) 和 3(3->2) 的两条边就是不存在的,因为costreverse_cost 是负数。

image2

无向图(cost, reverse_cost)

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)

在上面的示例中,id 为 2(1–3) 和 3(3–2) 的边是不存在的,因为 costrevrese_cost 为负数。

image3

不使用 geometry 的图

人际关系,基因,文件依赖等问题都可以通过 pgRouting 来解决,这些问题一般都不需要 geometry 数据。现在我们使用 Wiki 上的一个示例来进行说明:

image4

其中:

  • 找到从结点 1 到结点 5 的最短路径

  • 是一个无向图

  • 有 6 个结点

  • 有 9 条边

  1. 创建一个 pgroutetest 数据库 ,并创建扩展

    CREATE DATABASE pgroutetest;
    -- 连接到 pgroutetest 数据库
    \c pgroutetest
    CREATE EXTENSION pgRouting CASCADE;
    
  2. 创建表,字段如下:

    CREATE TABLE wiki
    (
        id     SERIAL,
        source INTEGER,
        target INTEGER,
        cost   INTEGER
    );
    
  3. 插入数据

    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);
    
  4. 寻找最短路径

    为了解决这个问题我们使用了 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
    

    即最短路径为 1->3->6->5

  5. 查看边的信息

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

使用 Geometry 的图

  1. 创建一个数据库

    createdb sampledata
    psql sampledata -c "CREATE EXTENSION pgrouting CASCADE"
    
  2. 导入数据

    这里我们手动导入数据,当然,你可以使用其他工具来导入数据,例如:

    • shp2pgsql

    • ogr2ogr

    • osm2pgsql

    • osm2pgrouting

    下图是一个整体的图说明:

image7

  1. 在数据库的设计中有一些字段会包含一个 reverse_ 的前缀来表示相反的方向。

    字段

    说明

    id

    唯一标识符

    source

    起始顶点标符

    target

    结束顶点标识符

    cost

    从起点到终点的成本(权重)

    capacity

    从起点到终点的流量

    reverse_cost

    从终点到起点的成本(权重)

    reverse_capacity

    从终点到起点的流量

    x1

    起始点 x 坐标

    y1

    起始点 y 坐标

    x2

    终止点 x 坐标

    y2

    终止点 y 坐标

    geom

    边的 geometry 数据

    创建边的表:

    CREATE TABLE edges
    (
        id               BIGSERIAL PRIMARY KEY,
        source           BIGINT,
        target           BIGINT,
        cost             FLOAT,
        reverse_cost     FLOAT,
        capacity         BIGINT,
        reverse_capacity BIGINT,
        x1               FLOAT,
        y1               FLOAT,
        x2               FLOAT,
        y2               FLOAT,
        geom             geometry
    );
    

    插入数据:

INSERT INTO edges (cost, reverse_cost, capacity, reverse_capacity, geom)
VALUES (1, 1, 80, 130, ST_MakeLine(ST_POINT(2, 0), ST_POINT(2, 1))),
(-1, 1, -1, 100, ST_MakeLine(ST_POINT(2, 1), ST_POINT(3, 1))),
(-1, 1, -1, 130, ST_MakeLine(ST_POINT(3, 1), ST_POINT(4, 1))),
(1, 1, 100, 50, ST_MakeLine(ST_POINT(2, 1), ST_POINT(2, 2))),
(1, -1, 130, -1, ST_MakeLine(ST_POINT(3, 1), ST_POINT(3, 2))),
(1, 1, 50, 100, ST_MakeLine(ST_POINT(0, 2), ST_POINT(1, 2))),
(1, 1, 50, 130, ST_MakeLine(ST_POINT(1, 2), ST_POINT(2, 2))),
(1, 1, 100, 130, ST_MakeLine(ST_POINT(2, 2), ST_POINT(3, 2))),
(1, 1, 130, 80, ST_MakeLine(ST_POINT(3, 2), ST_POINT(4, 2))),
(1, 1, 130, 50, ST_MakeLine(ST_POINT(2, 2), ST_POINT(2, 3))),
(1, -1, 130, -1, ST_MakeLine(ST_POINT(3, 2), ST_POINT(3, 3))),
(1, -1, 100, -1, ST_MakeLine(ST_POINT(2, 3), ST_POINT(3, 3))),
(1, -1, 100, -1, ST_MakeLine(ST_POINT(3, 3), ST_POINT(4, 3))),
(1, 1, 80, 130, ST_MakeLine(ST_POINT(2, 3), ST_POINT(2, 4))),
(1, 1, 80, 50, ST_MakeLine(ST_POINT(4, 2), ST_POINT(4, 3))),
(1, 1, 80, 80, ST_MakeLine(ST_POINT(4, 1), ST_POINT(4, 2))),
(1, 1, 130, 100, ST_MakeLine(ST_POINT(0.5, 3.5), ST_POINT(1.999999999999, 3.5))),
(1, 1, 50, 130, ST_MakeLine(ST_POINT(3.5, 2.3), ST_POINT(3.5, 4)));

在 QGIS 中我们就可以看到插入的数据了

image5

  1. 顶点

    现在我们已经有了边的数据,我们就可以使用 pgr_extractVertices 函数将顶点信息保存在一个数据表中

    SELECT * INTO vertices FROM pgr_extractVertices('SELECT id, geom FROM edges ORDER BY id');
    

    现在,我们查看一下顶点的数据:

    SELECT * FROM vertices;
    
    id | in_edges | out_edges |       x        |  y  |                    geom
    ----+----------+-----------+----------------+-----+--------------------------------------------
     1 |          | {6}       |              0 |   2 | 010100000000000000000000000000000000000040
     2 |          | {17}      |            0.5 | 3.5 | 0101000000000000000000E03F0000000000000C40
     3 | {6}      | {7}       |              1 |   2 | 0101000000000000000000F03F0000000000000040
     4 | {17}     |           | 1.999999999999 | 3.5 | 010100000068EEFFFFFFFFFF3F0000000000000C40
     5 |          | {1}       |              2 |   0 | 010100000000000000000000400000000000000000
     6 | {1}      | {2,4}     |              2 |   1 | 01010000000000000000000040000000000000F03F
     7 | {4,7}    | {8,10}    |              2 |   2 | 010100000000000000000000400000000000000040
     8 | {10}     | {12,14}   |              2 |   3 | 010100000000000000000000400000000000000840
     9 | {14}     |           |              2 |   4 | 010100000000000000000000400000000000001040
    10 | {2}      | {3,5}     |              3 |   1 | 01010000000000000000000840000000000000F03F
    11 | {5,8}    | {9,11}    |              3 |   2 | 010100000000000000000008400000000000000040
    12 | {11,12}  | {13}      |              3 |   3 | 010100000000000000000008400000000000000840
    13 |          | {18}      |            3.5 | 2.3 | 01010000000000000000000C406666666666660240
    14 | {18}     |           |            3.5 |   4 | 01010000000000000000000C400000000000001040
    15 | {3}      | {16}      |              4 |   1 | 01010000000000000000001040000000000000F03F
    16 | {9,16}   | {15}      |              4 |   2 | 010100000000000000000010400000000000000040
    17 | {13,15}  |           |              4 |   3 | 010100000000000000000010400000000000000840
    (17 rows)
    

    在数据我们可以看到 id 为 3 的顶点有进入为 6 的边,出去为 7 的边。

  2. 拓扑

    现在我们就可以设置边表中起始点和终止点的 id。

    /* -- 设置起点信息 */
    UPDATE edges AS e
    SET source = v.id, x1 = x, y1 = y
    FROM vertices AS v
    WHERE ST_StartPoint(e.geom) = v.geom;
    
    /* -- 设置终点信息 */
    UPDATE edges AS e
    SET target = v.id, x2 = x, y2 = y
    FROM vertices AS v
    WHERE ST_EndPoint(e.geom) = v.geom;
    

    查看一下拓扑数据:

    SELECT id, source, target FROM edges ORDER BY id;
    
    id | source | target
    ----+--------+--------
     1 |      5 |      6
     2 |      6 |     10
     3 |     10 |     15
     4 |      6 |      7
     5 |     10 |     11
     6 |      1 |      3
     7 |      3 |      7
     8 |      7 |     11
     9 |     11 |     16
    10 |      7 |      8
    11 |     11 |     12
    12 |      8 |     12
    13 |     12 |     17
    14 |      8 |      9
    15 |     16 |     17
    16 |     15 |     16
    17 |      2 |      4
    18 |     13 |     14
    
    我们可以在 QGIS 中查看当前的点和边:
    image6

    这里我们可以看到 id 为 1 的边的起始点为 5,终止点为 6。

API 说明

API 具体说明可参考官方文档

本文档参考pgRouting官方文档。