pgr_transitiveClosure - Experimental

pgr_transitiveClosure — Devuelve el grafo de cierre transitivo del grafo de entrada. En particular, el algoritmo de cierre transitivo implementado por Boost.Graph.

_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 (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.0.0

    • Nueva función experimental

Descripción

La función transitive_closure() transforma el grafo de entrada g en el grafo de cierre transitivo tc.

Esta implementación solo se puede utilizar con un grafo dirigido sin ciclos i.e., es decir, un grafo acíclico dirigido.

Las principales características son:

  • El proceso solo es válido para grafos acíclicos dirigidos. de lo contrario lanzará advertencias.

  • Los valores devueltos no se ordenan:

  • Tiempo de ejecución: \(O(|V||E|)\)

Firmas

Resumen

La función pgr_transitiveClosure tiene la siguiente firma:

pgr_transitiveClosure(Edges SQL)
RETURNS SETOF (id, vid, target_array)
Ejemplo

Grafo Completo de 3 vértices

SELECT * FROM pgr_transitiveclosure(
  'SELECT id,source,target,cost,reverse_cost FROM edge_table1'
);
 seq | vid | target_array
-----+-----+--------------
   1 |   0 | {1,3,2}
   2 |   1 | {3,2}
   3 |   3 | {2}
   4 |   2 | {}
(4 rows)

Parámetros

Columna

Tipo

Descripción

Edges SQL

TEXT

Consulta SQL como se describe en Inner query

Consulta interna

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

Peso de la arista (source, target)

  • Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.

reverse_cost

ANY-NUMERICAL

-1

Peso de la arista (target, source),

  • En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

DEVUELVE UN CONJUNTO DE (seq, vid, target_array)

La función devuelve una sola fila. Las columnas de la fila son:

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

vid

BIGINT

Identificador del vértice.

target_array

ARRAY[BIGINT]

Arreglo de identificadores de los vértices a los que se puede acceder desde el vértice v.

Ejemplos Adicionales

Ejemplo

Algunos subgrafos de los datos de muestra

SELECT * FROM pgr_transitiveclosure(
  'SELECT id,source,target,cost,reverse_cost FROM edge_table where id=2'
);
 seq | vid | target_array
-----+-----+--------------
   1 |   2 | {}
   2 |   3 | {2}
(2 rows)

SELECT * FROM pgr_transitiveclosure(
  'SELECT id,source,target,cost,reverse_cost FROM edge_table where id=3'
);
 seq | vid | target_array
-----+-----+--------------
   1 |   3 | {}
   2 |   4 | {3}
(2 rows)

SELECT * FROM pgr_transitiveclosure(
  'SELECT id,source,target,cost,reverse_cost FROM edge_table where id=2 or id=3'
);
 seq | vid | target_array
-----+-----+--------------
   1 |   2 | {}
   2 |   3 | {2}
   3 |   4 | {3,2}
(3 rows)

SELECT * FROM pgr_transitiveclosure(
  'SELECT id,source,target,cost,reverse_cost FROM edge_table where id=11'
);
 seq | vid | target_array
-----+-----+--------------
   1 |   6 | {11}
   2 |  11 | {}
(2 rows)

/* -- q3 */
SELECT * FROM pgr_transitiveclosure(
  'SELECT id,source,target,cost,reverse_cost FROM edge_table where cost=-1 or reverse_cost=-1'
);
 seq | vid | target_array
-----+-----+---------------
   1 |   2 | {}
   2 |   3 | {11,12,6,2}
   3 |   4 | {11,12,3,6,2}
   4 |   6 | {11,12}
   5 |  11 | {12}
   6 |  10 | {11,12}
   7 |  12 | {}
(7 rows)

Ver también

Índices y tablas