pgr_contraction
¶
pgr_contraction
— 执行图收缩操作并返回收缩后的顶点和边。
可用性
Version 3.8.0
New signature:
Previously compulsory parameter Contraction order is now optional with name
methods
.New name and order of optional parameters.
Deprecated signature pgr_contraction(text,bigint[],integer,bigint[],boolean)
版本3.0.0
结果列更改:删除了
seq
pgr_contractGraph
的名称更改Bug修复
Function promoted to official.
版本2.3.0
New experimental function.
描述¶
收缩通过移除部分顶点和边来减小图的大小,例如,可以添加代表原始边序列的边,从而减少图算法所用的总时间和空间。
主要特点是:
仅在具有正成本的边进行处理。
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.
Currently there are two types of contraction methods included in this function:
Dead End Contraction. See pgr_contractionDeadEnd - Proposed.
Linear Contraction. See pgr_contractionLinear - Proposed.
签名¶
[directed, methods, cycles, forbidden]
(type, id, contracted_vertices, source, target, cost)
- 示例:
Dead end and linear contraction in that order on an undirected graph.
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges', false);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 4 | {2} | -1 | -1 | -1
v | 7 | {1,3} | -1 | -1 | -1
v | 14 | {13} | -1 | -1 | -1
e | -1 | {5,6} | 7 | 10 | 2
e | -2 | {8,9} | 7 | 12 | 2
e | -3 | {17} | 12 | 16 | 2
e | -4 | {15} | 10 | 16 | 2
(7 rows)
参数¶
参数 |
类型 |
描述 |
---|---|---|
|
Edges SQL 如下所述。 |
可选参数¶
列 |
类型 |
默认 |
描述 |
---|---|---|---|
|
|
|
|
可选收缩参数¶
列 |
类型 |
默认 |
描述 |
---|---|---|---|
|
|
|
有序收缩操作。
|
|
|
\(1\) |
Number of times the contraction methods will be performed. |
|
|
|
禁止收缩的顶点标识符。 |
内部查询¶
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)
该函数返回一行数据。该行的列包括:
列 |
类型 |
描述 |
---|---|---|
|
|
Type of the row.
|
|
|
此列中的所有数字都是
|
|
|
收缩顶点标识符数组。 |
|
|
|
|
|
|
|
|
|
其他示例¶
仅死端收缩¶
SELECT type, id, contracted_vertices FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges',
methods => ARRAY[1]);
type | id | contracted_vertices
------+----+---------------------
v | 4 | {2}
v | 6 | {5}
v | 7 | {1,3}
v | 8 | {9}
v | 14 | {13}
(5 rows)
仅线性收缩¶
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges',
methods => ARRAY[2]);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
e | -1 | {3} | 1 | 7 | 2
e | -2 | {3} | 7 | 1 | 2
(2 rows)
循环¶
Contracting a graph can be done with more than one operation. The order of the operations affect the resulting contracted graph, after applying one operation, the set of vertices that can be contracted by another operation changes.
This implementation cycles cycles
times through the methods
.
<input>
do max_cycles times {
for (operation in operations_order)
{ do operation }
}
<output>
收缩示例数据¶
在本节中,将通过示例展示构建和使用收缩图。
使用无向图的 示例数据
首先是死端操作,然后是线性操作。
数据库中图的构建¶
原始图:

The results do not represent the contracted graph. They represent the changes that need to be done to the graph after applying the contraction methods.
例如,观察到顶点 \(6\) 没有出现在结果中,因为它不受收缩算法的影响。
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges', false);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
v | 4 | {2} | -1 | -1 | -1
v | 7 | {1,3} | -1 | -1 | -1
v | 14 | {13} | -1 | -1 | -1
e | -1 | {5,6} | 7 | 10 | 2
e | -2 | {8,9} | 7 | 12 | 2
e | -3 | {17} | 12 | 16 | 2
e | -4 | {15} | 10 | 16 | 2
(7 rows)
进行死端收缩操作后:

对上图进行线性收缩运算后:

