Fix manuever overrides finding bug#6739
Merged
mjjbell merged 4 commits intoProject-OSRM:masterfrom Mar 24, 2024
Merged
Conversation
Member
|
Good spot. Looks like it happened in #4907 |
Member
|
As this is a bug related to the multi-level partitioning, it's difficult to add a neat Cucumber test case. However, I've verified the fix using the example PBFs from the issue details - thanks for providing them, it's very helpful. |
mjjbell
approved these changes
Mar 17, 2024
Member
|
@rezashokry can you add an entry to CHANGELOG.md ? |
mjjbell
force-pushed
the
fix-maneuver-overrides-bug
branch
from
11adea8 to
e1aecf2
Compare
eliseier
pushed a commit
to wanderlog/osrm-backend
that referenced
this pull request
Mar 25, 2025
* sort manuever overrides vector after partition --------- Co-authored-by: rshokri <[email protected]> Co-authored-by: Michael Bell <[email protected]>
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Issue
I was trying to add some maneuver override relation to the map and I noticed some of them are not working.
I tried to find out why and I figured out this is because there is a vector of maneuver overrides which is assumed to be sorted to use binary search on it in lookup but its not sorted at the binary search stage.
The vector is already sorted in extract function but after the renumber in partition function the vector becomes unsorted.
Extraction:
https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/edge_based_graph_factory.cpp#L1225
Renumbering in partitioner: (which doesn't maintain the sorted array)
https://github.com/Project-OSRM/osrm-backend/blob/master/src/partitioner/partitioner.cpp#L163C1-L163C1
Finding maneuver overrides for each node:
https://github.com/Project-OSRM/osrm-backend/blob/master/src/engine/guidance/post_processing.cpp#L582
Binary search on the vector:
https://github.com/Project-OSRM/osrm-backend/blob/master/include/engine/datafacade/contiguous_internalmem_datafacade.hpp#L600
I just simply sort the vector after the rename function before the partition function writes it down.
Tasklist
Requirements / Relations
This pull request fixes this issue.