pgr_breadthFirstSearch - Experimental

pgr_breadthFirstSearch — Devuelve el recorrido en orden de acuerdo al algoritmo de Búsqueda de Anchura.

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloqueo del servidor

Advertencia

Funciones experimentales

  • No son oficialmente de la versión actual.

  • Es probable que oficialmente no formen parte de la siguiente versión:

    • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

    • El nombre puede cambiar.

    • La firma (declaración de funciones) podría cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden estar ausentes.

    • Posiblemente necesite codificación c/c++.

    • Puede haber carencia de documentación.

    • Hay documentación que, en dado caso, podría ser necesario reescribir.

    • Ejemplos de documentación que puede ser necesario generar automáticamente.

    • Puede ser necesaria más retroalimentación por parte de la comunidad.

    • Puede depender de una función propuesta de pgRouting.

    • Podría depender de una función obsoleta de pgRouting

Disponibilidad

Descripción

Proporciona el orden transversal de Primera Búsqueda de Amplitud desde un vértice raíz hasta una profundidad particular.

Las características principales son:

  • La implementación funcionará en cualquier tipo de grafo.

  • Proporciona el orden transversal de Primera Búsqueda de Amplitud desde un nodo de origen a un nivel de profundidad del objetivo o destino

  • Tiempo de ejecución de la Primera Búsqueda de Anchura: \(O(E + V)\)

Firmas

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])
pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])

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

Vértice Único

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])

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

La Primera Búsqueda de Amplitud transversal con vértice raíz \(2\)

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    2
);
 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 |    5 |    4 |    1 |        1
   4 |     2 |         2 |    8 |    7 |    1 |        2
   5 |     2 |         2 |    6 |    8 |    1 |        2
   6 |     2 |         2 |   10 |   10 |    1 |        2
   7 |     3 |         2 |    7 |    6 |    1 |        3
   8 |     3 |         2 |    9 |    9 |    1 |        3
   9 |     3 |         2 |   11 |   11 |    1 |        3
  10 |     3 |         2 |   13 |   14 |    1 |        3
  11 |     4 |         2 |   12 |   15 |    1 |        4
  12 |     4 |         2 |    4 |   16 |    1 |        4
  13 |     5 |         2 |    3 |    3 |    1 |        5
(13 rows)

Múltiples Vértices

pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])

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

La Primera Búsqueda de Amplitud tranversal comienza en vértices \(\{11, 12\}\) con profundidad \(depth <= 2\)

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    ARRAY[11,12], max_depth := 2
);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |        11 |   11 |   -1 |    0 |        0
   2 |     1 |        11 |   12 |   13 |    1 |        1
   3 |     2 |        11 |    9 |   15 |    1 |        2
   4 |     0 |        12 |   12 |   -1 |    0 |        0
   5 |     1 |        12 |    9 |   15 |    1 |        1
   6 |     2 |        12 |    6 |    9 |    1 |        2
   7 |     2 |        12 |    4 |   16 |    1 |        2
(7 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.

Root vids

ARRAY[ANY-INTEGER]

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

  • Se utiliza en Multiple Vertices.

  • Para fines de optimización, se omite cualquier valor duplicado.

Parámetros opcionales

Parámetro

Tipo

Valores predeterminados

Descripción

max_depth

BIGINT

\(9223372036854775807\)

Límite superior para la profundidad del nodo en el árbol

  • Cuando el valor es Negativo entonces produce error

dirigido

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido

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 Multiple Vertices 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.

Ejemplos Adicionales

Grafo no dirigido

Ejemplo

La Primera Búsqueda de Amplitud transversal desde vértices \(\{11, 12\}\) con profundidad \(depth <= 2\) considerando que el grafo no es dirigido.

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

Vértice Fuera del Grafo

Ejemplo

La salida de la función, cuando un vértice no está presente en el gráfo, se pasa como parámetro.

SELECT * FROM pgr_breadthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
    -10
);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
(0 rows)