pgr_kruskalDD

pgr_kruskalDD — Nodos de captación utilizando el algoritmo de Kruskal.

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.0.0

    • Nueva función Oficial

Descripción

Usando el algoritmo de Kruskal, extraerá los nodos que tienen costos agregados menores o iguales a la distancia desde un vértice (o vértices) raíz dentro del árbol de expansión mínimo calculado.

Las características principales son:

  • Su implementación es solo para grafo no dirigido.

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

  • Cuando el grafo es 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.

  • Se minimiza el peso total de todos los bordes del árbol o bosque.

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

  • Extrae todos los nodos que tienen costos menor o igual al valor de la distancia.

  • Las aristas extraídas conformarán el correspondiente árbol de expansión.

  • Arista \((u, v)\) no se incluye cuando:

    • La distancia de la raiz a:math:u > límite de la distancia.

    • La distancia de la raiz a \(v\) > límite de la distancia.

    • No se crean nuevos nodos en el grafo, por lo que cuando el vértice está dentro de los límites y parte de la arista no está dentro de los límites, la arsta no se incluye.

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

  • Primera Búsqueda de Profundidad, tiempo de ejecución: \(O(E + V)\)

Firmas

pgr_kruskalDD(SQL de aristas, raíz, distancia)
pgr_kruskalDD(SQL de aristas, raices, distancia)
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Vértice único

pgr_kruskalDD(SQL de aristas, raíz, distancia)
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)
Ejemplo:

El mínimo árbol de expansión que comienza en el vértice:math:6 con \(distance \leq 3.5\)

SELECT * FROM pgr_kruskalDD(
  'SELECT id, source, target, cost, reverse_cost FROM edges ORDER BY id',
  6, 3.5);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    5 |    1 |    1 |        1
   3 |     1 |         6 |   10 |    2 |    1 |        1
   4 |     2 |         6 |   15 |    3 |    1 |        2
   5 |     3 |         6 |   16 |   16 |    1 |        3
(5 rows)

Múltiples vértices

pgr_kruskalDD(SQL de aristas, raices, distancia)
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 \(\{9, 6\}\) con \(distance \leq 3.5\)

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

Parámetros

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describen abajo.

id raíz

BIGINT

Identificador del vértice raíz del árbol.

Raíces

ARREGLO[ENTEROS]

Arreglo de identificadores de los vértices raíz.

  • Valores \(0\) son ignorados

  • Con el propósito de optimización, valores duplicados son ignorados.

distancia

FLOAT

Límite superior para la inclusión del nodo en el resultado.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Consultas Internas

SQL aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

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

Parámetro

Tipo

Descripción

seq

BIGINT

Valor secuencial a partir de \(1\).

depth

BIGINT

Profundidad del node.

  • \(0\) cuando node = start_vid.

start_vid

BIGINT

Identificador del vértice raíz.

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 por recorrer edge.

agg_cost

FLOAT

Costo agregado desde start_vid hasta node.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Ver también

Índices y tablas