Supported versions:
pgr_primDD¶
pgr_primDD
— Nodos de captación mediante el algoritmo de Prim.
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 |
|
Consulta SQL descrita en Inner query. |
Root vid |
|
Identificador del vértice raíz del árbol.
|
Root vids |
|
Arreglo de identificadores de los vértices raíz.
|
Distancia |
|
Límite superior para la inclusión del nodo en el resultado.
|
Donde:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERIC
SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC
Consulta interna¶
Columna |
Tipo |
Valores predeterminados |
Descripción |
---|---|---|---|
id |
|
Identificador de la arista. |
|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
|
cost |
|
Peso de la arista (source, target)
|
|
reverse_cost |
|
-1 |
Peso de la arista (target, source),
|
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 |
|
Valor secuencial a partir de \(1\). |
profundidad |
|
Profundidad del
|
start_vid |
|
Identificador del vértice raíz.
|
node |
|
Identificador del |
edge |
|
Identificador del “”edge”” utilizado para llegar a “”node””.
|
cost |
|
Costo para atravesar |
agg_cost |
|
Costo agregado de |
Ver también¶
Las consultas utilizan la red Datos Muestra .
Índices y tablas