pgr_topologicalSort - Experimental¶
pgr_topologicalSort
— Returns the linear ordering of the vertices(s) for weighted directed acyclic graphs(DAG).
In particular, the topological sort algorithm implemented by Boost.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
- TBD
Description¶
The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then v comes before u in the ordering.
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.
- 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: \(O( (V + E))\)
Signatures¶
Summary
pgr_topologicalSort(edges_sql)
RETURNS SET OF (seq, sorted_v)
OR EMPTY SET
Example: | For a directed graph |
---|
SELECT * FROM pgr_topologicalsort(
'SELECT id,source,target,cost,reverse_cost FROM edge_table1'
);
seq | sorted_v
-----+----------
1 | 0
2 | 1
3 | 3
4 | 2
(4 rows)
Parameters¶
Parameter | Type | Default | Description |
---|---|---|---|
edges_sql | TEXT |
SQL query as described above. |
Inner query¶
edges_sql: | an SQL query, which should return a set of rows with the following columns: |
---|
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 (target, source),
|
Where:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Result Columns¶
Returns set of (seq, sorted_v)
Column | Type | Description |
---|---|---|
seq | INT |
Sequential value starting from 1. |
sorted_v | BIGINT |
Linear ordering of the vertices(ordered in topological order) |
See Also¶
- https://en.wikipedia.org/wiki/Topological_sorting
- The queries use the Sample Data network.
Indices and tables