Priority update in the contractNodes() method

Hi! I’m having some troubles in the priority update in the contractNodes() method.

In the prepareNodes() method, the calculatePriority() method is called for all nodes. The degree in the calculatePriority() is based in all ingoing and outgoing edges.

When the calculatePriority() method is called through a neighbour update in the contract() method, the degree is not calculated based in all ingoing and outgoing edges, but just a few. I just can’t understand why. The only special thing that I did: represent bidirectional edges as two unidirectional edges.

Any help?

What do you mean with ‘troubles’?

And there are several calls to the calculatePriority in the contractNodes method, which one you mean? Can you provide pointers directly to the code (via github)?

Why? And are all tests still passing?

For example:

I’m using the testDirectedGraph3 with two unidirectional edges instead of one bidirectional.

When I add the method doWork() after the prepareNodes(), the contraction will start.

The priority of the node with ID=3 will be updated in the following line (when polledNode=2)

This iterator in the calculatePriority() method should go over all edges of the node being updated, right? Instead, is iterating only over the edge going and coming to and from the node with ID=2.

I tested the same thing, with the same graph, but using the regular bidirectional model. In this case, I can use the example of the priority update of the node with ID=1 (when polledNode=3). The degree calculated for it is 2, but there’s 3 edges represented in the graph creation.

The degree variable should be the sum of all ingoing and outgoing edges, right (including new shortcuts)?

P.S.: No more links because I’m a new user and can post only two in the same reply.

Do you have problems understanding the contraction or have problems with the contraction in your case? If the latter: why do you need this change and are still all graph related tests passing?

Well, I’m increasing the number of edges, so the tests will fail for this specific case.

I’m separating the edges from one bidirectional edge to two unidirectional ones for a personal code test. I’m trying to build another framework to solve different kinds of queries based on Contraction Hierarchies.