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 \(3\) is a dead end node after node \(1\) 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 |
---|---|---|---|
\(6\) |
\(\{1\}\) |
Yes |
Has only one adjacent node. |
\(7\) |
\(\{2\}\) |
Yes |
Has only one adjacent node. |
\(8\) |
\(\{2, 3\}\) |
Yes |
有一个以上的相邻节点,且所有边都是传入的。 |
\(9\) |
\(\{4\}\) |
Yes |
Has only one adjacent node. |
\(10\) |
\(\{4, 5\}\) |
No |
有一个以上的相邻节点,且所有边都是向外的。 |
\(1,2,3,4,5\) |
Many adjacent nodes. |
No |
Has more than one adjacent node and some edges are incoming and some are outgoing. |
From above, nodes \(\{6, 7, 9\}\) are dead ends because the total number of adjacent vertices is one.
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 \(3\) is the dead end node:
![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 \(3\), node \(2\) is now a dead end node and is contracted:
![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 \(2\), stop. Node \(1\) has the information of nodes that were contracted.
![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)
另请参阅¶
索引和表格