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 <dan...@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 <cel...@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@openstreetmap.org > https://lists.openstreetmap.org/listinfo/osrm-talk > > > > _______________________________________________ > OSRM-talk mailing list > OSRM-talk@openstreetmap.org > https://lists.openstreetmap.org/listinfo/osrm-talk > >
_______________________________________________ OSRM-talk mailing list OSRM-talk@openstreetmap.org https://lists.openstreetmap.org/listinfo/osrm-talk
