Conceptos de pgRouting¶
Esta es una guía simple que va a través de los pasos básicos para empezar trabajar con pgRouting. Esta guía cubre:
Grafos¶
Definición de grafo¶
Un grafo es un par ordenado \(G = (V ,E)\) donde:
\(V\) es un conjunto de vértices, también llamados nodos.
\(E \subseteq \{( u, v ) \mid u , v \in V \}\)
Hay diferentes tipos de grafos:
Grafo no dirigido
\(E \subseteq \{( u, v ) \mid u , v \in V\}\)
Grafo no dirigido simple
\(E \subseteq \{( u, v ) \mid u , v \in V, u \neq v\}\)
Grafo dirigido
\(E \subseteq \{( u, v ) \mid (u , v) \in (V X V) \}\)
Grafo dirigido simple
\(E \subseteq \{( u, v ) \mid (u , v) \in (V X V), u \neq v\}\)
Grafos:
No tienen geometrías.
Algunos problemas de teoría de grafos requieren tener pesos, llamados cost en pgRouting.
En pgRouting hay varias maneras de representar in grafo en la base de datos:
Con
cost
(
id
,source
,target
,cost
)
Con
cost
yreverse_cost
(
id
,source
,target
,cost
,reverse_cost
)
Donde:
Columna |
Descripción |
---|---|
|
Identificador de la asirsta. Requerimiento para mantener consistente la base de datos. |
|
Identificador de un vértice. |
|
Identificador de un vértice. |
|
Peso de la arista (
|
|
Peso de la arista (
|
La decisión del grafo de ser directed o undirected es resultado al ejecutar el algoritmo de pgRouting.
Grafo con cost
¶
El grafo ponderado dirigido, \(G_d(V,E)\):
Datos de l grafo se obtienen mediante una consulta
SELECT id, source, target, cost FROM edges
El conjunto de aristas \(E\)
\(E = \{(source_{id}, target_{id}, cost_{id}) \text{ cuando } cost_{id} \ge 0 \}\)
Aristas donde
cost
es no negativo son parte del grafo.
El conjunto de vértices \(V\)
\(V = \{source_{id} \cup target_{id}\}\)
Todos los vértices``source`` y
target
son parte del grafo.
Grafo dirigido
En un grafo dirigido la arista \((source_{id}, target_{id}, cost_{id})\) tiene direccionalidad: \(source_{id} \rightarrow target_{id}\)
Para los siguientes datos:
SELECT *
FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3))
AS t(id, source, target, cost);
id | source | target | cost
----+--------+--------+------
1 | 1 | 2 | 5
2 | 1 | 3 | -3
(2 rows)
La arista \(2\) (\(1 \rightarrow 3\)) no es parte del grafo.
Los datos se representan en el siguiente grafo:
Grafo no dirigido
En un grafo no dirigido la arista \((source_{id}, target_{id}, cost_{id})\) no tiene direccionalidad: \(source_{id} \frac{\;\;\;\;\;}{} target_{id}\)
En términos de un grafo dirigido es como tener dos aristas: \(source_{id} \leftrightarrow target_{id}\)
Para los siguientes datos:
SELECT *
FROM (VALUES (1, 1, 2, 5), (2, 1, 3, -3))
AS t(id, source, target, cost);
id | source | target | cost
----+--------+--------+------
1 | 1 | 2 | 5
2 | 1 | 3 | -3
(2 rows)
Arista \(2\) (\(1 \frac{\;\;\;\;\;}{} 3\)) no es parte del grafo.
Los datos se representan en el siguiente grafo:
Grafo con cost
y reverse_cost
¶
El ponderado del grafo dirigido, \(G_d(V,E)\), se define por:
Datos de l grafo se obtienen mediante una consulta
SELECT id, source, target, cost, reverse_cost FROM edges
El conjunto de aristas \(E\):
\(E = \begin{split} \begin{align} & {\{(source_{id}, target_{id}, cost_{id}) \text{ when } cost_{id} >=0 \}} \\ & \cup \\ & {\{(target_{id}, source_{id}, reverse\_cost_{id}) \text{ when } reverse\_cost_{id} >=0 \}} \end{align} \end{split}\)
Aristas \((source \rightarrow target)\) done
cost
es no negativo son parte del grafo.Aristas \((target \rightarrow source)\) donde
reverse_cost
es no negativo son parte del grafo.
El conjunto de vértices \(V\):
\(V = \{source_{id} \cup target_{id}\}\)
Todos los vértices``source`` y
target
son parte del grafo.
Grafo dirigido
En un grafo dirigido ambas aristas tiene direccionalidad
arista \((source_{id}, target_{id}, cost_{id})\) tiene direccionalidad: \(source_{id} \rightarrow target_{id}\)
arista \((target_{id}, source_{id}, reverse\_cost_{id})\) tiene direccionalidad: \(target_{id} \rightarrow source_{id}\)
Para los siguientes datos:
SELECT *
FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1))
AS t(id, source, target, cost, reverse_cost);
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 | 1 | 2 | 5 | 2
2 | 1 | 3 | -3 | 4
3 | 2 | 3 | 7 | -1
(3 rows)
Aristas no son parte del grafo:
\(2\) (\(1 \rightarrow 3\))
\(3\) (\(3 \rightarrow 2\))
Los datos se representan en el siguiente grafo:
Grafo no dirigido
En un grafo dirigido ambas aristas no tiene direccionalidad
Arista \((source_{id}, target_{id}, cost_{id})\) es \(source_{id} \frac{\;\;\;\;\;}{} target_{id}\)
Arista \((target_{id}, source_{id}, reverse\_cost_{id})\) es \(target_{id} \frac{\;\;\;\;\;}{} source_{id}\)
En términos de un grafo dirigido es como tener cuatro aristas:
\(source_i \leftrightarrow target_i\)
\(target_i \leftrightarrow source_i\)
Para los siguientes datos:
SELECT *
FROM (VALUES (1, 1, 2, 5, 2), (2, 1, 3, -3, 4), (3, 2, 3, 7, -1))
AS t(id, source, target, cost, reverse_cost);
id | source | target | cost | reverse_cost
----+--------+--------+------+--------------
1 | 1 | 2 | 5 | 2
2 | 1 | 3 | -3 | 4
3 | 2 | 3 | 7 | -1
(3 rows)
Aristas no son parte del grafo:
\(2\) (\(1 \frac{\;\;\;\;\;}{} 3\))
\(3\) (\(3 \frac{\;\;\;\;\;}{} 2\))
Los datos se representan en el siguiente grafo:
Grafos sin geometrías¶
Relaciones personales, genealogía, problemas de dependencia de archivos puede ser resueltos usando pgRouting. Esos problemas, normalmente, no vienen con las geometrías asociadas con el grafo.
Ejemplo de Wiki¶
Resuelva el problema de ejemplo tomado de wikipedia):
Donde:
Problema es encontrar el camino mas corto desde \(1\) a \(5\).
Es un grafo dirigido.
Aunque visualmente se vea con geometrías, el dibujo no es a escala.
Las geometrías no esta asociadas con los vértices o aristas
Tiene 6 vértices \(\{1,2,3,4,5,6\}\)
Tiene 9 aristas:
\(\begin{split} \begin{align} E = & \{(1,2,7), (1,3,9), (1,6,14), \\ & (2,3,10), (2,4,13), \\ & (3,4,11), (3,6,2), \\ & (4,5,6), \\ & (5,6,9) \} \end{align} \end{split}\)
El grafo puede ser representados de varias maneras por ejemplo:
Prepara la base de datos¶
Crea una base de datos para el ejemplo, acceda a la base de datos e instala pgRouting:
$ createdb wiki
$ psql wiki
wiki =# CREATE EXTENSION pgRouting CASCADE;
Crear una tabla¶
Los elementos básicos necesarios para realizar routing básico en un grafo no dirigido son:
Columna |
Tipo |
Descripción |
---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
FLOTANTES |
Peso de la arista ( |
Donde:
- ENTEROS:
SMALLINT, INTEGER, BIGINT
- FLOTANTES:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
Usando este diseño de tabla para este ejemplo:
CREATE TABLE wiki (
id SERIAL,
source INTEGER,
target INTEGER,
cost INTEGER);
CREATE TABLE
Introduzca los datos¶
INSERT INTO wiki (source, target, cost) VALUES
(1, 2, 7), (1, 3, 9), (1, 6, 14),
(2, 3, 10), (2, 4, 15),
(3, 6, 2), (3, 4, 11),
(4, 5, 6),
(5, 6, 9);
INSERT 0 9
En cuentre el camino más corto¶
Para resolver el ejemplo se usa pgr_dijkstra:
SELECT * FROM pgr_dijkstra(
'SELECT id, source, target, cost FROM wiki',
1, 5, false);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 1 | 5 | 1 | 2 | 9 | 0
2 | 2 | 1 | 5 | 3 | 6 | 2 | 9
3 | 3 | 1 | 5 | 6 | 9 | 9 | 11
4 | 4 | 1 | 5 | 5 | -1 | 0 | 20
(4 rows)
Para ir de \(1\) a \(5\) el camino que atraviesa los siguientes vértices: \(1 \rightarrow 3 \rightarrow 6 \rightarrow 5\)
Información de vertices¶
Para obtener la información de los vértices, use pgr_extractVertices – Propuesto
SELECT id, in_edges, out_edges
FROM pgr_extractVertices('SELECT id, source, target FROM wiki');
id | in_edges | out_edges
----+----------+-----------
3 | {2,4} | {6,7}
5 | {8} | {9}
4 | {5,7} | {8}
2 | {1} | {4,5}
1 | | {1,2,3}
6 | {3,6,9} |
(6 rows)
Grafos con geometrías¶
Crear una Base de Datos de Ruteo¶
El primer paso para crear una base de datos y cargar pgRouting en la base de datos.
Típicamente se crea una base de datos para cada proyecto.
Una vez que se tenga una base de datos, cargue sus datos y construya la aplicación de routeo en esa base de datos.
createdb sampledata
psql sampledata -c "CREATE EXTENSION pgrouting CASCADE"
Cargar Datos¶
Hay varias maneras de cargar tus datos en pgRouting.
Creando manualmente la base de datos.
Datos Muestra: un pequeño grafo utilizado en los ejemplos de la documentación
Usando osm2pgrouting
Existen varias herramientas de codigo abierto que pueden ayudar, como:
- shp2pgsql:
cargador a postgresql de archivos shape
- ogr2ogr:
herramienta de conversión de datos vectoriales
- osm2pgsql:
cargar datos de OSM a postgresql
Tener en cuenta que estas herramientas no importan los datos a una estructura compatible con pgRouting y cuando esto sucede, la topología necesita ser ajustada.
Rompe en segmentos cada intersección segmento-segmento
Cuando falte, agregue columnas y asigne valores a
source
,target
,cost
,reverse_cost
.Conecte un grafo desconectado.
Crea la topología de un grafo completo
Crea uno o mas grafos según la aplicación que se desarrolla.
Crea un grafo contraído para calles de alta velocidad
Crear grafos por estado/país
En pocas palabras:
Prepara el grafo
Qué y cómo preparar el grafo, dependerá de la aplicación y/o de la calidad de los datos y/o de lo cerca que esté la información de tener una topología utilizable por pgRouting y/o algunos otros factores no mencionados.
Los pasos para preparar el grafo implican operaciones de geometría utilizando PostGIS y algunos otros implican operaciones de grafos como pgr_contraction para contraer un grafo.
El taller tiene un paso a paso sobre cómo preparar un grafo utilizando datos de Open Street Map, para una pequeña aplicación.
El uso de índices en el diseño de bases de datos en general:
Tener las geometrías indexadas.
Tener indexadas las columnas de identificadores.
Consultar la documentación de PostgreSQL y la documentación de PostGIS.
Construir una topología de ruteo¶
La información básica para usar la mayoría de las funciones de pgRouting id, source, target, cost, [reverse_cost]
es lo que en pgRouting se llama topología de ruteo.
reverse_cost
es opcional pero se recomienda encarecidamente tenerlo para reducir el tamaño de la base de datos debido al tamaño de las columnas de geometría. Dicho esto, en esta documentación se utiliza reverse_cost
.
Cuando los datos vienen con geometrías y no hay topología de ruteo, entonces este paso es necesario.
Todos los vértices iniciales y finales de las geometrías necesitan un identificador que se almacenará en las columnas source
y target
de la tabla de los datos. Del mismo modo, cost
y reverse_cost
necesitan tener el valor de atravesar la arista en ambas direcciones.
Si las columnas no existen, hay que añadirlas a la tabla en cuestión. (véase ALTER TABLE)
La función pgr_extractVertices – Propuesto se utiliza para crear una tabla de vértices basada en el identificador de arista y la geometría de la arista del grafo.
Finalmente, utilizando los datos almacenados en las tablas de vértices, se rellenan los campos source
y target
.
Consulte Datos Muestra para ver un ejemplo de construcción de una topología.
Los datos procedentes de OSM y utilizando osm2pgrouting <https://github.com/pgRouting/osm2pgrouting>`__ como herramienta de importación, vienen con la topología de ruteo. Ver un ejemplo de uso de ``osm2pgrouting
en el workshop.
Ajustar los costes¶
Para este ejemplo los valores coste
y coste_inverso
van a ser el doble de la longitud de la geometría.
Actualizar los costes a la longitud de la geometría¶
Suponer que las columnas cost
y reverse_cost
de los datos de la muestra representan:
\(1\) cuando la arista existe en el grafo
\(-1\) cuando la arista no existe en el grafo
Utilizando esa información de actualización a la longitud de las geometrías:
UPDATE edges SET
cost = sign(cost) * ST_length(geom) * 2,
reverse_cost = sign(reverse_cost) * ST_length(geom) * 2;
UPDATE 18
Lo que da los siguientes resultados:
SELECT id, cost, reverse_cost FROM edges;
id | cost | reverse_cost
----+--------------------+--------------------
6 | 2 | 2
7 | 2 | 2
4 | 2 | 2
5 | 2 | -2
8 | 2 | 2
12 | 2 | -2
11 | 2 | -2
10 | 2 | 2
17 | 2.999999999998 | 2.999999999998
14 | 2 | 2
18 | 3.4000000000000004 | 3.4000000000000004
13 | 2 | -2
15 | 2 | 2
16 | 2 | 2
9 | 2 | 2
3 | -2 | 2
1 | 2 | 2
2 | -2 | 2
(18 rows)
Tener en cuenta que para poder seguir los ejemplos de la documentación, todo se basa en el grafo original.
Volviendo a los datos originales:
UPDATE edges SET
cost = sign(cost),
reverse_cost = sign(reverse_cost);
UPDATE 18
Actualizar los costes en función de los códigos¶
Otros conjuntos de datos, pueden tener una columna con valores como
FT
flujo de vehículos en la dirección de la geometríaTF
flujo del vehículo opuesto a la dirección de la geometríaB
flujo de vehículos en ambas direcciones
Preparar una columna de códigos para el ejemplo:
ALTER TABLE edges ADD COLUMN direction TEXT;
ALTER TABLE
UPDATE edges SET
direction = CASE WHEN (cost>0 AND reverse_cost>0) THEN 'B' /* both ways */
WHEN (cost>0 AND reverse_cost<0) THEN 'FT' /* direction of the LINESSTRING */
WHEN (cost<0 AND reverse_cost>0) THEN 'TF' /* reverse direction of the LINESTRING */
ELSE '' END;
UPDATE 18
/* unknown */
Ajuste de los costes en función de los códigos:
UPDATE edges SET
cost = CASE WHEN (direction = 'B' OR direction = 'FT')
THEN ST_length(geom) * 2
ELSE -1 END,
reverse_cost = CASE WHEN (direction = 'B' OR direction = 'TF')
THEN ST_length(geom) * 2
ELSE -1 END;
UPDATE 18
Lo que da los siguientes resultados:
SELECT id, cost, reverse_cost FROM edges;
id | cost | reverse_cost
----+--------------------+--------------------
6 | 2 | 2
7 | 2 | 2
4 | 2 | 2
5 | 2 | -1
8 | 2 | 2
12 | 2 | -1
11 | 2 | -1
10 | 2 | 2
17 | 2.999999999998 | 2.999999999998
14 | 2 | 2
18 | 3.4000000000000004 | 3.4000000000000004
13 | 2 | -1
15 | 2 | 2
16 | 2 | 2
9 | 2 | 2
3 | -1 | 2
1 | 2 | 2
2 | -1 | 2
(18 rows)
Volviendo a los datos originales:
UPDATE edges SET
cost = sign(cost),
reverse_cost = sign(reverse_cost);
UPDATE 18
ALTER TABLE edges DROP COLUMN direction;
ALTER TABLE
Compruebe la Topología de Ruteo¶
Hay muchos problemas posibles en un grafo.
Es posible que los datos utilizados no se hayan diseñado teniendo en cuenta el ruteo.
Un grafo tiene unos requisitos muy específicos.
El grafo está desconectado.
Hay intersecciones no deseadas.
El grafo es demasiado grande y hay que contraerlo.
Se necesita un subgrafo para la aplicación.
y muchos otros problemas que el usuario de pgRouting, es decir, el desarrollador de aplicaciones, puede encontrar.
Aristas que se cruzan¶
Para obtener las aristas que se cruzan:
SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
id | id
----+----
13 | 18
(1 row)
Esa información es correcta, por ejemplo, cuando en términos de vehículos, es un túnel o puente cruczando sobre otra carretera.
Puede ser incorrecto, por ejemplo:
Cuando en realidad es una intersección de carreteras, donde los vehículos pueden hacer giros.
En cuanto a las líneas eléctricas, son capaces de cambiar de carretera incluso en un túnel o puente.
Cuando es incorrecta, hay que arreglarla:
Para vehículos y peatones
Si los datos provienen de OSM y fueron importados a la base de datos utilizando
osm2pgrouting
, la corrección debe hacerse en el OSM portal y los datos ser importados de nuevo.En general, cuando los datos proceden de un proveedor que tiene los datos preparados para el ruteo de vehículos, y hay un problema, los datos deben ser fijados por el proveedor
Para aplicaciones muy específicas
Los datos son correctos desde el punto de vista de la circulación de vehículos o peatones.
Los datos necesitan un arreglo local para la aplicación específica.
Una vez analizados uno a uno los cruces, para los que necesitan un arreglo local, hay que dividir las aristas.
SELECT ST_AsText((ST_Dump(ST_Split(a.geom, b.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18
UNION
SELECT ST_AsText((ST_Dump(ST_Split(b.geom, a.geom))).geom)
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18;
st_astext
---------------------------
LINESTRING(3.5 2.3,3.5 3)
LINESTRING(3 3,3.5 3)
LINESTRING(3.5 3,4 3)
LINESTRING(3.5 3,3.5 4)
(4 rows)
Hay que añadir las nuevas aristas a la tabla de aristas, actualizar el resto de atributos en las nuevas aristas, eliminar las aristas antiguas y actualizar la topología de encaminamiento.
Añadir aristas divididas¶
Para cada par de aristas de cruce debe realizarse un proceso similar a éste.
Las columnas insertadas y la forma en que se calculan se basan en la aplicación. Por ejemplo, si las aristas tienen un rasgo nombre, se copiará esa columna.
Para llos cálculos de pgRouting
Se puede utilizar un factor basado en la posición de la intersección de las aristas para ajustar las columnas
cost
yreverse_cost
.La información de capacidad, utilizada en las funciones Flow - Familia de funciones no necesita cambiar al dividir aristas.
WITH
first_edge AS (
SELECT (ST_Dump(ST_Split(a.geom, b.geom))).path[1],
(ST_Dump(ST_Split(a.geom, b.geom))).geom,
ST_LineLocatePoint(a.geom,ST_Intersection(a.geom,b.geom)) AS factor
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18),
first_segments AS (
SELECT path, first_edge.geom,
capacity, reverse_capacity,
CASE WHEN path=1 THEN factor * cost
ELSE (1 - factor) * cost END AS cost,
CASE WHEN path=1 THEN factor * reverse_cost
ELSE (1 - factor) * reverse_cost END AS reverse_cost
FROM first_edge , edges WHERE id = 13),
second_edge AS (
SELECT (ST_Dump(ST_Split(b.geom, a.geom))).path[1],
(ST_Dump(ST_Split(b.geom, a.geom))).geom,
ST_LineLocatePoint(b.geom,ST_Intersection(a.geom,b.geom)) AS factor
FROM edges AS a, edges AS b
WHERE a.id = 13 AND b.id = 18),
second_segments AS (
SELECT path, second_edge.geom,
capacity, reverse_capacity,
CASE WHEN path=1 THEN factor * cost
ELSE (1 - factor) * cost END AS cost,
CASE WHEN path=1 THEN factor * reverse_cost
ELSE (1 - factor) * reverse_cost END AS reverse_cost
FROM second_edge , edges WHERE id = 18),
all_segments AS (
SELECT * FROM first_segments
UNION
SELECT * FROM second_segments)
INSERT INTO edges
(capacity, reverse_capacity,
cost, reverse_cost,
x1, y1, x2, y2,
geom)
(SELECT capacity, reverse_capacity, cost, reverse_cost,
ST_X(ST_StartPoint(geom)), ST_Y(ST_StartPoint(geom)),
ST_X(ST_EndPoint(geom)), ST_Y(ST_EndPoint(geom)),
geom
FROM all_segments);
INSERT 0 4
Añadiendo nuevos vértices¶
Después de añadir todas las aristas de división requeridas por la aplicación, es necesario añadir los vértices recién creados a la tabla de vértices.
INSERT INTO vertices (in_edges, out_edges, x, y, geom)
(SELECT nv.in_edges, nv.out_edges, nv.x, nv.y, nv.geom
FROM pgr_extractVertices('SELECT id, geom FROM edges') AS nv
LEFT JOIN vertices AS v USING(geom) WHERE v.geom IS NULL);
INSERT 0 1
Actualizar la topología de aristas¶
/* -- set the source information */
UPDATE edges AS e
SET source = v.id
FROM vertices AS v
WHERE source IS NULL AND ST_StartPoint(e.geom) = v.geom;
UPDATE 4
/* -- set the target information */
UPDATE edges AS e
SET target = v.id
FROM vertices AS v
WHERE target IS NULL AND ST_EndPoint(e.geom) = v.geom;
UPDATE 4
Eliminar las aristas sobrantes¶
Una vez que toda la información significativa que necesita la aplicación se ha transportado a las nuevas aristas, se pueden eliminar las aristas de cruce.
DELETE FROM edges WHERE id IN (13, 18);
DELETE 2
Existen otras opciones para realizar esta tarea, como crear una vista, o una vista materializada.
Actializar la topología de vértices¶
Para mantener la coherencia del grafo, es necesario actualizar la topología de los vértices
UPDATE vertices AS v SET
in_edges = nv.in_edges, out_edges = nv.out_edges
FROM (SELECT * FROM pgr_extractVertices('SELECT id, geom FROM edges')) AS nv
WHERE v.geom = nv.geom;
UPDATE 18
Comprobación del cruce de aristas¶
No hay aristas que se crucen en el grafo.
SELECT a.id, b.id
FROM edges AS a, edges AS b
WHERE a.id < b.id AND st_crosses(a.geom, b.geom);
id | id
----+----
(0 rows)
Grafos desconectados¶
Para obtener la conectividad del grafo:
SELECT * FROM pgr_connectedComponents(
'SELECT id, source, target, cost, reverse_cost FROM edges'
);
seq | component | node
-----+-----------+------
1 | 1 | 1
2 | 1 | 3
3 | 1 | 5
4 | 1 | 6
5 | 1 | 7
6 | 1 | 8
7 | 1 | 9
8 | 1 | 10
9 | 1 | 11
10 | 1 | 12
11 | 1 | 13
12 | 1 | 14
13 | 1 | 15
14 | 1 | 16
15 | 1 | 17
16 | 1 | 18
17 | 2 | 2
18 | 2 | 4
(18 rows)
En este ejemplo, el componente \(2\) está formado por vértices \(\{2, 4\}\) y ambos vértices también forman parte del conjunto de resultados sin salida.
Este grafo debe estar conectado.
Nota
Con el grafo original de esta documentación, habría 3 componentes, ya que la arista de cruce en este grafo es un componente diferente.
Preparar el almacenamiento de la información de conexión¶
ALTER TABLE vertices ADD COLUMN component BIGINT;
ALTER TABLE
ALTER TABLE edges ADD COLUMN component BIGINT;
ALTER TABLE
Guardar la información de conexión de los vértices¶
UPDATE vertices SET component = c.component
FROM (SELECT * FROM pgr_connectedComponents(
'SELECT id, source, target, cost, reverse_cost FROM edges'
)) AS c
WHERE id = node;
UPDATE 18
Guardar la información de conexión de las aristas¶
UPDATE edges SET component = v.component
FROM (SELECT id, component FROM vertices) AS v
WHERE source = v.id;
UPDATE 20
Obtener el vértice más cercano¶
Usando pgr_findCloseEdges el vértice más cercano al componente \(1\) es el vértice \(4\). Y la arista más cercana al vértice \(4\) es la arista \(14\).
SELECT edge_id, fraction, ST_AsText(edge) AS edge, id AS closest_vertex
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges WHERE component = 1$$,
(SELECT array_agg(geom) FROM vertices WHERE component = 2),
2, partial => false) JOIN vertices USING (geom) ORDER BY distance LIMIT 1;
edge_id | fraction | edge | closest_vertex
---------+----------+--------------------------------------+----------------
14 | 0.5 | LINESTRING(1.999999999999 3.5,2 3.5) | 4
(1 row)
La arista edge
se puede utilizar para conectar los componentes, utilizando la información fraction
sobre la arista \(14\) para dividir la arista de conexión.
Conectando componentes¶
Existen tres formas básicas de conectar los componentes
Del vértice al punto inicial de la arista
Desde el vértice hasta el punto final de la arista
Del vértice al vértice más cercano de la arista
Esta solución requiere dividir el borde.
La siguiente consulta muestra las tres formas de conectar los componentes:
WITH
info AS (
SELECT
edge_id, fraction, side, distance, ce.geom, edge, v.id AS closest,
source, target, capacity, reverse_capacity, e.geom AS e_geom
FROM pgr_findCloseEdges(
$$SELECT id, geom FROM edges WHERE component = 1$$,
(SELECT array_agg(geom) FROM vertices WHERE component = 2),
2, partial => false) AS ce
JOIN vertices AS v USING (geom)
JOIN edges AS e ON (edge_id = e.id)
ORDER BY distance LIMIT 1),
three_options AS (
SELECT
closest AS source, target, 0 AS cost, 0 AS reverse_cost,
capacity, reverse_capacity,
ST_X(geom) AS x1, ST_Y(geom) AS y1,
ST_X(ST_EndPoint(e_geom)) AS x2, ST_Y(ST_EndPoint(e_geom)) AS y2,
ST_MakeLine(geom, ST_EndPoint(e_geom)) AS geom
FROM info
UNION
SELECT closest, source, 0, 0, capacity, reverse_capacity,
ST_X(geom) AS x1, ST_Y(geom) AS y1,
ST_X(ST_StartPoint(e_geom)) AS x2, ST_Y(ST_StartPoint(e_geom)) AS y2,
ST_MakeLine(info.geom, ST_StartPoint(e_geom))
FROM info
/*
UNION
-- This option requires splitting the edge
SELECT closest, NULL, 0, 0, capacity, reverse_capacity,
ST_X(geom) AS x1, ST_Y(geom) AS y1,
ST_X(ST_EndPoint(edge)) AS x2, ST_Y(ST_EndPoint(edge)) AS y2,
edge
FROM info */
)
INSERT INTO edges
(source, target,
cost, reverse_cost,
capacity, reverse_capacity,
x1, y1, x2, y2,
geom)
(SELECT
source, target, cost, reverse_cost, capacity, reverse_capacity,
x1, y1, x2, y2, geom
FROM three_options);
INSERT 0 2
Revisando componentes¶
Ignorando la arista que requiere más trabajo. El grafo está ahora totalmente conectado, ya que sólo hay un componente.
SELECT * FROM pgr_connectedComponents(
'SELECT id, source, target, cost, reverse_cost FROM edges'
);
seq | component | node
-----+-----------+------
1 | 1 | 1
2 | 1 | 2
3 | 1 | 3
4 | 1 | 4
5 | 1 | 5
6 | 1 | 6
7 | 1 | 7
8 | 1 | 8
9 | 1 | 9
10 | 1 | 10
11 | 1 | 11
12 | 1 | 12
13 | 1 | 13
14 | 1 | 14
15 | 1 | 15
16 | 1 | 16
17 | 1 | 17
18 | 1 | 18
(18 rows)
Contracción de un grafo¶
El grafo puede reducirse de tamaño utilizando Contraction - Familia de funciones
El cuando contraer dependerá del tamaño del gráfico, de los tiempos de procesamiento, de la corrección de los datos, de la aplicación final o de cualquier otro factor no mencionado.
A fairly good method of finding out if contraction can be useful is because of the number of dead ends and/or the number of linear edges.
A complete method on how to contract and how to use the contracted graph is described on Contraction - Familia de funciones
Callejones sin salida¶
To get the dead ends:
SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 1;
id
----
1
5
9
13
14
2
4
(7 rows)
That information is correct, for example, when the dead end is on the limit of the imported graph.
Visually node \(4\) looks to be as start/ending of 3 edges, but it is not.
Is that correct?
Is there such a small curb:
That does not allow a vehicle to use that visual intersection?
Is the application for pedestrians and therefore the pedestrian can easily walk on the small curb?
Is the application for the electricity and the electrical lines than can easily be extended on top of the small curb?
Is there a big cliff and from eagles view look like the dead end is close to the segment?
When there are many dead ends, to speed up, the Contraction - Familia de funciones functions can be used to divide the problem.
Linear edges¶
To get the linear edges:
SELECT id FROM vertices
WHERE array_length(in_edges || out_edges, 1) = 2;
id
----
3
15
17
(3 rows)
This information is correct, for example, when the application is taking into account speed bumps, stop signals.
When there are many linear edges, to speed up, the Contraction - Familia de funciones functions can be used to divide the problem.
Function’s structure¶
Once the graph preparation work has been done above, it is time to use a
La forma general de una llamada a una función de pgRouting es:
pgr_<name>(Inner queries, parameters, [
Optional parameters
)
Donde:
Inner queries: Are compulsory parameters that are
TEXT
strings containing SQL queries.parameters: Additional compulsory parameters needed by the function.
Optional parameters
: Are non compulsory named parameters that have a default value when omitted.
The compulsory parameters are positional parameters, the optional parameters are named parameters.
For example, for this pgr_dijkstra signature:
pgr_dijkstra(SQL de aristas, salidas, destinos, [directed
])
-
Is the first parameter.
It is compulsory.
It is an inner query.
It has no name, so Edges SQL gives an idea of what kind of inner query needs to be used
vid inical:
Es el segundo parámetro.
It is compulsory.
It has no name, so start vid gives an idea of what the second parameter’s value should contain.
destino
Is the third parameter.
It is compulsory.
It has no name, so end vid gives an idea of what the third parameter’s value should contain
directed
Is the fourth parameter.
It is optional.
It has a name.
The full description of the parameters are found on the Parameters section of each function.
Function’s overloads¶
A function might have different overloads. The most common are called:
Dependiendo de la sobrecarga, los tipos de los parámetros cambian.
One: ANY-INTEGER
Many:
ARRAY
[ANY-INTEGER]
Depending of the function the overloads may vary. But the concept of parameter type change remains the same.
Uno a Uno¶
Cuando se rutea desde:
Desde un vértice inicial
al un vértice final
Uno a Muchos¶
Cuando se rutea desde:
Desde un vértice inicial
a los vértices finales many
Muchos a Uno¶
Cuando se rutea desde:
Desde muchos vértices iniciales
al un vértice final
Muchos a Muchos¶
Cuando se rutea desde:
Desde muchos vértices iniciales
a los vértices finales many
Combinaciones¶
Cuando se rutea desde:
A partir de muchos diferentes vértices de inicio
a muchos diferentes vértices finales
Cada tupla especifica un par de vértices iniciales y un vértice final
Los usuarios pueden definir las combinaciones como deseen.
Necesita una SQL de combinaciones
Consultas Internas¶
Hay varios tipos de consultas internas válidas y también las columnas devueltas dependen de la función. El tipo de consulta interna dependerá de los requisitos de las funcion(es). Para simplificar la variedad de tipos, se utiliza ENTEROS y FLOTANTES.
Donde:
- ENTEROS:
SMALLINT, INTEGER, BIGINT
- FLOTANTES:
SMALLINT, INTEGER, BIGINT, REAL, FLOAT
SQL aristas¶
General¶
SQL de aristas para
Some uncategorised functions
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
General without id
¶
SQL de aristas para
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
General with (X,Y)¶
SQL de aristas para
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista (
|
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
|
FLOTANTES |
Coordenada X del vértice |
|
|
FLOTANTES |
Coordenada Y del vértice |
|
|
FLOTANTES |
Coordenada X del vértice |
|
|
FLOTANTES |
Coordenada Y del vértice |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Flujo¶
Edges SQL for Flow - Familia de funciones
SQL de aristas para
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
ENTEROS |
Peso de la arista ( |
|
|
ENTEROS |
-1 |
Peso de la arista (
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Edges SQL for the following functions of Flow - Familia de funciones
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
ENTEROS |
Capacidad de la arista (
|
|
|
ENTEROS |
-1 |
Capacidad de la arista (
|
|
FLOTANTES |
Peso de la arista ( |
|
|
FLOTANTES |
\(-1\) |
Peso de la arista ( |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
SQL Combinaciones¶
Utilizado en combinación firmas
Parámetro |
Tipo |
Descripción |
---|---|---|
|
ENTEROS |
Identificador del vértice de salida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
SQL restricciones¶
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Secuencia de identificadores de aristas que forman un camino que no se permite tomar. - Arreglos vacios o |
|
FLOTANTES |
Costo de tomar el camino prohibido. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
SQL de puntos¶
SQL de puntos para
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
valor |
Identificador del punto.
|
|
ENTEROS |
Identificador de la arista «más cercana» al punto. |
|
|
FLOTANTES |
El valor en <0,1> que indica la posición relativa desde el primer punto de la arista. |
|
|
|
|
Valor en [
|
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Parámetros¶
The main parameter of the majority of the pgRouting functions is a query that selects the edges of the graph.
Parámetro |
Tipo |
Descripción |
---|---|---|
|
SQL de aristas descritas más adelante. |
Depending on the family or category of a function it will have additional parameters, some of them are compulsory and some are optional.
The compulsory parameters are nameless and must be given in the required order. The optional parameters are named parameters and will have a default value.
Párametros para las funciones Via¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
Consulta SQL como se describe. |
||
vértices |
|
Arreglo ordenado de identificadores de vértices que serán visitados. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Para las funciones de TRSP¶
Columna |
Tipo |
Descripción |
---|---|---|
|
Consulta SQL como se describe. |
|
|
Consulta SQL como se describe. |
|
|
SQL de combinaciones como se describe a abajo |
|
salida |
ENTEROS |
Identificador del vértice de salida. |
salidas |
|
Arreglo de identificadores de vértices destino. |
destino |
ENTEROS |
Identificador del vértice de salida. |
destinos |
|
Arreglo de identificadores de vértices destino. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Columnas de resultados¶
Hay varios tipos de columnas devueltas que dependen de la función.
Columnas de resultados para una ruta¶
Used in functions that return one path solution
Devuelve el conjunto de (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 inicio 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 |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Se utiliza en las funciones siguientes:
Devuelve el conjunto de (seq, path_seq [, start_pid] [, end_pid], node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Posición relativa en la ruta.
|
|
|
Identificador del vértice/punto inicial de la ruta.
|
|
|
Identificador d vértice/punto final del camino.
|
|
|
Identificador del nodo en la ruta de
|
|
|
Identificador de la arsita utilizada para ir del
|
|
|
Costo para atravesar desde
|
|
|
Costo agregado desde
|
Se utiliza en las funciones siguientes:
Regresa (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 inicio de una ruta. |
|
|
Identificador del vértice inicial de la ruta actual. |
|
|
Identificador del vértice final de la ruta actual. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Multiple paths¶
Selective for multiple paths.¶
The columns depend on the function call.
Conjunto de (seq, path_id, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Identificador del camino.
|
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio 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 |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Non selective for multiple paths¶
Regardless of the call, al the columns are returned.
Devuelve el conjunto de (seq, path_id, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Identificador del camino.
|
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del vértice de salida. |
|
|
Identificador del vértice final. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Columnas de resultados de las funciones de costes¶
Used in the following
Conjunto de (start_vid, end_vid, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador del vértice de salida. |
|
|
Identificador del vértice final. |
|
|
Costo afregado desde |
Nota
Cuando las columnas del vértice inicial o del destino continen valores negativos, el identificador es para un Punto.
Columnas de resultados para funciones de flujo¶
Edges SQL for the following
Columna |
Tipo |
Descripción |
---|---|---|
seq |
|
Valor secuencial a partir de 1. |
arista |
|
Identificador de la arista en la consulta original(edges_sql). |
start_vid |
|
Identificador del primer vértice de la arista. |
end_vid |
|
Identificador del segundo vértice de la arista. |
flujo |
|
Flujo a través del arista en la dirección ( |
residual_capacity |
|
Capacidad residual del arista en la dirección ( |
Edges SQL for the following functions of Flow - Familia de funciones
Columna |
Tipo |
Descripción |
---|---|---|
seq |
|
Valor secuencial a partir de 1. |
arista |
|
Identificador de la arista en la consulta original(edges_sql). |
origen |
|
Identificador del primer vértice de la arista. |
objetivo |
|
Identificador del segundo vértice de la arista. |
flujo |
|
Flujo a través de la arista en la dirección (origen, destino). |
residual_capacity |
|
Capacidad residual de la arista en la dirección (origen, destino). |
costo |
|
El costo de enviar este flujo a través de la arista en la dirección (origen, destino). |
agg_cost |
|
El costo agregado. |
Columnas de resultados para funciones de árbol de expansión¶
Edges SQL for the following
Regresa el conjunto de (edge, cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador de la arista. |
|
|
Coste para atravezar el borde. |
Consejos de Rendimiento¶
Para las funciones de Ruteo¶
Para obtener resultados más rápidos, delimitar las consultas a un área de interés para el ruteo.
En este ejemplo, usar una consulta SQL interna que no incluya algunas aristas en la función de ruteo y dentro del área de los resultados.
SELECT * FROM pgr_dijkstra($$
SELECT id, source, target, cost, reverse_cost from edges
WHERE geom && (SELECT st_buffer(geom, 1) AS myarea
FROM edges WHERE id = 2)$$,
1, 2);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
(0 rows)
Cómo contribuir¶
Wiki
Edita una página existente Wiki de pgRouting.
O crea una nueva página Wiki
Crear una página en el Wiki de pgRouting
Asigne al título un nombre apropiado
Agregar funcionalidad a pgRouting
Consultar la documentation de desarrolladores
Índices y tablas