Missing edges in CH edge iterator

Open Source Routing Engine
1

Hi all,

I’m trying to implement a certain algorithm using a Dijkstra search on a CH Graph. I’m performing a top-down search through the nodes that is restricted to nodes with lower level, starting at the highest level node (in my test case: level 12348).
The problem is as follows: Using the AllCHEdgesIteratorImpl class (inside the CHGraphImpl) to show all existing connections, I can see there are about ~30 edges leading from/to my highest ranked node(Node id 189), of which the largest part are shortcuts, as expected.
Now using a CHEdgeiterator, setting the baseNode to 189, the Iterator only yields 4 edges, so only a small part of the total connections. It does not only return “physical edges”, also some shortcuts, so that is not the problem. It just does not return all adjacent edges.

As far as I understand, the EdgeIterator iterates over the edges adjacent to a node in a ID-downwards manner, so the edge with the highest ID should be the first to be returned by a call to getEdgeRef(int nodeId) in CHGraphImpl. This does return a lower edge ID however, not the highest shortcut ID as expected. nodesCH seems to be correctly initialized though.

I know this is quite confusing as there are many different things to consider here, but I’ve looked into this for quite a while now and I cannot find out why a wrong edgeID is returned. I’d appreciate any help.

Best,

Hendrik

2

When you remove the call ‘prepareGraph.disconnect’ (a necessary performance tuning), is then all like you think it should be?

3

So far, this seems to work. Thank you. Why exactly is the disconnect necessary?

4

Some uplinks are not necessary once we have the levels and so we can save looping over all edges which makes the search faster.

5

I’ll need to check how this affects my algorithm effectively. Thank you so far.

1 Like