• Supported versions:

pgr_primDD

pgr_primDD — Nodos de captación mediante el algoritmo de Prim.

Adentro: Boost Graph

Disponibilidad

• Versión 3.0.0

  • Nueva función Oficial

Descripción

Mediante el algoritmo Prim, se extraen los nodos que tienen costes agregados menores o iguales que el valor Distancia dentro del árbol de expansión mínimo calculado.

Las características principales son:

• Su implementación solo está en grafo no dirigido.

• El proceso se realiza sólo en las aristas con costos positivos.

• Cuando el grafo está conectado

  • Las aristas resultantes componen un árbol

• Cuando el grafo no está conectado,

  • Encuentra un árbol de expansión mínimo para cada componente conectado.

  • Las aristas resultantes conforman un bosque.

• Tiempo de ejecución de Prim: \(O(E*log V)\)

• Los nodos de árbol devueltos de un vértice raíz están en el orden de Primera Búsqueda de Profundidad.

• Depth First Search running time: \(O(E + V)\)

Firmas

Resumen

pgr_prim(Edges SQL, root vid, distance)
pgr_prim(Edges SQL, root vids, distance)

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Un solo vértice

pgr_primDD(Edges SQL, root vid, distance)

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Ejemplo

El árbol de expansión mínimo que comienza en el vértice:math:2 con \(agg\_cost <= 3.5\)

SELECT * FROM pgr_primDD(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    2, 3.5
);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         2 |    2 |   -1 |    0 |        0
   2 |     1 |         2 |    1 |    1 |    1 |        1
   3 |     1 |         2 |    3 |    2 |    1 |        1
   4 |     2 |         2 |    4 |    3 |    1 |        2
   5 |     2 |         2 |    6 |    5 |    1 |        2
   6 |     3 |         2 |    9 |    9 |    1 |        3
   7 |     3 |         2 |   11 |   11 |    1 |        3
   8 |     1 |         2 |    5 |    4 |    1 |        1
   9 |     2 |         2 |    8 |    7 |    1 |        2
  10 |     3 |         2 |    7 |    6 |    1 |        3
  11 |     2 |         2 |   10 |   10 |    1 |        2
  12 |     3 |         2 |   13 |   14 |    1 |        3
(12 rows)

Múltiples Vértices

pgr_primDD(Edges SQL, root vids, distance)

RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Ejemplo

El árbol de expansión mínimo que comienza en los vértices \(\{13, 2\}\) con \(agg\_cost <= 3.5\);

SELECT * FROM pgr_primDD(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[13,2], 3.5
);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         2 |    2 |   -1 |    0 |        0
   2 |     1 |         2 |    1 |    1 |    1 |        1
   3 |     1 |         2 |    3 |    2 |    1 |        1
   4 |     2 |         2 |    4 |    3 |    1 |        2
   5 |     2 |         2 |    6 |    5 |    1 |        2
   6 |     3 |         2 |    9 |    9 |    1 |        3
   7 |     3 |         2 |   11 |   11 |    1 |        3
   8 |     1 |         2 |    5 |    4 |    1 |        1
   9 |     2 |         2 |    8 |    7 |    1 |        2
  10 |     3 |         2 |    7 |    6 |    1 |        3
  11 |     2 |         2 |   10 |   10 |    1 |        2
  12 |     3 |         2 |   13 |   14 |    1 |        3
  13 |     0 |        13 |   13 |   -1 |    0 |        0
  14 |     1 |        13 |   10 |   14 |    1 |        1
  15 |     2 |        13 |    5 |   10 |    1 |        2
  16 |     3 |        13 |    2 |    4 |    1 |        3
  17 |     3 |        13 |    8 |    7 |    1 |        3
(17 rows)

Parámetros

Parámetro	Tipo	Descripción
Edges SQL	TEXT	Consulta SQL descrita en Inner query.
Root vid	BIGINT	Identificador del vértice raíz del árbol. Se utiliza en Vértice único En caso de \(0\) se consigue que el bosque de expansión comience en nodos aleatorios para cada árbol.
Root vids	ARRAY[ANY-INTEGER]	Arreglo de identificadores de los vértices raíz. Utilizado en Múltiples Vértices los valores \(0\) son ignorados Para fines de optimización, se omite cualquier valor duplicado.
Distancia	ANY-NUMERIC	Límite superior para la inclusión del nodo en el resultado. Cuando el valor es Negativo arroja error

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Consulta interna

Columna	Tipo	Valores predeterminados	Descripción
id	ANY-INTEGER		Identificador de la arista.
origen	ANY-INTEGER		Identificador del primer punto final en el vértice de la arista.
objetivo	ANY-INTEGER		Identificador del segundo punto final en el vértice de la arista.
cost	ANY-NUMERICAL		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	ANY-NUMERICAL	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

devuelve el conjunto SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	BIGINT	Valor secuencial a partir de \(1\).
profundidad	BIGINT	Profundidad del nodo. \(0\) cuando node = start_vid.
start_vid	BIGINT	Identificador del vértice raíz. En Múltiples Vértices los resultados están en orden ascendente.
node	BIGINT	Identificador del node alcanzado usando edge.
edge	BIGINT	Identificador del “”edge”” utilizado para llegar a “”node””. \(-1\) cuando node = start_vid.
cost	FLOAT	Costo para atravesar edge.
agg_cost	FLOAT	Costo agregado de start_vid a node.

Ver también

• Árbol de expansión - Categoría

• Prim - Familia de funciones

• Las consultas utilizan la red Datos Muestra .

• Boost: Prim’s algorithm documentation

• Wikipedia: algoritmo de Prim

Índices y tablas

• Índice

• Página de Búsqueda