Skip to content

Distance in the Matrix for MLD #5013

@TheMarex

Description

@TheMarex

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions