# pgRouting Manual (3.6)

## pgr_topologicalSort - Experimental

# `pgr_topologicalSort` - Experimental

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

Boost Graph Inside

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

## Additional examples

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

## See Also

- Sample Data

- https://en.wikipedia.org/wiki/Topological_sorting

Indices and tables

- Index

- Search Page