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

Minimum Reachable optimization #29

Open
Kalashnikovni opened this issue May 6, 2024 · 0 comments
Open

Minimum Reachable optimization #29

Kalashnikovni opened this issue May 6, 2024 · 0 comments
Assignees
Labels
enhancement New feature or request

Comments

@Kalashnikovni
Copy link
Collaborator

Currently the minimum reachable operation composes many times different maps. By profiling some examples, this last operation proved to be one of the most costly in regards to execution time. A very brief sketch of the proposed new implementation to be testes is as follows:

  1. Keep track of MRV (minimum reachable vertex) with a representative's map Rmap, and the distance to each of them with a distance map Dmap. Also, a successor map Smap will indicate the path used to reach each MRV.
  2. Calculate a new Rmap with adjacent vertices using minAdj.
  3. Between all the possible successors that lead to the MRV, choose the one with minimum distance to the MRV according to Dmap. The distance is necessary for the case in which the graph contains cycles.
@Kalashnikovni Kalashnikovni added the enhancement New feature or request label May 6, 2024
@Kalashnikovni Kalashnikovni self-assigned this May 6, 2024
@Kalashnikovni Kalashnikovni added this to Backlog in SB-Graph library issue tracker. via automation May 6, 2024
@Kalashnikovni Kalashnikovni moved this from Backlog to To do in SB-Graph library issue tracker. May 6, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Development

No branches or pull requests

1 participant