Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Make merging of graph files possible #293

Open
karussell opened this issue Dec 10, 2014 · 20 comments
Open

Make merging of graph files possible #293

karussell opened this issue Dec 10, 2014 · 20 comments

Comments

@karussell
Copy link
Member

karussell commented Dec 10, 2014

It is possible to merge one or more areas with OSM tools but what would it take to merge two already imported and prepared areas "on the fly"? Would be interesting for the mobile scenario (Android/iOS) where the users only want to download one area by one and routing should work across those areas. As a first step try without CH. Still the node and edge ID mapping could be complex or a graph copying is required using lots of resources. The location index needs to be dynamic instead of 'read-only'. Or the merged index needs to be created on-device.

A workaround could be to offer on-demand extraction of the bigger or combined area from a world wide graph. Still the user would download an area which is already existent on his device.

One further solution could be to implement a graph wrapper which contains multiple areas and manages the edge and node ID-offsets. Still this would not work for CH and this would require a border nodes matching.

@gyorfiavarlehel
Copy link

gyorfiavarlehel commented Dec 11, 2014

Is that feasible to load only the appropriate area (gh folder)? Set all areas in graphhopper and it will use only one area at a time. When a calculation is done in one area then destroy those resources and load the resources of the other area. In this way we can keep always one area in the memory. I think we can live with the load/destroy time.

BTW: How it is made on the graphhopper maps page?
https://graphhopper.com/maps/?point=48.381794%2C9.992065&point=47.368594%2C8.519897&layer=Lyrk

@devemux86
Copy link
Contributor

devemux86 commented Dec 11, 2014

That's a good question.
But what you mean is that if we have two route points, one in each graph, then there should be two calculated semi-routes that can combine?

@karussell
Copy link
Member Author

karussell commented Dec 11, 2014

Of course a workaround like this is always possible, but I do not like heuristics (yet) for the GraphHopper itself.

@ghost
Copy link

ghost commented Jan 20, 2015

See osmand code base how this is done for routing across several datasets.

@arlindiDev
Copy link

arlindiDev commented Oct 24, 2016

Is there any solution to route between two different areas, if they are actually next to each other?

@kkalera
Copy link

kkalera commented Sep 18, 2017

Hi everyone, I've been looking into graphhopper for a while now. I would like to start doing some work on this improvement since it would be very beneficial to myself aswell. But I've only been using graphhopper, not developing it. Does anyone have a few pointers on where to start ?

@boldtrn
Copy link
Member

boldtrn commented Sep 19, 2017

Does anyone have a few pointers on where to start ?

Nice that you want to get started with this :). I think, the way I would do this is: load the two graphs as usual (in a wrapper graph, so that GraphHopper itself does not know about this). Then you would have to check if there are nodes that are placed at the same location, you would have to "glue" the graph at these points so that you can seamlessly iterate from Graph A to Graph B. This will not work for CH and probably not easily work for LM (I have no idea how to do it with LM, but it might be possible). BTW: The described idea is essentially the same as the idea above by @karussell.

One further solution could be to implement a graph wrapper which contains multiple areas and manages the edge and node ID-offsets. Still this would not work for CH and this would require a border nodes matching.

Just to give you a heads-up, this is no trivial task :).

@karussell
Copy link
Member Author

karussell commented Sep 19, 2017

I think the problem is that our node and edge IDs have to be consecutive (makes other things much easier), so this wrapper graph is necessary which does the mapping and every subgraph gets an ID offset. The glueing part might be easier if you create the big graph first and cut out the smaller pieces later.

@eriadam
Copy link

eriadam commented Oct 23, 2017

This would be a very important feature for mobile. We could then create smaller areas instead of countries or continents, so the data downloaded to the devices would be dramatically reduced.

@kkalera
Copy link

kkalera commented Oct 27, 2017

I think that I will need to understand exactly how graphhopper works to do this. Is there any documentation on this or would someone of the creators be willing to talk about this with me?

@karussell
Copy link
Member Author

karussell commented Oct 27, 2017

You can open a new topic in our forum to discuss this.

@carlos-mg89
Copy link

carlos-mg89 commented Sep 12, 2018

