Update of "graphs-intro"
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview

Artifact ID: da508a08a68c887f903fc6f6beeeaa8fd666a3da
Page Name:graphs-intro
Date: 2012-05-02 18:25:18
Original User: sandro
Parent: 3ec46122050f6e97e6db13cda0ca294fee2add51 (diff)
Content

back to the OSM tools Wiki page.

Routing algorithms are intended to identify the shortest path connecting two points on a network; but a network, in order to properly support routing algorithms must be carefully represented as a graph, i.e. must absolutely respect some strong topological constraints:


graph-ok.png When a graph contains topological inconsistencies, this condition forbids the routing algorithms to compute the expected optimal travel solution: you can think of this as a kind of data poisoning.
Do you remember the immortal GIGO principle, the one stating that garbage in, garbage out ?

It's the infamous wrongly-noded condition, unhappily affecting many graphs: as much more noding-errors there are in a graph, as lowest will be its average quality. Graphs affected by a large amount of noding-errors are quite useless for any practical purpose, and should be considered of infimous quality.

A correctly-noded graph (i.e. one you can expect to decently support routing algorithms) should exactly be as the one shown:
  • each intersection is clearly marked by a corresponding node (all nodes are numbered in this figure)
  • each way (road, street or whatever else) is represented as a collection of many consecutive individual arcs, clearly split accordingly to intersections (aka nodes)
  • Please note: pay close attention to the two intersections marked by black arrows: there is no node here, i.e. there there is no connection, even if there is an apparent intersection between two arcs.
This is not at all an exceptional condition: simply think of some flyover (aka overpass); obviously a car cannot magically jump from one arc to the other (because there is strong vertical gap separating the one from the other). So in this case the intersection simply is a perspective illusion, due to 2D flattening on the map: but there is no real connection between the arcs. Exactly the same is for tunnels and subways (aka underpasses).
Placing a Node on the Graph on these cases is an obviuos error, and will cause routing algorithms to return crazy and misleading travel solutions.

Important conclusion: re-processing a malformed Graph could apparently seem an obvious option in order to enhance a poor and unsatisfying average quality: but such an automatic process seriously risks to introduce many further unexpected noding errors into the Graph. Poor quality always remains poor quality; there is no silver bullet you can use in order to safely recover missing / wrong informations in the underlying raw-data.
high-five.jpg

Reality check: Networks in Open Street Map

Roma_Centro.png Open Street Map is a well known community-driven project aimed to produce a high-quality, detailed (and absolutely free) map of the world. OSM represents all map objects using the following three-tier hierarchy:
  • Nodes simply are geometric points: an OSM-Node may represent e.g. a tree, a pylon, a school, a shop ...
  • Ways are ordered sequences of nodes (i.e. they are geometric polylines): an OSM-Way may represent e.g. a wall, a canal, a road, a cycleway ...
  • Relations are complex objects based on Nodes, Ways or other Relations as well: a typical OSM-Relation may represent e.g. a complex route, an area such as a building, a wood, a lake ...
  • each OSM-object is fully qualified by an accompanying set of tags, i.e. by key:value pairs specifying the intended role (e.g. highway:motorway, highway:cycleway or railway:rail) and other properties useful in order to qualify the mapped object.

Supporting very rich and detailed data useful for routing purposes seems to be one of the main scopes of the OSM project, accordingly to the accompanying documentation. Let's go to directly check what is reality.
Unhappily (as first hand experience sadly learns), OSM-Ways representing roads, streets and alike aren't modelled at all accordingly to the before mentioned properly-noded criteria expected by a Graph.
The actual situation widely varies from country to country (from town to town more precisely, mainly accordingly to local mappers tastes and preferences ... this one is a community-project after all, you cannot expect a strong overall consistency): anyway, the most typical case you can expect to encounter is the one shown:
  • a typical Way represents a uninterrupted line accordingly to topomimy / traffic regulation (in this figure numbers identify each OSM-Way)
  • very rarely intersections (aka junctions / crossings) are explictitly represented as naively expected
  • happily enough, in many cases (not always ..) an OSM-Node is wisely placed corresponding to the intersection; so reconstructing a genuine Graph is a real option (although one surely requiring a huge re-processing work).
  • Please note: such an indirect approach requires applying many heuristic assumptions.
    Do you remember the before mentioned flyover / subway dilemma ?
    While attempting to correctly renode the Graph we'll surely risk to introduce several false-intersections, and there is absolutely no way to avoid this, simply because OSM raw-data very often doesn't supply enough informations in order to correctly identify the Nodes and the Arcs of the Graph.
