pgr_degree #2297
Description
One of the tasks done by pgr_analyzeGraph is to answer the foloowing question:
"How many dead end nodes are in the undirected graph?"
In the form of a notice:
NOTICE: Dead ends: 7
What it does for solving that question is:
- Alters the table
<edge_table>_vertices_pgrby adding a column to namedcnt<-- acronym of "degree" of a node- This impĺies that a user must have the appropriate rights to modify tables
- Proceeds to count the degree of the nodes and Updates the column values.
- Count the number of leaf nodes (aka where the degree <= 1) and writing up the notice message
Note: leaf nodes is the term used in graph theory, dead end is the term used on roads, but graphs are not only about roads.
By having a pgr_degree function (that does not atler tables and/or directly updates table's columns) to have a faster responsive query
Using the information from pgr_extractVertices (either called directly or been saved on a table) the degree of the nodes can be calculated.
The following examples is of what is to be expected to work (without creating tables, altering tables or modifying table columns):
Degree of all the nodes
SELECT * FROM pgr_degree(
$$SELECT id FROM edge_table$$,
$$SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, the_geom AS geom FROM edge_table')$$);
id | 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)
Degree of a subgraph
SELECT * FROM pgr_degree(
$$SELECT id FROM edge_table WHERE id < 17$$,
$$SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, the_geom AS geom FROM edge_table')$$);
id | degree
----+--------
1 | 1
2 | 0
3 | 2
4 | 0
5 | 1
6 | 3
7 | 4
8 | 3
9 | 1
10 | 3
11 | 4
12 | 3
13 | 0
14 | 0
15 | 2
16 | 3
17 | 2
(17 rows)
The number of leaf nodes (aka dead ends)
SELECT count(*)
FROM (SELECT * FROM pgr_degree(
$$SELECT id FROM edge_table WHERE id < 17$$,
$$SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, the_geom AS geom FROM edge_table')$$)) a
WHERE degree <= 1;
count
-------
7
(1 row)