OpenStreetMap

Connectivity of a routing graph

Posted by andygol on 23 December 2016 in English (English)

Ways marked with tags highway=* form a network of roads. One of the tasks of such network is the ability to construct a route from one area of the network to another. This is possible only under the condition that these areas have common connection point — do not have gaps between them and do not form with each other, unconnected "islands".

image

https://en.wikipedia.org/wiki/Stronglyconnectedcomponent

In addition to route planning, an important part of the map of the road network is its visual integrity. Since a different set of roads are shown on different scales (levels of generalization), it is important that the road network would look like a single entity.

Thus, in general (low) scale will be used to display important/basic types of roads: motorway, trunk; sometimes they may be supplemented by primary roads. With further increase of scale, they will be supplemented by regional roads — secondary and tertiary, and on a most detailed scale, we will see even streets and other feeder roads.

Based on this, the main approach in roads classification, in cases where official information about their classification is absent, we should follow next principle:

After the lower class roads are cut off/hidden, the remaining roads must be linked to form a holistic road network.

So, the whole country should be covered by roads, trunk +motorway class, without gaps (when you hide trunk road, motorway may be discontinuous, as they are an improved version of trunk); in large cities, primary roads should join with them (primary roads also play a key role in the transport network of a large region - state, regions, territories). If secondary road from two neighboring regions are connected to each other through lower road classification, then at a larger scale they would form an unlinked traffic graph. This not only causes visual comfort but also makes it impossible to construct a route between them.

How to check the connectivity of a road graph?

To test the connectivity of routing graph you can use several methods:

  • create tool for automatic testing (validator)
  • try to build the route with the aid of one of available services
  • visually assess road connectivity graph

For a quick visual assessment of a small section of the road network, you can use a set of filters in JOSM, which will help us to hide/show the way of a certain class

image

Filters in JOSM are processed from top to down, so they should be placed in the appropriate order.

image

After the activation/deactivation of the filters, we will be able to verify the presence or absence of gaps in the road network.

Вашингтон

Compliance with this simple principle allows us to have holistic road network at any level of data generalization at all times.

Comment from butrus_butrus on 29 December 2016 at 10:39

Please, note that your road categories are USA specific and may not have the same meaning/importance in other parts of the world. Thanks!

Hide this comment

Comment from daniel-j-h on 6 January 2017 at 16:16

The Open Source Routing Machine shows you these connectivity issues, as we are already running Tarjan's algorithm for strongly connected components on the graph.

  • On the demo server bottom left "Small Components Layer"
  • In the debug map in addition to maxspeeds and turn penalties

both times in pink.

The same layer is getting published to the OSM Inspector, too.

Hide this comment

Leave a comment

Parsed with Markdown

  • Headings

    # Heading
    ## Subheading

  • Unordered list

    * First item
    * Second item

  • Ordered list

    1. First item
    2. Second item

  • Link

    [Text](URL)
  • Image

    ![Alt text](URL)

Login to leave a comment