graph-ko.png

Railway Networks in Open Street Map

OSM supports railway network as well: attempting to apply routing algorithms to some railway graph may apparently seem a rather extravagant option, but is a real task usually performed by traffic engineers for planning purposes.
Moreover railway networks are usually much simpler than road networks: so after all getting a glance at them may be useful in order to acquire some general order conclusion about OSM networks.
rail1.png OSM railways representations are surprisingly detailed: each single rail seems to be correctly mapped, at least as a general tendency.
Yet another time detail and accuracy widely vary depending on local mappers taste: anyway in many cases there is an appreciable attempt to carefully reproduce each single rail into the map.
Anyway, at least in this very specific example, a strong simplification has been applied: in real world this main railway line is double-track, not single-track as in the OSM map. So after all, this representation is only apparently accurate.

Please note: any rail junction used in the above station actually corresponds to a single slip switch, as the one shown in this picture (the simplest and most widely used kind of rail switch).
single_slip.jpg
double_slip.jpg rail2.png Not all rail junctions are so simple as the ones shown above. A further more complex case exists: when two rails crosses (as shown by the black arrow) we can expect to have two strongly different conditions:
  • a double slip switch actually allows to choose between two different directions (i.e. it must be represented as a Node into the Graph)
  • a flat crossing (aka level junction) doesn't support this capability, and shouldn't be represented as a Node
  • expecting such a sophisticate representation to be consistently supported by OSM seems to be a little bit overoptimistic
level_junction.jpg
Yet another possible condition exists: as this OSM examples correctly shows, a flying junction exists when two railway lines crosses, but at different levels and being separated by a vertical gap (i.e. one line passes over the other one).

In this case inserting a Node corresponding to the junction is an obvious error, and will introduce into the Graph a false-connection not existing in the real world; and in turn this may well be the cause of absurdly misleading and highly improbable routing results.
flying.png

Common noding errors plaguing OSM networks: a first example

rail4.png rail4zoom.png
This railway line (about 15 Km) apparently seems to be a valid one at first glance: anyway no routing algorithm will never be able to transit on this line.
The cause accounting for this issue isn't at all easy to be identified: I actually used a rather sophisticated analysis based on Node Cardinality, i.e. carefully determining the number of Arcs connected to each Node.
In the position pointed by the black arrow there is at least one Node (red dot) presenting a Cardinality=1, i.e. belonging to simply one Arc, thus representing a terminal node and not allowing any further connection.
While exploring this selected area at high zoom factors anything becomes immediately clear: there is a bad topological inconsistency at this point, and the railway line is irremediably split in two halves without any possible connection.

Please note: the actual gap simply measures few centimetres on the terrain: but it's enough to determine a complete failure in topological continuity, thus introducing catastrophic errors in routing algorithms.
Sadly enough, topology errors like this one aren't at all rare in OSM networks: and are really difficult to be identified and resolved simply using ordinary GIS / mapping tools. Some kind of more specific approach is surely required in these cases (e.g. using some network/graph aware DBMS).

Common noding errors plaguing OSM networks: a second example

rail3.png rail3zoom.png
This case represent an excellent example of impossible junction: and I've been able to identify this further issue yet another time using an analysis based on Node Cardinality. As the black arrow shows, there is a node presenting a Cardinality=1.
As we can easily check using an higher zoom factor, there is no functional connection at all between the two railway lines: routing algorithms will surely fail here, because this one represents a first class unrecoverable topology issue.

Conclusions: a provisional assessment


back to the OSM tools Wiki page.