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 change the configuration
in the config.yml to read car
, foot
or all vehicles. See the installation section
for more details.
The import process is fast e.g. complete Germany takes roughly 10 minutes. Additionally, it will take time if you
enable speed mode by using profiles_ch
in the config.yml which will dramatically improve query time
but requires more RAM for the import.
To process algorithms you need a Graph. At the moment there is one main implementation GraphHopperStorage which can be used:
The interface Graph is developed in the sense that the implementation can be as much efficient as possible
The data layout for the DataAccess objects in GraphHopperStorage called 'nodes' and 'edges' is the following:
Some explanations:
For some algorithms like Landmarks or Contraction Hierarchies there additional storages necessary and the 'table' layout is special. Furthermore there is a key value storage to store street names, conditional tags and more - preferable where the storage size is unknown.
Also there is a version in every data structure which is changed if the data structure of GraphHopper gets incompatible to the previous versions.
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 the 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 we use the RoutingCHGraph which additionally holds shortcuts. While path extraction we need to identify those shortcuts and get the edges recursively, this is done in Path4CH.
In order to traverse the CHGraph like a normal Graph one needs to hide the shortcuts, which is done automatically for you if you call graph.getBaseGraph(). This is necessary in a LocationIndex and in the Path class in order to identify how many streets leave a junction or similar. See issue #116 for more information.
In real world we have addresses and/or coordinates for the start and end point. To get the coordinate from an address you will need a geocoding solution which is not part of this GraphHopper routing engine.
To get the closest node or edge id from a coordinate we provide you with an efficient lookup concept: the LocationIndexTree. See here for more information. See #17 and #221.
In order to route not only from junctions (which are nodes) we introduced with the QueryGraph in issue #27, which creates virtual nodes and edges at the query coordinates. It provides a lightweight wrapper around the Graph and is created per query so that queries do not influence each other.
It can be also introduced for all kinds of dynamically changed nodes and is tested for a few thousand locations.
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。