Use cases

Shortest Path

The main purpose of GraphHopper are its shortest path implementations available when combined with OpenStreetMap or indoor data you could create fast shortest path real world applications.

Also a contraction hierarchy implementation with extreme speed-up is implemented.

For more details have a look into the Developers section!

Spatial Index

All spatial indices are using spatial keys to make them more memory efficient.

• In-memory, simple quadtree - read this blog post to see how this can be made even faster!
• Very lightweight spatial index. This can be only used in combination with a Graph! E.g. you can have an index with under 30MB for dozens of millions of nodes in an already existing Graph implementation.
• A Map<Coordinate,Long> via on-disc or in-memory SpatialHashtable. You can read this blog post to get more information about it.

Integration

You can use GraphHopper algorithms or data structures from other storages as well. As an example you can take a look into the neo4j integration - which is a bit outdated as not needed and also not fruitful as 5 times slower, 5 times more memory, too slow import ... but would love to have something - give me your pull request ;) !

To integrate your storage system you need to implement the Graph interface and if you want to use the OSMReader to fill your graph with OpenStreetMap data you need to overwrite/extend the GraphStorage. For the Graph it is important that a lookup of edges should not require a 'search' but instead use a direct access to the data. To import data with an external storage you can use this class.

Self-made

Use GraphStorage and one of the DataAccess (MMapDataAccess, RAMDataAccess) implementations!

The main disadvantage of the memory mapped DataAccess is that at the moment it is not even thread safe for multiple reading threads. But it is e.g. perfectly suited for one-thread and memory limited scenarios like on Android.

The RAMDataAccess is only read-thread safe but it could be relative easy transformed into a fully thread safe class (not done at the moment as not needed and slower).

In OSMReader you can find how GraphStorage is used.

To perform some real work (bidirectional dijkstra) you can use the run.sh script:

./run.sh dijkstrabi

Neo4j

When implementing this for neo4j you will use the internal IDs - even a hashmap lookup is O(1) and should be avoided!

Lucene

Although I failed (yet) to implement a fast graph storage via lucene it should be possible. As the documents could be accessed directly by the document id. The problem with this is that you have to avoid updates. For every update lucene inserts a NEW document with a new document ID and deletes the old document. But the GraphHoppers' OSM-import mechanism uses updates to add edges etc and so

1. there will be big gaps between the doc ids, which would make dijkstra etc a bit inefficient. We rely on bitsets nearly everywhere to make even big graph traversals memory efficient.
2. but more important: other refering nodes need an update too (which results in even more updates etc :( ).

The good news is that even external IDs can be made very fast. Have a look into my lumeo project and into this issue.