pgr_degree

pgr_degree —对于无向图中的每个顶点，返回与该顶点关联的边的计数。

Proposed

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 PostgreSQL NOTICE.

  • The code can be used as base code for the particular application requirements.

• No ordering is performed.

签名

pgr_degree(Edges SQL , [dryrun])

pgr_degree(Edges SQL , Vertex SQL, [dryrun])

RETURNS SETOF (node, degree)

OR EMPTY SET

边

pgr_degree(Edges SQL , [dryrun])

RETURNS SETOF (node, degree)

OR EMPTY SET

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

pgr_degree(Edges SQL , Vertex SQL, [dryrun])

RETURNS SETOF (node, degree)

OR EMPTY SET

示例:

提取顶点信息

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	TEXT	Edges SQL 如下所述
Vertex SQL	TEXT	Vertex SQL 如下所述

可选参数

参数	类型	默认	描述
dryrun	BOOLEAN	false	当为真时，不要处理查询，而是获取一个通知（NOTICE）来显示查询的结果。

内部查询

Edges SQL

For the Edges and Vertices signature:

列	类型	描述
id	BIGINT	边的标识符。

For the Edges signature:

列	类型	描述
id	BIGINT	边的标识符。
source	BIGINT	边的第一个端点顶点的标识符。
target	BIGINT	边的第二个端点顶点的标识符。

Vertex SQL

For the Edges and Vertices signature:

列	类型	描述
id	BIGINT	边的第一个端点顶点的标识符。
in_edges	BIGINT[]	以顶点 id 作为*第一个端点*的边的标识符数组。 当缺失时， out_edges 必须存在。
out_edges	BIGINT[]	以顶点 id 作为*第二个端点*的边的标识符数组。 缺失时， in_edges 必须存在。

结果列

列	类型	描述
node	BIGINT	顶点标识符
degree	BIGINT	与顶点 id 关联的边数

其他示例

Degree of a loop

A loop contributes 2 to a vertex's degree.

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\}\)

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?

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)

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.

另请参阅

• Topology - 函数族

• pgr_extractVertices

索引和表格

• Index

• Search Page