Skip to content

Allow single edge paths in MLD alternatives, #4691#4693

Merged
oxidase merged 1 commit intomasterfrom
fix/4691
Nov 21, 2017
Merged

Allow single edge paths in MLD alternatives, #4691#4693
oxidase merged 1 commit intomasterfrom
fix/4691

Conversation

@oxidase
Copy link
Copy Markdown
Contributor

@oxidase oxidase commented Nov 20, 2017 •
edited by daniel-j-h
Loading

Issue

The PR fixes #4691, by allowing alternative routes with packed.path.empty().
Also an additional check node != fst.GetData(node).parent was added to prevent infinite loops if has_plateaux_at_node(node, fst, snd) and node is the first (last) node of the route.

Tasklist

  • add regression / cucumber cases (see docs/testing.md)
  • review
  • adjust for comments

@oxidase oxidase requested a review from daniel-j-h November 20, 2017 10:05
daniel-j-h
daniel-j-h reviewed Nov 20, 2017
View reviewed changes
Copy link
Copy Markdown
Member

@daniel-j-h daniel-j-h left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good - wondering if the check can be made earlier when we generate the candidate via nodes. Then we could eliminate the edge case in a single location, no?

@oxidase
Copy link
Copy Markdown
Contributor Author

oxidase commented Nov 20, 2017

@daniel-j-h such alternatives are ok for CH, so it is better to keep them also in MLD. This requires edges vector emptiness checks in all filters that use packed paths.

@daniel-j-h
Copy link
Copy Markdown
Member

daniel-j-h commented Nov 20, 2017

Yes I was only talking about the MLD alternatives implementation.

What I meant was removing these candidates early on during stepping already so that we don't have to think about this edge case when adding new filters later on.

But now that we have a reproducible test case I'm fine with both approaches.

@oxidase
Copy link
Copy Markdown
Contributor Author

oxidase commented Nov 20, 2017

Unfortunately CH alternatives results are not consistent wrt OS and the test fails on OSX and Windows builds

@oxidase oxidase force-pushed the fix/4691 branch 2 times, most recently from a26cf0b to 4710676 Compare November 20, 2017 21:04
@oxidase
Copy link
Copy Markdown
Contributor Author

oxidase commented Nov 21, 2017

@daniel-j-h i looked at the test fail on windows build. The problem in a loop shortcut that is not handled for CH alternative routes in computeWeightAndSharingOfViaPath so the alternative path weight instead of 7 at

osrm-backend/src/engine/routing_algorithms/alternative_path_ch.cpp

Line 308 in a53794f

*sharing_of_via_path += facade.GetEdgeData(edgeID).weight;
is the weight of the complete loop 6.8+7=13.8 and is filtered out. I did not find the reason why the loop shortcut is added with an msvc build. Both issues are completely out scope of the PR, so i added @mld-only tag to skip the test for CH.

@oxidase oxidase merged commit 7361558 into master Nov 21, 2017
@oxidase oxidase deleted the fix/4691 branch November 21, 2017 11:28
@oxidase oxidase mentioned this pull request Nov 29, 2017
Merged
3 tasks
This was referenced Mar 4, 2026
Open
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@daniel-j-h daniel-j-h daniel-j-h approved these changes

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Undefined behaviour in MLD alternatives

2 participants

@oxidase @daniel-j-h