`pgr_trspVia` - 拟议¶

pgr_trspVia 穿过有限制的顶点列表的路线。

Warning

下一版本的拟议功能。

它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分：
- 这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
- 名字可能不会改变。（但仍然有可能改变）
- 签名可能不会改变。（但仍然有可能改变）
- 功能可能不会改变。（但仍然有可能改变）
- pgTap 测试已经完成。但可能需要更多。
- 文档可能需要完善。

可用性

版本 3.4.0
- 新提议的函数：
  - pgr_trspVia (One Via)

描述¶

给定一个顶点列表和一个图，这个函数等同于在所有 \(i < size\_of(via\;vertices)\) 的情况下找到从 \(vertex_i\) 到 \(vertex_{i+1}\) 的最短路径，尽量避免使用受限路径。

路径代表路线的各个部分。

通用算法如下：

执行 pgr_dijkstraVia -拟议。
对于通过限制的解决方案的子路径集，则
- 执行对路径有限制的 TRSP 算法。
- 注意，完成此操作后， U_turn_on_edge 标志将被忽略。

签名¶

一次通过¶

pgr_trspVia(Edges SQL, Restrictions SQL, via vertices, [options])

选项： [directed, strict, U_turn_on_edge]

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

OR EMPTY SET

示例:: Find the route that visits the vertices \(\{5, 1, 8\}\) in that order on an directed graph.

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 1, 8]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         5 |       1 |    5 |    1 |    1 |        0 |              0
   2 |       1 |        2 |         5 |       1 |    6 |    4 |    1 |        1 |              1
   3 |       1 |        3 |         5 |       1 |    7 |   10 |    1 |        2 |              2
   4 |       1 |        4 |         5 |       1 |    8 |   12 |    1 |        3 |              3
   5 |       1 |        5 |         5 |       1 |   12 |   13 |    1 |        4 |              4
   6 |       1 |        6 |         5 |       1 |   17 |   15 |    1 |        5 |              5
   7 |       1 |        7 |         5 |       1 |   16 |    9 |    1 |        6 |              6
   8 |       1 |        8 |         5 |       1 |   11 |    8 |    1 |        7 |              7
   9 |       1 |        9 |         5 |       1 |    7 |    7 |    1 |        8 |              8
  10 |       1 |       10 |         5 |       1 |    3 |    6 |    1 |        9 |              9
  11 |       1 |       11 |         5 |       1 |    1 |   -1 |    0 |       10 |             10
  12 |       2 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |             10
  13 |       2 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |             11
  14 |       2 |        3 |         1 |       8 |    7 |   10 |  101 |        2 |             12
  15 |       2 |        4 |         1 |       8 |    8 |   -2 |    0 |      103 |            113
(15 rows)

参数¶

参数	类型	描述
Edges SQL	`TEXT`	Edges SQL 按描述查询。
Restrictions SQL	`TEXT`	Restrictions SQL 按描述查询。
via vertices	`ARRAY[` ANY-INTEGER `]`	将要访问的有序顶点标识符数组。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT

可选参数¶

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

Via可选参数¶

参数	类型	默认	描述
`strict`	`BOOLEAN`	`false`	当为 `true` 时，如果路径丢失，则停止并返回 EMPTY SET 当 `false` 忽略丢失的路径时，返回找到的所有路径
`U_turn_on_edge`	`BOOLEAN`	`true`	为 true 时，从访问过的顶点出发时不会试图避开

内部查询¶

Edges 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

Restrictions SQL¶

列	类型	描述
`path`	`ARRAY` [ANY-INTEGER]	形成不允许采用的路径的边缘标识符序列。 - 空数组或 `NULL` 数组将被忽略。 - 具有 `NULL` 元素的数组将引发异常。
`Cost`	ANY-NUMERICAL	走禁路的成本。

其中：

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

结果列¶

列	类型	描述
`seq`	`INTEGER`	从 1 开始的顺序值。
`path_id`	`INTEGER`	路径的标识符。第一条路径的值为 1。
`path_seq`	`INTEGER`	路径中的相对位置。路径开头的值为 1。
`start_vid`	`BIGINT`	路径起始顶点的标识符。
`end_vid`	`BIGINT`	路径结束顶点的标识符。
`node`	`BIGINT`	从 `start_vid` 到 `end_vid` 路径中节点的标识符。
`edge`	`BIGINT`	用于从路径序列中的 `node` 到下一个节点的边的标识符。 -1，表示路径的最后一个节点。路由的最后一个节点为 -2。
`cost`	`FLOAT`	从使用 `edge` 的 `node` 遍历到路径序列中的下一个节点的成本。
`agg_cost`	`FLOAT`	从 `start_vid` 到 `node` 的总成本。
`route_agg_cost`	`FLOAT`	从 seq = 1 的 `start_vid` 到当前 seq 的 `end_vid` 的总费用。

其他示例¶

