pgr_lineGraphFull - 实验¶
pgr_lineGraphFull —将给定图转换为新图，其中原始图的所有顶点都转换为线图。
Warning
可能服务器崩溃
这些功能可能会导致服务器崩溃
Warning
实验功能
它们不是当前版本的正式版本。
它们可能不会正式成为下一个版本的一部分：
这些函数可能不使用 ANY-INTEGER 和 ANY-NUMERICAL
名称可能会改变。
签名可能会改变。
功能可能会改变。
pgTap 测试可能丢失。
可能需要 c/c++编码。
可能缺乏文档。
文档（如果有）可能需要重写。
可能需要自动生成文档示例。
可能需要社区的大量反馈。
可能取决于 pgRouting 的拟议功能
可能依赖于 pgRouting 的已弃用函数
可用性
版本2.6.0
新的 实验 函数
描述¶
pgr_lineGraphFull, 通过将每个顶点转换为完全图并保留所有原始边，将原始有向图转换为有向线图。 新的连接边的成本为 0，并位于相邻的原始边之间，尊重方向性。
结果图的一个可能的应用是 "具有两个边限制的路由"：
设置在连接边上的边之间布线时使用顶点的成本
通过删除连接边来禁止两条边之间的布线
这是可能的，因为原始图中的每个交叉点（顶点）现在都是完整的图，对于穿过该交叉点的每个可能的转弯都有一条新边。
主要特点是：
该函数适用于 有向 图。
当输入图中使用负顶点 id 时，结果是不确定的。
当输入图中使用重复的边 id 时，结果是不确定的。
运行时间：TBD（待定）
签名¶
总结
pgr_lineGraphFull(Edges SQL)
返回
(seq, source, target, cost, edge) 的集合OR EMPTY SET
- 示例:
边 \(\{4, 7, 8, 10\}\) 子图的全线图
SELECT * FROM pgr_lineGraphFull(
$$SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE id IN (4, 7, 8, 10)$$);
seq | source | target | cost | edge
-----+--------+--------+------+------
1 | -1 | 7 | 1 | 4
2 | 6 | -1 | 0 | 0
3 | -2 | 6 | 1 | -4
4 | -3 | 3 | 1 | -7
5 | -4 | 11 | 1 | 8
6 | -5 | 8 | 1 | 10
7 | 7 | -2 | 0 | 0
8 | 7 | -3 | 0 | 0
9 | 7 | -4 | 0 | 0
10 | 7 | -5 | 0 | 0
11 | -6 | -2 | 0 | 0
12 | -6 | -3 | 0 | 0
13 | -6 | -4 | 0 | 0
14 | -6 | -5 | 0 | 0
15 | -7 | -2 | 0 | 0
16 | -7 | -3 | 0 | 0
17 | -7 | -4 | 0 | 0
18 | -7 | -5 | 0 | 0
19 | -8 | -2 | 0 | 0
20 | -8 | -3 | 0 | 0
21 | -8 | -4 | 0 | 0
22 | -8 | -5 | 0 | 0
23 | -9 | -6 | 1 | 7
24 | 3 | -9 | 0 | 0
25 | -10 | -7 | 1 | -8
26 | 11 | -10 | 0 | 0
27 | -11 | -8 | 1 | -10
28 | 8 | -11 | 0 | 0
(28 rows)
参数¶
参数 |
类型 |
描述 |
|---|---|---|
|
Edges SQL 如下所述。 |
内部查询¶
Edges SQL¶
列 |
类型 |
默认 |
描述 |
|---|---|---|---|
|
ANY-INTEGER |
边的标识符。 |
|
|
ANY-INTEGER |
边的第一个端点顶点的标识符。 |
|
|
ANY-INTEGER |
边的第二个端点顶点的标识符。 |
|
|
ANY-NUMERICAL |
边( |
|
|
ANY-NUMERICAL |
-1 |
边(
|
其中：
- ANY-INTEGER:
SMALLINT,INTEGER,BIGINT- ANY-NUMERICAL:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
结果列¶
返回 (seq, source, target, cost, edge) 的集合
列 |
类型 |
描述 |
|---|---|---|
|
|
从 1 开始的顺序值。
|
|
|
当前边的源顶点的标识符。
|
|
|
当前边的目标顶点的标识符。
|
|
|
边 (
|
|
|
边 (
|
其他示例¶
本节的示例基于 示例数据 网络。 这些示例包括包含具有 reverse_cost 的边 4、7、8 和 10 的子图。
数据¶
此示例显示此图形转换如何为图形中的每个可能的转弯创建附加边。
SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE id IN (4, 7, 8, 10);
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
4 | 6 | 7 | 1 | 1
7 | 3 | 7 | 1 | 1
8 | 7 | 11 | 1 | 1
10 | 7 | 8 | 1 | 1
(4 rows)
转变¶
SELECT * FROM pgr_lineGraphFull(
$$SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE id IN (4, 7, 8, 10)$$);
seq | source | target | cost | edge
-----+--------+--------+------+------
1 | -1 | 7 | 1 | 4
2 | 6 | -1 | 0 | 0
3 | -2 | 6 | 1 | -4
4 | -3 | 3 | 1 | -7
5 | -4 | 11 | 1 | 8
6 | -5 | 8 | 1 | 10
7 | 7 | -2 | 0 | 0
8 | 7 | -3 | 0 | 0
9 | 7 | -4 | 0 | 0
10 | 7 | -5 | 0 | 0
11 | -6 | -2 | 0 | 0
12 | -6 | -3 | 0 | 0
13 | -6 | -4 | 0 | 0
14 | -6 | -5 | 0 | 0
15 | -7 | -2 | 0 | 0
16 | -7 | -3 | 0 | 0
17 | -7 | -4 | 0 | 0
18 | -7 | -5 | 0 | 0
19 | -8 | -2 | 0 | 0
20 | -8 | -3 | 0 | 0
21 | -8 | -4 | 0 | 0
22 | -8 | -5 | 0 | 0
23 | -9 | -6 | 1 | 7
24 | 3 | -9 | 0 | 0
25 | -10 | -7 | 1 | -8
26 | 11 | -10 | 0 | 0
27 | -11 | -8 | 1 | -10
28 | 8 | -11 | 0 | 0
(28 rows)
在转换后的图中，原始图中的所有边仍然存在（黄色），但现在我们为跨顶点 7 的每个转弯提供了额外的边（橙色）。
创建标识变换顶点的表¶
变换后的图中的每个顶点都是通过分割原始图中的顶点而创建的。 除非原始图中的某个顶点是叶顶点，否则它将在变换后的图中生成多个顶点。 转换后的图中新创建的顶点之一将被赋予与原始图中创建它的顶点相同的顶点标识符，但新创建的其余顶点将具有负顶点 id。
以下是如何生成一个表的示例，该表将新创建的顶点的 id 与创建它们的原始顶点进行映射
存储边结果¶
第一步是将 pgr_lineGraphFull 调用的结果存储到表中
SELECT seq AS id, source, target, cost, edge
INTO lineGraph_edges
FROM pgr_lineGraphFull(
$$SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE id IN (4, 7, 8, 10)$$);
SELECT 28
创建映射表¶
从原始图的顶点信息
SELECT id, NULL::BIGINT original_id
INTO vertex_map
FROM vertices;
SELECT 17
增加新的顶点
INSERT INTO vertex_map (id)
(SELECT id
FROM pgr_extractVertices(
$$SELECT id, source, target FROM lineGraph_edges$$) WHERE id < 0);
INSERT 0 11
填写映射表¶
正的顶点标识符是原始标识符
UPDATE vertex_map
SET original_id = id
WHERE id > 0;
UPDATE 17
检查顶点图
SELECT *
FROM vertex_map ORDER BY id DESC;
id | original_id
-----+-------------
17 | 17
16 | 16
15 | 15
14 | 14
13 | 13
12 | 12
11 | 11
10 | 10
9 | 9
8 | 8
7 | 7
6 | 6
5 | 5
4 | 4
3 | 3
2 | 2
1 | 1
-1 |
-2 |
-3 |
-4 |
-5 |
-6 |
-7 |
-8 |
-9 |
-10 |
-11 |
(28 rows)
当没有成本到达目标并且源具有原始值时，就会发生自循环。
SELECT *, source AS targets_original_id
FROM lineGraph_edges
WHERE cost = 0 and source > 0;
id | source | target | cost | edge | targets_original_id
----+--------+--------+------+------+---------------------
2 | 6 | -1 | 0 | 0 | 6
7 | 7 | -2 | 0 | 0 | 7
8 | 7 | -3 | 0 | 0 | 7
9 | 7 | -4 | 0 | 0 | 7
10 | 7 | -5 | 0 | 0 | 7
24 | 3 | -9 | 0 | 0 | 3
26 | 11 | -10 | 0 | 0 | 11
28 | 8 | -11 | 0 | 0 | 8
(8 rows)
从自循环更新值
WITH
self_loops AS (
SELECT DISTINCT source, target, source AS targets_original_id
FROM lineGraph_edges
WHERE cost = 0 and source > 0)
UPDATE vertex_map SET original_id = targets_original_id
FROM self_loops WHERE target = id;
UPDATE 8
检查顶点表
SELECT *
FROM vertex_map WHERE id < 0
ORDER BY id DESC;
id | original_id
-----+-------------
-1 | 6
-2 | 7
-3 | 7
-4 | 7
-5 | 7
-6 |
-7 |
-8 |
-9 | 3
-10 | 11
-11 | 8
(11 rows)
从内部自我循环更新
WITH
assigned_vertices
AS (SELECT id, original_id
FROM vertex_map
WHERE original_id IS NOT NULL),
cross_edges
AS (SELECT DISTINCT e.source, v.original_id AS source_original_id
FROM lineGraph_edges AS e
JOIN vertex_map AS v ON (e.target = v.id)
WHERE source NOT IN (SELECT id FROM assigned_vertices)
)
UPDATE vertex_map SET original_id = source_original_id
FROM cross_edges WHERE source = id;
UPDATE 3
检查顶点图
SELECT *
FROM vertex_map WHERE id < 0
ORDER BY id DESC;
id | original_id
-----+-------------
-1 | 6
-2 | 7
-3 | 7
-4 | 7
-5 | 7
-6 | 7
-7 | 7
-8 | 7
-9 | 3
-10 | 11
-11 | 8
(11 rows)
添加软限制¶
需要使用边 4 -> 7 从顶点 6 到顶点 3 的软限制。
识别限制¶
运行 pgr_dijkstraNear - 拟议 时，成本将会增加的地方是边 8，其成本为 0
SELECT seq, path_seq, start_vid, end_vid, node, original_id, edge, cost, agg_cost
FROM (SELECT * FROM pgr_dijkstraNear(
$$SELECT * FROM lineGraph_edges$$,
(SELECT array_agg(id) FROM vertex_map where original_id = 6),
(SELECT array_agg(id) FROM vertex_map where original_id = 3))) dn
JOIN vertex_map AS v1 ON (node = v1.id);
seq | path_seq | start_vid | end_vid | node | original_id | edge | cost | agg_cost
-----+----------+-----------+---------+------+-------------+------+------+----------
3 | 3 | -1 | 3 | -3 | 7 | 4 | 1 | 1
1 | 1 | -1 | 3 | -1 | 6 | 1 | 1 | 0
4 | 4 | -1 | 3 | 3 | 3 | -1 | 0 | 2
2 | 2 | -1 | 3 | 7 | 7 | 8 | 0 | 1
(4 rows)
要更改的边是上一个查询中的 WHERE cost = 0 AND seq != 1 AND edge != -1 ：
SELECT edge FROM pgr_dijkstraNear(
$$SELECT * FROM lineGraph_edges$$,
(SELECT array_agg(id) FROM vertex_map where original_id = 6),
(SELECT array_agg(id) FROM vertex_map where original_id = 3))
WHERE cost = 0 AND seq != 1 AND edge != -1;
edge
------
8
(1 row)
向限制添加值¶
将成本更新到边：
UPDATE lineGraph_edges
SET cost = 100
WHERE id IN (
SELECT edge FROM pgr_dijkstraNear(
$$SELECT * FROM lineGraph_edges$$,
(SELECT array_agg(id) FROM vertex_map where original_id = 6),
(SELECT array_agg(id) FROM vertex_map where original_id = 3))
WHERE cost = 0 AND seq != 1 AND edge != -1);
UPDATE 1
- 示例:
路由从 \(6\) 到 \(3\)
现在，该路线不使用边 8，而是在叶顶点上进行 U 形转弯。
WITH
results AS (
SELECT * FROM pgr_dijkstraNear(
$$SELECT * FROM lineGraph_edges$$,
(SELECT array_agg(id) FROM vertex_map where original_id = 6),
(SELECT array_agg(id) FROM vertex_map where original_id = 3)))
SELECT seq, path_seq, start_vid, end_vid, node, original_id, edge, cost, agg_cost
FROM results
LEFT JOIN vertex_map AS v1 ON (node = v1.id) ORDER BY seq;
seq | path_seq | start_vid | end_vid | node | original_id | edge | cost | agg_cost
-----+----------+-----------+---------+------+-------------+------+------+----------
1 | 1 | -1 | 3 | -1 | 6 | 1 | 1 | 0
2 | 2 | -1 | 3 | 7 | 7 | 10 | 0 | 1
3 | 3 | -1 | 3 | -5 | 7 | 6 | 1 | 1
4 | 4 | -1 | 3 | 8 | 8 | 28 | 0 | 2
5 | 5 | -1 | 3 | -11 | 8 | 27 | 1 | 2
6 | 6 | -1 | 3 | -8 | 7 | 20 | 0 | 3
7 | 7 | -1 | 3 | -3 | 7 | 4 | 1 | 3
8 | 8 | -1 | 3 | 3 | 3 | -1 | 0 | 4
(8 rows)
简化叶顶点¶
在这个例子中，遍历叶顶点没有额外的成本。
使用顶点图赋予叶顶点其原始值。¶
在source 列
WITH
u_turns AS (
SELECT e.id AS eid, v1.original_id
FROM linegraph_edges as e
JOIN vertex_map AS v1 ON (source = v1.id)
AND v1.original_id IN (3, 6, 8, 11))
UPDATE lineGraph_edges
SET source = original_id
FROM u_turns
WHERE id = eid;
UPDATE 8
在target列
WITH
u_turns AS (
SELECT e.id AS eid, v1.original_id
FROM linegraph_edges as e
JOIN vertex_map AS v1 ON (target = v1.id)
AND v1.original_id IN (3, 6, 8, 11))
UPDATE lineGraph_edges
SET target = original_id
FROM u_turns
WHERE id = eid;
UPDATE 8
删除叶节点上的自循环¶
叶节点的自循环为
SELECT * FROM linegraph_edges
WHERE source = target
ORDER BY id;
id | source | target | cost | edge
----+--------+--------+------+------
2 | 6 | 6 | 0 | 0
24 | 3 | 3 | 0 | 0
26 | 11 | 11 | 0 | 0
28 | 8 | 8 | 0 | 0
(4 rows)
哪些可以删除
DELETE FROM linegraph_edges
WHERE source = target;
DELETE 4
- 示例:
路由从 \(6\) 到 \(3\)
现在可以使用 pgr_dijkstra` 使用原始顶点 id 来完成路由
WITH
results AS (
SELECT * FROM pgr_dijkstra(
$$SELECT * FROM lineGraph_edges$$, 6, 3))
SELECT seq, path_seq, node, original_id, edge, cost, agg_cost
FROM results
LEFT JOIN vertex_map AS v1 ON (node = v1.id) ORDER BY seq;
seq | path_seq | node | original_id | edge | cost | agg_cost
-----+----------+------+-------------+------+------+----------
1 | 1 | 6 | 6 | 1 | 1 | 0
2 | 2 | 7 | 7 | 9 | 0 | 1
3 | 3 | -4 | 7 | 5 | 1 | 1
4 | 4 | 11 | 11 | 25 | 1 | 2
5 | 5 | -7 | 7 | 16 | 0 | 3
6 | 6 | -3 | 7 | 4 | 1 | 3
7 | 7 | 3 | 3 | -1 | 0 | 4
(7 rows)
完整的路由图¶
从原始图中添加边¶
将所有不参与折线图过程的边添加到新表中
SELECT id, source, target, cost, reverse_cost
INTO new_graph from edges
WHERE id NOT IN (4, 7, 8, 10);
SELECT 14
一些获取边新标识符的管理任务
CREATE SEQUENCE new_graph_id_seq;
CREATE SEQUENCE
ALTER TABLE new_graph ALTER COLUMN id SET DEFAULT nextval('new_graph_id_seq');
ALTER TABLE
ALTER TABLE new_graph ALTER COLUMN id SET NOT NULL;
ALTER TABLE
ALTER SEQUENCE new_graph_id_seq OWNED BY new_graph.id;
ALTER SEQUENCE
SELECT setval('new_graph_id_seq', (SELECT max(id) FROM new_graph));
setval
--------
18
(1 row)
添加新计算的边¶
INSERT INTO new_graph (source, target, cost, reverse_cost)
SELECT source, target, cost, -1 FROM lineGraph_edges;
INSERT 0 24
使用路由图¶
当使用这种方法进行具有软限制的路由时，将会出现 uturn
- 示例:
路由从 \(6\) 到 \(3\)
WITH
results AS (
SELECT * FROM pgr_dijkstra(
$$SELECT * FROM new_graph$$, 6, 3))
SELECT seq, path_seq, node, original_id, edge, cost, agg_cost
FROM results
LEFT JOIN vertex_map AS v1 ON (node = v1.id) ORDER BY seq;
seq | path_seq | node | original_id | edge | cost | agg_cost
-----+----------+------+-------------+------+------+----------
1 | 1 | 6 | 6 | 35 | 1 | 0
2 | 2 | 7 | 7 | 20 | 0 | 1
3 | 3 | -4 | 7 | 41 | 1 | 1
4 | 4 | 11 | 11 | 37 | 1 | 2
5 | 5 | -7 | 7 | 27 | 0 | 3
6 | 6 | -3 | 7 | 40 | 1 | 3
7 | 7 | 3 | 3 | -1 | 0 | 4
(7 rows)
- 示例:
路由从 \(5\) 到 \(1\)
WITH
results AS (
SELECT * FROM pgr_dijkstra(
$$SELECT * FROM new_graph$$, 5, 1))
SELECT seq, path_seq, node, original_id, edge, cost, agg_cost
FROM results
LEFT JOIN vertex_map AS v1 ON (node = v1.id) ORDER BY seq;
seq | path_seq | node | original_id | edge | cost | agg_cost
-----+----------+------+-------------+------+------+----------
1 | 1 | 5 | 5 | 1 | 1 | 0
2 | 2 | 6 | 6 | 35 | 1 | 1
3 | 3 | 7 | 7 | 20 | 0 | 2
4 | 4 | -4 | 7 | 41 | 1 | 2
5 | 5 | 11 | 11 | 37 | 1 | 3
6 | 6 | -7 | 7 | 27 | 0 | 4
7 | 7 | -3 | 7 | 40 | 1 | 4
8 | 8 | 3 | 3 | 6 | 1 | 5
9 | 9 | 1 | 1 | -1 | 0 | 6
(9 rows)
另请参阅¶
索引和表格