pgr_degree
¶
pgr_degree
— For each vertex in an undirected graph, return the count of
edges incident to the vertex.
Warning
Proposed functions for next mayor release.
They are not officially in the current release.
They will likely officially be part of the next mayor release:
The functions make use of ANY-INTEGER and ANY-NUMERICAL
Name might not change. (But still can)
Signature might not change. (But still can)
Functionality might not change. (But still can)
pgTap tests have being done. But might need more.
Documentation might need refinement.
Availability
Version 3.8.0
Error messages adjustment.
New signature with only Edges SQL.
Function promoted to official.
Version 3.4.0
New proposed function.
Description¶
Calculates the degree of the vertices of an undirected graph
The degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex.
Works for undirected graphs.
A loop contributes 2 to a vertex’s degree.
A vertex with degree 0 is called an isolated vertex.
Isolated vertex is not part of the result
Vertex not participating on the subgraph is considered and isolated vertex.
There can be a
dryrun
execution and the code used to get the answer will be shown in a PostgreSQLNOTICE
.The code can be used as base code for the particular application requirements.
No ordering is performed.
Signatures¶
dryrun
])(node, degree)
Edges¶
dryrun
])(node, degree)
- example:
Get the degree of the vertices defined on the edges table
SELECT * FROM pgr_degree($$SELECT id, source, target FROM edges$$)
ORDER BY node;
node | degree
------+--------
1 | 1
2 | 1
3 | 2
4 | 1
5 | 1
6 | 3
7 | 4
8 | 3
9 | 1
10 | 3
11 | 4
12 | 3
13 | 1
14 | 1
15 | 2
16 | 3
17 | 2
(17 rows)
Edges and Vertices¶
(node, degree)
- Example:
Extracting the vertex information
pgr_degree
can use pgr_extractVertices embedded in the call.
For decent size networks, it is best to prepare your vertices table before hand
and use it on pgr_degree
calls. (See Using a vertex table)
Calculate the degree of the nodes:
SELECT * FROM pgr_degree(
$$SELECT id FROM edges$$,
$$SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, geom FROM edges')$$);
node | degree
------+--------
1 | 1
2 | 1
3 | 2
4 | 1
5 | 1
6 | 3
7 | 4
8 | 3
9 | 1
10 | 3
11 | 4
12 | 3
13 | 1
14 | 1
15 | 2
16 | 3
17 | 2
(17 rows)
Parameters¶
Parameter |
Type |
Description |
---|---|---|
|
Edges SQL as described below |
|
|
Vertex SQL as described below |
Optional parameters¶
Parameter |
Type |
Default |
Description |
---|---|---|---|
|
|
|
|
Inner Queries¶
Edges SQL¶
For the Edges and Vertices signature:
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the edge. |
For the Edges signature:
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the edge. |
|
|
Identifier of the first end point vertex of the edge. |
|
|
Identifier of the second end point vertex of the edge. |
Vertex SQL¶
For the Edges and Vertices signature:
Column |
Type |
Description |
---|---|---|
|
|
Identifier of the first end point vertex of the edge. |
|
|
Array of identifiers of the edges that have the vertex
|
|
|
Array of identifiers of the edges that have the vertex
|
Result columns¶
Column |
Type |
Description |
---|---|---|
|
|
Vertex identifier |
|
|
Number of edges that are incident to the vertex |
Additional Examples¶
Degree of a loop¶
A loop contributes 2 to a vertex’s degree.
![graph G {
2 [shape=circle;style=filled;color=green;fontsize=8;width=0.3;fixedsize=true];
2 -- 2 [label="1",fontsize=8];
}](_images/graphviz-f073d7caa11bc4ba9bfb5b716979fff8d20250cc.png)
Using the Edges signature.
SELECT * from pgr_degree('SELECT 1 as id, 2 as source, 2 as target');
node | degree
------+--------
2 | 2
(1 row)
Using the Edges and Vertices signature.
SELECT * FROM pgr_degree(
$$SELECT 1 AS id$$,
$$SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT 1 as id, 2 as source, 2 as target')$$);
node | degree
------+--------
2 | 2
(1 row)
Degree of a sub graph¶
For the following is a subgraph of the Sample Data:
![graph G {
5,6,10 [shape=circle;style=filled;color=lightgreen;fontsize=8;width=0.3;fixedsize=true];
1,2,3,4,7,8,9,11,12,13,14,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
5 -- 6 [label="1",fontsize=8];
10 -- 6 [label="2",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-6106b47f99707f3fa761a76504010ae8159fd677.png)
The vertices not participating on the edge are considered isolated
their degree is 0 in the subgraph and
their degree is not shown in the output.
Using the Edges signature.
SELECT * FROM pgr_degree($$SELECT * FROM edges WHERE id IN (1, 2)$$);
node | degree
------+--------
10 | 1
6 | 2
5 | 1
(3 rows)
Using the Edges and Vertices signature.
SELECT * FROM pgr_degree(
$$SELECT * FROM edges WHERE id IN (1, 2)$$,
$$SELECT id, in_edges, out_edges FROM vertices$$);
node | degree
------+--------
5 | 1
6 | 2
10 | 1
(3 rows)
Using a vertex table¶
For decent size networks, it is best to prepare your vertices table before hand
and use it on pgr_degree
calls.
Extract the vertex information and save into a table:
CREATE TABLE vertices AS
SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, geom FROM edges');
SELECT 17
Calculate the degree of the nodes:
SELECT * FROM pgr_degree(
$$SELECT id FROM edges$$,
$$SELECT id, in_edges, out_edges FROM vertices$$);
node | degree
------+--------
1 | 1
2 | 1
3 | 2
4 | 1
5 | 1
6 | 3
7 | 4
8 | 3
9 | 1
10 | 3
11 | 4
12 | 3
13 | 1
14 | 1
15 | 2
16 | 3
17 | 2
(17 rows)
Dry run execution¶
To get the query generated used to get the vertex information, use dryrun =>
true
.
The results can be used as base code to make a refinement based on the backend development needs.
SELECT * FROM pgr_degree(
$$SELECT id FROM edges WHERE id < 17$$,
$$SELECT id, in_edges, out_edges FROM vertices$$,
dryrun => true);
NOTICE:
WITH
-- a sub set of edges of the graph goes here
g_edges AS (
SELECT id FROM edges WHERE id < 17
),
-- sub set of vertices of the graph goes here
all_vertices AS (
SELECT id, in_edges, out_edges FROM vertices
),
g_vertices AS (
SELECT id,
unnest(
coalesce(in_edges::BIGINT[], '{}'::BIGINT[])
||
coalesce(out_edges::BIGINT[], '{}'::BIGINT[])) AS eid
FROM all_vertices
),
totals AS (
SELECT v.id, count(*)
FROM g_vertices v
JOIN g_edges e ON (v.eid = e.id) GROUP BY v.id
)
SELECT id::BIGINT, count::BIGINT FROM all_vertices JOIN totals USING (id)
;
node | degree
------+--------
(0 rows)
Finding dead ends¶
If there is a vertices table already built using pgr_extractVertices
and want the degree of the whole graph rather than a subset, it can be forgo using
pgr_degree
and work with the in_edges
and out_edges
columns
directly.
The degree of a dead end is 1.
To get the dead ends:
SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 1;
id
----
1
5
9
13
14
2
4
(7 rows)
A dead end happens when
The vertex is the limit of a cul-de-sac, a no-through road or a no-exit road.
The vertex is on the limit of the imported graph.
If a larger graph is imported then the vertex might not be a dead end
Node

Is node
![graph G {
1,2,4,5,9,13,14 [shape=circle;style=filled;color=lightgreen;fontsize=8;width=0.3;fixedsize=true];
3,6,7,8,10,11,12,15,16,17 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
5 -- 6 [label="1",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]; 1 -- 3 [label="6",fontsize=8];
3 -- 7 [label="7",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]; 8 -- 9 [label="",fontsize=8];
16 -- 17 [label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
2 -- 4 [label="17",fontsize=8]; 13 -- 14 [label="18",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-4fb3b0c0f783a75e6df1c7b7487897c1a989e67f.png)
The answer to that question will depend on the application.
Is there such a small curb:
That does not allow a vehicle to use that visual intersection?
Is the application for pedestrians and therefore the pedestrian can easily walk on the small curb?
Is the application for the electricity and the electrical lines than can easily be extended on top of the small curb?
Is there a big cliff and from eagles view look like the dead end is close to the segment?
Depending on the answer, modification of the data might be needed.
When there are many dead ends, to speed up processing, the Contraction - Family of functions functions can be used to contract the graph.
Finding linear vertices¶
The degree of a linear vertex is 2.
If there is a vertices table already built using the pgr_extractVertices
To get the linear edges:
SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 2;
id
----
3
15
17
(3 rows)
![graph G {
3,15,17 [shape=circle;style=filled;color=lightgreen;fontsize=8;width=0.3;fixedsize=true];
1,2,4,5,6,7,8,9,10,11,12,13,14,16 [shape=circle;style=filled;color=cyan;fontsize=8;width=0.3;fixedsize=true];
5 -- 6 [label="1",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]; 1 -- 3 [label="6",fontsize=8];
3 -- 7 [label="7",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]; 8 -- 9 [label="",fontsize=8];
16 -- 17 [label="15",fontsize=8]; 15 -- 16 [label="16",fontsize=8];
2 -- 4 [label="17",fontsize=8]; 13 -- 14 [label="18",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-6d7238dd25f707b964398483a953a70c2f345780.png)
These linear vertices are correct, for example, when those the vertices are speed bumps, stop signals and the application is taking them into account.
When there are many linear vertices, that need not to be taken into account, to speed up the processing, the Contraction - Family of functions functions can be used to contract the problem.
See Also¶
Indices and tables