[OSRM-talk] Accessing graph data in osrm

Chris Elion celion at lyft.com
Fri Dec 2 00:28:00 UTC 2016


Thanks for the quick response Daniel. I'll need to think it over a bit; I
may end just using something along the lines of GetNetworkDistance[WithCore]
instead.

*Chris Elion*
Senior Software Engineer
415.646.6488 <+14156466488>
[image: Lyft] <http://www.lyft.com/>

On Wed, Nov 30, 2016 at 4:13 PM, Daniel Patterson <daniel at mapbox.com> wrote:

> 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
>
>   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
>
>   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) 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
>
>
>
> _______________________________________________
> 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/20161201/647fd03c/attachment.html>


More information about the OSRM-talk mailing list