How to: v2.0
pgRouting v2.0
- Is no longer supported
- This page is Historical
Here you can find the "How to" for that version.
Table of Contents:
- Author: Daniel Kastl
- License: Creative Commons
Both Dijkstra and A-Star algorithms have the ability to compute the cost for both sides of an edge of a graph, which can be very useful when finding a route with a road network that has one-way streets.
This little example will illustrate how this is done. The sample data was created using OpenJump and then was saved in a PostGIS database where pgRouting was also installed.
The graph looks like this; note that edge !#2 was digitized from right to left, unlike most of the edges which were digitized left to right. This was done to simulate a one way street.
When computing for the cost of both sides of the edge, a reverse_cost field is necessary to be passed to the routing algorithm.
Initially, both the cost and the reverse_cost values set to the length of the edge.
routing=# UPDATE rtest SET cost=length(the_geom), rcost=length(the_geom);
UPDATE 5
Then, to increase the reverse_cost of edge !#2, a value of 1,000,000 was added to the value of the reverse_cost field.
routing=# UPDATE rtest SET rcost=rcost + 1000000 WHERE gid = 2;
routing=# SELECT gid,cost,rcost,source,target FROM rtest ORDER BY gid;
gid | cost | rcost | source | target
----+------------------+---------------------+--------+--------
1 | 90.4777391240398 | 90.4777391240398 | 1 | 2
2 | 266.663211021467 | 000266.663211021467 | 3 | 2
3 | 74.7975644284963 | 74.7975644284963 | 2 | 4
4 | 264.887335603738 | 264.887335603738 | 4 | 5
5 | 49.0618009646755 | 49.0618009646755 | 3 | 5
(5 rows)
The last parameter of both Dijkstra and A-Star algorithms determines whether the reverse cost will also be computed when finding a route through the graph.
When set to false, both algorithms will search using only the cost parameter, which in this case is just the length of each edge. For this example, we'll find a route between node #1 until node #3.
routing=# SELECT * FROM shortest_path_astar('SELECT gid AS id,source::int4,
target::int4, cost::double precision, rcost::double precision AS reverse_cost,
x1,y1,x2,y2 FROM rtest',1,3,false,false);
vertex_id | edge_id | cost
-----------+---------+------------------
1 | 1 | 90.4777391240398
2 | 2 | 266.663211021467
3 | -1 | 0
(3 rows)
Now, if the reverse parameter is set to true, the algorithms will use the reverse_cost and see that node 2 of edge #2 has a very high cost and will look for another route.
routing=# SELECT * FROM shortest_path_astar('SELECT gid AS id, source::int4,
target::int4, cost::double precision, rcost::double precision AS reverse_cost,
x1,y1,x2,y2 FROM rtest',1,3,false,true);
vertex_id | edge_id | cost
----------+---------+------------------
1 | 1 | 90.4777391240398
2 | 3 | 74.7975644284963
4 | 4 | 264.887335603738
5 | 5 | 49.0618009646755
3 | -1 | 0
(5 rows)
Although having the ability to compute the cost of both sides of the edge is a very nifty feature, it come with a heavy price since it will impact performance quite a bit and thus should be used only when it is really necessary.
routing=# EXPLAIN ANALYZE SELECT * FROM shortest_path_astar('SELECT gid
AS id,source::int4, target::int4, cost::double precision, rcost::double
precision AS reverse_cost,x1,y1,x2,y2 FROM rtest',1,3,false,false);
QUERY PLAN
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar (cost=0.00..12.50 rows=1000 width=16)
(actual time=0.954..0.958 rows=3 loops=1) Total runtime: 1.020 ms
(2 rows)
routing=# EXPLAIN ANALYZE SELECT * FROM shortest_path_astar('SELECT gid
AS id, source::int4, target::int4, cost::double precision, rcost::double
precision AS reverse_cost,x1,y1,x2,y2 FROM rtest',1,3,false,true);
QUERY PLAN
--------------------------------------------------------------------------------
Function Scan on shortest_path_astar (cost=0.00..12.50 rows=1000 width=16)
(actual time=11.088..11.093 rows=5 loops=1) Total runtime: 11.155 ms(2 rows)
the end.
- Author: Daniel Kastl
- License: Creative Commons
Routing Engines always require the source and target nodes for every line in order to create a search for the shortest path. Creating this data on line networks involves creating a topology on that network.
The follow will hopefully explain a little bit about graphs and and how to use the directed and reverse cost arguments in the pgRouting function calls. If you use assign_vertex_id() to build your graph, it builds an undirected graph. Now you might have some oneway streets and you can create a reverse_cost column and start by populating it with the cost column values. Now you can treat you graph as a directed graph using the forward cost and reverse_cost for the cost to traverse an edge from A-B or B-A respectively. Since these values are all the same it is not very interesting, but if you have oneway streets you can now edit the cost or the reverse_cost values so that the wrong way has a very high cost. Many of the pgRouting function have boolean arguments '''directed''' and '''has_reverse_cost'''. If you set '''has_reverse_cost=true''', you should also set '''directed=true''' or it will ignore your reverse costs.
pgRouting gives the ability to create the source-target (start-end nodes) information within PostgreSQL using assign_vertex_id():
SELECT assign_vertex_id(table_name, snapping_range, geometry_column_name, edge_id_column_name);
where table_name is the name of the edges table, nodes within snapping_range (value is in your current projection units) will be snapped, geometry_column_name is the name of the geometry column (usually 'the_geom'), edge_id_column_name is the name of the edge id column (usually gid).
This function requires 'source' and 'target' integer fields.
ALTER TABLE ways ADD COLUMN source integer;
ALTER TABLE ways ADD COLUMN target integer;
SELECT assign_vertex_id('ways', 0.00001, 'the_geom', 'gid');
There is other software, that can be used to create a topology:
As of this writing, the latest PostGIS 1.1.2, has started adding a topology functionality. But it is still in a very alpha stage and there is very little documentation yet on how to create the topology. This page will be updated once the topology functionality becomes stable enough to use.
For those with an !ArcInfo license, creating a topology is done by just issuing the BUILD command:
build line {Coverage Name}
and then exporting the coverage to a shape file, which can then be imported into PostGIS. The BUILD command will build fnode, tnode, length columns which can be renamed in PostgreSQL into source and target, and the length can be set as the intial cost.
GRASS can be used also to create a topology, but extracting the topology information and bringing it into PostgreSQL is not as simple as that of !ArcInfo's since the topolgy information is not included into with the data set when it is exported to a shape file.
The topolgy creation command "v.build" has a dump option though that will output the information into the stream which in turn can be piped into to a file. For example:
v.build map=dourol option=build,dump > dourokukan.txt
The output will be like this;
---------- TOPOLOGY DUMP ----------
N,S,E,W,T,B: 35.897887, 24.281578, 153.985841, 138.943042, 0.000000, 0.000000
Nodes (148304 nodes, alive + dead ):
node = 1, n_lines = 3, xy = 139.756532, 35.67451
line = 1, type = 2, angle = -2.265356
line = -20, type = 2, angle = -0.055499
line = 8, type = 2, angle = 1.281166
node = 2, n_lines = 3, xy = 139.756261, 35.674216
line = -9, type = 2, angle = -2.827622
line = 2, type = 2, angle = -1.878154
...
...
...
Lines (220672 lines, alive + dead ):
line = 1, type = 2, offset = 14 n1 = 1, n2 = 2, left/area = 0, right = 0
N,S,E,W,T,B: 35.674510, 35.674216, 139.756532, 139.756261, 0.000000, 0.000000
line = 2, type = 2, offset = 79 n1 = 2, n2 = 3, left/area = 0, right = 0
N,S,E,W,T,B: 35.674216, 35.672010, 139.756261, 139.755285, 0.000000, 0.000000
line = 3, type = 2, offset = 160 n1 = 3, n2 = 4, left/area = 0, right = 0
N,S,E,W,T,B: 35.672010, 35.671649, 139.755285, 139.755014, 0.000000, 0.000000
A perl program like table_topo.pl can be used to convert GRASS output into SQL files that will create node and line tables containing the topological information. These tables can then be linked into the PostGIS network table to create the source-target node information.
