Introduction

[Note: I started writing this in March of 2014 but got side-tracked by other things. Since I’ve started working on byCycle again recently and made some updates to how it processes OSM data, I’m finally getting around to publishing this.]

I’m in the process of updating a side project to use OpenStreetMap (OSM) as its primary data source. When I started, I didn’t know anything about the OSM data schema or how to use it for routing. I found some info in the OSM wiki and various other sources, but it all came together after I downloaded some data and started playing with it.

Since I couldn’t find a concise tutorial on this topic, I figured I’d write up what I learned so that it might help others who are interested in creating their own routing engine based on OSM data (mostly for fun, probably not for profit). The focus here is less on the technologies I used (Python 3 & PostgreSQL w/ PostGIS) and more on the data and how to process it for routing.

The basic steps are:

1. Get familiar with OSM terminology
2. Get some data (in JSON format)
3. Extract the relevant parts of the data, massage it a bit, and load it into a database
4. Create a graph that can be used for routing from the data loaded into the database

In the end, it’s pretty straightforward, but there are few tricky bits, and that’s essentially what this post is about.

Terminology

• Nodes – These are used to represent street intersections, points of interest, and also the line geometry of ways. Nodes are composed of an ID, a latitude & longitude, and maybe some tags.
• Ways – These are used to represent roads, paths, buildings, and anything else that has a shape. Ways are composed of an ID, a sequence of node references, and some tags. Ways representing streets often span multiple real-world street segments. Creating a topologically correct graph that can be used for routing requires splitting such ways where they intersect with other ways. There are other tags/hints in the OSM data that can be used for this too, but that’s not covered here.
• Tags – These are key/value pairs that are attached to nodes, ways, and relations. As an example, many ways have a ‘highway’ tag, which indicates that they are streets (or some other kind of path). Technically, tags can be anything and anyone can add new tags willy-nilly. In actuality, they seem to be fairly standardized. The fact that they aren’t totally standardized causes some additional complexity in using OSM data for routing.
• Relations – These can be used to specify a relationship between a set of nodes and/or ways (e.g., a bus route). I’m going to ignore relations entirely in the rest of this article.

Note: some details elided.

Get Some Data

In the beginning, I was manually exporting data from the main OSM site. There are a few problems with this approach:

• You can only download a small amount of data this way.
• You can’t filter the data. You probably don’t want *all* the data in a given region, since it’s not all useful for routing.
• It’s discouraged in the OSM documentation.
• It’s manual.

Eventually,  I stumbled across XAPI, which is an extended version of the main OSM API that lets you download filtered XML data. Free XAPI Web services are were provided by MapQuest and others.

Fast forward a few years and XAPI is deprecated and the Overpass API/QL is now recommended. The Overpass API can output JSON instead of XML, which means smaller/faster downloads and simpler code for processing the OSM data.

For example, the following query will download data for a small area around downtown Portland, Oregon. It will include only ways that have a ‘highway’ tag along with the nodes associated with those ways:

http://overpass-api.de/api/interpreter?data=[out:json];(way[highway](45.52036,-122.67279,45.52542,-122.66281);>;);out;

This requests ways with a highway tag that are inside a bounding box specified as south, west, north, and east coordinates. The ‘highway’ tag is used to indicate streets, highways (AKA motorways), cycle tracks, sidewalks, “foot paths”, stairs, etc. My understanding is that any way that can be walked, biked, roller-bladed, or driven on will have a ‘highway’ tag.

The > after the coordinates tells Overpass to recurse downward, which is how you get it to return all the associated ways and nodes in the bounding box. This bit with recursion to get “completed ways” was the trickiest part of understanding the Overpass API/QL. I highly recommend using the Overpass Turbo tool to test your queries within a small bounding box to make sure you’re getting all the data you expect.

Note: It’s possible to do much more complex Overpass QL queries, but the relatively simple query above works for my purposes.

Code for fetching JSON data from the Overpass API

Load the Data

I found osm2pgsql early on and thought this part was going to be super easy, but osm2pgsql is oriented toward cartography and doesn’t insert any node data into the database [note: I originally wrote this in 2014, so that may or may not still be true]. That makes it somewhat more difficult to use for routing (you could use spatial analysis to figure out the topology, but that seems like a lot of extra work when the topology is already well defined in the OSM data).

Instead, I wrote my own loader. Reading an OSM JSON file downloaded from the Overpass API is straightforward since the structure of the data is pretty simple:

