Cost Matrix - Categoría

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 ANY-INTEGER y ANY-NUMERICAL

    • Es posible que el nombre no cambie. (Pero todavía puede)

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

    • Es posible que 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

Sinopsis

Vendedor Viajante - Familia de funciones necesita como entrada una matriz de costos simétrica y sin borde (u, v), debe valorar \(\infty\).

Esta colección de funciones devolverá una matriz de costes en forma de tabla.

Características

Las características principales son:

  • Se puede utilizar como entrada para pgr_TSP.

    • Use directly when the resulting matrix is symmetric and there is no \(\infty\) value.

    • Será responsabilidad de los usuarios hacer que la matriz sea simétrica.

      • Mediante el uso de la media geométrica o armónica de los valores no simétricos.

      • Mediante el uso de max o min, los valores no simétricos.

      • Estableciendo el triángulo superior para que sea la imagen reflejada del triángulo inferior.

      • Estableciendo el triángulo inferior para que sea la imagen reflejada del triángulo superior.

    • También es responsabilidad de los usuarios para fijar un valor \(\infty\) value.

  • Cada función funciona como parte de la familia a la que pertenece.

  • No devuelve una ruta.

  • Devuelve la suma de los costos de la ruta más corta para la combinación de pares de nodos en el grafo.

  • El proceso se realiza sólo en las aristas con costos positivos.

  • Valores son regresados cuando hay una ruta.

    • Cuando el vértice inicial y el vértice final son iguales, no hay camino.

      • The aggregate cost in the non included values (v, v) is 0.

    • Cuando el vértice inicial y el vértice final son diferentes y no hay ninguna ruta.

      • The aggregate cost in the non included values (u, v) is \(\infty\).

  • Let be the case the values returned are stored in a table:

    • The unique index would be the pair: (start_vid, end_vid).

  • Dependiendo de la función y sus parámetros, los resultados pueden ser simétricos.

    • The aggregate cost of (u, v) is the same as for (v, u).

  • Any duplicated value in the start vids are ignored.

  • Los valores regresados se ordenan:

    • start_vid ascending

    • end_vid ascending

Parameters

Used in:

Column

Type

Description

Edges SQL

TEXT

Edges SQL as described below

start vids

ARRAY[BIGINT]

Array of identifiers of starting vertices.

Used in:

Column

Type

Description

Edges SQL

TEXT

Edges SQL as described below

Points SQL

TEXT

Points SQL as described below

start vids

ARRAY[BIGINT]

Array of identifiers of starting vertices.

Optional parameters

Column

Type

default

Description

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected.

Inner query

Edges SQL

Used in:

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

Points SQL

Parameter

Type

Default

Description

pid

ANY-INTEGER

value

Identifier of the point.

  • Use with positive value, as internally will be converted to negative value

  • If column is present, it can not be NULL.

  • If column is not present, a sequential negative value will be given automatically.

edge_id

ANY-INTEGER

Identifier of the «closest» edge to the point.

fraction

ANY-NUMERICAL

Value in <0,1> that indicates the relative postition from the first end point of the edge.

side

CHAR

b

Value in [b, r, l, NULL] indicating if the point is:

  • In the right r,

  • In the left l,

  • In both sides b, NULL

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Return Columns

Set of (start_vid, end_vid, agg_cost)

Column

Type

Description

start_vid

BIGINT

Identifier of the starting vertex.

end_vid

BIGINT

Identifier of the ending vertex.

agg_cost

FLOAT

Aggregate cost from start_vid to end_vid.

Ver también

Índices y tablas