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
135
136
137
138
139
140
141
142
143
144
|
..
****************************************************************************
pgRouting Manual
Copyright(c) pgRouting Contributors
This documentation is licensed under a Creative Commons Attribution-Share
Alike 3.0 License: http://creativecommons.org/licenses/by-sa/3.0/
****************************************************************************
|
* **Supported versions:**
`Latest <https://docs.pgrouting.org/latest/en/pgr_topologicalSort.html>`__
(`3.4 <https://docs.pgrouting.org/3.4/en/pgr_topologicalSort.html>`__)
`3.3 <https://docs.pgrouting.org/3.3/en/pgr_topologicalSort.html>`__
`3.2 <https://docs.pgrouting.org/3.2/en/pgr_topologicalSort.html>`__
`3.1 <https://docs.pgrouting.org/3.1/en/pgr_topologicalSort.html>`__
`3.0 <https://docs.pgrouting.org/3.0/en/pgr_topologicalSort.html>`__
``pgr_topologicalSort`` - Experimental
===============================================================================
``pgr_topologicalSort`` — Linear ordering of the vertices for directed acyclic
graphs (DAG).
.. figure:: images/boost-inside.jpeg
:target: https://www.boost.org/libs/graph/doc/topological_sort.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
-------------------------------------------------------------------------------
The topological sort algorithm creates a linear ordering of the vertices such
that if edge :math:`(u,v)` appears in the graph, then :math:`v` comes before
:math:`u` in the ordering.
The main characteristics are:
* Process is valid for directed acyclic graphs only. otherwise it will throw
warnings.
* For optimization purposes, if there are more than one answer, the function
will return one of them.
* The returned values are ordered in topological order:
* Running time: :math:`O(V + E)`
Signatures
-------------------------------------------------------------------------------
.. rubric:: Summary
.. index::
single: topologicalSort - Experimental on v3.0
.. admonition:: \ \
:class: signatures
| pgr_topologicalSort(`Edges SQL`_)
| RETURNS SET OF |result-toposort|
| OR EMPTY SET
:Example: Topologically sorting the graph
.. literalinclude:: doc-topologicalSort.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-toposort|
.. list-table::
:width: 81
:widths: auto
:header-rows: 1
* - Column
- Type
- Description
* - ``seq``
- ``INTEGER``
- Sequential value starting from :math:`1`
* - ``sorted_v``
- ``BIGINT``
- Linear topological ordering of the vertices
Additional examples
-------------------------------------------------------------------------------
:Example: Topologically sorting the one way segments
.. literalinclude:: doc-topologicalSort.queries
:start-after: -- q2
:end-before: -- q3
:Example: Graph is not a DAG
.. literalinclude:: doc-topologicalSort.queries
:start-after: -- q3
:end-before: -- q4
See Also
-------------------------------------------------------------------------------
* :doc:`sampledata`
* https://en.wikipedia.org/wiki/Topological_sorting
.. rubric:: Indices and tables
* :ref:`genindex`
* :ref:`search`
|