{
  "version": 0.6,
  "generator": "Overpass API 0.7.54.12 054bb0bb",
  "osm3s": {
    "timestamp_osm_base": "2017-12-13T05:00:00Z",
    "copyright": "The data included in this document is from www.openstreetmap.org. The data is made available under ODbL."
  },
  "elements": [
    {
      "type": "node",
      "id": 5079801671,
      "lat": 45.5350519,
      "lon": -122.6565833,
      "tags": {
        "highway": "traffic_signals"
      }
    },
    {
      "type": "node",
      "id": 40624981,
      "lat": 45.5459387,
      "lon": -122.6565138
    },

    ... more nodes ...

    {
      "type": "way",
      "id": 48268202,
      "nodes": [
        5079801671,
        1396604495,
        4673994633,
        4673994632,
        40601347,
        3850595129,
        40624967,
        40624969,
        40624973,
        40616052,
        4922848332,
        40624976,
        4922848331,
        40624979,
        40606102,
        40624981
      ],
      "tags": {
        "bicycle": "designated",
        "highway": "residential",
        "maxspeed": "25 mph",
        "name": "Northeast 9th Avenue",
        "sidewalk": "both"
      }
    },

    ... more ways ...
}

Here we can see that way 48268202 has several associated nodes and some tags. The first and last nodes are intersections. The other nodes define they way’s line geometry and might also be intersections (see below). The tags indicate that it’s a residential street that has sidewalks on both sides and is designated as part of the bicycle network.

Notably, this example way spans several blocks, so it has to be split into its component blocks before it can be used for routing (technically it doesn’t, but doing so enables better routing).

The loader first goes through all the nodes in the JSON data and determines if they are intersections. Nodes at the start and end of a way are always considered intersections (although thinking about it now, that might not actually be correct). In addition, nodes that are shared by two or more ways are considered intersections. All of the nodes are inserted into a temporary database table (so they can be used later for street geometry). The nodes that correspond to intersections are inserted into a separate, persistent table.

After the nodes are processed, the loader goes through all the ways in the JSON data, extracts specific tags, and inserts “street” records into the database. The geometry for each way/street is created by looking up the corresponding nodes in the temporary node table, putting them into the correct order, and creating a line geometry object that can be inserted into a PostGIS geometry column.

Code for loading OSM data into a Postgres/PostGIS database

Create a Graph and Do Some Routing

Technically, there’s an implicit graph structure in the database, but for now I’m not using it directly. The eventual goal is to migrate to a graph database such as Neo4j or maybe use pgRouting. For now, I’m using a simple library named Dijkstar to build a graph and perform shortest path queries.

The graph creation script reads the street table and adds an edge in each direction for two-way streets and a single edge for one-way streets. The edges are simply tuples of street attributes such as length that can be used by a cost function that’s passed into the path-finding function. The graph is essentially just a dictionary, and it’s saved using marshal from the Python standard library.

At this point, the graph can be loaded and queried for a shortest path by specifying a pair of node IDs, but that isn’t super user-friendly. Check out the route service in byCycle to see an example of how it can be used in “real” (i.e., side-project, just-for-fun) code.

Code for creating a graph from data loaded into the database

Code

All of the code used to do the processing described above is free/open source and can viewed on GitHub.

After reading Ned Batchelder’s Iter-tools for puzzles: oddity post yesterday, my first thought was to use itertools.groupby(). That version is the fastest I could come up with (by quite a bit actually, especially for longer sequences), but it requires sorting the iterable first, which uses additional space and won’t work with infinite sequences.

My next thought was to use a set to keep track of seen elements, but that requires the keys to be hashable, so I scrapped that idea.

I figured using a list to keep track of seen elements wouldn’t be too bad if the seen list was never allowed to grow beyond two elements. After playing around with this version for a while, I finally came up with something on par with Ned’s version performance wise while meeting the following objectives:

• Don’t require keys to be hashable
• Don’t store the elements read from the iterable
• Support infinite sequences

Some interesting things:

• Rearranging the branches to use in instead of not in sped things up more than I would have thought
• Initially, I was checking the lengths of the seen and common lists on every iteration, which slowed things down noticeably (which isn’t all that surprising really)
• Setting the key function to the identity function lambda v: v is noticeably slower than checking to see if it’s set on every iteration (also not surprising)
• Using sets/dicts for seen, common, and uncommon didn’t make a noticeable difference (I tried adding a hashable option and setting things up accordingly, but it wasn’t worth the additional complexity)

Here’s the code (the gist includes a docstring, tests, and a simplistic benchmark):

def oddity(iterable, key=None, first=False):
    seen = []
    common = []
    uncommon = []

    for item in iter(iterable):
        item_key = key(item) if key else item

        if item_key in seen:
            if item_key in common:
                if first and uncommon:
                    return item_key, uncommon[1]
            else:
                common.append(item_key)
                if len(common) == 2:
                    raise TooManyCommonValuesError

                if item_key in uncommon:
                    i = uncommon.index(item_key)
                    j = i + 2
                    uncommon[i:j] = []
        else:
            seen.append(item_key)
            if len(seen) == 3:
                raise TooManyDistinctValuesError
            uncommon.extend((item_key, item))

    if len(seen) == 0:
        raise EmptyError

    if len(common) == 0:
        raise NoCommonValueError

    if len(uncommon) == 0:
        uncommon_value = None
    else:
        uncommon_value = uncommon[1]

return common[0], uncommon_value

It’s an old saw, but I was wondering today why some projects don’t cut releases more often. The repo for a project may contain the bug fix you need, but it’s just sitting there on GitHub. I think it often just comes down to the fact that making releases is tedious.

You have to update the version number (perhaps in multiple places), update the change log (hopefully), merge your development branch into your release/master branch, create a tag, clean your dev environment, build a distributable package, upload that package, maybe upload some docs, push some commits, etc.

Doing all that manually isn’t much fun, so…

Write a script to do it for you.

Write it in Python or Bash or as a make target or whatever floats your boat. It’s a one-time cost that pays off big.

You can’t quite automate everything–like writing a (good) change log–but you can automate most of the process.

As an example, I wrote this release script for a project I started a month and half ago. I’ve already made 13 15 26 alpha releases because it’s so easy to do. Putting in an hour or two up front was well worth it.

If you’re feeling lazy, you can use something like zest.releaser (for Python projects). I’ve used it in the past and it’s been the inspiration for all the release scripts I’ve written since.

During an interview a while back, I was asked to name some things I hate about Python. For some reason, I choked and couldn’t think of a good answer (I kind of wanted to blame the interview process, but that’s a rant for another time).

Maybe I’ve just been programming in Python for too long, and that’s why I couldn’t think of something (or maybe I’m just a massive Python fanboy). On the other hand, I’ve been programming in JavaScript (which I generally like) for about as long, and I can think of at least a few things right off the top of my head (mostly related to weak typing).

I did a search to see what other people don’t like about Python to get some inspiration, but I didn’t come across anything I truly hate.

Things That Don’t Bother Me

• Significant whitespace. I love it.
• Explicit self. I guess it would be “convenient” if I didn’t have to add self to every method signature, but I really don’t spend much time on that, and it takes about 1ns to type (in fact, my IDE fills it in for me). There are technical and stylistic considerations here, but the upshot for me is that it just doesn’t matter, and I actually like that all instance attribute access requires the self. prefix.
• “Crippled” lambda. There are rare occasions where I want to define more complex anonymous functions, but there’s no loss of expressiveness from having to use a “regular” named function instead. Maybe multi-line anonymous functions that allow statements would lead to different/better ways of thinking about programs, but I’m not particularly convinced of that. (Aside: one thing I do hate relating to this is the conflation of lambdas and closures–normal functions are closures in the same way that lambdas are.)
• Packaging. I don’t know why, but I’ve never had any problems with setuptools. There are some issues with the installation of eggs when using easy_install, but I think pip fixes them. I am glad that setuptools is now being actively developed again and the distribute fork is no longer necessary.
• Performance, GIL, etc. I’ve used Python for some pretty serious data crunching (hello, multiprocessing) as well as for Web stuff. There are cases where something else might have been faster, but Python has almost never been too slow (caveat: for my use cases). Of course, Python isn’t suitable for some things, but for most of the things I need to do, it’s plenty fast enough.
• len(), et al. I don’t have anything to say about this other than it’s a complete non-issue for me. Commentary about how this means Python isn’t purely object-oriented makes me a little cranky.

Things That Bug Me a Little Bit

• The way super works in Python 2 is kind of annoying (being required to pass the class and self  in the super() call). This is fixed in Python 3, where you can just say super().method() in the common case.
• Unicode vs bytes in Python 2. This is also fixed in Python 3 (some people have argued that it’s not, but I haven’t run into any issues with it yet (maybe it’s because I’m working on a Python 3 only project?)).
• The implicit namespace package support added in Python 3.3 causes some trouble for my IDE (PyCharm), but I’m assuming this is a temporary problem. I also had some trouble using nose and py.test with namespace packages. Again, I assume (hope) this is only temporary.

Things That Bother Me a Little More

• The Python 2/3 gap is a bit troublesome. Sometimes I think the perception that there’s a problem may be more of a problem, but I don’t maintain any major open source projects, so I’m not qualified to say much about this. Personally, I’ve really been enjoying Python 3, and I do think it offers some worthwhile advantages over Python 2.

Conclusion

There isn’t one. I left some things out intentionally (various quirks). I probably forgot some things too.