# pgr_topologicalSort - Experimental¶

pgr_topologicalSort — Linear ordering of the vertices for directed acyclic graphs (DAG).

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

## 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.

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:

Topologically sorting the graph

SELECT * FROM pgr_topologicalsort(
$$SELECT id, source, target, cost FROM edges WHERE cost >= 0 UNION SELECT id, target, source, reverse_cost FROM edges WHERE cost < 0$$);
seq | sorted_v
-----+----------
1 |        1
2 |        5
3 |        2
4 |        4
5 |        3
6 |       13
7 |       14
8 |       15
9 |       10
10 |        6
11 |        7
12 |        8
13 |        9
14 |       11
15 |       16
16 |       12
17 |       17
(17 rows)



## Parameters¶

Parameter

Type

Description

Edges SQL

TEXT

Edges SQL as described below.

## Inner Queries¶

### Edges SQL¶

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)

• When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

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

INTEGER

Sequential value starting from $$1$$

sorted_v

BIGINT

Linear topological ordering of the vertices

Example:

Topologically sorting the one way segments

SELECT * FROM pgr_topologicalsort(
$$SELECT id, source, target, cost, -1 AS reverse_cost FROM edges WHERE cost >= 0 UNION SELECT id, source, target, -1, reverse_cost FROM edges WHERE cost < 0$$);
seq | sorted_v
-----+----------
1 |        5
2 |        2
3 |        4
4 |       13
5 |       14
6 |        1
7 |        3
8 |       15
9 |       10
10 |        6
11 |        7
12 |        8
13 |        9
14 |       11
15 |       12
16 |       16
17 |       17
(17 rows)


Example:

Graph is not a DAG

SELECT * FROM pgr_topologicalsort(
$$SELECT id, source, target, cost, reverse_cost FROM edges$$);
ERROR:  Graph is not DAG
CONTEXT:  SQL function "pgr_topologicalsort" statement 1