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
Warning
Experimental functions
Availability
Support
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.
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)
Parameter | Type | Default | Description |
---|---|---|---|
edges_sql | TEXT |
SQL query as described above. |
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 |
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) |
Indices and tables