pgr_prim

pgr_prim — Bosque de expansión de grafo mínimo, utilizando el algoritmo Prim.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0
    • Nueva función Oficial

Soporte

  • Supported versions:

Descripción

Este algoritmo encuentra el bosque de expansión mínimo en un grafo posiblemente desconectado usando el algoritmo de Prim.

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)\)
  • EMPTY SET es regresado cuando no hay aristas en el grafo

Firmas

Resumen

pgr_prim(edges_sql)

RETURNS SET OF (edge, cost)
OR EMPTY SET
Ejemplo:Bosque de Expansión Mínimo de un subgrafo 
SELECT edge, cost FROM pgr_prim(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table WHERE id < 14'
) ORDER BY edge;
 edge | cost
------+------
    1 |    1
    2 |    1
    3 |    1
    4 |    1
    5 |    1
    6 |    1
    7 |    1
    9 |    1
   10 |    1
   11 |    1
   13 |    1
(11 rows)

Parámetros

Parámetro Tipo Descripción
Edges SQL TEXT Consulta SQL descrita en Inner query.

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 SET OF (conjunto de) (edge, cost)

Columna Tipo Descripción
edge BIGINT Identificador de la arista.
cost FLOAT Coste para atravezar el borde.