pgr_transitiveClosure - Experimental¶
pgr_transitiveClosure
— Returns the transitive closure graph of the input graph.
In particular, the transitive closure algorithm implemented by Boost.Graph.
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.0.0
New experimental function
Description¶
The transitive_closure() function transforms the input graph g into the transitive closure graph tc.
This implementation can only be used with a directed graph with no cycles i.e. directed acyclic graph.
- The main characteristics are:
Process is valid for directed acyclic graphs only. otherwise it will throw warnings.
The returned values are not ordered:
Running time: \(O(|V||E|)\)
Signatures¶
Summary
The pgr_transitiveClosure function has the following signature:
pgr_transitiveClosure(Edges SQL)
RETURNS SETOF (id, vid, target_array)
- Example
Complete Graph of 3 vertexs
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)
Parameters¶
Column |
Type |
Description |
---|---|---|
Edges SQL |
|
SQL query as described in Inner query |
Inner query¶
Column |
Type |
Default |
Description |
---|---|---|---|
id |
|
Identifier of the edge. |
|
source |
|
Identifier of the first end point vertex of the edge. |
|
target |
|
Identifier of the second end point vertex of the edge. |
|
cost |
|
Weight of the edge (source, target)
|
|
reverse_cost |
|
-1 |
Weight of the edge (target, source),
|
Where:
- ANY-INTEGER
SMALLINT, INTEGER, BIGINT
- ANY-NUMERICAL
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Result Columns¶
RETURNS SETOF (seq, vid, target_array)
The function returns a single row. The columns of the row are:
Column |
Type |
Description |
---|---|---|
seq |
|
Sequential value starting from 1. |
vid |
|
Identifier of the vertex. |
target_array |
|
Array of identifiers of the vertices that are reachable from vertex v. |
Additional Examples¶
- Example
Some sub graphs of the sample data
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)
See Also¶
The queries use the Sample Data network.
Indices and tables