Potential matrix issues

[karussell]

I'm relatively certain that they are some bugs but I'm not 100% sure as I have integrated the code differently using an unmodified GraphHopper.

You can try to reproduce them if you run a few (5000) matrix request with 2 or 5 points over berlin area via comparing with single 1 to 1 requests.

RPHASTAlgorithm.calcPaths

 for (int i = 0; i < sourceIds.length; i++) {
  int sourceNode = sourceIds[i];
  if (sourceNode == -1)
     continue;

  // BUG FIX 1
  MultiTreeSPEntry existing = _bestWeightMapFrom.get(sourceNode);
  if (existing != null) {
     existing.getItem(i).weight = 0.0001;
     continue;
  }

  ...
}

and

// BUG FIX 2: if query node is directly part of the subgraph (no virtual node) it could be higher than a leaf from the highest node and not reachable in runDownwardSearch
// TODO write test where query node is 6763 and shortest is over 6763->35469->47681 but only 6763-5422-47681 is returned without the fix as 6763 is not reached from 5422
//         .-> 5422 ------
// 6763 <-/               \
//    \------> 35469 <-\   \
//                      -- 47681
for (int i = 0; i < sourceIds.length; i++) {
     int sourceNode = sourceIds[i];
     MultiTreeSPEntry mspTree = _bestWeightMapFrom.get(sourceNode);
     mspTree.getItem(i).update = true;
      _prioQueue.add(mspTree);
}

 _outEdgeExplorer = _targetGraph.createExplorer();
runDownwardSearch();

And finally a more tricky one in RPHASTAlgorithm.fillEdgesDownward where update=false is hindering a necessary update of a better path - I've just commented out the continue, which only slightly decreases query speed. Currently unsure why the upward search "continue" does not lead to problems.

// BUG FIX 3: this optimization leads to suboptimal routes in rare cases of bigger matrices (berlin, measurement.count=30 measurement.points_per_query=5)
// if (_msptItem.update == false) {
//    continue;
// }

I highly recommend to build some minor unit tests and creating or extend a measurement suite like we have in core GH to run real requests over a bigger area and do performance judgements.

[HendrikLeuschner]

Thanks, I'll have a look at the bugs

[HendrikLeuschner]

@karussell Could you elaborate on your first bug fix? As far as I can see you've added a check whether a node has weights assigned to it already, correct? This is never the case in our implementation as RPHASTAlgorithm.calcpaths is the first method to be called after the algorithm creation, which in turn creates the weightmap. Which part did I miss?

[karussell]

I think this is a rare edge case if you have coordinates resulting in the same node IDs, often different coordinates that snap to the same coordinate on the road resulting in the same tower node (but sometimes also pillar node).

[HendrikLeuschner]

Okay, that makes sense, though it's a rare case. Concerning the second bug: Here I also do not quite understand the problem. We build the SubGraph from the targets going upwards level-wise until we reach the globally highest node. Then we search for the highest node going upwards from all source nodes. We then calculate the weights as described in the (R)PHAST papers. I don't understand how node 6764 in your example can be part of the subgraph but not reached from the highest node (5422).

[karussell]

Okay, that makes sense, though it's a rare case.

Sure and no big problems as a result, unlike with the other 2 bugs

Concerning the second bug

It is also an edge case IMO (but frequent in praxis) and happens only if a query results in a tower node and not a virtual node. The difference is the level: a tower node has a fixed one associated (and makes here this problem) and a virtual node is always explored (see DownwardSearchEdgeFilter.accept)

[HendrikLeuschner]

I'm afraid I still do not see the problem. The DownwardEdgeFilter is used while creating the Subgraph. The initial building routine has all destination nodes as queue. The graph is then built upwards level-wise, which means all nodes with a level higher than the current node are accepted by the DownwardEdgeFilter (The name is a bit misleading here). When the highest node in the graph is reached by all nodes, the subgraph building routine stops. Then the paths from all start nodes to the highest nodes are built using the UpwardEdgeFilter (It accepts the same nodes concerning level, base <= adj, but uses Forward-edges instead of backward). In the third step, the subgraph is explored from the highest node downwards. The two search spaces are then combined, yielding the shortest paths for all nodes to all nodes by using the CH properties of preserving the shortest path in shortcuts. It does not matter if a destination node starts with some level x or no level, because it will reach the highest node with level >= x. As the Downward search traverses the subgraph (without any level filtering) that has been built from the destination nodes themselves, I really don't see how a destination node should not be reached.

[karussell]

The DownwardEdgeFilter is used while creating the Subgraph.

Yes, I know. I also find the naming misleading. Maybe I explain myself a bit wrong or my reasoning is just wrong, but there is an issue and you'll find it if you compare matrix requests with single route requests.

