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

Soporte

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