pgr_degree
¶
pgr_degree
—对于无向图中的每个顶点,返回与该顶点关联的边的计数。
Warning
下一版本的拟议功能。
它们并未正式出现在当前版本中。
它们可能会正式成为下一个版本的一部分:
这些函数使用 ANY-INTEGER 和 ANY-NUMERICAL
名字可能不会改变。(但仍然有可能改变)
签名可能不会改变。(但仍然有可能改变)
功能可能不会改变。(但仍然有可能改变)
pgTap 测试已经完成。 但可能需要更多。
文档可能需要完善。
可用性
Version 3.8.0
Error messages adjustment.
New signature with only Edges SQL.
Function promoted to official.
版本 3.4.0
New proposed function.
描述¶
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.
适用于 无向 图。
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.
签名¶
dryrun
])(node, degree)
边¶
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)
- 示例:
提取顶点信息
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)
参数¶
参数 |
类型 |
描述 |
---|---|---|
|
Edges SQL 如下所述 |
|
|
Vertex SQL 如下所述 |
可选参数¶
参数 |
类型 |
默认 |
描述 |
---|---|---|---|
|
|
|
|
内部查询¶
Edges SQL¶
For the Edges and Vertices signature:
列 |
类型 |
描述 |
---|---|---|
|
|
边的标识符。 |
For the Edges signature:
列 |
类型 |
描述 |
---|---|---|
|
|
边的标识符。 |
|
|
边的第一个端点顶点的标识符。 |
|
|
边的第二个端点顶点的标识符。 |
Vertex SQL¶
For the Edges and Vertices signature:
列 |
类型 |
描述 |
---|---|---|
|
|
边的第一个端点顶点的标识符。 |
|
|
以顶点
|
|
|
以顶点
|
结果列¶
列 |
类型 |
描述 |
---|---|---|
|
|
顶点标识符 |
|
|
与顶点 |
其他示例¶
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)
子图的度数¶
For the following is a subgraph of the 示例数据:
\(E = \{(1, 5 \leftrightarrow 6), (1, 6 \leftrightarrow 10)\}\)
\(V = \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17\}\)
![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)
模拟执行¶
要获取用于生成顶点信息的查询,请使用 dryrun => true
。
结果可作为基础代码,根据后台开发需要进行改进。
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.
获取死端:
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 \(4\), is a dead end on the query, even that it visually looks like an end point of 3 edges.

Is node \(4\) a dead end or not?
![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.
有这么小的路边吗:
这不允许车辆使用该视觉交叉路口?
是否适用于行人,因此行人可以轻松地在小路边行走?
电力和电线的应用是否可以轻松地延伸到小路边顶部?
是否有一个大悬崖,从鹰的角度看,死胡同靠近该路段?
Depending on the answer, modification of the data might be needed.
When there are many dead ends, to speed up processing, the 收缩 - 函数族 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
要获得线性边:
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 收缩 - 函数族 functions can be used to contract the problem.
另请参阅¶
索引和表格