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

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 |
|
Consulta SQL como se describió anteriormente. |
vértice raíz |
|
Identificador del vértice inicial. |
Inner Queries¶
Edges SQL¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
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 |
---|---|---|
|
|
Valor secuencial a partir de 1. |
vertex_id |
|
Identificador de vértice. |
idom |
|
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¶
“Wikipedia: árbol de dominador” <https://en.wikipedia.org/wiki/Dominator_(graph_theory)>`__
Índices y tablas