所有这些示例都是关于按有向图上的顺序访问顶点 \(\{5, 7, 1, 8, 15\}\) 的路线。

主查询 ¶

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         5 |       7 |    5 |    1 |    1 |        0 |              0
   2 |       1 |        2 |         5 |       7 |    6 |    4 |    1 |        1 |              1
   3 |       1 |        3 |         5 |       7 |    7 |   -1 |    0 |        2 |              2
   4 |       2 |        1 |         7 |       1 |    7 |    7 |    1 |        0 |              2
   5 |       2 |        2 |         7 |       1 |    3 |    6 |    1 |        1 |              3
   6 |       2 |        3 |         7 |       1 |    1 |   -1 |    0 |        2 |              4
   7 |       3 |        1 |         1 |       8 |    1 |    6 |    1 |        0 |              4
   8 |       3 |        2 |         1 |       8 |    3 |    7 |    1 |        1 |              5
   9 |       3 |        3 |         1 |       8 |    7 |   10 |  101 |        2 |              6
  10 |       3 |        4 |         1 |       8 |    8 |   -1 |    0 |      103 |            107
  11 |       4 |        1 |         8 |      15 |    8 |   12 |    1 |        0 |            107
  12 |       4 |        2 |         8 |      15 |   12 |   13 |    1 |        1 |            108
  13 |       4 |        3 |         8 |      15 |   17 |   15 |    1 |        2 |            109
  14 |       4 |        4 |         8 |      15 |   16 |   16 |    1 |        3 |            110
  15 |       4 |        5 |         8 |      15 |   15 |   -2 |    0 |        4 |            111
(15 rows)

第三条路径的总成本。¶

SELECT agg_cost FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
 agg_cost
----------
      103
(1 row)

第三条路径末端的路径总成本。¶

SELECT route_agg_cost FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE path_id = 3 AND edge < 0;
 route_agg_cost
----------------
            107
(1 row)

路由中访问的节点。¶

SELECT row_number() over () as node_seq, node
FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE edge <> -1 ORDER BY seq;
 node_seq | node
----------+------
        1 |    5
        2 |    6
        3 |    7
        4 |    3
        5 |    1
        6 |    3
        7 |    7
        8 |    8
        9 |   12
       10 |   17
       11 |   16
       12 |   15
(12 rows)

到达所访问顶点时的路线总成本。¶

SELECT path_id, route_agg_cost FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE edge < 0;
 path_id | route_agg_cost
---------+----------------
       1 |              2
       2 |              4
       3 |            107
       4 |            111
(4 rows)

节点的 "前方通过 "或 "访问 "状态。¶

SELECT seq, route_agg_cost, node, agg_cost ,
CASE WHEN edge = -1 THEN $$visits$$
ELSE $$passes in front$$
END as status
FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[5, 7, 1, 8, 15])
WHERE agg_cost <> 0 or seq = 1;
 seq | route_agg_cost | node | agg_cost |     status
-----+----------------+------+----------+-----------------
   1 |              0 |    5 |        0 | passes in front
   2 |              1 |    6 |        1 | passes in front
   3 |              2 |    7 |        2 | visits
   5 |              3 |    3 |        1 | passes in front
   6 |              4 |    1 |        2 | visits
   8 |              5 |    3 |        1 | passes in front
   9 |              6 |    7 |        2 | passes in front
  10 |            107 |    8 |      103 | visits
  12 |            108 |   12 |        1 | passes in front
  13 |            109 |   17 |        2 | passes in front
  14 |            110 |   16 |        3 | passes in front
  15 |            111 |   15 |        4 | passes in front
(12 rows)

模拟算法的工作原理。¶

该算法执行 pgr_dijkstraVia -拟议

SELECT * FROM pgr_dijkstraVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  ARRAY[6, 3, 6]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       3 |    7 |    7 |    1 |        1 |              1
   3 |       1 |        3 |         6 |       3 |    3 |   -1 |    0 |        2 |              2
   4 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              2
   5 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              3
   6 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |              4
(6 rows)

检测哪些子路径通过了限制，本例中是针对 path_id = 5 从 6 到 3，因为该路径 \(15 \rightarrow 1\) 受到限制。

执行 pgr_trsp - 拟议针对冲突路径建议的算法。

SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  6, 3);
 path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0
       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1
       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2
       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3
       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4
       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5
       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6
       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7
       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8
(9 rows)

从 pgr_dijkstraVia -拟议提议的结果中，它删除了冲突路径，并使用 pgr_trsp - 拟议提议的算法的结果构建解决方案：

WITH
solutions AS (
  SELECT path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_dijkstraVia(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    ARRAY[6, 3, 6]) WHERE path_id != 1
  UNION
  SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    $$SELECT path, cost FROM restrictions$$,
    6, 3)),
with_seq AS (
  SELECT row_number() over(ORDER BY path_id, path_seq) AS seq, *
  FROM solutions),
