CH improve amount of created shortcuts

[Stunkymonkey]

as seen here, the amount of shortcuts is not optimal.
The current approach as described in the original publication is creating shortcuts, if the contracting node is not part of the shortest path from previous neighbor to the next neighbor. As seen here this can lead to non perfect amount of shortcuts.
A "newer" approach is, to have a distinct set of previous neighbors and another distinct set with following neighbors. Then use Dijkstra and calculate the travel-costs. If the cost is equal to the cost from previous to contracting node to the following neighbor then the path from neighbor to neighbor is the optimal path. Therefore a new shortcut has to be created. Otherwise another better path is available and will create a shortcut in the future.
The path itself does not have to be fully resolved. Only the costs are important. Additional Improvement

i already did an implementation in rust, but with a different data-structure: link

maybe I find some time and could try implement it for your model. Is this wanted? Or do your prefer doing this yourself?

[Stunkymonkey]

my implementation is using OSM-files. The factor of edges before and after contraction is around 2.

[easbar]

Thanks for your comments!

I am not sure if I fully understand what you mean, but these additional shortcuts can be prevented by sorting the pairs of incoming/outgoing edges at the contracted node by their weights (sort the pairs by the sum of the weights of their incoming and outgoing edge). Sorting them ensures that the necessary shortcuts are introduced first and then serve as witness paths (thus preventing) the unnecessary ones. Is that what you mean? Or do you think there is another way that does not require this sorting? It'd be certainly interesting to try this, yes, do you have an estimate how it affects preparation vs. query time?

my implementation is using OSM-files. The factor of edges before and after contraction is around 2

You mean the number of shortcuts roughly equals the number of edges of the graph? Yes that is my experience as well (for OSM graphs). Do you have an estimate how much the optimization you suggested reduces the number of shortcuts? Or do you mean the optimization you mentioned reduces the number of shortcuts by a factor of two? That would be rather surprising to me I do not expect it to be so significant.

The path itself does not have to be fully resolved. Only the costs are important. Additional Improvement

Yes that should be an easy way to improve preparation time.

And of course yes if you feel like contributing some code do not hesitate to send a PR. But if not I will probably try this myself because I'm interested how this is going to turn out.

[easbar]

The path itself does not have to be fully resolved. Only the costs are important

I briefly tried this (simply commenting out the path building) and it looks like the preparation time is reduced by about 10% (not so bad). We only need to find a way to make the path building conditional, because in dijkstra.rs I would like to keep it for testing purposes.

[Stunkymonkey]

what I did: an extra flag which can be set wether you only want the costs or the whole path? not super pretty
or you could split in in different functions (highlevel idea):

calc_cost(start, end) -> Option<usize> {
  _dist_table, cost = normal_dijskstra(start, end);
  return cost;
}

calc_path(start, end) -> Option<(vec[nodeIds], usize)> {
  result = normal_dijskstra(start, end);
  match (dist_table, cost) { 
    None => None
    Some => {
      path = resolve_path(end, dist_table);
      Some(path, cost);
    }
  }
}

[Stunkymonkey]

I am not sure if I fully understand what you mean, but these additional shortcuts can be prevented by sorting the pairs of incoming/outgoing edges at the contracted node by their weights (sort the pairs by the sum of the weights of their incoming and outgoing edge). Sorting them ensures that the necessary shortcuts are introduced first and then serve as witness paths (thus preventing) the unnecessary ones. Is that what you mean? Or do you think there is another way that does not require this sorting? It'd be certainly interesting to try this, yes, do you have an estimate how it affects preparation vs. query time?

yes in my case there can exist multiple ways between one node.

You mean the number of shortcuts roughly equals the number of edges of the graph? Yes that is my experience as well (for OSM graphs). Do you have an estimate how much the optimization you suggested reduces the number of shortcuts? Or do you mean the optimization you mentioned reduces the number of shortcuts by a factor of two? That would be rather surprising to me I do not expect it to be so significant.

the factor is only the amount of edges before contraction and after it. sadly i do not know how much this reduces the amount of shortcuts compared to your solution. maybe there is a research paper for it.

[easbar]

or you could split in in different functions

Yes, I did that here: 19acab2, but not entirely sure if this really gives a significant speed-up, maybe only on large graphs?

how much this reduces the amount of shortcuts compared to your solution.

we should just try ;)

[Stunkymonkey]

i will try this later today

[Stunkymonkey]

Your code is quite clean, thanks to this i created this draft. Have a look at it.
It seems to me, that the improvement fixes calc_shortcuts_witness_via_center, but due to newly created shortcuts in calc_shortcuts_witness the improvement is not really noticeable.

[easbar]

See discussion in #16.