pgr_contractionDeadEnd
- Proposed¶
pgr_contractionDeadEnd
— Performs graph contraction and returns the contracted
vertices and edges.
Warning
下一版本的拟议功能。
它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分:
这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
名字可能不会改变。(但仍然有可能改变)
签名可能不会改变。(但仍然有可能改变)
功能可能不会改变。(但仍然有可能改变)
pgTap 测试已经完成。 但可能需要更多。
文档可能需要完善。
可用性
Version 3.8.0
新提议的函数。
描述¶
收缩通过移除部分顶点和边来减小图的大小,例如,可以添加代表原始边序列的边,从而减少图算法所用的总时间和空间。
主要特点是:
仅在具有正成本的边进行处理。
Does not return the full contracted graph.
Only changes on the graph are returned.
The returned values include:
The new edges generated by linear contraction.
The modified vertices generated by dead end contraction.
返回值的排序如下:
column
id
ascending when its a modified vertex.column
id
with negative numbers descending when its a new edge.
A node is considered a dead end node when:
在无向图上:
相邻顶点的个数为1。
在有向图上:
When there is only one adjacent vertex or
When all edges are incoming regardless of the number of adjacent vertices.
签名¶
[directed, forbidden]
(type, id, contracted_vertices, source, target, cost)
- 示例:
Dead end contraction on an undirected graph.
SELECT * FROM pgr_contractionDeadEnd(
'SELECT id, source, target, cost, reverse_cost FROM edges',
directed => false);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 4 | {2} | -1 | -1 | -1
v | 6 | {5} | -1 | -1 | -1
v | 7 | {1,3} | -1 | -1 | -1
v | 8 | {9} | -1 | -1 | -1
v | 14 | {13} | -1 | -1 | -1
(5 rows)
The green nodes are dead end nodes.
Node
is a dead end node after node is contracted.
![graph G {
splines=false;
1,2,3,5,9,13 [shape=circle;style=filled;color=lightgreen;fontsize=8;width=0.3;fixedsize=true];
4,6,7,8,10,11,12,14,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
4 [label="4,{2}"];
6 [label="6,{5}"];
7 [label="7,{1,3}"];
8 [label="8,{9}"];
14 [label="14,{13}"];
6 -- 10 [label="2",fontsize=8];
10 -- 15 [label="3",fontsize=8]; 6 -- 7 [label="4",fontsize=8];
10 -- 11 [label="5",fontsize=8];
7 -- 11 [label="8",fontsize=8];
11 -- 16 [label="9",fontsize=8]; 7 -- 8 [label="10",fontsize=8];
11 -- 12 [label="11",fontsize=8]; 8 -- 12 [label="12",fontsize=8];
12 -- 17 [label="13",fontsize=8];
16 -- 17 [label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
1 [pos="0,2!"]; 2 [pos="0.5,3.5!"];
3 [pos="1,2!"]; 4 [pos="2,3.5!"];
5 [pos="2,0!"]; 6 [pos="2,1!"];
7 [pos="2,2!"]; 8 [pos="2,3!"];
9 [pos="2,4!"]; 10 [pos="3,1!"];
11 [pos="3,2!"]; 12 [pos="3,3!"];
13 [pos="3.5,2.3!"]; 14 [pos="3.5,4!"];
15 [pos="4,1!"]; 16 [pos="4,2!"];
17 [pos="4,3!"];
}](_images/graphviz-09e10c04c727d31eec492eab5746af897f9fcb08.png)
参数¶
参数 |
类型 |
描述 |
---|---|---|
|
Edges SQL 如下所述。 |
可选参数¶
列 |
类型 |
默认 |
描述 |
---|---|---|---|
|
|
|
|
可选收缩参数¶
列 |
类型 |
默认 |
描述 |
---|---|---|---|
|
|
Empty |
禁止收缩的顶点标识符。 |
内部查询¶
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
结果列¶
Returns set of (type, id, contracted_vertices, source, target, cost)
该函数返回一行数据。该行的列包括:
列 |
类型 |
描述 |
---|---|---|
|
|
Value = |
|
|
A pseudo id of the edge.
|
|
|
收缩顶点标识符数组。 |
|
|
当前边的源顶点的标识符。 |
|
|
当前边的目标顶点的标识符。 |
|
|
Weight of the current edge. |
其他示例¶
无向图上的死端顶点¶
The green nodes are dead end nodes.
它们只有一个相邻节点。
![graph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | {<5> 5 | <6> 6}}"; pos="2.5,1!"];
1,2,3,4 [shape=circle;fontsize=8;fixedsize=true;style=filled];
2,3 [color=deepskyblue];
1,4 [color=green];
{G:5,G:6} -- {2,3} [weight=1, penwidth=3];
1 -- 2 -- 1;
3 -- 4;
1 [pos="1,0!"]; 2 [pos="2,0!"]; 3 [pos="3,0!"]; 4 [pos="4,0!"];
}](_images/graphviz-1c24ab7e60f517bb9ef04765d3876cadce6a4c3d.png)
SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
(1, 1, 2, 1, 1),
(2, 3, 4, 1, -1),
(3, 2, 5, 1, 1), (4, 2, 6, 1, 1),
(5, 3, 5, 1, 1), (5, 3, 6, 1, 1))
AS edges(id,source,target,cost,reverse_cost)$$,
directed => true);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 2 | {1} | -1 | -1 | -1
v | 3 | {4} | -1 | -1 | -1
(2 rows)
![graph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | {<5> 5 | <6> 6}}"; pos="2.5,1!"];
2,3 [shape=circle;fontsize=8;fixedsize=true;style=filled];
2,3 [color=deepskyblue];
2 [label="2, {1}"]; 3 [label="3, {4}"];
{G:5,G:6} -- {2,3} [weight=1, penwidth=3];
2 [pos="2,0!"]; 3 [pos="3,0!"];
}](_images/graphviz-3370f619564ce43a83c68cabc60595106c8a81f0.png)
有向图上的死端顶点¶
The green nodes are dead end nodes
蓝色节点具有无限数量的传入和/或传出边缘。
![digraph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | { | | | | }}"; pos="2.5,3!"];
1,2,3,4,5,6,7,8,9,10 [shape=circle;fontsize=8;fixedsize=true;style=filled];
1,2,3,4,5,10 [color=deepskyblue];
6,7,8,9 [color=green];
{1,2,3,4,5} -> G [dir=both;weight=1, penwidth=3];
1 -> 6 -> 1;
2 -> 7;
{3, 2} -> 8;
9 -> 4;
10 -> {4, 5};
2 [pos="1,4!"]; 3 [pos="2,4!"];
G [pos="2.5,3!"];
1 [pos="1,1!"]; 2 [pos="2,1!"]; 3 [pos="3,1!"]; 4 [pos="4,1!"]; 5 [pos="5,1!"];
6 [pos="1,0!"]; 7 [pos="2,0!"]; 8 [pos="3,0!"]; 9 [pos="4,0!"]; 10 [pos="5,0!"];
}](_images/graphviz-6960d9a7cc004f22357ed2df4395c81f4453d60d.png)
节点 |
相邻节点 |
死端 |
Reason |
---|---|---|---|
Yes |
Has only one adjacent node. |
||
Yes |
Has only one adjacent node. |
||
Yes |
有一个以上的相邻节点,且所有边都是传入的。 |
||
Yes |
Has only one adjacent node. |
||
No |
有一个以上的相邻节点,且所有边都是向外的。 |
||
Many adjacent nodes. |
No |
Has more than one adjacent node and some edges are incoming and some are outgoing. |
From above, nodes
When there are more than one adjacent vertex, all edges need to be all incoming edges otherwise it is not a dead end.
SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
(1, 1, 6, 1, 1),
(2, 2, 7, 1, -1),
(3, 2, 8, 1, -1),
(4, 3, 8, 1, -1),
(5, 9, 4, 1, -1),
(6, 10, 4, 1, 1),
(7, 10, 5, 1, 1),
/* Rest of the graph */
(8, 1, 25, 1, 1), (9, 1, 26, 1, 1),
(10, 2, 25, 1, 1), (11, 2, 26, 1, 1),
(12, 3, 25, 1, 1), (13, 3, 26, 1, 1),
(14, 4, 25, 1, 1), (15, 4, 26, 1, 1),
(16, 5, 25, 1, 1), (17, 5, 26, 1, 1)) AS edges(id,source,target,cost,reverse_cost)$$,
directed => true);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 1 | {6} | -1 | -1 | -1
v | 2 | {7,8} | -1 | -1 | -1
v | 3 | {8} | -1 | -1 | -1
v | 4 | {9} | -1 | -1 | -1
(4 rows)
![digraph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | { | | | | }}"; pos="2.5,3!"];
1,2,3,4,5,10 [shape=circle;fontsize=8;fixedsize=true;style=filled];
1,2,3,4,5,10 [color=deepskyblue];
{1,2,3,4,5} -> G [dir=both;weight=1, penwidth=3];
10 -> {4, 5};
2 [pos="1,4!"]; 3 [pos="2,4!"];
G [pos="2.5,3!"];
1 [label="1, {6}";pos="1,1!"]; 2 [label="2, {7,8}";pos="2,1!"];
3 [label="3, {8}";pos="3,1!"]; 4 [label="4, {9}";pos="4,1!"]; 5 [pos="5,1!"];
10 [pos="5,0!"];
}](_images/graphviz-245db535af656e6524dab0622a0da5521f2f1e69.png)
Step by step dead end contraction¶
The dead end contraction will stop until there are no more dead end nodes.
For example, from the following graph where
![digraph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | { | | | | }}"; pos="2,3!"];
1,2,3 [shape=circle;fontsize=8;fixedsize=true;style=filled];
1,2 [color=deepskyblue];
3 [color=green];
{1} -> G [dir=both;weight=1, penwidth=3];
1 -> 2 -> 3;
G [pos="2.5,3!"];
1 [pos="1,1!"]; 2 [pos="2,1!"]; 3 [pos="3,1!"];
}](_images/graphviz-da4ed291fcc11b0540b23dbf3a5c9a4335487756.png)
After contracting
![digraph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | { | | | | }}"; pos="2,3!"];
1,2 [shape=circle;fontsize=8;fixedsize=true;style=filled];
1 [color=deepskyblue];
2 [color=green];
{1} -> G [dir=both;weight=1, penwidth=3];
1 -> 2;
G [pos="2.5,3!"];
1 [pos="1,1!"]; 2 [label="2, {3}";pos="2,1!"];
}](_images/graphviz-36beb2cf1db17be6d509dfca32d48b88fbdcb45a.png)
After contracting
![digraph G {
G [shape=record;style=filled;fillcolor=deepskyblue;
label="{Rest of the Graph | { | | | | }}"; pos="2,3!"];
1 [shape=circle;fontsize=8;fixedsize=true;style=filled];
1 [color=deepskyblue];
{1} -> G [dir=both;weight=1, penwidth=3];
G [pos="2.5,3!"];
1 [label="1, {2,3}";pos="2,1!"];
}](_images/graphviz-0dc0b6bfc522238b8ea2cedd8edc6126892ab49e.png)
SELECT * FROM pgr_contractionDeadEnd(
$$SELECT * FROM (VALUES
(1, 1, 2, 1, -1),
(2, 2, 3, 1, -1),
/* Rest of the graph */
(3, 1, 25, 1, 1), (4, 1, 26, 1, 1),
(5, 25, 25, 1, 1), (6, 25, 26, 1, 1)) AS edges(id,source,target,cost,reverse_cost)$$,
directed => true);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 1 | {2,3} | -1 | -1 | -1
(1 row)
Creating the contracted graph¶
Steps for the creation of the contracted graph¶
Add additional columns.
ALTER TABLE vertices ADD is_contracted BOOLEAN DEFAULT false;
ALTER TABLE
ALTER TABLE vertices ADD contracted_vertices BIGINT[];
ALTER TABLE
Save results into a table.
SELECT * INTO contraction_results
FROM pgr_contractionDeadEnd(
'SELECT id, source, target, cost, reverse_cost FROM edges',
directed => false);
SELECT 5
使用 is_contracted
列来指示收缩的顶点。
UPDATE vertices
SET is_contracted = true
WHERE id IN (SELECT unnest(contracted_vertices) FROM contraction_results);
UPDATE 6
Fill contracted_vertices
with the information from the results that belong
to the vertices.
UPDATE vertices
SET contracted_vertices = contraction_results.contracted_vertices
FROM contraction_results
WHERE type = 'v' AND vertices.id = contraction_results.id;
UPDATE 5
The contracted vertices are not part of the contracted graph.
SELECT id, is_contracted
FROM vertices WHERE is_contracted ORDER BY id;
id | is_contracted
----+---------------
1 | t
2 | t
3 | t
5 | t
9 | t
13 | t
(6 rows)
收缩图¶
DROP VIEW IF EXISTS contracted_graph;
NOTICE: view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
WITH
vertices_in_graph AS (
SELECT id FROM vertices WHERE is_contracted = false
)
SELECT id, source, target, cost, reverse_cost
FROM edges
WHERE source IN (SELECT * FROM vertices_in_graph)
AND target IN (SELECT * FROM vertices_in_graph)
ORDER BY id;
CREATE VIEW
![graph G {
splines=false;
4,6,7,8,10,11,12,14,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
4 [label="4,{2}"];
6 [label="6,{5}"];
7 [label="7,{1,3}"];
8 [label="8,{9}"];
14 [label="14,{13}"];
6 -- 10 [label="2",fontsize=8];
10 -- 15 [label="3",fontsize=8]; 6 -- 7 [label="4",fontsize=8];
10 -- 11 [label="5",fontsize=8];
7 -- 11 [label="8",fontsize=8];
11 -- 16 [label="9",fontsize=8]; 7 -- 8 [label="10",fontsize=8];
11 -- 12 [label="11",fontsize=8]; 8 -- 12 [label="12",fontsize=8];
12 -- 17 [label="13",fontsize=8];
16 -- 17 [label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
4 [pos="2,3.5!"];
6 [pos="2,1!"];
7 [pos="2,2!"]; 8 [pos="2,3!"];
10 [pos="3,1!"];
11 [pos="3,2!"]; 12 [pos="3,3!"];
14 [pos="3.5,4!"];
15 [pos="4,1!"]; 16 [pos="4,2!"];
17 [pos="4,3!"];
}](_images/graphviz-0f73cc9d674c207beec7c0030b424cbd1b9dd24f.png)
Using when departure and destination are in the contracted graph¶
SELECT *
FROM pgr_dijkstra('SELECT * FROM contracted_graph', 6, 17);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 17 | 6 | 4 | 1 | 0
2 | 2 | 6 | 17 | 7 | 8 | 1 | 1
3 | 3 | 6 | 17 | 11 | 11 | 1 | 2
4 | 4 | 6 | 17 | 12 | 13 | 1 | 3
5 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(5 rows)
![graph G {
splines=false;
4,6,7,8,10,11,12,14,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
4 [label="4,{2}"];
6 [label="6,{5}"];
7 [label="7,{1,3}"];
8 [label="8,{9}"];
14 [label="14,{13}"];
6 -- 10 [label="2",fontsize=8];
10 -- 15 [label="3",fontsize=8]; 6 -- 7 [color=red;label="4",fontsize=8];
10 -- 11 [label="5",fontsize=8];
7 -- 11 [color=red;label="8",fontsize=8];
11 -- 16 [label="9",fontsize=8]; 7 -- 8 [label="10",fontsize=8];
11 -- 12 [color=red;label="11",fontsize=8]; 8 -- 12 [label="12",fontsize=8];
12 -- 17 [color=red;label="13",fontsize=8];
16 -- 17 [label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
4 [pos="2,3.5!"];
6 [pos="2,1!"];
7 [pos="2,2!"]; 8 [pos="2,3!"];
10 [pos="3,1!"];
11 [pos="3,2!"]; 12 [pos="3,3!"];
14 [pos="3.5,4!"];
15 [pos="4,1!"]; 16 [pos="4,2!"];
17 [pos="4,3!"];
}](_images/graphviz-fb96c71385be96c073e575d76eb1da8af92db50f.png)
Using when departure/destination is not in the contracted graph¶
SELECT * FROM pgr_dijkstra(
'WITH cul_de_sac AS (
SELECT contracted_vertices || id as v
FROM vertices WHERE 1 = ANY(contracted_vertices))
SELECT id, source, target, cost, reverse_cost FROM edges, cul_de_sac
WHERE source = ANY(v) AND target = ANY(v)
UNION
SELECT id, source, target, cost, reverse_cost FROM contracted_graph',
1, 17);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 17 | 1 | 6 | 1 | 0
2 | 2 | 1 | 17 | 3 | 7 | 1 | 1
3 | 3 | 1 | 17 | 7 | 8 | 1 | 2
4 | 4 | 1 | 17 | 11 | 9 | 1 | 3
5 | 5 | 1 | 17 | 16 | 15 | 1 | 4
6 | 6 | 1 | 17 | 17 | -1 | 0 | 5
(6 rows)
![graph G {
splines=false;
1,3 [shape=circle;style=filled;color=lightgreen;fontsize=8;width=0.3;fixedsize=true];
4,6,7,8,10,11,12,14,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
4 [label="4,{2}"];
6 [label="6,{5}"];
7 [label="7,{1,3}"];
8 [label="8,{9}"];
14 [label="14,{13}"];
1 -- 3 [color=red;label="6",fontsize=8];
3 -- 7 [color=red;label="7",fontsize=8];
6 -- 10 [label="2",fontsize=8];
10 -- 15 [label="3",fontsize=8]; 6 -- 7 [label="4",fontsize=8];
10 -- 11 [label="5",fontsize=8];
7 -- 11 [color=red;label="8",fontsize=8];
11 -- 16 [color=red;label="9",fontsize=8]; 7 -- 8 [label="10",fontsize=8];
11 -- 12 [label="11",fontsize=8]; 8 -- 12 [label="12",fontsize=8];
12 -- 17 [label="13",fontsize=8];
16 -- 17 [color=red;label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
1 [pos="0,2!"];
3 [pos="1,2!"]; 4 [pos="2,3.5!"];
6 [pos="2,1!"];
7 [pos="2,2!"]; 8 [pos="2,3!"];
10 [pos="3,1!"];
11 [pos="3,2!"]; 12 [pos="3,3!"];
14 [pos="3.5,4!"];
15 [pos="4,1!"]; 16 [pos="4,2!"];
17 [pos="4,3!"];
}](_images/graphviz-1027eeee89fdb0afb0b1167084efcba514616b36.png)
Using when departure and destination are not in the contracted graph¶
SELECT * FROM pgr_dijkstra(
'WITH cul_de_sac AS (
SELECT contracted_vertices || id as v
FROM vertices WHERE 1 = ANY(contracted_vertices) OR 9 = ANY(contracted_vertices))
SELECT id, source, target, cost, reverse_cost FROM edges, cul_de_sac WHERE source = ANY(v) AND target = ANY(v)
UNION
SELECT id, source, target, cost, reverse_cost FROM contracted_graph',
1, 9);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 9 | 1 | 6 | 1 | 0
2 | 2 | 1 | 9 | 3 | 7 | 1 | 1
3 | 3 | 1 | 9 | 7 | 10 | 1 | 2
4 | 4 | 1 | 9 | 8 | 14 | 1 | 3
5 | 5 | 1 | 9 | 9 | -1 | 0 | 4
(5 rows)
![graph G {
splines=false;
1,3,9 [shape=circle;style=filled;color=lightgreen;fontsize=8;width=0.3;fixedsize=true];
4,6,7,8,10,11,12,14,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
4 [label="4,{2}"];
6 [label="6,{5}"];
7 [label="7,{1,3}"];
8 [label="8,{9}"];
14 [label="14,{13}"];
1 -- 3 [color=red;label="6",fontsize=8];
3 -- 7 [color=red;label="7",fontsize=8];
8 -- 9 [color=red;label="7",fontsize=8];
6 -- 10 [label="2",fontsize=8];
10 -- 15 [label="3",fontsize=8]; 6 -- 7 [label="4",fontsize=8];
10 -- 11 [label="5",fontsize=8];
7 -- 11 [label="8",fontsize=8];
11 -- 16 [label="9",fontsize=8]; 7 -- 8 [label="10",fontsize=8];
11 -- 12 [label="11",fontsize=8]; 8 -- 12 [label="12",fontsize=8];
12 -- 17 [label="13",fontsize=8];
16 -- 17 [label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
1 [pos="0,2!"];
3 [pos="1,2!"]; 4 [pos="2,3.5!"];
6 [pos="2,1!"];
7 [pos="2,2!"]; 8 [pos="2,3!"];
9 [pos="2,4!"]; 10 [pos="3,1!"];
11 [pos="3,2!"]; 12 [pos="3,3!"];
14 [pos="3.5,4!"];
15 [pos="4,1!"]; 16 [pos="4,2!"];
17 [pos="4,3!"];
}](_images/graphviz-71ddba31051fac0c8694973c7d5a06026a36e97d.png)
另请参阅¶
索引和表格