pgr_breadthFirstSearch - Experimental

pgr_breadthFirstSearch — Devuelve los orden(es) transversales mediante el algoritmo Breadth First Search.

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloque 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 (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

Descripción

Proporciona el orden transversal de Primera Búsqueda de Amplitud desde un vértice raíz hasta una profundidad particular.

Las características principales son:

  • La implementación funcionará en cualquier tipo de grafo.

  • Provides the Breadth First Search traversal order from a source node to a target depth level.

  • Running time: \(O(E + V)\)

Firmas

Summary

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

Single vertex

pgr_breadthFirstSearch(Edges SQL, Root vid [, max_depth] [, directed])
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_breadthFirstSearch(
  '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 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    8 |   10 |    1 |        2
   7 |     3 |         6 |    1 |    6 |    1 |        3
   8 |     3 |         6 |   16 |    9 |    1 |        3
   9 |     3 |         6 |   12 |   11 |    1 |        3
  10 |     3 |         6 |    9 |   14 |    1 |        3
  11 |     4 |         6 |   17 |   15 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

Multiple vertices

pgr_breadthFirstSearch(Edges SQL, Root vids [, max_depth] [, directed])
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_breadthFirstSearch(
  '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 |     1 |         6 |    7 |    4 |    1 |        1
   5 |     2 |         6 |   15 |    3 |    1 |        2
   6 |     2 |         6 |   11 |    5 |    1 |        2
   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 |     1 |        12 |    8 |   12 |    1 |        1
  12 |     1 |        12 |   17 |   13 |    1 |        1
  13 |     2 |        12 |   10 |    5 |    1 |        2
  14 |     2 |        12 |    7 |    8 |    1 |        2
  15 |     2 |        12 |   16 |    9 |    1 |        2
  16 |     2 |        12 |    9 |   14 |    1 |        2
(16 rows)

Parámetros

Parámetro

Tipo

Descripción

Edges SQL

TEXT

Edges SQL as described below.

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

Optional parameters

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • When true the graph is considered Directed

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

Inner Queries

Edges SQL

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice de la arista.

target

ANY-INTEGER

Identificador del segundo vértice de la arista.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source)

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

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

Costo agregado desde start_vid hasta node.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

ANY-NUMERIC:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT, NUMERIC

Ejemplos Adicionales

Ejemplo:

Same as Single vertex with edges in ascending order of id.

SELECT * FROM pgr_breadthFirstSearch(
  '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 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    8 |   10 |    1 |        2
   7 |     3 |         6 |    1 |    6 |    1 |        3
   8 |     3 |         6 |   16 |    9 |    1 |        3
   9 |     3 |         6 |   12 |   11 |    1 |        3
  10 |     3 |         6 |    9 |   14 |    1 |        3
  11 |     4 |         6 |   17 |   15 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

Ejemplo:

Same as Single vertex with edges in descending order of id.

SELECT * FROM pgr_breadthFirstSearch(
  '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 |     1 |         6 |    5 |    1 |    1 |        1
   4 |     2 |         6 |    8 |   10 |    1 |        2
   5 |     2 |         6 |   11 |    8 |    1 |        2
   6 |     2 |         6 |    3 |    7 |    1 |        2
   7 |     3 |         6 |    9 |   14 |    1 |        3
   8 |     3 |         6 |   12 |   12 |    1 |        3
   9 |     3 |         6 |   16 |    9 |    1 |        3
  10 |     3 |         6 |    1 |    6 |    1 |        3
  11 |     4 |         6 |   17 |   13 |    1 |        4
  12 |     4 |         6 |   15 |   16 |    1 |        4
  13 |     5 |         6 |   10 |    3 |    1 |        5
(13 rows)

The resulting traversal is different.

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

ascending descending

Ver también

Índices y tablas