[GIS] What does ‘building topology’ mean for pgRouting

pgroutingpostgistopology

From a couple of answers at gis.stackexchange.com and at the pgRouting mailing list I have found out that pgRouting 'builds topology'. What does that mean?

If for example we import an .osm file into PostGIS and then apply all the pgRouting scripts, what does happen?

I thought that pgRouting just creates a table of road links (edges) from the OSM nodes, but after following the FOSS4G workshop I see the following tables in my database:

List of relations
 Schema |       Name       | Type  |  Owner   
--------+------------------+-------+----------
 public | classes          | table | postgres
 public | geometry_columns | table | postgres
 public | nodes            | table | postgres
 public | spatial_ref_sys  | table | postgres
 public | types            | table | postgres
 public | vertices_tmp     | table | postgres
 public | ways             | table | postgres

I know what geometry_columns and spatial_ref_sys serve for, but what about the other tables and how do they relate to each other?

What is topology in pgRouting's parlance?

Best Answer

Routing is a graph problem, not a pure geometry problem per se (I am using a bit loose terms here for the sake of clarity). What that means is that you have to grab the original geometries from your features - potentially from various different spatial tables (aka Feature Classes in ESRI speak) and build a graph representation (aka Network Topology ) that is suitable for traditional routing algorithms like A*, traditional Dijkstra, etc. You have to think that, depending on the problem you are solving, you may choose different weights assigned to traversing the edges (is cost traversal based on geometric length, or some attribute like speed limit?), put restrictions on turns around edges (is a left or u-turn allowed?), assign different classes to the edges (residential, freeway, toll bridge, whatever), etc etc. Heck, you even have a choice to do node-to-node routing or edge-to-edge which gives different results.

The process of extracting the necessary information from your spatial tables is referred to as "building network topology" and the tables are where they are stored on the db. With the information I gave you, hopefully now the become obvious :)

Related Question