Has there been any progress with this feature?

@carlos-mg89
Copy link

carlos-mg89 commented Sep 21, 2018

I was wondering if it'd be of any use to share with you the Valhalla project: https://github.com/valhalla/valhalla

It's a project I found a few weeks ago, but which I didn't investigate it until the past week. They work in a very different way than Graphhopper does, and perhaps there is a good reason about why you do what you do the way you do it. And the same for Valhalla project. I'm just trying to share with you how they make offline routing possible.

Basically, they generate graph tiles, and these graph tiles allow the algorithm to calculate the routing while offline, without many issues. You can generate the graphs of the planet file, and then pack them by areas (countries or regions, for example). So it is possible to download the packages in different time spans, and as long as the graphs are next to each other, the routing algorithm would calculate the route.

This is a very different way of tackling the routing. Valhalla calculates routing on the fly, since the graphs only have the edges and some other information, but the routes aren't calculated on advance, so calculating the graphs for Europe, for example, takes only 3-4h on a decent (but not very powerful) desktop computer.

As far as I understood, Graphhopper algorithm, does calculate all the routes in advance (which is why is so fast, but why it takes so long to calculate the necessary data). So perhaps is not that simple to combine the 2 methodologies, but maybe it's possible to create a hybrid algorithm for Grahhopper, so we can, for example, generate the routing data for the whole planet, and chunk it by bounding boxes, or generate the routing files with information of the area that is related to favor routing between different graphs.

i don't think this is a feature that's high priority in Graphhopper, but maybe it's somewhere on the project calendar and could be nice to share with the rest of the people an estimate date?

@karussell
Copy link
Member Author

karussell commented Sep 21, 2018

As far as I understood, Graphhopper algorithm, does calculate all the routes in advance

No, this is wrong. GraphHopper is very flexible and can work without any preparation (ie. without LM and without CH) but even with those preparations we do not calculate routes in advance but data that makes routing faster.

could be nice to share with the rest of the people an estimate date

We rely on the community and won't give such dates. It is not a top priority for us at the moment but you can change this :)

@carlos-mg89
Copy link

carlos-mg89 commented Sep 21, 2018

True about the first point of your reply. Didn't explain myself properly enough. I knew it's possible to disable CH and LM, but forgot at the moment of writing the message.

Thanks for replying by the way.

@inaderi
Copy link

inaderi commented Jul 17, 2019

Hi there.
I want to implement this thing ( the easy way : fixed equally sized rectilinear tiles). I've worked a bit with graphhopper and I did it with the location index and names. (dividing them vertically into bounding box tiles).
But I'm confused how to split edged and nodes ?
Please help me with a hint about how to initiate it ?

Ismail

@inaderi
Copy link

inaderi commented Aug 12, 2019

Hey Everybody
It's been a while I'm learning graphhopper's source code. I have implemented wrapper class in order to divide Edges, Location Index and NameIndex into squared tiles, Edges was a bit harder than others. Still working to complete it. Hope it will get done well and adding this feature to graphhopper.
Ismail

@carlos-mg89
Copy link

carlos-mg89 commented Dec 27, 2019

Is there anything about this matter being tackled, even if partially, on the new 1.0 release?

Having this would be an incredible feature. Well basically, to allow the load of different graph files, and have the GraphHopper library do the necessary calculations to allow a calculation of routes between 2 or more graphs.

I believe it isn't an easy task to achieve, since GraphHopper wasn't thought in this way (that's what I've understood so far).

@inaderi
Copy link

inaderi commented Dec 27, 2019

I made it possible by diving graph into custom square tiles by implementing wrapper classes around storage classes such as nameIndexWrapper, nodeWrapper, edgeWrapper, datawrapper(geoWrapper, turncostWrapper, ...) and so on .

It's not a smart way, having some redundancy data (like edges which their nodes are in two different tiles and storing a mapping of node id's ).

If you are eager to we could discuss about it.

@inaderi
Copy link

inaderi commented Dec 28, 2019

It's obvious, but I forgot to mention that I'm not a developer of Graphhopper and I'm not involved in the new release. So maybe it is better to wait to hear Peter's answer:)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

9 participants