pgr_edwardMoore - Experimental¶
pgr_edwardMoore — Returns the shortest path using Edward-Moore algorithm.
Advertencia
Posible bloqueo del servidor
Estas funciones pueden crear un bloque 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.2.0
New experimental signature:
pgr_edwardMoore(Combinations)
Versión 3.0.0
New experimental signatures:
pgr_edwardMoore(One to One)pgr_edwardMoore(One to Many)pgr_edwardMoore(Many to One)pgr_edwardMoore(Many to Many)
Descripción¶
Algoritmo de Edward Moore es una mejora del algoritmo Bellman-Ford. Puede calcular las rutas más cortas desde un único vértice de origen a todos los demás vértices de un grafo dirigido ponderado. La principal diferencia entre algoritmo de Edward Moore y algoritmo de Bellman Ford radica en el tiempo de ejecución.
El peor de los casos de funcionamiento del algoritmo es \(O(| V | * | E |)\) similar a la complejidad temporal del algoritmo Bellman-Ford. Sin embargo, los experimentos sugieren que este algoritmo tiene una complejidad de tiempo de ejecución promedio de \(O( | E | )\) para grafos aleatorios. Esto es significativamente más rápido en términos de velocidad de cálculo.
Thus, the algorithm is at-best, significantly faster than Bellman-Ford algorithm and is at-worst,as good as Bellman-Ford algorithm
The main characteristics are:
Valores son regresados cuando hay una ruta.
Cuando el vértice inicial y el vértice final son iguales, no hay camino.
The agg_cost the non included values (v, v) is \(0\)
Cuando el vértice inicial y el vértice final son diferentes y no hay camino:
El
agg_costde los valores no incluídos(u, v)es :math: infty
For optimization purposes, any duplicated value in the start vids or end vids are ignored.
Los valores regresados se ordenan:
start vid ascending
end vid ascending
Running time:
Worst case: \(O(| V | * | E |)\)
Average case: \(O( | E | )\)
Firmas¶
Summary
pgr_edwardMoore(Edges SQL, start vid, end vid [, directed]) pgr_edwardMoore(Edges SQL, start vid, end vids [, directed]) pgr_edwardMoore(Edges SQL, start vids, end vid [, directed]) pgr_edwardMoore(Edges SQL, start vids, end vids [, directed]) pgr_edwardMoore(Edges SQL, Combinations SQL [, directed]) RETURNS (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost) OR EMPTY SET
Uno a Uno¶
pgr_edwardMoore(Edges SQL, start vid, end vid [, directed]); RETURNS (seq, path_seq, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo:
From vertex \(6\) to vertex \(10\) on a directed graph
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, 10, true);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 6 | 4 | 1 | 0
2 | 2 | 7 | 8 | 1 | 1
3 | 3 | 11 | 9 | 1 | 2
4 | 4 | 16 | 16 | 1 | 3
5 | 5 | 15 | 3 | 1 | 4
6 | 6 | 10 | -1 | 0 | 5
(6 rows)
One to Many¶
pgr_edwardMoore(Edges SQL, start vid, end vids [, directed]); RETURNS (seq, path_seq, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo:
From vertex \(6\) to vertices \(\{ 10, 17\}\) on a directed graph
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
6, ARRAY[10, 17]);
seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
1 | 1 | 10 | 6 | 4 | 1 | 0
2 | 2 | 10 | 7 | 8 | 1 | 1
3 | 3 | 10 | 11 | 9 | 1 | 2
4 | 4 | 10 | 16 | 16 | 1 | 3
5 | 5 | 10 | 15 | 3 | 1 | 4
6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 1 | 17 | 6 | 4 | 1 | 0
8 | 2 | 17 | 7 | 8 | 1 | 1
9 | 3 | 17 | 11 | 11 | 1 | 2
10 | 4 | 17 | 12 | 13 | 1 | 3
11 | 5 | 17 | 17 | -1 | 0 | 4
(11 rows)
Muchos a Uno¶
pgr_edwardMoore(Edges SQL, start vids, end vid [, directed]); RETURNS (seq, path_seq, start_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo:
From vertices \(\{6, 1\}\) to vertex \(17\) on a directed graph
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 1], 17);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 1 | 1 | 6 | 1 | 0
2 | 2 | 1 | 3 | 7 | 1 | 1
3 | 3 | 1 | 7 | 8 | 1 | 2
4 | 4 | 1 | 11 | 11 | 1 | 3
5 | 5 | 1 | 12 | 13 | 1 | 4
6 | 6 | 1 | 17 | -1 | 0 | 5
7 | 1 | 6 | 6 | 4 | 1 | 0
8 | 2 | 6 | 7 | 8 | 1 | 1
9 | 3 | 6 | 11 | 11 | 1 | 2
10 | 4 | 6 | 12 | 13 | 1 | 3
11 | 5 | 6 | 17 | -1 | 0 | 4
(11 rows)
Muchos a Muchos¶
pgr_edwardMoore(Edges SQL, start vids, end vids [, directed]); RETURNS (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo:
From vertices \(\{6, 1\}\) to vertices \(\{10, 17\}\) on an undirected graph
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[6, 1], ARRAY[10, 17],
directed => false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 10 | 1 | 6 | 1 | 0
2 | 2 | 1 | 10 | 3 | 7 | 1 | 1
3 | 3 | 1 | 10 | 7 | 4 | 1 | 2
4 | 4 | 1 | 10 | 6 | 2 | 1 | 3
5 | 5 | 1 | 10 | 10 | -1 | 0 | 4
6 | 1 | 1 | 17 | 1 | 6 | 1 | 0
7 | 2 | 1 | 17 | 3 | 7 | 1 | 1
8 | 3 | 1 | 17 | 7 | 8 | 1 | 2
9 | 4 | 1 | 17 | 11 | 11 | 1 | 3
10 | 5 | 1 | 17 | 12 | 13 | 1 | 4
11 | 6 | 1 | 17 | 17 | -1 | 0 | 5
12 | 1 | 6 | 10 | 6 | 2 | 1 | 0
13 | 2 | 6 | 10 | 10 | -1 | 0 | 1
14 | 1 | 6 | 17 | 6 | 4 | 1 | 0
15 | 2 | 6 | 17 | 7 | 8 | 1 | 1
16 | 3 | 6 | 17 | 11 | 11 | 1 | 2
17 | 4 | 6 | 17 | 12 | 13 | 1 | 3
18 | 5 | 6 | 17 | 17 | -1 | 0 | 4
(18 rows)
Combinaciones¶
pgr_edwardMoore(Edges SQL, Combinations SQL [, directed]); RETURNS (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost) OR EMPTY SET
- Ejemplo:
Uso de una tabla de combinaciones en un grafo no dirigido.
The combinations table:
SELECT source, target FROM combinations;
source | target
--------+--------
5 | 6
5 | 10
6 | 5
6 | 15
6 | 14
(5 rows)
The query:
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT source, target FROM combinations',
false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 5 | 10 | 6 | 2 | 1 | 1
5 | 3 | 5 | 10 | 10 | -1 | 0 | 2
6 | 1 | 6 | 5 | 6 | 1 | 1 | 0
7 | 2 | 6 | 5 | 5 | -1 | 0 | 1
8 | 1 | 6 | 15 | 6 | 2 | 1 | 0
9 | 2 | 6 | 15 | 10 | 3 | 1 | 1
10 | 3 | 6 | 15 | 15 | -1 | 0 | 2
(10 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
|---|---|---|
|
Edges SQL as described below |
|
|
Combinations SQL as described below |
|
start vid |
|
Identificador del vértice inicial de la ruta. |
start vids |
|
Arreglo de identificadores de vértices iniciales. |
end vid |
|
Identificador del vértice final de la ruta. |
end vids |
|
Arreglo de identificadores de vértices finales. |
Optional parameters¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
|
|
|
Inner Queries¶
Edges SQL¶
Columna |
Tipo |
x Defecto |
Descripción |
|---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge ( |
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT- FLOTANTES:
SMALLINT,INTEGER,BIGINT,REAL,FLOAT
Combinations SQL¶
Parámetro |
Tipo |
Descripción |
|---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Donde:
- ENTEROS:
SMALLINT,INTEGER,BIGINT
Return columns¶
Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost,
agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta. |
|
|
Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. |
|
|
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
|
|
Identificador del nodo en la ruta de |
|
|
Identifier of the edge used to go from |
|
|
Costo del desplazamiento desde |
|
|
Aggregate cost from |
Additional Examples¶
- Example 1:
Demonstration of repeated values are ignored, and result is sorted.
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 10 | 7 | 8 | 1 | 0
2 | 2 | 7 | 10 | 11 | 9 | 1 | 1
3 | 3 | 7 | 10 | 16 | 16 | 1 | 2
4 | 4 | 7 | 10 | 15 | 3 | 1 | 3
5 | 5 | 7 | 10 | 10 | -1 | 0 | 4
6 | 1 | 7 | 15 | 7 | 8 | 1 | 0
7 | 2 | 7 | 15 | 11 | 9 | 1 | 1
8 | 3 | 7 | 15 | 16 | 16 | 1 | 2
9 | 4 | 7 | 15 | 15 | -1 | 0 | 3
10 | 1 | 10 | 7 | 10 | 5 | 1 | 0
11 | 2 | 10 | 7 | 11 | 8 | 1 | 1
12 | 3 | 10 | 7 | 7 | -1 | 0 | 2
13 | 1 | 10 | 15 | 10 | 5 | 1 | 0
14 | 2 | 10 | 15 | 11 | 9 | 1 | 1
15 | 3 | 10 | 15 | 16 | 16 | 1 | 2
16 | 4 | 10 | 15 | 15 | -1 | 0 | 3
17 | 1 | 15 | 7 | 15 | 16 | 1 | 0
18 | 2 | 15 | 7 | 16 | 9 | 1 | 1
19 | 3 | 15 | 7 | 11 | 8 | 1 | 2
20 | 4 | 15 | 7 | 7 | -1 | 0 | 3
21 | 1 | 15 | 10 | 15 | 3 | 1 | 0
22 | 2 | 15 | 10 | 10 | -1 | 0 | 1
(22 rows)
- Example 2:
Making start vids the same as end vids.
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 10 | 7 | 8 | 1 | 0
2 | 2 | 7 | 10 | 11 | 9 | 1 | 1
3 | 3 | 7 | 10 | 16 | 16 | 1 | 2
4 | 4 | 7 | 10 | 15 | 3 | 1 | 3
5 | 5 | 7 | 10 | 10 | -1 | 0 | 4
6 | 1 | 7 | 15 | 7 | 8 | 1 | 0
7 | 2 | 7 | 15 | 11 | 9 | 1 | 1
8 | 3 | 7 | 15 | 16 | 16 | 1 | 2
9 | 4 | 7 | 15 | 15 | -1 | 0 | 3
10 | 1 | 10 | 7 | 10 | 5 | 1 | 0
11 | 2 | 10 | 7 | 11 | 8 | 1 | 1
12 | 3 | 10 | 7 | 7 | -1 | 0 | 2
13 | 1 | 10 | 15 | 10 | 5 | 1 | 0
14 | 2 | 10 | 15 | 11 | 9 | 1 | 1
15 | 3 | 10 | 15 | 16 | 16 | 1 | 2
16 | 4 | 10 | 15 | 15 | -1 | 0 | 3
17 | 1 | 15 | 7 | 15 | 16 | 1 | 0
18 | 2 | 15 | 7 | 16 | 9 | 1 | 1
19 | 3 | 15 | 7 | 11 | 8 | 1 | 2
20 | 4 | 15 | 7 | 7 | -1 | 0 | 3
21 | 1 | 15 | 10 | 15 | 3 | 1 | 0
22 | 2 | 15 | 10 | 10 | -1 | 0 | 1
(22 rows)
- Example 3:
Manually assigned vertex combinations.
SELECT * FROM pgr_edwardMoore(
'SELECT id, source, target, cost, reverse_cost FROM edges',
'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
9 | 1 | 12 | 10 | 12 | 13 | 1 | 0
10 | 2 | 12 | 10 | 17 | 15 | 1 | 1
11 | 3 | 12 | 10 | 16 | 16 | 1 | 2
12 | 4 | 12 | 10 | 15 | 3 | 1 | 3
13 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(13 rows)
Ver también¶
Índices y tablas