pgr_transitiveClosure
- Experimental¶
pgr_transitiveClosure
— Transitive closure graph of a directed 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¶
Transforms the input directed graph into the transitive closure of the graph.
The main characteristics are:
- Process is valid for directed graphs.
- The transitive closure of an undirected graph produces a cluster graph
- Reachability between vertices on an undirected graph happens when they belong to the same connected component. (see pgr_connectedComponents)
- The returned values are not ordered
- The returned graph is compresed
- Running time: \(O(|V||E|)\)
Signatures¶
Summary
The pgr_transitiveClosure function has the following signature:
pgr_transitiveClosure(Edges SQL) RETURNS SETOF (seq, vid, target_array)
Example: | Rechability of a subgraph |
---|
SELECT * FROM pgr_transitiveclosure(
'SELECT id, source, target, cost, reverse_cost
FROM edges WHERE id IN (2, 3, 5, 11, 12, 13, 15)')
ORDER BY vid;
seq | vid | target_array
-----+-----+--------------------
1 | 6 | {}
6 | 8 | {12,17,16}
2 | 10 | {12,17,16,11,6}
4 | 11 | {12,17,16}
5 | 12 | {17,16}
3 | 15 | {12,17,16,10,11,6}
8 | 16 | {17,16}
7 | 17 | {17,16}
(8 rows)
Inner Queries¶
Edges SQL¶
Column | Type | Default | Description |
---|---|---|---|
id |
ANY-INTEGER | Identifier of the edge. | |
source |
ANY-INTEGER | Identifier of the first end point vertex of the edge. | |
target |
ANY-INTEGER | Identifier of the second end point vertex of the edge. | |
cost |
ANY-NUMERICAL | Weight of the edge (source , target ) |
|
reverse_cost |
ANY-NUMERICAL | -1 | Weight of the edge (
|
Where:
ANY-INTEGER: | SMALLINT , INTEGER , BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT , INTEGER , BIGINT , REAL , FLOAT |
Result Columns¶
RETURNS SETOF (seq, vid, target_array)
Column | Type | Description |
---|---|---|
seq |
INTEGER |
Sequential value starting from \(1\) |
vid |
BIGINT |
Identifier of the source of the edges |
target_array |
BIGINT |
Identifiers of the targets of the edges
|
See Also¶
Indices and tables