Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Distance in the Matrix for MLD #5013

Closed
TheMarex opened this issue Apr 10, 2018 · 1 comment
Closed

Distance in the Matrix for MLD #5013

TheMarex opened this issue Apr 10, 2018 · 1 comment
Labels

Comments

@TheMarex
Copy link
Member

TheMarex commented Apr 10, 2018

This issue is tracking the implementation of distance values for the MLD table service and is part of #1353. To achieve this, we are going to utilize the same techniques as employed in #4990. We save the parent pointer in the heap and search buckets, retrieve the packed path, unpack and annotate the path.

  • The ManyToManyHeap need to store the parent node
  • The NodeBucket needs to store the parent node
  • MLD does not have a separate unpacking function, the search function returns an unpacked path. This needs to be refactored but is out-of-scope for this change.
  • We need to take the unpacking part of the MLD search function and use it as base to build a specialize calculateEBGNodeAnnotations
  • After the unpacked path is computed unpacked_nodes contains the list of nodes.
  • For every node you can execute the computeEdgeDistance function from the CH version to obtain the distance.

The main snag is that our calculateEBGNodeAnnotations distance function for MLD will need two heaps to work with (it calls the search function internally). Luckily the MLD SearchEngineData enables us to use these heaps.

@TheMarex TheMarex added the MLD label Apr 10, 2018
@ghoshkaj ghoshkaj mentioned this issue Apr 12, 2018
6 tasks
@TheMarex TheMarex added this to the distance-matrix milestone Apr 24, 2018
@TheMarex
Copy link
Member Author

TheMarex commented May 8, 2018

This is merged!

@TheMarex TheMarex closed this as completed May 8, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant