pgr_degree
¶
pgr_degree
- Para cada vértice de un grafo no dirigido, devuelve el número de aristas incidentes en el vértice.
Advertencia
Funciones propuestas para la próxima versión mayor.
No están oficialmente en la versión actual.
Es probable que oficialmente formen parte del próximo lanzamiento:
Las funciones hacen uso de ENTEROS y FLOTANTES
Probablemente el nombre no cambie. (Pero todavía puede)
Es posible que la firma no cambie. (Pero todavía puede)
Probablemente la funcionalidad no cambie. (Pero todavía puede)
Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.
Es posible que la documentación necesite un refinamiento.
Disponibilidad
Versión 3.8.0
Error messages adjustment.
New signature with only Edges SQL.
Función promovida a oficial.
Versión 3.4.0
Nueva función propuesta.
Descripción¶
Calcula el grado de los vértices de un grafo no dirigido
El grado (o valencia) de un vértice de un grafo es el número de aristas incidentes al vértice.
Funciona para grafos no dirigidos.
A loop contributes 2 to a vertex’s degree.
A vertex with degree 0 is called an isolated vertex.
Vértice aislado no forma parte del resultado
Vertex not participating on the subgraph is considered and isolated vertex.
Dado que se trata de una ejecución
dryrun
, el código de todos los cálculos se muestra en elNOTICE
de PostgreSQL.The code can be used as base code for the particular application requirements.
No se realiza ningún ordenamiento.
Firmas¶
dryrun
])(node, degree)
Edges¶
dryrun
])(node, degree)
- ejemplo:
Obtener el grado de los vértices definidos en la tabla de aristas
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)
Aristas y Vértices¶
(node, degree)
- Ejemplo:
Extraer la información del vértice
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)
Calcula el grado de los vértices:
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)
Parámetros¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
SQL de aristas como se describe a continuación |
|
|
Vertex SQL como se describe abajo |
Parámetros opcionales¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Consultas Internas¶
SQL aristas¶
Para la firma Aristas y Vértices:
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador de la arista. |
Para la firma Aristas:
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador de la arista. |
|
|
Identificador del primer vértice de la arista. |
|
|
Identificador del segundo vértice de la arista. |
SQL de vértices¶
Para la firma Aristas y Vértices:
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador del primer vértice de la arista. |
|
|
Arreglo de identificadores de las aristas que tienen el vértice
|
|
|
Arreglo de identificadores de las aristas que tienen el vértice
|
Columnas de resultados¶
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador de vértice |
|
|
Número de aristas incidentes al vértice |
Ejemplos Adicionales¶
Grado de un bucle¶
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)
Usando la firma Aristas.
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)
Grado de un subgrafo¶
Para el siguiente sub-grafo de Datos Muestra:
![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.
Usando la firma Aristas.
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)
Usando una tabla de vértices¶
Para un tamaño de red razonable, es mejor preparar previamente una tabla de vértices y utilizarla en las llamadas a pgr_degree
.
Extraer la información del vértice y almacenar en una tabla:
CREATE TABLE vertices AS
SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, geom FROM edges');
SELECT 17
Calcula el grado de los vértices:
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)
Ejecución de prueba¶
Para obtener la consulta generada que se usa para obtener la información de vértices, utilizar dryrun := true
.
Los resultados se pueden usar como código base para realizar un refinamiento basado en las necesidades de desarrollo de back-end.
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)
Encontrando callejones sin salida¶
Si se tiene una tabla de vértices ya construida usando pgr_extractVertices
y se quiere el grado de todo el grafo en lugar de un subconjunto, se puede trabajar con las columnas in_edges
y out_edges
directamente.
El grado de un sin salida es 1.
Para obtener los callejones sin salida:
SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 1;
id
----
1
5
9
2
4
13
14
(7 rows)
Un callejón sin salida se produce cuando
El vértice es el límite de un callejón sin salida, una vía de no paso o una vía de no salida.
El vértice esta en el limite del grafo importado.
Si se importa un grafo más grande, puede que el vértice no sea un callejón sin salida.
El nodo

¿Es el nodo
![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)
La respuesta a esta pregunta dependerá de la aplicación.
Hay un bordillo tan pequeño:
¿Eso no permite a un vehículo utilizar esa intersección visual?
¿Es la aplicación para peatones y por lo tanto el peatón puede caminar fácilmente en una acera pequeña?
¿Es la aplicación para la electricidad y las líneas eléctricas que se puede extender fácilmente en la parte superior de la acera pequeña?
¿Hay un gran acantilado y desde la vista de las águilas parece que el callejón sin salida está cerca del segmento?
Dependiendo de la respuesta, será necesario la modificación de datos.
Cuando hay muchos callejones sin salida, para acelerar el procesamiento, se pueden utilizar las funciones de Contraction - Familia de funciones para contraer el grafo.
Encontrando vértices lineales¶
El grado de un vértice lineal es 2.
Cuando hay una tabla de vértices construida usando pgr_extractVertices
Para obtener las aristas lineales:
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)
Estos vértices lineales son correctos, por ejemplo, cuando esos vértices son badenes, señales de alto y la aplicación los tiene en cuenta.
Cuando hay muchas aristas lineales, que no necesitan tomarse en cuenta, para acelerar el procesamiento se pueden utilizar las funciones Contraction - Familia de funciones para contraer el grafo.
Ver también¶
Índices y tablas