pgr_degree

pgr_degree - Para cada vértice de un grafo no dirigido, devuelve el número de aristas incidentes en el vértice.

Proposed

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

Version 3.8.0

• Error messages adjustment.

• New signature with only Edges SQL.

• Function promoted to official.

Versión 3.4.0

• New proposed function.

Descripción

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.

• Funciona para grafos no dirigidos.

• 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.

Firmas

pgr_degree(Edges SQL , [dryrun])

pgr_degree(SQL de aristas , SQL de vértices, [dryrun])

REGRESA CONJUNTO DE (node, degree)

O CONJUNTO VACÍO

Edges

pgr_degree(Edges SQL , [dryrun])

REGRESA CONJUNTO DE (node, degree)

O CONJUNTO VACÍO

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(SQL de aristas , SQL de vértices, [dryrun])

REGRESA CONJUNTO DE (node, degree)

O CONJUNTO VACÍO

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)

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)

Parámetros

Parámetro	Tipo	Descripción
SQL de aristas	TEXT	SQL de aristas como se describe a continuación
SQL de vértices	TEXT	Vertex SQL como se describe abajo

Parámetros opcionales

Parámetro	Tipo	x Defecto	Descripción
dryrun	BOOLEAN	false	Cuando verdadero, no procesar y recibir un AVISO de la consulta resultante.

Consultas Internas

SQL aristas

For the Edges and Vertices signature:

Columna	Tipo	Descripción
id	BIGINT	Identificador de la arista.

For the Edges signature:

Columna	Tipo	Descripción
id	BIGINT	Identificador de la arista.
source	BIGINT	Identificador del primer vértice de la arista.
target	BIGINT	Identificador del segundo vértice de la arista.

SQL de vértices

For the Edges and Vertices signature:

Columna	Tipo	Descripción
id	BIGINT	Identificador del primer vértice de la arista.
in_edges	BIGINT[]	Arreglo de identificadores de las aristas que tienen el vértice id como primer punto final. Si falta, out_edges debe existir.
out_edges	BIGINT[]	Arreglo de identificadores de las aristas que tienen el vértice id como segundo punto final. Si falta, in_edges debe existir.

Columnas de resultados

Columna	Tipo	Descripción
node	BIGINT	Identificador de vértice
degree	BIGINT	Número de aristas incidentes al vértice id

Ejemplos Adicionales

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)

Grado de un subgrafo

For the following is a subgraph of the Datos Muestra:

• \(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)

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)

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.

Para obtener los callejones sin salida:

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.

• 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?

Depending on the answer, modification of the data might be needed.

When there are many dead ends, to speed up processing, the Contraction - Familia de funciones 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

Para obtener las aristas lineales:

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 Contraction - Familia de funciones functions can be used to contract the problem.

Ver también

• Topología - Familia de Funciones

• pgr_extractVertices

Índices y tablas

• Índice

• Página de Búsqueda