Supported versions: Latest (3.4) 3.3 3.2

`pgr_depthFirstSearch` - Proposed¶

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
- 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 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
- New experimental signatures:
  - pgr_depthFirstSearch (Single Vertex)
  - pgr_depthFirstSearch (Multiple Vertices)

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)

Vértice único¶

pgr_depthFirstSearch(Edges SQL, Root vid [, directed] [, max_depth])
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Ejemplo:: From root vertex \(6\) on a directed graph with edges in ascending order of 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(Edges SQL, Root vids [, directed] [, max_depth])
RETURNS SET OF (seq, depth, start_vid, node, edge, cost, agg_cost)

Ejemplo:: From root vertices \(\{12, 6\}\) on an undirected graph with depth \(<= 2\) and edges in ascending order of 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 Aristas	`TEXT`	SQL Aristas descritas más adelante.
Raíz	`BIGINT`	Identificador del vértice raíz del árbol. When value is \(0\) then gets the spanning forest starting in aleatory nodes for each tree in the forest.
Raíces	`ARREGLO[ENTEROS]`	Arreglo de identificadores de los vértices raíz. \(0\) values are ignored Con el propósito de optimización, valores duplicados son ignorados.

Parámetro

Tipo

Descripción

SQL Aristas

TEXT

SQL Aristas descritas más adelante.

Raíz

BIGINT

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

When value is \(0\) then gets the spanning forest starting in aleatory nodes for each tree in the forest.

Raíces

ARREGLO[ENTEROS]

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

\(0\) values are ignored
Con el propósito de optimización, valores duplicados son ignorados.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
ANY-NUMERIC:: 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.

DFS optional parameters¶

Parámetro	Tipo	x Defecto	Descripción
`max_depth`	`BIGINT`	\(9223372036854775807\)	Upper limit of the depth of the tree. When negative throws an error.

Parámetro

Tipo

x Defecto

Descripción

max_depth

BIGINT

\(9223372036854775807\)

Upper limit of the depth of the tree.

When negative throws an error.

Consultas internas¶

SQL de 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

Return columns¶

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\) when `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\) when `node` = `start_vid`.
`cost`	`FLOAT`	Costo por recorrer `edge`.
`agg_cost`	`FLOAT`	Coste agregado desde `start_vid` al `node`.

Donde:

ENTEROS:: SMALLINT, INTEGER, BIGINT
ANY-NUMERIC:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Ejemplos Adicionales¶

Ejemplo:: Same as Single vertex but with edges in descending order of 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.

The left image shows the result with ascending order of ids and the right image shows with descending order of the edge identifiers.

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 - Proposed¶

Descripción¶

Firmas¶

Vértice único¶

Múltiples vértices¶

Parámetros¶

Parámetros opcionales¶

DFS optional parameters¶

Consultas internas¶

SQL de aristas¶

Return columns¶

Ejemplos Adicionales¶

Ver también¶

`pgr_depthFirstSearch` - Proposed¶