Via- Categoria

propuesta

Advertencia

Funciones propuestas para la próxima versión mayor.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte del próximo lanzamiento:

    • Las funciones hacen uso de ENTEROS y FLOTANTES

    • Probablemente el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Probablemente la funcionalidad no cambie. (Pero todavía puede)

    • Se han hecho pruebas con pgTap. Pero tal vez se necesiten más.

    • Es posible que la documentación necesite un refinamiento.

Información general

La intención de esta categoría es resolver el problema general:

Dado un grafo y una lista de vértices, encuentra el camino mas corto entre \(vertex_i\) and \(vertex_{i+1}\) para todos los vértices

En otras palabras, encuentre la ruta continua que visite todos los vértices en el orden dado.

camino:

representa una sección de una ruta.

ruta:

es una secuencia de caminos

Parámetros

Usado en:

Parámetro

Tipo

x Defecto

Descripción

SQL de aristas

TEXT

Consulta SQL como se describe.

vértices

ARRAY [ENTEROS ]

Arreglo ordenado de identificadores de vértices que serán visitados.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

Ademas de los parámetros obligatorios que tiene cada función, hay parámetros opcionales que existen dado el tipo de función.

Parámetros opcionales Vía

Usado en todas las funciones Via

Parámetro

Tipo

x Defecto

Descripción

strict

BOOLEAN

false

  • Cuando true si un camino le faltan paradas y regresa EMPTY SET

  • Cuando false, ignora las rutas faltantes y devuelve todas las rutas encontradas

U_turn_on_edge

BOOLEAN

true

  • Cuando true saliendo desde un vértice visitado no intentara esquivarlo

Consultas Internas

Dependiendo de la función, serán necesarias una o mas consultas internas.

SQL aristas

Columna

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

Peso de la arista (source, target)

reverse_cost

FLOTANTES

-1

Peso de la arista (target, source)

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

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL restricciones

Columna

Tipo

Descripción

path

ARRAY [ENTEROS]

Secuencia de identificadores de aristas que forman un camino que no se permite tomar. - Arreglos vacios o NULL son ignorados. - Arreglos que tienen NULL arrojan una excepción.

Cost

FLOTANTES

Costo de tomar el camino prohibido.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Columna

Tipo

Descripción

seq

INTEGER

Valor secuencial a partir de 1.

path_id

INTEGER

Identificador del camino. Tiene valor 1 para el primer camino.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.

start_vid

BIGINT

Identificador del vértice inicial de la ruta.

end_vid

BIGINT

Identificador del vértice final de la ruta.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identificador de la arsita utilizada para ir del node al siguiente nodo de la secuencia de ruta.

  • -1 para el último nodo de la ruta.

  • -2 para el último nodo de la ruta.

cost

FLOAT

Costo para atravesar desde node usando edge hasta el siguiente nodo en la secuencia de la ruta.

agg_cost

FLOAT

Costo agregado desde start_vid hasta node.

route_agg_cost

FLOAT

Costo total desde start_vid en seq = 1 hasta end_vid del seq actual.

Nota

Cuando las columnas start_vid, end_vid y``node`` tengan valores negativos, el identificador es para un Punto.

Ver también

Índices y tablas