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

Is it possible to access underlying graph data #5570

Closed
jmarca opened this issue Oct 3, 2019 · 2 comments

Comments

@jmarca
Copy link

@jmarca jmarca commented Oct 3, 2019

Apologies in advance---this isn't an issue so much as a question.

I would like to process a small city for edge-covering problems, like the Chinese Postman Problem.

Obviously I could write my own node and edge extraction code, etc etc, but why reinvent the wheel, esp when I like the flexibility of the OSRM approach to extracting content from OSM files.

I'm not sure the best way to go about accessing the underlying network graph, however. Should I just hack out a CPP solver as part of the server algorithms in my own fork? Or is there a hook in the node or C++ bindings to access the underlying graph (if there is, I can't find it).

Thanks

@danpat

This comment has been minimized.

Copy link
Member

@danpat danpat commented Oct 3, 2019

There does exist such a graph, although access to it isn't easy by default. OSRM has so far focused primarily on shortest-path problems, so the actual routing graphs used (the CH and MLD graphs) aren't really useful for arc-covering problems - it's not possible to traverse all edges directly, particularly with the CH graph.

However - @TheMarex did some work about 18 months ago to show how to implement A*:

https://github.com/Project-OSRM/osrm-backend/commits/algorihm/astar

The last 4 commits on that branch show how to access the base graph - the one that hasn't been processed for accelerated shortest-path queries.

While this branch is pretty behind master, I don't think it's meaningfully behind - it shows how to create a new "routing algorithm".

It assumes you've created data using the MLD pipeline - osrm-extract then osrm-partition then osrm-customize.

I'd use this as a starting point. This stuff isn't exposed in the public library bindings by default (the "routing algorithm" concept is an internal concept), but you could certainly make a new routing algorithm, then implement a new plugin that implements the public interface to the behaviour you want to write (say /route_inspection/startpoint;stoppoint;<polygon for region to cover> or something).

@jmarca

This comment has been minimized.

Copy link
Author

@jmarca jmarca commented Oct 3, 2019

Thanks for the pointers. I'll take a look. Closing this to keep things neat.

@jmarca jmarca closed this Oct 3, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.