pgr_depthFirstSearch - Experimental¶
pgr_depthFirstSearch
— Devuelve un recorrido de búsqueda de profundidad del grafo. El grafo puede ser dirigido o no dirigido.
![_images/boost-inside.jpeg](_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 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 |
|
Consulta SQL descrita en Inner query. |
Root vid |
|
Identificador del vértice raíz del árbol.
|
Root vids |
|
Arreglo de identificadores de los vértices raíz.
|
Parámetros opcionales¶
Parámetro |
Tipo |
Valores predeterminados |
Descripción |
---|---|---|---|
dirigido |
|
|
|
max_depth |
|
\(9223372036854775807\) |
Límite superior para la profundidad del recorrido
|
Consulta interna¶
Edges SQL
Columna |
Tipo |
Valores predeterminados |
Descripción |
---|---|---|---|
id |
|
Identificador de la arista. |
|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
|
cost |
|
|
|
reverse_cost |
|
-1 |
|
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 |
|
Valor secuencial a partir de \(1\). |
profundidad |
|
Profundidad del
|
start_vid |
|
Identificador del vértice raíz.
|
node |
|
Identificador del |
edge |
|
Identificador del “”edge”” utilizado para llegar a “”node””.
|
cost |
|
Costo para atravesar |
agg_cost |
|
Costo agregado de |
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
“Wikipedia: Algoritmo de la Primera Búsqueda de Profundidad <https://en.wikipedia.org/wiki/Depth-first_search>`__
Índices y tablas