pgr_topologicalSort - Experimental

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

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloque del servidor

Advertencia

Funciones experimentales

  • No son oficialmente de la versión actual.

  • Es probable que oficialmente no formen parte de la siguiente versión:

    • Las funciones no podrían hacer uso de ANY-INTEGER ni ANY-NUMERICAL

    • El nombre puede cambiar.

    • La firma (declaración de funciones) podría cambiar.

    • La funcionalidad puede cambiar.

    • Las pruebas de pgTap pueden estar ausentes.

    • Posiblemente necesite codificación c/c++.

    • Puede haber carencia de documentación.

    • Hay documentación que, en dado caso, podría ser necesario reescribir.

    • Ejemplos de documentación que puede ser necesario generar automáticamente.

    • Puede ser necesaria más retroalimentación por parte de la comunidad.

    • Puede depender de una función propuesta de pgRouting

    • Podría depender de una función obsoleta de pgRouting

Disponibilidad

  • Versión 3.0.0

    • Nueva función experimental

Descripción

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.

Las principales características son:

  • El proceso solo es válido para grafos acíclicos dirigidos. de lo contrario lanzará advertencias.

  • For optimization purposes, if there are more than one answer, the function

    will return one of them.

  • Los valores devueltos se ordenan en orden topológico:

  • Running time: \(O(V + E)\)

Firmas

Resumen

pgr_topologicalSort(Edges SQL)
RETURNS SET OF (seq, sorted_v)
OR EMPTY SET
Ejemplo:

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)

Parámetros

Parámetro

Tipo

Descripción

Edges SQL

TEXT

Edges SQL as described below.

Inner Queries

Edges SQL

Columna

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice de la arista.

target

ANY-INTEGER

Identificador del segundo vértice de la arista.

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.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve conjunto de (seq, sorted_v)

Columna

Tipo

Descripción

seq

INTEGER

Sequential value starting from \(1\)

sorted_v

BIGINT

Linear topological ordering of the vertices

Additional examples

Ejemplo:

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)

Ejemplo:

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

Ver también

Índices y tablas