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

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.

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.

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.

ascendente descendente

Ver también

Índices y tablas