The problem is maybe that it is assumed that there is at least one step for the upward search, which in this case is not existing (IMO because the query node is a tower node).

[HendrikLeuschner]

I'll need to look into that again.
Concerning your third bug: I think I know what the problem here is. The whole 'update' logic is used to save some computational time, exploiting the fact that we use one MultiTreeSPEntry for n entries instead of n SPTEntries. Basically what happens is the following: When we visit a node, we calculate weights from all start nodes to that node and set them as the node weight. But some (mostly higher level) nodes might be visited from multiple start nodes. Now if that happens, it's possible (and I guess quite likely) that the weight coming from node A has changed, but the weight for the path from node B has not changed. So we only need to recalculate the weight of the weight array entry belonging to node A. This is done via the update flag.
Now here's my guess what the problem is: this works fine in the upwards search. Now when the algo continues to the downward search, some nodes that are in the subgraph and have been visited by the upwards search. So some of their update entries might be false. Therefore they are not updated in the downwards search, even though that flag value was valid only for the upwards search.
I suppose the flags have to be reset for all entries in the weightmap (or at least entries that are in the subgraph) before starting the downward search part. I will do that right now. I'll let you know about a fix, maybe you can try the changes or tell me your test cases so I can check on my machine.

[karussell]

Ok. Regarding the test: I was not able to extract a unit test yet. But it was easy to run some random matrix requests on berlin and compare them with single route requests - see here for the code I'm using: https://gist.github.com/karussell/99dfdb7a73105bd31f38c64e4f66a8e4

[karussell]

And this is the line where it starts to do the single requests: https://gist.github.com/karussell/99dfdb7a73105bd31f38c64e4f66a8e4#file-measurement-java-L276

[HendrikLeuschner]

Concerning bug 3: Adding
if(!_targetGraph.containsNode(currEdge.adjNode)) currEdge.resetUpdate(false);
in line 312 should solve the problem. I have not tested yet though. Will try tomorrow.
The additional check prevents the optimization to happen in the upwards pass on nodes that are in the subgraph, which in turn will prevent failures in the downwards pass.

[karussell]

if the SubGraph method is meant like

    public boolean containsNode(int node) {
        return _node2edgesMap.containsKey(node);
    }

then this does not help in my case.

[karussell]

Sorry, can confirm this worked in my test case! ... used the wrong currEdge.resetUpdate(false)

[karussell]

But performance speaks now for commenting out if (_msptItem.update == false) continue; since I realized that we could remove all update related code in the fillEdgesDownward like resetUpdate (Is this correct?)

I do not see how the "continue" helps with performance in fillEdgesDownward as it only skips a tiny code branch or should it be necessary for correctness?

For 500 locations, area berlin I get constantly 1.17s for the new containsNode approach and 1.0s for commenting out the continue. Without the resetUpdate removals the commenting out approach is also at ~1.15s.

Furthermore I ran several random 100x100 requests across Germany and compared this with single route requests and did not find a difference with the fixes.

[karussell]

There is one more bug left, which I'm unsure about. Let me call it bug 1b as it is related to bug 1. If there are two locations very close to each other this results in a weight==0, ie. the same situation that is currently used for "disconnected points".

I'm unsure how to apply the current workaround of a small weight>0 to avoid this. Can we instead try to move the "notation" to weight<0 for "disconnected points" instead or even better the actual reality weight=positive infinity and change the necessary places to ignore the weight for the summation?

[HendrikLeuschner]

I'm on vacation right now and will look at the issues as soon as I am back.

[HendrikLeuschner]

I do not see how the "continue" helps with performance in fillEdgesDownward as it only skips a tiny code branch or should it be necessary for correctness?

In theory this helps with performance like it does in the upwards pass. The overhead might be larger than the improvement though, which it looks like regarding your test times. It is not necessary for correctness, the intention is to skip redundant computations.

There is one more bug left, which I'm unsure about. Let me call it bug 1b as it is related to bug 1. If there are two locations very close to each other this results in a weight==0, ie. the same situation that is currently used for "disconnected points".

I'm unsure how to apply the current workaround of a small weight>0 to avoid this. Can we instead try to move the "notation" to weight<0 for "disconnected points" instead or even better the actual reality weight=positive infinity and change the necessary places to ignore the weight for the summation?

The original idea behind choosing weight=0 was to skip the weight assignment when creating a new entry, therefore saving some variable assignment time as the floats are initialized to 0 by default. We changed the implementation of the MultiTreeSPEntry quite a bit and it might not be necessary anymore. Have you tried it with a changed init weight (positive infinity or -1)?

[karussell]

Have you tried it with a changed init weight (positive infinity or -1)?

yes, with positive infinity. I do not see another option (or maybe Double.MAX_VALUE)