• Supported versions:

pgr_topologicalSort - Experimental

pgr_topologicalSort — Devuelve el orden lineal de los vértices para los grafos acíclicos dirigidos ponderados (DAG). En particular, el algoritmo de ordenación topológica implementado por Boost.Graph.

_images/boost-inside.jpeg

Adentro: Boost Graph

Advertencia

Posible bloqueo del servidor

  • Estas funciones pueden crear un bloqueo 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

  • TBD

Descripción

El algoritmo de ordenación topológica crea un orden lineal de los vértices de tal manera que si la arista (u,v) aparece en el grafo, entonces v viene antes de u en el orden.

Esta implementación solo se puede utilizar con un grafo dirigido sin ciclos i.e., es decir, un grafo acíclico dirigido.

Las principales características son:

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

  • Para fines de optimización, si hay más de una respuesta, la función devolverá una de ellas.

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

  • Tiempo de ejecución: \(O( (V + E))\)

Firmas

Resumen

pgr_topologicalSort(edges_sql)

RETURNS SET OF (seq, sorted_v)
OR EMPTY SET
Ejemplo

Para un grafo dirigido

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)

Parámetros

Parámetro

Tipo

Valores predeterminados

Descripción

edges_sql

TEXT

Consulta SQL como se describió anteriormente.

Consulta interna

edges_sql

Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna

Tipo

Valores predeterminados

Descripción

id

ANY-INTEGER

Identificador de la arista.

origen

ANY-INTEGER

Identificador del primer punto final en el vértice de la arista.

objetivo

ANY-INTEGER

Identificador del segundo punto final en el vértice de la arista.

cost

ANY-NUMERICAL

Peso de la arista (source, target)

  • Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.

reverse_cost

ANY-NUMERICAL

-1

Peso de la arista (target, source),

  • En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve conjunto de (seq, sorted_v)

Columna

Tipo

Descripción

seq

INT

Valor secuencial a partir de 1.

sorted_v

BIGINT

Orden lineal de los vértices (ordenados en orden topológico)

Ver también

Índices y tablas