Potential matrix issues about openrouteservice HOT 18 CLOSED

Thanks, I'll have a look at the bugs

from openrouteservice.

@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?

from openrouteservice.

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

from openrouteservice.

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

from openrouteservice.

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)

from openrouteservice.

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.

from openrouteservice.

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

from openrouteservice.

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.

from openrouteservice.

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

from openrouteservice.

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

from openrouteservice.

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.

from openrouteservice.

if the SubGraph method is meant like

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

then this does not help in my case.

from openrouteservice.

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

from openrouteservice.

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.

from openrouteservice.

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?

from openrouteservice.

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

from openrouteservice.

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

from openrouteservice.

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)

from openrouteservice.