pgr_transitiveClosure - Experimental - pgRouting Manual (3.0)
![Logo](images/pgrouting.png)
pgr_transitiveClosure - Experimental
pgr_transitiveClosure
- Returns the transitive closure graph of the input graph.
In particular, the transitive closure algorithm implemented by Boost.Graph.
![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.0.0
-
New experimental function
-
Support
-
Supported versions: current( 3.0 )
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(VE)\)
-
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