[OSRM-talk] Accessing graph data in osrm

Daniel Patterson daniel at mapbox.com
Thu Dec 1 00:13:55 UTC 2016


Hi Chris,

  Ah, this is tricky.  If you just create a Datafacade pointing at a `.osrm` files, you don't really get an easily explorable graph.  Only the Contraction Hierarchy is loaded into memory, and it's not really conducive to simple neighbor traversal.  In order to find a path in a CH, you need to know both ends of the route, it's inherently bidirectional.

  Check out the workflow at:

  https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation#graph-edge <https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation#graph-edge>

  this shows the various transformations that happen to the road graph from OSM data.  We then create the Contraction Heirarchy based on the edge-expanded graph, and that's what's available during routing.  I didn't bother drawing the CH graph as the final step after the edge-expanded graph, because, well, it's just a mess of lines and shortcuts.

  When you call NearestPhantomNodesInRange(), it returns the IDs of the edge-expanded-graph nodes (the black dots in the fourth step).  A single PhantomNode will have two node IDs, one for each travel direction allowed on the snapped edge.

  The .u and .v properties *are* the original node-based-graph node IDs and can be looked up with GetCoordinateOfNode().  In order to get the node-based-node IDs for the rest of the road between the endpoints, you need to call GetUncompressedForwardGeometry(phantom_node.packed_geometry_id) which will return a vector of node-based-node IDs that you can pass to GetCoordinateOfNode().

  The GetAdjacentEdgeRange/GetTarget functions return nodes in the CH graph, so they could go anywhere.  The problem is that the CH is inherently bidirectional, so if you ask for all the outgoing edges from a node, you may not get all the neighbors - the connection may only exist in the graph in reverse *from the neighbor* - there's no way to discover the reverse edge without already knowing the target.  If you look in the codebase for "FindSmallestEdge", you'll find a function that does this: looks at all the edges from the source, and if no connection is found, looks at all the edges from the target.

  Hopefully this demonstrates that directly exploring a CH is .... annoying.

  However, all is not lost.  This might help help in your quest:

    https://github.com/Project-OSRM/osrm-backend/blob/isochrone_tool/src/tools/isochrone.cpp <https://github.com/Project-OSRM/osrm-backend/blob/isochrone_tool/src/tools/isochrone.cpp>

  This is an unfinished, but basically functional, isochrone generator.  It creates a normal Datafacade, but *also* loads the full node-based-graph into memory.  It uses the NearestPhantomNode function to find the edge-based-node, and the nodeIDs from GetUncompressedGeometry to find the entry point into the graph.

  Note that this tool is *not* exploring the edge-based-graph, which is probably what you would want if you're trying to follow valid connectivity - the node-based-graph doesn't have any turn restriction information in it, so it may not work for your case, but hopefully this points you in the right direction.

daniel

> On Nov 30, 2016, at 1:53 PM, Chris Elion <celion at lyft.com> wrote:
> 
> Hi folks,
> I'm trying to write some code that accesses the road graph, so that I can try out some alternative mapmatching algorithms (and also allow our data scientists to experiment with some other things). We're already using osrm in production, so leveraging the infrastructure we already have should in theory make my life easier.
> 
> The GetAdjacentEdgeRange/GetTarget interface for the static graph (as described in https://github.com/Project-OSRM/osrm-backend/wiki/Quick-start-to-Code <https://github.com/Project-OSRM/osrm-backend/wiki/Quick-start-to-Code>) seems straightforward. However, I'm stuck trying to find a node or edge close to a Coordinate as the starting point for my iterations. My two attempts so far have been
> 
> 1) Use BaseDataFacade::NearestPhantomNodesInRange() - it's not obvious to me how to get the "real" node from the phantom node.
> 2) Use BaseDataFacade::GetEdgesInBox() gives reasonable-looking results - the NodeIDs EdgeBasedNode::u and ::v appear correct when I pass them to BaseDataFacade::GetCoordinateOfNode(). But the IDs are out of range when I pass them to BaseDataFacade::GetAdjacentEdgeRange()
> 
> Any suggestions on how to salvage either of these approaches? Or is there a better way to go about this?
> 
> Thanks in advance!
> 
> -Chris
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20161130/46be56bc/attachment.html>


More information about the OSRM-talk mailing list