search

LdDl / ch

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) technique for computing shortest path in graph.
Apache License 2.0
46 stars 5 forks source link

Unify vertex heaps #32

Closed magnushiie closed 1 year ago

magnushiie commented 1 year ago

This unifies forwardHeap and backwardHeap - only one of the bidirectionalVertex's fields of queryDist or revQueryDistance was ever used simultaneously in one direction. This reduces memory usage a bit (10%), and helps further refactorings.

LdDl commented 1 year ago

@SimonWaldherr Are you able to check if you have "Resolve Conflicts" button?

image I do not see this button in my view (I guess it's role model policy by GitHub, since you are the author of PR)

From GitHub docs button should be located at right top corner: image

magnushiie commented 1 year ago

I can resolve the conflicts, sorry, it was an artifact of separating the changes to multiple PRs. Will resolve in 1h

magnushiie commented 1 year ago

Should be OK now.

LdDl commented 1 year ago

Should be OK now.

Thanks!

As I see, basically you've got rid of redundant queryDist/revQueryDistance with theirs parent structs by defining single struct to rule them all (dist field in vertexDist struct). Initialization with Infinity value (queryDist or revQueryDistance - which is depends on either forward or backward propagation) leads to additional memory consumption (could be really big on large graphs). Did I get it right?

magnushiie commented 1 year ago

Yes, my understanding is the infinity values were never used nor updated.