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:

• the network must be represented as a collection of nodes and arcs
• each arc always has two extreme points, and each of such extreme points must identify a corresponding node
• two nodes can never share the same coordinates (no overlapping nodes are allowed)
• any arc has a precise direction, i.e. it connects one-way a node_from to a node_to
• in many cases the connection is allowed in both ways; anyway arcs are conceptually to be thought as unidirectional
• thinking of bidirectional arcs as two different arcs drawn in opposite directions is a clearer conceptual approach;
  even when arcs are implicitly handled as bidirectional by your favourite sw tool.
• a connection between two arcs is possible only if they share a common node

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.

---

Reality check: Networks in Open Street Map

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.

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.

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

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

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.

Common noding errors plaguing OSM networks: a first example

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

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

• OSM roads and railways are often mapped in a very careful and highly detailed fashion
• the data model adopted by OSM seems to be adequate enough so to decently support Networks, and there are enough qualifiers (aka tags in OSM parlance) supporting rich and detailed routing-related informations.
  Anyway there is no clearly established criterion allowing to directly map OSM-Ways to Graph-Arcs: a huge reprocessing work is surely required, and several arbitrary / heuristic assumptions are required, thus introducing further causes of possible quality degradation / accuracy loss.
• actual accuracy and trustworthiness seems to be widely variable from zone to zone: there is an obvious dispersion and many self-inconsistencies.
  Somewhere there is an excessive attention to map every possible inch of rail (may well be absolutely neglibible); in other cases even the main stations are simply represented on the map by a single rail thus suppressing any detail. Representation of double-trak and single-trak lines is too much often completely unreliable and unconsistent.
• the observed average data-quality in many cases is really far from being adequate and satisfying (i.e. is frankly disappointing).
  Such issues are most notably affecting noding correctness, which usually is a painful plague killing any possible attempt to extract a reasonably valid Graph.
• all this considered, any attempt directly aimed to use OSM networks for serious routing purposes seem to be too much optimistic.
  In order to get some professional result (not excellent, but simply of average quality) a strong effort and a patient review / debugging / integration work would be probably required.
  If you are simply interested to cover a single small-sized area this one could probably be a realistic option: but when you absolutely need to cover a complex wider network the bare amount of work required in order to repair at least the most obvious issues will probably be completely unpractical.

back to the OSM tools Wiki page.