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)).

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.