GPSies.com using the GraphHopper Directions API

The founder Klaus of GPSies contacted me nearly 2 years ago when GraphHopper was still in its infancy. GPSies was using Google Maps in its path planning tool and as they are free to use and want to keep it they did not want to buy into the business version of Google Maps so they were seeking for alternatives. At that time GraphHopper was already fast but could not scale to world wide coverage and Klaus provided the necessary hardware to me for experimentation. After a few months of tweaking and further months of testing and minor bug fixing we were able together to replace Google Maps API with a self-hosted GraphHopper on a GPSies server.

Also other customer often requested a hosted version of GraphHopper and so the idea of the GraphHopper Directions API for business was born with several benefits over existing routing APIs like basing it on OpenStreetMap data, high privacy standards, a permissive usage policy and world wide coverage even for bike routing.

Today we proudly announce that GPSies switched to this architecture making routing for GPSies more efficient and more up-to-date and still keep the costs low. Especially the daily OpenStreetMap data updates and regular software updates will make GPSies keep on growing!

The Builder Pattern in Java With the Least Code Possible

Immutable objects are important to make your code more robust, especially in days of more parallelization. A builder pattern is used when some of the variables of an immutable class are required and some are optional. But this leads to a massive constructor explosion, at least in Java. Today I think I found an improved builder pattern which could be used with no attribute duplication in the builder class and no separate private constructor in the domain class.

Usual Constructors

Here is a normal immutable class with the various necessary constructors for only one optional field ‘age':

public class Person {
  private final String name; // required
  private final int age;     // optional

  public Person(String name, int age) {
     this.name = name;
     this.age = age;
  }
  public Person(String name) {
     this.name = name;
  }
  public Person(int age) {
     this.age = age;
  }

  public String getName() {
     return this.name;
  }
  public int getAge() {
     return age;
  }
}

Builder Pattern 1.0

The builder pattern removes the need of various constructor combinations:

public class Person {
  private final String name; // required
  private final int age;     // optional
  private Person(PersonBuilder pb) {
     this.age = pb.age;
     this.name = pb.name;
  }

  public String getName() {
     return this.name;
  }
  public int getAge() {
     return age;
  }
}

public class PersonBuilder {
  private String name;
  private int age;

  public PersonBuilder name(String name) {
     this.name = name;
     return this;
  }
  public PersonBuilder age(int age) {
     this.age = age;
     return this;
  }

  public Person create() {
     return new Person(this);
  }
}

The usage is:

Person p = new PersonBuilder().
   name("testing").
   age(20).
   create();

Builder Pattern 2.0

Now my builder pattern with less overhead. Of course in real world examples you won’t have only one optional field making the savings more obvious. The Builder Pattern 2.0 uses a static embedded subclass for the builder and still uses (package) protected fields. As you can see this solution is only ~5 lines more than the original immutable object without the constructors as it just moves the setters into a separate class:

public class Person {
  String name; // required
  int age;     // optional

  public String getName() {
     return this.name;
  }
  public int getAge() {
     return age;
  }

  public static class BEGIN extends Person {
    public BEGIN name(String name) {
      this.name = name;
      return this;
    }
    public BEGIN age(int age) {
      this.age = age;
      return this;
    }

    public Person END() {
      return this;
    }
  } // end of builder class
} // end of domain class

The usage is similar to the original builder pattern:

Person p = new Person.BEGIN().
   name("testing").
   age(20).
   END();

Keep in mind that this solution has the ‘drawback’ of no unnecessary object creation involved like builder pattern 1.0. And therefor the END method is not thread-safe unlike the create method. (You can fix that via this.clone() within END, not sure if you like that). Also I think for those cases you probably need more something like a factory. As noted in the comments the builder class START should be renamed to Builder and then even better create a public static method ala ‘Builder Start() { return new Builder(); }’ where you then can avoid the ‘new’ when using it.

Improvement: Builder Pattern 2.1

After the comments and having this implemented in production I observed drawbacks. E.g. that you don’t have to call the END method at all as the subclass is also accepted. And that you could theoretically just downcast a Person object to its builder and change the variables again. The simplest solution is to use composition instead of inheritance like we do with our AlgorithmOptions object at GraphHopper, this way we can also use private fields again.

Conclusion

This new builder pattern is suited if a method has several arguments with some of them optional. You can move these arguments into a separate class and use this pattern to avoid code duplication like I’ll probably do for some classes in GraphHopper. For everyone in love with magic (unlike me) they can also have a look into the project lombok as noted in the comments. Still the best thing would be to have something like this directly in Java and being able to write:

Person p = new Person(name="testing", age=20);

GraphHopper Directions API Going Private Beta

Today we are proud to announce that our Directions API goes into private beta. Contact us and take part to get an API key and try our latest features.

