pgr_contraction
¶
pgr_contraction
— Performs graph contraction and returns the contracted
vertices and edges.
Availability
Version 3.0.0
Return columns change:
seq
is removedName change from
pgr_contractGraph
Bug fixes
Official function
Version 2.3.0
New experimental function
Description¶
Contraction reduces the size of the graph by removing some of the vertices and edges and, for example, might add edges that represent a sequence of original edges decreasing the total time and space used in graph algorithms.
The main Characteristics are:
Process is done only on edges with positive costs.
Does not return the full contracted graph
Only changes on the graph are returned
Currnetly there are two types of contraction methods
Dead End Contraction
Linear Contraction
The returned values include
the added edges by linear contraction.
the modified vertices by dead end contraction.
The returned values are ordered as follows:
column
id
ascending when type isv
column
id
descending when type ise
Signatures¶
Summary
The pgr_contraction function has the following signature:
[ max_cycles, forbidden_vertices, directed]
(type, id, contracted_vertices, source, target, cost)
- Example:
Making a 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',
ARRAY[1, 2], directed => 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)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below. |
|
contraction Order |
|
Ordered contraction operations.
|
Optional Parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
Contraction optional parameters¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
|
Empty |
Identifiers of vertices forbidden for contraction. |
|
|
\(1\) |
Number of times the contraction operations on |
Inner Queries¶
Edges SQL¶
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER:
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns¶
Returns set of (type, id, contracted_vertices, source, target, cost)
The function returns a single row. The columns of the row are:
Column |
Type |
Description |
---|---|---|
|
|
Type of the
|
|
|
All numbers on this column are
|
|
|
Array of contracted vertex identifiers. |
|
|
|
|
|
|
|
|
|
Additional Examples¶
- Example:
Only dead end contraction
SELECT type, id, contracted_vertices FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[1]);
type | id | contracted_vertices
------+----+---------------------
v | 4 | {2}
v | 6 | {5}
v | 7 | {1,3}
v | 8 | {9}
v | 14 | {13}
(5 rows)
- Example:
Only linear contraction
SELECT * FROM pgr_contraction(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[2]);
type | id | contracted_vertices | source | target | cost
------+----+---------------------+--------+--------+------
e | -1 | {3} | 1 | 7 | 2
e | -2 | {3} | 7 | 1 | 2
(2 rows)
See Also¶
Indices and tables