pgr_lengauerTarjanDominatorTree -Experimental

pgr_lengauerTarjanDominatorTree — Devuelve el dominador inmediato de todos los vértices.

_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

Soporte

  • Versiones soportadas: actual(3.2)

Descripción

El algoritmo calcula el dominador inmediato de cada vértice llamado idom, una vez que se calcula la idom de cada vértice y, a continuación, haciendo que cada idom de cada vértice como su elemento primario, se pueda construir el árbol del dominador.

Las características principales son:

  • El algoritmo solo funciona en el grafo dirigido.

  • Los valores devueltos no están ordenados.

  • El algoritmo devuelve idom de cada vértice.

  • Si el vértice raíz no está presente en el grafo, devuelve un conjunto vacío.

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

Firmas

Resumen

pgr_lengauerTarjanDominatorTree(Edges SQL, root vertex) -- Experimental on v3.2
RETURNS SET OF (seq, vertex_id, idom)
OR EMPTY SET
Ejemplo

El lengauerTarjanDominatorTree con vértice raíz \(1\)

SELECT * FROM pgr_lengauertarjandominatortree(
    $$SELECT id,source,target,cost,reverse_cost FROM edge_table$$,
    1
);
 seq | vertex_id | idom
-----+-----------+------
   1 |         1 |    0
   2 |         2 |    1
   3 |         3 |    4
   4 |         4 |    9
   5 |         5 |    2
   6 |         6 |    5
   7 |         7 |    8
   8 |         8 |    5
   9 |         9 |    5
  10 |        10 |    5
  11 |        11 |    5
  12 |        12 |    5
  13 |        13 |   10
  14 |        14 |    0
  15 |        15 |    0
  16 |        16 |    0
  17 |        17 |    0
(17 rows)

Parámetros

Columna

Tipo

Descripción

Edges SQL

TEXT

Consulta SQL como se describió anteriormente.

vértice raíz

BIGINT

Identificador del vértice inicial.

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 el conjunto de (seq, vertex_id,idom)

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

vertex_id

BIGINT

Identificador de vértice.

idom

BIGINT

Dominador inmediato del vértice.

Ejemplos Adicionales

Los ejemplos de esta sección utilizan lo siguiente Se utilizan redes para consultas marcadas como directed , cost y reverse_cost

Ejemplo

Cuando la arista se desconecte del grafo, entonces devolverá el dominador inmidiate de todos los demás vértices como cero.

SELECT * FROM pgr_lengauertarjandominatortree(
    $$SELECT id,source,target,cost,reverse_cost FROM edge_table$$,
    16
);
 seq | vertex_id | idom
-----+-----------+------
   1 |         1 |    0
   2 |         2 |    0
   3 |         3 |    0
   4 |         4 |    0
   5 |         5 |    0
   6 |         6 |    0
   7 |         7 |    0
   8 |         8 |    0
   9 |         9 |    0
  10 |        10 |    0
  11 |        11 |    0
  12 |        12 |    0
  13 |        13 |    0
  14 |        14 |    0
  15 |        15 |    0
  16 |        16 |    0
  17 |        17 |   16
(17 rows)