<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Hi Chris,</div><div class=""><br class=""></div><div class="">  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.</div><div class=""><br class=""></div><div class="">  Check out the workflow at:</div><div class=""><br class=""></div><div class="">  <a href="https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation#graph-edge" class="">https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation#graph-edge</a></div><div class=""><br class=""></div><div class="">  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.</div><div class=""><br class=""></div><div class="">  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.</div><div class=""><br class=""></div><div class="">  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().</div><div class=""><br class=""></div><div class="">  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.</div><div class=""><br class=""></div><div class="">  Hopefully this demonstrates that directly exploring a CH is .... annoying.</div><div class=""><br class=""></div><div class="">  However, all is not lost.  This might help help in your quest:</div><div class=""><br class=""></div><div class="">    <a href="https://github.com/Project-OSRM/osrm-backend/blob/isochrone_tool/src/tools/isochrone.cpp" class="">https://github.com/Project-OSRM/osrm-backend/blob/isochrone_tool/src/tools/isochrone.cpp</a></div><div class=""><br class=""></div><div class="">  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.</div><div class=""><br class=""></div><div class="">  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.</div><div class=""><br class=""></div><div class="">daniel</div><div class=""><br class=""></div><div><blockquote type="cite" class=""><div class="">On Nov 30, 2016, at 1:53 PM, Chris Elion <<a href="mailto:celion@lyft.com" class="">celion@lyft.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Hi folks,</div><div class="">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.</div><div class=""><br class=""></div><div class="">The GetAdjacentEdgeRange/GetTarget interface for the static graph (as described in <a href="https://github.com/Project-OSRM/osrm-backend/wiki/Quick-start-to-Code" class="">https://github.com/Project-OSRM/osrm-backend/wiki/Quick-start-to-Code</a>) 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</div><div class=""><br class=""></div><div class="">1) Use BaseDataFacade::NearestPhantomNodesInRange() - it's not obvious to me how to get the "real" node from the phantom node.</div><div class="">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()</div><div class=""><br class=""></div><div class="">Any suggestions on how to salvage either of these approaches? Or is there a better way to go about this?</div><div class=""><br class=""></div><div class="">Thanks in advance!</div><div class=""><br class=""></div><div class="">-Chris</div>
</div>
_______________________________________________<br class="">OSRM-talk mailing list<br class=""><a href="mailto:OSRM-talk@openstreetmap.org" class="">OSRM-talk@openstreetmap.org</a><br class="">https://lists.openstreetmap.org/listinfo/osrm-talk<br class=""></div></blockquote></div><br class=""></body></html>