pgr_johnson

pgr_johnson - Devuelve la suma de los costes de la ruta más corta para cada par de nodos del grafo mediante el algoritmo Floyd-Warshall.

_images/boost-inside.jpeg

Boost Graph Inside

Disponibilidad

  • Version 2.2.0

    • Cambio de firma

    • Firma antigua ya no soportada

  • Versión 2.0.0

    • Función oficial

Descripción

El algoritmo Johnson, es una buena opción para calcular la suma de los costos de la ruta más corta para cada par de nodos en el grafo, para grafos dispersos. Utiliza la implementación del Boost que se ejecuta en \(O(V E \log V)\) tiempo,

Las principales características son:

  • No devuelve una ruta.

  • Devuelve la suma de los costos de la ruta más corta para cada par de nodos del grafo.

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

  • Boost devuelve una matriz:math:V times V donde los valores son infinitos. Representar la distancia entre vértices para los que no hay ruta.

    • Solo devolvemos los valores no infinitos en forma de un conjunto de (start_vid, end_vid, agg_cost).

  • Sea el caso, los valores devueltos se almacenan en una tabla, por lo que el índice único sería el par: “(start_vid, end_vid)”.

  • Para el grafo no dirigido, los resultados son simétricos.

    • El agg_cost de (u, v) es el mismo que para (v, u).

  • En caso de start_vid = end_vid, el agg_cost = 0.

  • Recommended, use a bounding box of no more than 3500 edges.

Firmas

Resumen

pgr johnson(Edges SQL [, directed])
RETURNS SET OF (start_vid, end_vid, agg_cost)
OR EMPTY SET
Example

Para vértices \(\{1, 2, 3, 4\}\) en un grafo no dirigido

SELECT * FROM pgr_johnson(
    'SELECT source, target, cost FROM edge_table WHERE id < 5
         ORDER BY id',
    false
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         1 |       2 |        1
         1 |       5 |        2
         2 |       1 |        1
         2 |       5 |        1
         5 |       1 |        2
         5 |       2 |        1
(6 rows)

Parámetros

Parámetro

Tipo

x Defecto

Descripción

Edges SQL

TEXT

Edges SQL as described below.

Optional parameters

Columna

Tipo

default

Descripción

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected.

Consulta interna

Edges SQL

Columna

Tipo

x Defecto

Descripción

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo 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:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Columnas de Resultados

Devuelve un conjunto de (start_vid, end_vid, agg_cost)

Set of (start_vid, end_vid, agg_cost)

Columna

Tipo

Descripción

start_vid

BIGINT

Identificador del vértice inicial.

end_vid

BIGINT

Identificador del vértice final.

agg_cost

FLOAT

Aggregate cost from start_vid to end_vid.

Ver también

Índices y tablas