What does 'building topology' mean for pgRouting?

Question

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?

Answer 1

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 :)

Answer 2

To follow on from Ragi's excellent answer, the data stored in a geometry column is just there to make pretty pictures, it has no logical relationship to any other piece of geometry. For instance, two counties share a border, but the lines that make up those borders are separate entities: if you move one line of one county border, you will see a gap between the counties. If, on the other hand, they were topologically related, there would be a conceptual single line that separates them, so moving that line will be reflected in both counties' borders.

With pgRouting, the nodes and ways of your example (which is the OSM nomenclature for such things, they are also known as vertices and edges, and any number of other things) represent this logical connectedness. In general, for a road network, nodes represent junctions, and ways are the lines joining those nodes. So say you have a road that in the real world is called the A38, and which has 5 side roads coming off it, it will be made of 7 nodes (including the start and end nodes), and 6 ways. The ways will be unique but have the same name tag of A38, but pgRouting knows how they are all joined up. Now, the road may twist and snake between nodes, but topologically that is unimportant, the same structure can be represented with straight lines between nodes. The London Underground map is a good example of the topological relationship between stations where absolute locations is pointless when you're underground.