在数据库上创建收缩图的过程:¶
添加附加列¶
Adding extra columns to the edges and vertices tables. In this documentation the following will be used:
Column. |
描述 |
---|---|
|
属于顶点/边的顶点集 |
|
在顶点表上
|
|
在边表上
|
ALTER TABLE vertices
ADD is_contracted BOOLEAN DEFAULT false,
ADD contracted_vertices BIGINT[];
ALTER TABLE
ALTER TABLE edges
ADD is_new BOOLEAN DEFAULT false,
ADD contracted_vertices BIGINT[];
ALTER TABLE
存储收缩信息¶
Store the contraction results in a table.
SELECT * INTO contraction_results
FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges', false);
SELECT 7
Update the edges and vertices tables¶
使用 is_contracted
列来指示收缩的顶点。
UPDATE vertices
SET is_contracted = true
WHERE id IN (SELECT unnest(contracted_vertices) FROM contraction_results);
UPDATE 10
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 3
插入由 pgr_contraction 生成的新边。
INSERT INTO edges(source, target, cost, reverse_cost, contracted_vertices, is_new)
SELECT source, target, cost, -1, contracted_vertices, true
FROM contraction_results
WHERE type = 'e';
INSERT 0 4
收缩图¶
属于收缩图的顶点。
SELECT id FROM vertices WHERE is_contracted = false ORDER BY id;
id
----
4
7
10
11
12
14
16
(7 rows)
属于收缩图的边。
WITH
vertices_in_graph AS (SELECT id FROM vertices WHERE is_contracted = false)
SELECT id, source, target, cost, reverse_cost, contracted_vertices
FROM edges
WHERE
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
AND
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target)
ORDER BY id;
id | source | target | cost | reverse_cost | contracted_vertices
----+--------+--------+------+--------------+---------------------
5 | 10 | 11 | 1 | -1 |
8 | 7 | 11 | 1 | 1 |
9 | 11 | 16 | 1 | 1 |
11 | 11 | 12 | 1 | -1 |
19 | 7 | 10 | 2 | -1 | {5,6}
20 | 7 | 12 | 2 | -1 | {8,9}
21 | 12 | 16 | 2 | -1 | {17}
22 | 10 | 16 | 2 | -1 | {15}
(8 rows)
Visually:

使用收缩图¶
Depending on the final application the graph is to be prepared.
In this example the final application will be to calculate the cost from two
vertices in the original graph by using the contracted graph with pgr_dijkstraCost
计算收缩图中给定源和目标之间的最短路径时,存在三种情况:
情况1:源和目标都属于收缩图。
情况 2:源和/或目标属于边缘子图。
情况 3:源和/或目标属于一个顶点。
The final application should consider all of those cases.
Create a view (or table) of the contracted graph:
DROP VIEW IF EXISTS contracted_graph;
NOTICE: view "contracted_graph" does not exist, skipping
DROP VIEW
CREATE VIEW contracted_graph AS
SELECT id,source, target, cost, reverse_cost, contracted_vertices FROM edges
WHERE
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.source)
AND
EXISTS (SELECT id FROM vertices AS v WHERE NOT is_contracted AND v.id = edges.target);
CREATE VIEW
Create the function that will use the contracted graph.
CREATE OR REPLACE FUNCTION path_cost(source BIGINT, target BIGINT)
RETURNS SETOF FLOAT AS
$BODY$
SELECT agg_cost FROM pgr_dijkstraCost(
/* The inner query */
'WITH
cul_de_sac AS (
SELECT contracted_vertices || id as v
FROM vertices WHERE ' || $1 ||' = ANY(contracted_vertices)
OR ' || $2 ||' = ANY(contracted_vertices)),
linears_to_expand AS (
SELECT id, contracted_vertices
FROM edges WHERE is_new AND (' || $1 ||' = ANY(contracted_vertices)
OR '|| $2 ||' = ANY(contracted_vertices))
),
additional_vertices AS (
SELECT * FROM cul_de_sac UNION SELECT contracted_vertices FROM linears_to_expand)
SELECT id, source, target, cost, reverse_cost
FROM edges, additional_vertices WHERE source = ANY(v) OR target = ANY(v)
UNION
SELECT id, source, target, cost, reverse_cost
FROM contracted_graph LEFT JOIN linears_to_expand c USING (id) WHERE c.id IS NULL',
source, target, false);
$BODY$ LANGUAGE SQL;
CREATE FUNCTION
情况1:源和目标都属于收缩图。
SELECT * FROM path_cost(10, 12);
path_cost
-----------
2
(1 row)
Case 2: Source and/or target belong to an edge that has contracted vertices.
SELECT * FROM path_cost(15, 12);
path_cost
-----------
3
(1 row)
Case 3: Source and/or target belong to a vertex that has been contracted.
SELECT * FROM path_cost(15, 1);
path_cost
-----------
5
(1 row)
另请参阅¶
索引和表格