Developers
Before you start install jdk6 or jdk7 and do:
$ git clone git://github.com/graphhopper/graphhopper.git
$ cd graphhopper
$ ./graphhopper.sh web unterfranken.osm- These steps make a part of Germany routable. It'll download and unzip the osm file. Then it creates routable files for graphhopper in unterfranken-gh. It'll skip this step if files are already present.
- It builds the graphhopper jars. If Maven is not available it will automatically download it.
- Also check the android version
If you have problems please let us know via our mailing list.
Open the project with NetBeans or enable Maven in your IDE. Maven is downloaded to graphhopper/maven if not installed when executing graphhopper.sh.
Use one of the following snippets to start development with GraphHopper
// Initialization for the API to be used on a desktop or server pc
GraphHopperAPI gh = new GraphHopper().forServer();
gh.load("graph-hopper-folder");
// Offline API on Android
GraphHopperAPI gh = new GraphHopper().forAndroid();
gh.load("graph-hopper-folder");
// Online: Connect to your own hosted graphhopper web service, for GraphHopperWeb see graphhopper-web
GraphHopperAPI gh = new GraphHopperWeb();
gh.load("http://your-graphhopper-service.com/api");
GHRequest request = new GHRequest(new GeoPoint(fromLat, fromLon), new GeoPoint(toLat, toLon));
request.algorithm("astar");
GHResponse response = gh.route(request);
print(response.distance() + " " + response.time());
PointList points = response.createPoints();
for(int i = 0; i < points.size(); i++) {
add(point.latitude(i), point.longitude(i));
}If you want direct access to the more low-level API you can use this snippet. For more details on Android-usage have a look into this Android site
- For an example of how to use graphhopper in a web application see the graphhopper-web
- For an Android example see graphhopper-android
- You can use graphhopper on the Desktop with the help of the yet outdated mapsforge swing library. The new 'rewrite' branch of mapsforge will help here soon.
In order to integrate GraphHopper into your application you could use some lower level classes to get more power out of it. E.g. query the graph by a geo point (latitude,longitude) - for that you get one of the implementations of Location2IDIndex. Then use that point to query a RoutingAlgorithm implementation.
If you develop for Android have a look into graphhopper-android. For smallish graph (e.g. size of Berlin) use a RAMDataAccess driven GraphStorage (loads all into memory). For larger ones use the ContractionHierarchies preparation class and MMapDataAccess to avoid OutOfMemoryErrors.
If you develop a web application there is graphhopper-web. The simple API (json,jsonp,binary) in graphhopper-web is optimized regarding several aspects:
- It tries to return a smallish data set (encoded polyline, gzip filter)
- It enables cross-site scripting on the server- and client-site (jQuery, header setting)
- To make things simple it uses the GeoCoder called Nominatim to get the name for a latitude+longitude point or vice versa.
- Where it utilizes the jquery Deferred object to chain ajax requests and avoids browser UI blocking when resolving locations in parallel.
For simplicity you could just start jetty from maven and schedule it as background job: nohup ./graphhopper.sh web unterfranken.osm. Then your service should be accessible on port 8989. For production usage this is not recommended.
Instead install the latest jetty (8 or 9) as a service. Tomcat should also work. Then create a war file via mvn clean war:war and copy it from the target/ folder to your jetty installation. Then copy web/config.properties also there and change this properties file to point to the required graphhopper folder.
Increase the Xmx/Xms values of your jetty server e.g. for world wide coverage with a hierarchical graph I do the following in bin/jetty.sh
export JAVA=java-home/bin/java
export JAVA_OPTIONS="-server -Xconcurrentio -Xmx15000m -Xms15000m"Important notes:
- none-hierarchical graphs should be limited to a certain distance otherwise you'll require lots of RAM per request!
- if you have strange speed problems which could be related to low memory you can try to entire disable swap. Or just try it out via
sudo swapoff -a. Swapping out is very harmful to Java programs especially when the GC kicks in.
To get a better understanding also take a look in the source code, especially in the unit tests! There are mainly three parts:
The default import is done via OSMReader which imports OpenStreetMap data. You can configure it via API or use the graphhopper.sh script which utilizes the config.properties where you can specify if it should read CAR, FOOT etc or all at once. You'll have to make sure that you allocate enough memory for your specific graph (E.g. ~1GB for Germany). The import process shouldn't take that long. E.g. complete germany with 30mio edges and 30mio nodes takes about 20 minutes on my oldish laptop. Additionally it will take time if you choose osmreader.chShortcuts=fastest in the config.properties which will dramatically improve query time.
To process algorithms you need a Graph. At the moment there is one main implementation GraphStorage which can be used:
- in-memory with a safe/flush option (RAMDataAccess) and
- a memory mapped (MMapDataAccess).
The interface Graph is developed in the sense that the implementation can be as much efficient as possible - i.e. node ids and edge ids are successive (and so are just indices) and in the range of 0 to MAX-1. This design could be used to have an array-like structure in the underlying DataAccess implementation like it is currently the case.
The data layout is the following:
Some explanations:
- One node has several edges which is implemented with a linked list. E.g. node 3 points to its first edge in the edge area at position 0 to edge 0-3 (nodeA-nodeB where nodeA is always smaller than nodeB). To get the next edge of node 3 you need nextB and this goes to edge 1-3, again node 3 is nodeB, but for the next edge 3-5 node 3 is nodeA ... and so on.
- For you custom data import keep in mind that although the nodes 4 and 6 have no edges they still 'exist' and consume space in the current implementations of DataAccess. For OSMReader this cannot be the case as separate networks with only a small number of nodes are removed (very likely OSM bugs).
For some algorithms there are special implementations of the Graph. E.g. there is a LevelGraphStorage which is a Graph with the possibility to store shortcut edges and a level for every node. This special storage is necessary for Contraction Hierarchies. For this the graph needs also some preprocessing (which can take several hours for bigger areas like Europe) which is done in the OSMReader when configured (osmreader.chShortcuts=fastest) or via API in PrepareContractionHierarchies. In order to use the shortcuts and get the benefits of the optimized graph you must use the algorithm returned from createAlgo() in the preparation class.
A LevelGraphStorage (and all subclasses of GraphStorage) cannot read files created with GraphStorage and vice versa. Also there is a file version which is changed if the data structure of GraphHopper gets incompatible to the previous versions.
The neo4j and tinkerpop implementations in graphhopper-experiments are highly experimental und no longer supported/recommended.
In the routing package you'll find some shortest path algorithms like Dijkstra or A* etc. For those algorithms you need a Graph.
An algorithm needs a kind of path extraction: from the shortest-path-tree one needs to determine the route (list of edges) including the distance and time. Afterwards from this list the exact point (latitude,longitude) can be determined. For bidirectional algorithms this is a bit more complicated and done in PathBidirRef. For Contraction Hierarchies one needs to additionally find the shortcutted edges and process them recursivly - this is done in Path4CH.