pgr_topologicalSort - Experimental

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

_images/boost-inside.jpeg

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

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:  The graph must be a DAG.
HINT:  Working with Directed Graph

CONTEXT:  SQL function "pgr_topologicalsort" statement 1