aggregation AS (SELECT seq, SUM(cost) OVER(ORDER BY seq) AS route_agg_cost FROM with_seq)
SELECT with_seq.*, COALESCE(route_agg_cost, 0) AS route_agg_cost
FROM with_seq LEFT JOIN aggregation ON (with_seq.seq = aggregation.seq + 1);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1 |              1
   3 |       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2 |              2
   4 |       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3 |              3
   5 |       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4 |              4
   6 |       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5 |              5
   7 |       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6 |              6
   8 |       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7 |              7
   9 |       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8 |              8
  10 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              8
  11 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              9
  12 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |             10
(12 rows)

得到与 pgr_trspVia 相同的结果：

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[6, 3, 6]);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       3 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       3 |    7 |   10 |    1 |        1 |              1
   3 |       1 |        3 |         6 |       3 |    8 |   12 |    1 |        2 |              2
   4 |       1 |        4 |         6 |       3 |   12 |   13 |    1 |        3 |              3
   5 |       1 |        5 |         6 |       3 |   17 |   15 |    1 |        4 |              4
   6 |       1 |        6 |         6 |       3 |   16 |    9 |    1 |        5 |              5
   7 |       1 |        7 |         6 |       3 |   11 |    8 |    1 |        6 |              6
   8 |       1 |        8 |         6 |       3 |    7 |    7 |    1 |        7 |              7
   9 |       1 |        9 |         6 |       3 |    3 |   -1 |    0 |        8 |              8
  10 |       2 |        1 |         3 |       6 |    3 |    7 |    1 |        0 |              8
  11 |       2 |        2 |         3 |       6 |    7 |    4 |    1 |        1 |              9
  12 |       2 |        3 |         3 |       6 |    6 |   -2 |    0 |        2 |             10
(12 rows)

示例 8:: 有时，当设置为 false 时， U_turn_on_edge 标志会被忽略。

第一步，进行 pgr_dijkstraVia -拟议不考虑在同一边上掉头。但路径 \(16 \rightarrow 13\) （第 4 行和第 5 行）受到限制，结果正在使用它。

SELECT * FROM pgr_dijkstraVia(
    $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
    ARRAY[6, 7, 6], U_turn_on_edge => false);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       7 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       7 |    7 |   -1 |    0 |        1 |              1
   3 |       2 |        1 |         7 |       6 |    7 |    8 |    1 |        0 |              1
   4 |       2 |        2 |         7 |       6 |   11 |    9 |    1 |        1 |              2
   5 |       2 |        3 |         7 |       6 |   16 |   16 |    1 |        2 |              3
   6 |       2 |        4 |         7 |       6 |   15 |    3 |    1 |        3 |              4
   7 |       2 |        5 |         7 |       6 |   10 |    2 |    1 |        4 |              5
   8 |       2 |        6 |         7 |       6 |    6 |   -2 |    0 |        5 |              6
(8 rows)

当执行 pgr_trsp - 拟议针对冲突路径的拟议算法时，没有 U_turn_on_edge 标志。

SELECT 1 AS path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost FROM pgr_trsp(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  7, 6);
 path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
---------+----------+-----------+---------+------+------+------+----------
       1 |        1 |         7 |       6 |    7 |    4 |    1 |        0
       1 |        2 |         7 |       6 |    6 |   -1 |    0 |        1
(2 rows)

因此，当设置为 false 时，结果会忽略 U_turn_on_edge 标志。

SELECT * FROM pgr_trspVia(
  $$SELECT id, source, target, cost, reverse_cost FROM edges$$,
  $$SELECT path, cost FROM restrictions$$,
  ARRAY[6, 7, 6], U_turn_on_edge => false);
 seq | path_id | path_seq | start_vid | end_vid | node | edge | cost | agg_cost | route_agg_cost
-----+---------+----------+-----------+---------+------+------+------+----------+----------------
   1 |       1 |        1 |         6 |       7 |    6 |    4 |    1 |        0 |              0
   2 |       1 |        2 |         6 |       7 |    7 |   -1 |    0 |        1 |              1
   3 |       2 |        1 |         7 |       6 |    7 |    4 |    1 |        0 |              1
   4 |       2 |        2 |         7 |       6 |    6 |   -2 |    0 |        1 |              2
(4 rows)

另请参阅¶

Via - 类别
示例数据网络。

索引和表格

pgr_trspVia - 拟议¶

描述¶

签名¶

一次通过¶

参数¶

可选参数¶

Via可选参数¶

内部查询¶

Edges SQL¶

Restrictions SQL¶

结果列¶

其他示例¶

主查询¶

第三条路径的总成本。¶

第三条路径末端的路径总成本。¶

路由中访问的节点。¶

到达所访问顶点时的路线总成本。¶

节点的 "前方通过 "或 "访问 "状态。¶

模拟算法的工作原理。¶

另请参阅¶

`pgr_trspVia` - 拟议¶

主查询 ¶