The GraphHopper Directions API includes

  • The Routing API, a fast web service to calculate world wide routes for walking, biking and car.
  • The Matrix API, based on the Routing API you can calculate so called distance matrices more efficient.
  • The Geocoding API, a world wide address search. Still under heavy development and not yet production grade although with good results in several European countries.
  • Daily OpenStreetMap updates
  • A mature service based on the open source routing engine GraphHopper. Read more about GraphHopper at opensource.com

See the Routing and Geocoding API in action at GraphHopper Maps!

GraphHopper now also Available for Offline Routing on iOS

Today we announce the first availability of GraphHopper for iOS. It is still in an experimental shape but we would like to engage people to play with it and report issues. Go directly to the git repository and continue reading.

With GraphHopper we are in the process of building a fast and open source alternative to existing routing solutions. We provide a world wide instance for car routing, biking and walking called GraphHopper Maps. Where you can see the routing engine GraphHopper in action, combined with map tiles and address search served from other software. As GraphHopper is written in Java we already made routing possible on several platforms like Linux, Windows, Mac OS X, Raspberry Pi, Android and even offline in the Browser. But still one major platform – iOS – was missing and we thought about ways to make this possible.

RoboVM?

The most simple solution to port a Java project these days is RoboVM. RoboVM makes a complete Android app running on iOS. Several users made their none-trivial games working with the help of RoboVM and so it should be also relative easy for an app which includes GraphHopper to be used on iOS too.

J2OBJC!

But we also wanted to have the possibility that a native iOS app can use GraphHopper as a library. And according to my investigations this is currently relative hard to achieve with RoboVM. So we decided to use the conversion tool j2objc which creates Objective-C code from Java code. The first running demo on an iPhone was made by Tobias which was a huge step in the right direction (pun intended) and really nice work! It showed the first time that it was possible at all and the dream of platform independence nearly came true. Still there were several glitches in the setup which I wanted to avoid in the first release. Tobias did not found enough time for this so I was seaking help in the GraphHopper community and I got in touch with Calin who recently had enough time and was polishing like crazy. Where ‘polishing’ means creating workarounds for j2objc bugs and using good old make to avoid Xcode limitations, telling me to fix things directly in GraphHopper, preparing a nice demo, finding bugs in other tools and the usual coder safari.

Success!

At the end he was able to produce the necessary scripts and adaptations to create a static library via j2objc and a simple-to-setup demo. Only very few so called compatibility classes had to be written in Java but Calin made it possible to completely avoid custom Objective-C code, even for the more advanced things like memory mapping. With that we can almost always automatically create the updated version out of ‘GraphHopper Java’. And GraphHopper on iOS is fast, for example a route through entire Germany takes only about 1sec on iPhone 6!

We again ask for you help and feedback!

And thanks again to Tobias & Calin!

The Flexibility of GraphHopper

I often hear some misconceptions about the flexibility of GraphHopper. In this post I speak about GraphHopper core.

Flexibility Mode

GraphHopper is designed to be fast and flexible. For example you can route through entire Germany in about 1 second on average without any speed-up method, I’ll call this ‘flexibility mode’. You have to keep in mind that this involves traversing millions of nodes in the road network. In this mode you have all possibilities and advantages like on-demand profiles, small base graph, support for multiple vehicles and so on. A naive implementation for OpenStreetMap data probably won’t reach this query speed, even if coded in C++. Additionally we fight with the memory waste and garbage collection in Java.

Speed up Mode

The main disadvantage for the flexibility mode is that long queries will need lots of RAM, which is also not very handy on mobile devices. So you’ll have to limit the length of the route, increase the heuristical nature of the algorithm OR which is our default mode: switch to the speed up mode which uses a special algorithm called contraction hierarchies. The speed up mode comes with disadvantes e.g. only one query profile is possible or a bigger base graph. But it dramatically reduces the necessary RAM per query and as a nice side effect makes the query 50-500 times faster, depending on the length of the route. These are the reasons that the default mode for GraphHopper is the speed up mode. (And our Directions API is provided only in this speed up mode.) With GraphHopper switching between modes is just a configuration change (chShortcuts=fastest or chShortcuts=no) and our architecture was build with this in mind and is open for new and completely different speed-up algorithms. The benefit of this simplicity is that you can play around and tune the routing of one or more vehicles with various options in the flexibility mode, and then if you need performance or want to use it on mobile devices you can switch to the speed up mode.

Digitalizing GPX Points or How to Track Vehicles With GraphHopper

Recently I was asked again if I know a method, or even better a tool, which makes GPX points more align to the existing streets in OpenStreetMap. E.g. currently in Mapilarry all recorded streets are not really smooth and digitalized if you look at them in detail. GraphHopper cannot do this out of the box but provides a toolchain which will make this digitalization easier.

