1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
..
****************************************************************************
pgRouting Manual
Copyright(c) pgRouting Contributors
This documentation is licensed under a Creative Commons Attribution-Share
Alike 3.0 License: https://creativecommons.org/licenses/by-sa/3.0/
****************************************************************************
|
* **Supported versions:**
`Latest <https://docs.pgrouting.org/latest/en/pgr_transitiveClosure.html>`__
(`3.4 <https://docs.pgrouting.org/3.4/en/pgr_transitiveClosure.html>`__)
`3.3 <https://docs.pgrouting.org/3.3/en/pgr_transitiveClosure.html>`__
`3.2 <https://docs.pgrouting.org/3.2/en/pgr_transitiveClosure.html>`__
`3.1 <https://docs.pgrouting.org/3.1/en/pgr_transitiveClosure.html>`__
`3.0 <https://docs.pgrouting.org/3.0/en/pgr_transitiveClosure.html>`__
``pgr_transitiveClosure`` - Experimental
===============================================================================
``pgr_transitiveClosure`` — Transitive closure graph of a directed graph.
.. figure:: images/boost-inside.jpeg
:target: https://www.boost.org/libs/graph/doc/transitive_closure.html
Boost Graph Inside
.. include:: experimental.rst
:start-after: begin-warn-expr
:end-before: end-warn-expr
.. rubric:: 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 :doc:`pgr_connectedComponents`)
* The returned values are not ordered
* The returned graph is compresed
* Running time: :math:`O(|V||E|)`
Signatures
-------------------------------------------------------------------------------
.. rubric:: Summary
The pgr_transitiveClosure function has the following signature:
.. index::
single: transitiveClosure - Experimental on v3.0
.. admonition:: \ \
:class: signatures
| pgr_transitiveClosure(`Edges SQL`_)
| RETURNS SET OF |result-closure|
:Example: Rechability of a subgraph
.. literalinclude:: doc-transitiveClosure.queries
:start-after: -- q1
:end-before: -- q2
Parameters
-------------------------------------------------------------------------------
.. include:: pgRouting-concepts.rst
:start-after: only_edge_param_start
:end-before: only_edge_param_end
Inner Queries
-------------------------------------------------------------------------------
Edges SQL
...............................................................................
.. include:: pgRouting-concepts.rst
:start-after: basic_edges_sql_start
:end-before: basic_edges_sql_end
Result Columns
-------------------------------------------------------------------------------
RETURNS SET OF |result-closure|
.. list-table::
:width: 81
:widths: auto
:header-rows: 1
* - Column
- Type
- Description
* - ``seq``
- ``INTEGER``
- Sequential value starting from :math:`1`
* - ``vid``
- ``BIGINT``
- Identifier of the source of the edges
* - ``target_array``
- ``BIGINT``
- Identifiers of the targets of the edges
* Identifiers of the vertices that are reachable from vertex v.
See Also
-------------------------------------------------------------------------------
* :doc:`sampledata`
* https://en.wikipedia.org/wiki/Transitive_closure
.. rubric:: Indices and tables
* :ref:`genindex`
* :ref:`search`
|
