pgr_depthFirstSearch - Propuesto

pgr_depthFirstSearch — Devuelve un recorrido de búsqueda de profundidad del grafo. El grafo puede ser dirigido o no dirigido.

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Funciones propuestas para la próxima versión.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte de la próxima versión:

    • Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL

    • Es posible que el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Es posible que la funcionalidad no cambie. (Pero todavía puede)

    • Se han hecho pruebas de pgTap. Pero tal vez se necesiten más.

    • Es posible que la documentación necesite un refinamiento.

Disponibilidad

  • Versión 3.3.0

    • Promovido a función propuesta

  • Versión 3.2.0

    • Nueva función experimental

Descripción

El algoritmo de Primera Búsqueda de Profundidad es un algoritmo de recorrido que comienza desde un vértice raíz, va lo más profundo posible y retrocede una vez que se alcanza un vértice sin vértices adyacentes o con todos los vértices adyacentes visitados. El recorrido continúa hasta que se visitan todos los vértices accesibles desde el vértice raíz.

Las características principales son:

  • La implementación funciona para los grafos dirigidos y no dirigidos.

  • Proporciona la orden del recorrido de Primera Búsqueda de Profundidad desde un vértice raíz o desde un conjunto de vértices raíz.

  • Un parámetro opcional de profundidad máxima no negativo para limitar los resultados hasta una profundidad particular.

  • Para fines de optimización, se omiten los valores duplicados en los Root vids.

  • No produce la ruta más corta desde un vértice de origen a un vértice de destino.

  • No se garantiza que el coste agregado del recorrido sea mínimo.

  • Los valores devueltos se ordenan en orden ascendente de start_vid.

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

Firmas

Resumen

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

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

Uso de valores predeterminados

Ejemplo

Desde el vértice raíz \(2\) en un grafo dirigido

SELECT * FROM pgr_depthFirstSearch(
    '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 |     3 |         2 |    7 |    6 |    1 |        3
   6 |     2 |         2 |    6 |    8 |    1 |        2
   7 |     3 |         2 |    9 |    9 |    1 |        3
   8 |     4 |         2 |   12 |   15 |    1 |        4
   9 |     4 |         2 |    4 |   16 |    1 |        4
  10 |     5 |         2 |    3 |    3 |    1 |        5
  11 |     3 |         2 |   11 |   11 |    1 |        3
  12 |     2 |         2 |   10 |   10 |    1 |        2
  13 |     3 |         2 |   13 |   14 |    1 |        3
(13 rows)

Un solo vértice

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

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

Desde el vértice raíz \(2\) en un grafo no dirigido, con \(depth <= 2\)

SELECT * FROM pgr_depthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id',
    2, directed => false, max_depth => 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 |    3 |    2 |    1 |        1
   4 |     2 |         2 |    4 |    3 |    1 |        2
   5 |     2 |         2 |    6 |    5 |    1 |        2
   6 |     1 |         2 |    5 |    4 |    1 |        1
   7 |     2 |         2 |    8 |    7 |    1 |        2
   8 |     2 |         2 |   10 |   10 |    1 |        2
(8 rows)

Múltiples vértices

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

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

A partir de los vértices de la raíz \(\{11, 2\}\) en un grafo no dirigido con \(depth <= 2\)

SELECT * FROM pgr_depthFirstSearch(
    'SELECT id, source, target, cost, reverse_cost FROM edge_table
    ORDER BY id',
    ARRAY[11, 2], directed => false, max_depth => 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 |    3 |    2 |    1 |        1
   4 |     2 |         2 |    4 |    3 |    1 |        2
   5 |     2 |         2 |    6 |    5 |    1 |        2
   6 |     1 |         2 |    5 |    4 |    1 |        1
   7 |     2 |         2 |    8 |    7 |    1 |        2
   8 |     2 |         2 |   10 |   10 |    1 |        2
   9 |     0 |        11 |   11 |   -1 |    0 |        0
  10 |     1 |        11 |    6 |   11 |    1 |        1
  11 |     2 |        11 |    3 |    5 |    1 |        2
  12 |     2 |        11 |    5 |    8 |    1 |        2
  13 |     2 |        11 |    9 |    9 |    1 |        2
  14 |     1 |        11 |   10 |   12 |    1 |        1
  15 |     2 |        11 |   13 |   14 |    1 |        2
  16 |     1 |        11 |   12 |   13 |    1 |        1
(16 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

dirigido

BOOLEAN

true

  • En caso de true el grafo es Dirigido

  • When false the graph is Undirected.

max_depth

BIGINT

\(9223372036854775807\)

Límite superior para la profundidad del recorrido

  • Cuando el valor es Negativo entonces produce error

Consulta interna

Edges SQL

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

  • Cuando es positivo: el borde (origen, destino) existe en el grafo.

  • Cuando es negativo: el borde (origen, desitno) no existe en el grafo.

reverse_cost

ANY-NUMERICAL

-1

  • Cuando es positivo: el borde (origen, destino) existe en el grafo.

  • Cuando es negativo: el borde (destino, origen) no existe en el 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.

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

Los ejemplos de esta sección se basan en la red Datos Muestra.

Ejemplo: No hay orden interno en el recorrido

En la siguiente consulta, la consulta interna del ejemplo: «Uso de valores predeterminados» se modifica para que los datos se introducen en el algoritmo se proporciona en el orden inverso del identificador.

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

El recorrido resultante es diferente.

La imagen izquierda muestra el resultado con el orden ascendente de los ids y la imagen derecha muestra con el orden descendente de los ids:

ascendente descendente

Ver también

Índices y tablas