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

  • Versión 3.2.0

    • Nueva función experimental

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)
RETURNS SET OF (seq, vertex_id, idom)
OR EMPTY SET
Ejemplo:

The dominator tree with root vertex \(5\)

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

Parámetros

Columna

Tipo

Descripción

SQL de aristas

TEXT

Consulta SQL como se describió anteriormente.

vértice raíz

BIGINT

Identificador del vértice inicial.

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

Columnas de Resultados

Returns set of (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

Ejemplo:

Dominator tree of another component.

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

Ver también

Índices y tablas