Update: this is now open source.

Map Matching

The necessary process before an import would be Map Matching. Quoting (my own words ;)) from Wikipedia:

Map matching is the process of associating a sorted list of user or vehicle positions to the road network on a digital map. The main purposes are to track vehicles, analyze traffic flow and finding the start point of the driving directions.

Or as a picture:

map-matching

I’m explaining in this blog post the simple steps which can taken to implement something like this with a very simple method. This is not an invention by me, other papers suggesting a similar technique. Also we should use some open testing data additionally to the normal unit tests. Some wordings are necessary before we go deeper:

  • A GPS point is a tuple or object which contains latitude, longitude (, elevation) at which position it was recorded.
  • A GPX point is a tuple or object which contains latitude, longitude (, elevation) and the timestamp at which it was recorded. And a GPX list ist a list of GPX points.
  • In the digital world of maps we need a data structure to handle the road network. This data structure is a graph where the junctions from real world are nodes and the streets between them are the edges.

The question is also why would we need a routing engine at all?

Because:

  • firstly you don’t need to write the import process of OpenStreetMap and the closest edge lookup and probably some other tools necessary for map matching and
  • secondly the routing process will fill gaps between larger distances of two GPX points, and will be able to guess those gaps depending on the vehicle and
  • thirdly using a routing engine will make the outcome more realistic, e.g. avoiding going left and then returning the identical street to go further in the straight direction.
  • Lastly with GraphHopper you’ll be easily able to provide such a procedure even for the world wide case as it stores everything very compact and can be used in-memory or on-disc.

We start with an example: example1a

All maps are from Lyrk and data is from OpenStreetMap contributors

In the left map you see the street parts highlighted where only the edges closest to the GPX points are selected. Whereas in the right map the most probable way was taken via a routing engine like GraphHopper.

The simple algorithm

The results for the map on the left side are easy to get, see the gist for example 1. For the map on the right side can try the following procedure explained in pseudocode here or see example 2 as gist for a more complete one:

  1. Find 3 closest edges per GPX point
  2. Associate every edge with a weighting, which is the distance from the edge to the point. The larger the distance the smaller is the probability that the best path goes through it.
  3. Find the best path from the first GPX point to the last, but take into account the weighting and therefor the distance to the GPX points
  4. As a post-processing step you need to assign the GPX points to the resulting path, you can do so via the edge ids and to find the coordinates you can either use path.calcPoints or the lower level API ala edgeState.fetchWayGeometry.

This simple algorithm should work in the most cases and is very fast

The enhancements

There are two limitations of this simple algorithm:

  • If there are loops in the GPX list, then the Dijkstra from step 3 will throw data away
  • and it will happen that another route than the route marked with GPX points is taken. E.g. in the case if the GPX signal is not that frequent and the edge of one point is rather short, which means it will have a small influence on the overall weighting of the taken route.

The following improvements are possible

  • You could do a simple workaround and cut the incoming GPX list when you detect a loop and feed those GPX-list-parts to the algorithm.
  • Or find the best route not from start to end but ‘step by step’. For example from pointX to pointX+4, then pointX+4 to pointX+8 and so on, where you need to merge the results. To avoid suboptimal paths at the intersection (here pointX+4) you’ll need to ‘overlap’ the routes. So you will need to calculate the routes for pointX to pointX+4, then pointX+3 to pointX+7, …. instead. Merging will be more complex probably.
  • A more complex solution could be to maintain a list of e.g. 3 alternative end-results. As you already get 3 edge candidates for every GPX point you can then try to find all routes between them. You could think that this will slow down the search a lot but with GraphHopper you can tweak e.g. the Dijkstra or DijkstraOneToMany algorithm to do this in an efficient manner. E.g. if you want to get the best result but you want to search from multiple destinations you can do: DijkstraBidirectionRef dijkstra = new DijkstraBidirectionRef(hopper.getGraph(), flagEncoder, weighting); dijkstra.initFrom(nodeFrom, distanceToPossibility1); dijkstra.initFrom(node, distanceToPossibility2); … dijkstra.initTo(nodeTo, distanceToEndPossibility1); dijkstra.initTo(nodeTo, distanceToEndPossibility2); …

There are lots of other problems which you’ll encounter, that is the ugly real life with GPS signal errors, tunnels and so on. One example problem is if you are tracking e.g. a truck waiting in front of traffic lights in a one way street. You’ll see several nearly identical GPX points but as they have an error associated they won’t be identical and it could happen that they go ‘backwards’ in the one-way which will result in an extra loop if use the ‘step-by-step’ variant of the shortest path calculation:

example2