pgr_lengauerTarjanDominatorTree -Experimental - pgRouting Manual (3.3)
![Logo](images/pgrouting.png)
pgr_lengauerTarjanDominatorTree -Experimental
pgr_lengauerTarjanDominatorTree
- Returns the immediate dominator of all
vertices.
![images/boost-inside.jpeg](images/boost-inside.jpeg)
Warning
Possible server crash
-
These functions might create a server crash
Warning
Experimental functions
-
They are not officially of the current release.
-
They likely will not be officially be part of the next release:
-
The functions might not make use of ANY-INTEGER and ANY-NUMERICAL
-
Name might change.
-
Signature might change.
-
Functionality might change.
-
pgTap tests might be missing.
-
Might need c/c++ coding.
-
May lack documentation.
-
Documentation if any might need to be rewritten.
-
Documentation examples might need to be automatically generated.
-
Might need a lot of feedback from the comunity.
-
Might depend on a proposed function of pgRouting
-
Might depend on a deprecated function of pgRouting
-
Availability
-
Version 3.2.0
-
New experimental function
-
Description
The algorithm calculates the immidiate dominator of each vertex called idom , once idom of each vertex is calculated then by making every idom of each vertex as its parent, the dominator tree can be built.
The main Characteristics are:
-
The algorithm works in directed graph only.
-
The returned values are not ordered.
-
The algorithm returns idom of each vertex.
-
If the root vertex not present in the graph then it returns empty set.
-
Running time: \(O((V+E)log(V+E))\)
Signatures
Summary
(seq,
vertex_id,
idom)
- Example :
-
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)
Parameters
Column |
Type |
Description |
---|---|---|
|
SQL query as described above. |
|
root vertex |
|
Identifier of the starting vertex. |
Inner Queries
Edges SQL
Column |
Type |
Default |
Description |
---|---|---|---|
|
ANY-INTEGER |
Identifier of the edge. |
|
|
ANY-INTEGER |
Identifier of the first end point vertex of the edge. |
|
|
ANY-INTEGER |
Identifier of the second end point vertex of the edge. |
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Where:
- ANY-INTEGER :
-
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL :
-
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Result Columns
Returns set of
(seq,
vertex_id,
idom)
Column |
Type |
Description |
---|---|---|
|
|
Sequential value starting from 1 . |
|
|
Identifier of vertex . |
|
|
Immediate dominator of vertex. |
Additional Examples
- Example :
-
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)
See Also
Indices and tables