pgr_depthFirstSearch - Experimental

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

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 o 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

• 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]) -- Experimental on v3.2
pgr_depthFirstSearch(Edges SQL, Root vids [, directed] [, max_depth]) -- Experimental on v3.2

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. Se utiliza en Single Vertex.
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. En Múltiples Vértices 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

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:

Ver también

• Las consultas utilizan la red 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

• Índice

• Página de Búsqueda