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
|
:file: This file is part of the pgRouting project.
:copyright: Copyright (c) 2019-2026 pgRouting developers
:license: Creative Commons Attribution-Share Alike 3.0 https://creativecommons.org/licenses/by-sa/3.0
.. index::
single: Ordering Family ; pgr_topologicalSort - Experimental
single: topologicalSort - Experimental on v3.0
|
``pgr_topologicalSort`` - Experimental
===============================================================================
``pgr_topologicalSort`` — Linear ordering of the vertices for directed acyclic
graphs (DAG).
.. include:: experimental.rst
:start-after: warning-begin
:end-before: end-warning
.. rubric:: Availability
.. rubric:: Version 4.0.0
* Standardize output to |result_node_order|
.. rubric:: 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)`
|Boost| Boost Graph Inside
Signatures
-------------------------------------------------------------------------------
.. rubric:: Summary
.. admonition:: \ \
:class: signatures
| pgr_topologicalSort(`Edges SQL`_)
| Returns set of |result_node_order|
| OR EMPTY SET
:Example: Topologically sorting the graph
.. literalinclude:: 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_node_order|
.. list-table::
:width: 81
:widths: auto
:header-rows: 1
* - Column
- Type
- Description
* - ``seq``
- ``INTEGER``
- Sequential value starting from :math:`1`
* - ``node``
- ``BIGINT``
- Linear topological ordering of the vertices
Additional examples
-------------------------------------------------------------------------------
:Example: Topologically sorting the one way segments
.. literalinclude:: topologicalSort.queries
:start-after: -- q2
:end-before: -- q3
:Example: Graph is not a DAG
.. literalinclude:: topologicalSort.queries
:start-after: -- q3
:end-before: -- q4
See Also
-------------------------------------------------------------------------------
* :doc:`sampledata`
* `Boost: topological sort
<https://www.boost.org/libs/graph/doc/topological_sort.html>`__
* https://en.wikipedia.org/wiki/Topological_sorting
.. rubric:: Indices and tables
* :ref:`genindex`
* :ref:`search`
|
