Forward and backward traversal in node base mode

Hi,
Thank you for the great work on this awesome routing engine.
I’ve been looking at the code and I met a behavior that I don’t understand.
In AbstractBidirCHAlgo, both fillEdgesFrom and fillEdgesTo use fillEdges with reverse set to false/true where both edges should meet at some traversalId. If we consider a routing from points A and B where A is in forward traversal and B is in backward traversal and meet at some node Z the route would be :
A —>---Z----<----B
How do we know that the route between Z and B is allowed if we are traversing the graph from B to Z ?

NB: in node based mode, the reverse is only used for weight calculation.

Many thanks,

Hm, no its more like we find this route: A—>---Z—>---B. The backward search (fillEdgesTo) is traversing incoming edges, so if we explore a node x it looks for all edges incoming to x, like this: x<-p.

Hi Easbar,
Thank you for the reply.
Could you please indicate where the traversal of the incoming edges is done in the code. I was looking at getTraversalId which will always return the adjNode for both backward and forward :

protected int getTraversalId(RoutingCHEdgeIteratorState edge, int origEdgeId, boolean reverse) {
return getTraversalId(edge, reverse);
}

protected int getTraversalId(RoutingCHEdgeIteratorState edge, boolean reverse) {
return traversalMode.createTraversalId(edge.getBaseNode(), edge.getAdjNode(), edge.getEdge(), reverse);
}

public final int createTraversalId(int baseNode, int adjNode, int edgeId, boolean reverse) {
if (edgeBased) {
return GHUtility.createEdgeKey(baseNode, adjNode, edgeId, reverse);
}
return adjNode;
}

The edge traversing is here:

GraphHopper stores unidirectional edges, so the EdgeIterator traverses all edges (regardless of direction) adjacent to currEdge.adjNode here, but when calculating the weight a few lines below the reverse flag is considered such that the correct direction is used. Every edge has ‘access flags’ that are used to check which directions are allowed for a given edge and the calculated weight can be different for the two directions (some edge properties are direction dependent (like speed), while others are not (like distance)).

Powered by Discourse