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

Soporte

  • 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