Versiones soportadas: Última (3.4) 3.3 3.2

`pgr_depthFirstSearch` - Propusto¶

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 mayor.

No están oficialmente en la versión actual.
Es probable que oficialmente formen parte del próximo lanzamiento:
- Las funciones hacen uso de ENTEROS y FLOTANTES
- Probablemente el nombre no cambie. (Pero todavía puede)
- Es posible que la firma no cambie. (Pero todavía puede)
- Probablemente la funcionalidad no cambie. (Pero todavía puede)
- Se han hecho pruebas con 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:
  - pgr_depthFirstSearch (Vértice único)
  - pgr_depthFirstSearch (Vértices multiples)

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 el recorrido de Búsqueda de Primero 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(SQL de aristas, raíz, [opciones])
pgr_depthFirstSearch(SQL de aristas, raices, [opciones])
options: [directed, max_depth]

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

Vértice único¶

pgr_depthFirstSearch(SQL de aristas, raíz, [opciones])

options: [directed, max_depth]

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

Ejemplo:: Desde el vértice raíz \(6\) en un grafo dirigido con aristas en orden ascendente de id

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

Múltiples vértices¶

pgr_depthFirstSearch(SQL de aristas, raices, [opciones])

options: [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 \(\{12, 6\}\) en un grafo no dirigido con profundidad \(<= 2\) y aristas ordenadas ascendentemente in términos de id

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

Parámetros¶

Parámetro	Tipo	Descripción
SQL de aristas	`TEXT`	SQL de aristas descritas más adelante.
raíz	`BIGINT`	Identificador del vértice raíz del árbol. Cuando el valor es \(0\) se obtiene el bosque de expansión que comienza en nodos aleatorios para cada árbol del bosque.
raices	`ARRAY` [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.

Parámetro

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas descritas más adelante.

raíz

BIGINT

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

Cuando el valor es \(0\) se obtiene el bosque de expansión que comienza en nodos aleatorios para cada árbol del bosque.

raices

ARRAY [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.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
FLOTANTES:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Parámetros opcionales¶

Columna	Tipo	x Defecto	Descripción
`directed`	`BOOLEAN`	`true`	Cuando `true` el gráfo se considera Dirigido Cuando `false` el gráfo se considera No Dirigido.

Parámetros opcionales de DFS¶

Parámetro	Tipo	x Defecto	Descripción
`max_depth`	`BIGINT`	\(9223372036854775807\)	Límite superior para la profundidad del árbol. Cuando negativo arroja error.

Parámetro

Tipo

x Defecto

Descripción

max_depth

BIGINT

\(9223372036854775807\)

Límite superior para la profundidad del árbol.

Cuando negativo arroja error.

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

Ejemplos Adicionales¶

Ejemplo:: Igual que Vértice único pero con aristas en orden descendente de id.

SELECT * FROM pgr_depthFirstSearch(
  'SELECT id, source, target, cost, reverse_cost FROM edges
  ORDER BY id DESC',
  6);
 seq | depth | start_vid | node | edge | cost | agg_cost
-----+-------+-----------+------+------+------+----------
   1 |     0 |         6 |    6 |   -1 |    0 |        0
   2 |     1 |         6 |    7 |    4 |    1 |        1
   3 |     2 |         6 |    8 |   10 |    1 |        2
   4 |     3 |         6 |    9 |   14 |    1 |        3
   5 |     3 |         6 |   12 |   12 |    1 |        3
   6 |     4 |         6 |   17 |   13 |    1 |        4
   7 |     5 |         6 |   16 |   15 |    1 |        5
   8 |     6 |         6 |   15 |   16 |    1 |        6
   9 |     7 |         6 |   10 |    3 |    1 |        7
  10 |     8 |         6 |   11 |    5 |    1 |        8
  11 |     2 |         6 |    3 |    7 |    1 |        2
  12 |     3 |         6 |    1 |    6 |    1 |        3
  13 |     1 |         6 |    5 |    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 identificadores de aristas.

Ver también¶

DFS - Categoría
Datos Muestra
Boost: Documentación del algoritmo de Primera Búsqueda de Profundidad
Boost: Documentación del algoritmo DFS No dirigido
“Wikipedia: Algoritmo de la Primera Búsqueda de Profundidad <https://en.wikipedia.org/wiki/Depth-first_search>`__

Índices y tablas

pgr_depthFirstSearch - Propusto¶

Descripción¶

Firmas¶

Vértice único¶

Múltiples vértices¶

Parámetros¶

Parámetros opcionales¶

Parámetros opcionales de DFS¶

Consultas Internas¶

SQL aristas¶

Columnas de Resultados¶

Ejemplos Adicionales¶

Ver también¶

`pgr_depthFirstSearch` - Propusto¶