Creating Data for Routing Applications
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.
Graphs, Directed, unDirected, Reverse Costs
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
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:
PostGIS
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 are very little documentation yet on how to create the topology. This page will be updated once the topology functionality becomes stable enough to use.
ArcInfo
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
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.
Program
Support topology http://pgrouting.postlbs.org/ticket/27
